Рабочая программа для дисциплины "Элементы математической логики"

Министерство образования Республики Мордовия ГБПОУ РМ «Саранский техникум энергетики и электронной  техники имени А. И. Полежаева» РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ Элементы математической логики 2016 г. 2 ОДОБРЕНА Предметной (цикловой) Комиссией      «Информационные технологии» Председатель ПЦК ______________Е.И. Козлова Протокол № _____ от «______» __________2016 г. СОГЛАСОВАНО Заместитель директора по УМР _______________Л. В. Филютина Директор техникума, к.т.н. ________________В. В. Конаков Рабочая программа учебной дисциплины разработана на основе Федерального государственного   образовательного   стандарта   (далее   –   ФГОС)   по специальности   среднего   профессионального   образования   (далее   ­   СПО) 09.02.03   «Программирование   в   компьютерных   системах»   (базовой подготовки)© Разработчик: Абросимова   С.Н.,   преподаватель   специальных   дисциплин,   ГБПОУ   РМ «Саранский   техникум   энергетики   и   электронной   техники   имени   А.   И. Полежаева» Рецензенты:  Каледин   О.Е,   доцент   кафедры   «Алгебры   и   геометрии»   факультета математики и информационных технологий  ФГБОУ ВПО «МГУ  имени   Н.П. Огарева», кандидат физико­математических наук   А.А.,   Лияськина дисциплин, ГБПОУ РМ «Саранский техникум энергетики и электронной техники» имени А. И. Полежаева преподаватель специальных     © © © СОДЕРЖАНИЕ 3 1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ        ДИСЦИПЛИНЫ 2. СТРУКТУРА   И   СОДЕРЖАНИЕ   УЧЕБНОЙ ДИСЦИПЛИНЫ 3. УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ 4. КОНТРОЛЬ   И   ОЦЕНКА   РЕЗУЛЬТАТОВ   ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ стр. 4 5 12 13 4 1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ Элементы математической логики  1.1. Область применения программы Рабочая   программа   учебной   дисциплины   является   частью   основной профессиональной   образовательной   программы   в   соответствии   с   ФГОС   по специальности СПО  09.02.03   Программирование в компьютерных системах, входящей   в   состав   укрупненной   группы  09.00.00   Информатика   и вычислительная техника. 1.2.   Место   дисциплины   в   структуре   основной   профессиональной образовательной программы:  дисциплина   входит   в   математический   и  общий естественнонаучный цикл. 1.3.   Цели   и   задачи   дисциплины   –   требования   к   результатам   освоения дисциплины: В результате освоения дисциплины обучающийся должен уметь:    ­ выполнять операции над множествами;    ­  исследовать бинарные отношения на заданные свойства;    ­ строить таблицы истинности для формул логики;    ­ упрощать формулы логики;    ­ представлять булевы функции в виде формул заданного типа, проверять    множество булевых функций на полноту;    ­  выполнять операции над предикатами, записывать области истинности      предикатов, формализовать предложение с помощью логики предикатов. В результате освоения дисциплины обучающийся должен знать: ­ основные принципы математической логики; ­ основные принципы теории множеств и теории алгоритмов; ­ формулы алгебры высказываний; ­ метод минимизации алгебраических выражений; ­основы алгебры предикатов.   1.4. Рекомендуемое количество часов на освоение программы дисциплины: максимальной учебной нагрузки обучающегося 175 часов, в том числе: обязательной аудиторной учебной нагрузки обучающегося 117 часов; 5 самостоятельной работы обучающегося 58 часов. 6 2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ 2.1. Объем учебной дисциплины и виды учебной работы Вид учебной работы Максимальная учебная нагрузка (всего) Обязательная аудиторная учебная нагрузка (всего)  в том числе:         лабораторные занятия         практические занятия         контрольные работы Самостоятельная работа обучающегося (всего)         работа с основной и дополнительной литературой;         подготовка рефератов по темам;         решение задач прикладного характера.   Итоговая аттестация в форме дифференцированного зачета Количество часов  175 117 ­ 44 ­ 58 7 2.2. Тематический план и содержание учебной дисциплины «Элементы математической логики» Наименование разделов и тем 1 Раздел   1   Введение   в математическую логику Тема 1.1 Предмет и значение логики. Раздел 2 Множества Тема   2.1   Основы   теории множеств Тема 2.2 Основные операции над множествами.    2.3   Отношения Бинарные Тема множеств. отношения и их свойства.   Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся Объем часов Уровень освоения 2 Математическая   логика   в   системе   современного   образования. История   развития   логики.   Традиционная   формальная   логика. Математическая символьная логика.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Рефераты на тему: «История становления логики как науки». Понятие   множества,   подмножества.  Собственные  и  несобственные подмножества.   Конечные   и   бесконечные   множества.   Пустое множества. Мощность множества. Способы задания множеств.  Объединение   множеств.   Пересечение   множеств.   Дополнение (разность)   множеств.   Использование   диаграмм   Эйлера­Венна   для иллюстрации основных операций над множествами.  Практическое занятие Решение задач с множествами. Решение   задач   на   подсчет   количества   элементов   в   объединении множеств.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Отношения   множеств.   Унарные,   бинарные,   тернарные   и  n­арные отношения   множеств.   Декартово   произведение   двух   множеств. Свойства бинарных отношений.  Самостоятельная работа обучающихся  Работа с основной и дополнительной литературой. Графическое представление декартового произведения множеств.  3 5 2 3 27 2 2 4 2 2 3 4 2 2 1 2 8 Элементы   Основные 2.4 Тема комбинаторики. правила.  Тема   2.5   Основные   классы комбинаций. Раздел 3 Формулы логики Тема 3.1 Понятие  высказывания. Основные  логические операции и их  свойства.  Тема 3.2 Формулы логики.  Тема 3.3 Таблица  истинности и методика её  построения.      Класс комбинаторных задач. Основные классы комбинаций. Общие правила   комбинаторики.   Правило   суммы.   Правило   произведения. Метод включений и исключений.  Практическое занятие Решение задач на применение основных правил комбинаторики.  Перестановки. Перестановки с повторениями. Сочетания. Свойства сочетаний. Сочетания с повторениями. Размещения. Размещения с повторениями. Разбиение множеств и чисел.  Практическое занятие Решение задач на нахождение различных комбинаций. Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Понятие высказывания. Функция истинности. Основные логические операции и их свойства.  Отрицание.   Конъюнкция   двух   высказываний.   Дизъюнкция   двух высказываний.   Импликация   двух   высказываний.   Эквивалентность двух высказываний.   Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Рефераты на тему: Варианты импликации.  Понятие   формулы   логики.   Пропозициональные   переменные. Классификация   формул.   Выполнимые   формулы.   Тождественно истинные   формулы   (тавтологии).   Опровержимые   формулы. Тождественно ложные формулы (противоречия). Практическое задание  Формализация высказываний.  Структура   таблицы   истинности.   Правила   построения   таблицы истинности для сложных высказываний. Практическое занятие Составление таблиц истинности для сложных высказываний.  2 2 4 2 2 34 2 3 2 2 2 4 2 2 2 2 2 9 Тема 3.4 Равносильные  формулы. Законы логики.  Тема 3.5 Методика  упрощения формул логики с помощью равносильных  преобразований.  Тема 3.6 Логический анализ  предложений  математического и  естественного языков.  Раздел 4 Булевы функции Тема 4.1 Понятие булевой  функции.  Тема 4.2 Представление  булевых функций над  заданной системой функций. Тема 4.3 ДНФ, КНФ.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Решение задач прикладного характера. Равносильные   формулы.   Свойства   отношений   равносильности. Законы   логики.   Закон   двойного   отрицания.   Переместительные законы. Сочетательные законы. Распределительные законы. Законы де Моргана.  Проверка равносильности формул с помощью таблиц истинности Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Равносильные   преобразования.   Приемы   и   способы   при   упрощении логических формул. Практическое задание Упрощение   формул   логики   с   помощью   равносильных преобразований.  Логический   анализ   предложений   математического   языка. Логический анализ предложений естественного языка.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Понятие булевой функции и функции многозначной логики. Булевы функции от одного аргумента.  Представление булевых функций над заданной системой функций. Табличный способ задания булевых функций.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Простая конъюнкция. Дизъюнктивная нормальная форма. Простой дизъюнкт.   Конъюнктивная   нормальная   форма.   Представление булевых   функций   в   виде   ДНФ   и   КНФ.   Алгоритм   приведения формулы к ДНФ и КНФ.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. 4 2 2 2 2 2 2 3 42 2 2 3 2 2 2 2 2 2 2 2 2 10 Тема 4.4 Методика  представления булевой  функции в совершенных  нормальных формах. СКНФ.   СДНФ.   Алгоритм   образования   СДНФ   по   таблице истинности. Алгоритм образования СКНФ по таблице истинности. Алгоритм приведения к СДНФ и СКНФ. Практическое занятие  Представление булевой функции в виде совершенной ДНФ.  Представление булевой функции в виде совершенной КНФ.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Двоичное сложение. Свойства двоичного сложения.  Многочлен Жегалкина. Теорема Жегалкина. Алгоритм построения многочлена Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина. Понятие выражение одних булевых функций через другие.  Проблема выражения одних функций через другие.  Основные   классы   функций.   Функции   сохраняющие   константу. Самодвойственные   функции.   Монотонные   функции.   Линейные функции.  Практическое занятие Проверка булевых функций на принадлежность к ласам функций Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Полная   система   множества   булевых   функций.   Необходимое   и достаточное условие полноты системы булевых функций. Стрелка Пирса. Штрих Шеффера.  Практическое занятие Проверка множества булевых функций на полноту. Самостоятельная работа обучающихся Методика   представления   булевой   функции   в   виде   минимальной ДНФ графическим методом.  Тема 4.5 Операция  двоичного сложения и  её  свойства.  Тема 4.6 Многочлен  Жегалкина. Тема 4.7 Основные класса  функций  Тема 4.8 Теорема Поста.  Функции Шеффера и Пирса. Раздел 5 Предикаты 2 4 3 2 2 2 2 2 2 3 2 2 3 31 2 2 2 1 2 2 2 11 Тема 5.1 Понятие  предиката, предикаты  различной местности.  Тема 5.2 Логические  операции над предикатами.  Тема 5.3 Кванторы.  Кванторные операции над  предикатами.  Тема 5.4 Понятие  предикатной формулы,  свободные  и связанные  переменные.  Тема 5.5 Формализация  предложений с помощью  логики предикатов.  Раздел 6 Элементы теории алгоритмов    Квантор   Квантор   существования. Понятие   предиката.   Предикаты   различной   местности. Классификация   предикатов.   Области   определения     и   истинности предиката.  Практическое занятие  Определение логического значения высказываний.  Нахождение области определения и области истинности предиката.  Отрицание   предиката.   Конъюнкция   двух   предикатов.   Дизъюнкция двух предикатов. Основные теоремы.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Квантор   общности. единственности.  Построение   отрицаний   к   предикатам,   содержащим   кванторные операции.  Практическое занятие Символическая   запись   предложений   математического   и естественного языков.  Преобразование   предложений   математического   и   естественных языков.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой. Определение формулы логики предикатов. Классификация формул логики предикатов.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой Метода   и   приемы   для   формализации   предложений   с   помощью логики предикатов.  Практическое задание  Формализация предложений с помощью логики предикатов.  Понятие   алгоритма. Интуитивное понятие алгоритма   Откуда   взялось   слово   «алгоритм». 2 4 2 3 2 2 4 3 2 3 2 2 36 2 2 2 2 2 2 2 2 12 Тема 6.1 Интуитивное  понятие алгоритма и его  характерные черты.  Свойства алгоритма. Формы представления алгоритмов.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой.  Рефераты на темы: «История возникновения понятия «алгоритм».   Тема 6.2 Основные  алгоритмические структуры. Тема 6.3 Рекурсивные  функции. Тема 6.4 Нормальный  алгоритм Маркова.  Тема 6.5 Машина Поста Следование.  Выбор. Ветвление. Сложные и простые условия. Цикл. Арифметический  цикл. Цикл с условием.  Циклы с предусловие  и постусловием.   Практическое занятие Описание алгоритмических структур на языке блок­схем. Понятие рекурсии в широком смысле слова. Рекурсивные объекты. Рекуррентные соотношения.  Рекурсивные функции.  Практическое занятие Представление функций в рекурсивной форме.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой.  Частично рекурсивные формулы. Нормальный алгоритм Маркова. Основная гипотеза теории алгоритмов в форме Маркова. Универсальный алгоритм Маркова. Нормальная схема. Тезис Маркова. Практическое занятие  Применение нормального алгоритма Маркова.  Работа алгоритма Маркова.  Самостоятельная работа обучающихся Работа с основной и дополнительной литературой.  Рефераты   на   тему:  Эквивалентность определений алгоритма в виде нормального алгоритма Маркова. Основные понятия и операции. Финитный процесс. Способ задания проблемы и формулировка. Гипотеза Поста. Проблемы соответствий Поста над алфавитом. Практическое занятие Решение задач с помощью машины Поста.  2 3 2 2 2 2 4 2 4 3 3 2 2 2 2 2 2 13 Самостоятельная работа обучающихся Работа с основной и дополнительной литературой.  Всего 3 175 Для характеристики уровня освоения учебного материала используются следующие обозначения:  1 – ознакомительный (узнавание ранее изученных объектов, свойств);  2 – репродуктивный (выполнение деятельности по образцу, инструкции или под руководством);  3 – продуктивный (планирование и самостоятельное выполнение деятельности, решение проблемных задач). 14 3. УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ 3.1. Требования к минимальному материально­техническому  обеспечению Оборудование учебного кабинета:  1. посадочные места по количеству студентов;     2. рабочее место преподавателя;   3. комплект учебно­методических разработок; 4. презентации уроков; 5. видеоролики; 6. плакаты. 3.2. Информационное обеспечение обучения Перечень   рекомендуемых   учебных   изданий, дополнительной литературы Основные источники:   Интернет­ресурсов, 1. Игошин В.И. Математическая логика: Учебное пособие. –М:          ИНФРА­  М, 2012. 2. Канцедал   С.А.   Дискретная   математика:   Учебное   пособие.   –М:   ИД «Форум»:ИНФА­М, 2011  Дополнительные источники: 1. Галушкина Ю.И., Марьямов А.Н., Конспект лекций по дискретной  математике М., 2012.  2. Самохин А.В. Математическая логика и  теория алгоритмов.  Учебное пособие­ М.: МГТУГА, 2011 15 4.КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ Контроль  и оценка  результатов освоения дисциплины осуществляется преподавателем   в   процессе   проведения   практических,   а   также   выполнения обучающимися индивидуальных заданий, проектов, исследований. Результаты обучения (освоенные умения, усвоенные знания) Формы и методы контроля и оценки результатов обучения  1 2 Умения:  выполнять операции над множествами исследовать бинарные отношения на  заданные свойства строить таблицы истинности для  формул логики упрощать формулы логики представлять булевы функции в виде  формул заданного типа, проверять  множество булевых на полноту выполнять операции над предикатами,  записывать области истинности  предикатов, формализовать  предложение с помощью логики  предикатов Знания: основные принципы математической  логики основные принципы теории множеств и теории алгоритмов формулы алгебры высказываний метод минимизации алгебраических  выражений  основы алгебры предикатов   индивидуальные задания тесты индивидуальные задания практические занятия индивидуальные задания практическое занятие тесты индивидуальные   задания,   доклады   и рефераты практическое занятие индивидуальные задания тесты 16