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

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

164

Обязательная аудиторная учебная нагрузка (всего)

108

в том числе:

практические занятия

18

Самостоятельная работа обучающегося (всего)

56

в том числе:

решение задач, написание сообщений, нахождение различных способов решения задач

56

Итоговая аттестация в форме дифференцированного зачета

Наименование разделов и тем

Содержание учебного материала, лабораторные  работы и практические занятия, самостоятельная работа обучающихся, курсовая работа (проект) (если предусмотрены)

Объем часов

Уровень освоения

1

2

3

444

Раздел 1. Теория множеств

26

Тема 1.1. Общие понятия теории множеств. Язык теории множеств

Содержание учебного материала

2

Понятие «множество», элемент множества. Способы задания множеств: указание характеристического свойства, перечисление элементов. Пустое множество.

2

Самостоятельная работа обучающихся

Свойства счетных множеств (конспект)

2

Тема 1.2. Общие понятия теории множеств. Язык теории множеств

Содержание учебного материала

2

Изображение множеств (круги Эйлера, диаграммы Венна). Понятие «подмножества». Универсальное множество.  Равные множества.  Мощность множества

2

Самостоятельная работа обучающихся

Диаграммы Эйлера-Венна (сообщение)

2

Тема 1.3 Основные операции над множествами

Содержание учебного материала

2

Введение операций над множествами. Свойства операций над множествами.

Теоретико-множественные операции и их связь с логическими операциями: включение, объединение, пересечение, разность, дополнение множеств.

2

Самостоятельная работа обучающихся

Решение логических задач

2

Тема 1.4 Основные операции над множествами

Содержание учебного материала

2

Законы пересечения и объединения множеств. Прямое (декартово) произведение множеств. Основные тождества алгебры множеств

2

Самостоятельная работа обучающихся

Решение уравнений с множествами

2

Тема 1.5 Соответствие между множествами. Отображения множеств

Содержание учебного материала

2

Основные понятия: соответствие между множествами, образ и прообраз элемента, множество значений, область определений, обратное соответствие. Задание соответствий: аналитический, табличный, графический

2

Самостоятельная работа обучающихся

Доказательство основных тождеств алгебры множеств

2

Тема 1.6 Соответствие между множествами. Отображения множеств

Содержание учебного материала

2

Виды отображений: взаимно-однозначное, обратное отображение, равносильное, эквивалентное, равномощные. Композиция функций. Тождественное отображение. Отношения и их свойства, виды отношений.

2

Практическая работа №1 «Решение задач с использованием аппарата теории множеств»

2

Самостоятельная работа обучающихся

Нечеткие множества и операции над ними (конспект)

2

Раздел 2. Алгебра (логика) высказываний

38

Тема 2.1 Высказывания и операции над ними

Содержание учебного материала

2

Алгебра логики. Высказывания и высказывательные формы. Отрицание высказываний. Конъюнкция и дизъюнкция. Союзы языка и логические операции (Язык и логика).

Импликация, эквиваленция, сумма по модулю два.

2

Тема 2.2 Формулы алгебры высказываний

Содержание учебного материала

2

Понятие формулы алгебры высказываний. Таблицы истинности. Вычисление логического значение формулы и построение таблицы истинности для формул. Классификация формул алгебры высказываний.

2

Самостоятельная работа обучающихся

Логика вопросов и ответов (конспект)

2

Тема 2.3 Формулы алгебры высказываний

Содержание учебного материала

2

Понятие формулы алгебры высказываний. Таблицы истинности. Вычисление логического значение формулы и построение таблицы истинности для формул. Классификация формул алгебры высказываний.

2

Практическая работа № 2 «Построение таблиц истинности логических выражений»

2

Тема 2.4 Тавтологии алгебры высказываний

Содержание учебного материала

2

Основные тавтологии алгебры высказываний. Правила получения тавтологий.

Упрощение формул. Закон двойственности в алгебре логики

2

Самостоятельная работа обучающихся 

Решение задач на минимизацию логических выражений с помощью алгебры логики

2

Тема 2.5 Логическая равносильность формул

Содержание учебного материала

2

Понятие равносильности формул. Алгоритм проверки формул на равносильность. Равносильные преобразования формул

2

Самостоятельная работа обучающихся 

Решение логических задач

2

Тема 2.6 Логическая равносильность формул

Содержание учебного материала

2

Понятие равносильности формул. Алгоритм проверки формул на равносильность. Равносильные преобразования формул

2

Практическая работа №3 «Тождественные преобразования формул с использованием законов алгебры логики»

2

Тема 2.7 Нормальные формы для формул алгебры логики

Содержание учебного материала

2

Понятие нормальных форм. Совершенные нормальные формы. Основные определения для построения совершенной дизъюнктивной нормальной формы (СДНФ).

2

Самостоятельная работа обучающихся 

Приведение формул к СДНФ

2

Тема 2.8 Нормальные формы для формул алгебры логики

Содержание учебного материала

2

Основные определения для построения совершенной конъюнктивной нормальной формы (СКНФ). Алгоритм составления СДНФ и СКНФ

2

Практическая работа №4 «Приведение формул к совершенным нормальным формам по таблицам истинности»

2

Тема 2.9 Логическое следование формул

Содержание учебного материала

2

Понятие логического следования. Алгоритм проверки формул на логическое следование. Свойства и признаки логического следования. Метод от противного проверки формул на логическое следование. Метод резолюций проверки формул на логическое следование.

2

Самостоятельная работа обучающихся 

Проверка формул на логическое следование

2

Тема 2.10 Приложение алгебры высказываний в логико-математической практики

Содержание учебного материала

2

Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиций. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Решение «логических» задач.

2

Самостоятельная работа обучающихся 

Роль математической логики в обучении информатике или математике (сообщение)

2

Раздел 3. Булевы функции

30

Тема 3.1 Булевы функции от одного, двух и n аргументов

Содержание учебного материала

2

Происхождение булевых функций. Логические функции. Равенство функций. Формулы. Булевы функции одной переменной: тождественный нуль, тождественная единица, отрицание.

2

Тема 3.2 Булевы функции от одного, двух и n аргументов

Содержание учебного материала

2

Определение функции алгебры логики n переменных. Число функций n переменных. Обозначение функций: штрих Шеффера, стрелка Пирса, сумма Жегалкина. Способы задания булевых функций. Соглашение о написании формул

2

Тема 3.3 Минимизация булевых функций

Содержание учебного материала

2

Разложение функций по переменным. Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ). Построение нормальных форм для заданной булевой функции.

2

Самостоятельная работа обучающихся 

Выполнение упражнений на составление СДНФ и СКНФ.

2

Тема 3.4 Минимизация булевых функций

Содержание учебного материала

2

Приведение формул к совершенным нормальным формам с помощью равносильных преобразований. Упрощение формул логики до минимальной ДНФ. Карты Карно

2

Практическая работа №5 «Преобразование логических выражений с помощью карт Карно»

2

Самостоятельная работа обучающихся

Алгоритм составления карты Карно для булевых функций трех (четырех переменных).

2

Тема 3.5 Многочлен Жегалкина

Содержание учебного материала

2

Определение многочлена Жегалкина. Построение многочлена Жегалкина по таблице истинности. Преобразование дизъюнктивной нормальной формы. Метод треугольника. Алгебраический метод

2

Самостоятельная работа обучающихся

Построение многочлена Жегалкина

2

Тема 3.6 Многочлен Жегалкина

Содержание учебного материала

2

Определение многочлена Жегалкина. Построение многочлена Жегалкина по таблице истинности. Преобразование дизъюнктивной нормальной формы. Метод треугольника. Алгебраический метод

2

Практическая работа №6 «Проверка полноты множества функций. Использования теоремы Поста»

2

Тема 3.7 Основные классы функций. Полнота множества

Содержание учебного материала

2

Функционально замкнутые классы. Функциональная замкнутость класса функций алгебры логики.

Классы функций: класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс линейных функций, класс монотонных функций.

Функционально полные системы функций. Критерий полноты системы функций.

Теорема Поста-Яблонского

2

Самостоятельная работа обучающихся

Изучить примеры доказательства полноты системы, например {+, V, 1}, составив таблицы Поста.

2

Тема 3.8 Применение булевых функций в теории дискретных преобразователей информации

Содержание учебного материала

2

Булевы функции и релейно-контактные схемы. Функциональные схемы. Релейно-контактные схемы в компьютерах. Анализ и синтез релейно-контактных схем

2

Самостоятельная работа обучающихся

Построение релейно-контактных схем

2

Раздел 4. Логика предикатов

32

Тема 4.1 Основные понятия, связанные с предикатами

Содержание учебного материала

2

Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов

2

Тема 4.2 Логические операции над предикатами

Содержание учебного материала

2

Отрицание предиката. Конъюнкция и дизъюнкция  двух предикатов. Свойство отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов

2

Самостоятельная работа обучающихся

Решение вариативных задач и упражнений

2

Тема 4.3 Логические операции над предикатами

Содержание учебного материала

2

Отрицание предиката. Конъюнкция и дизъюнкция  двух предикатов. Свойство отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов

2

Тема 4.4 Кванторные операции над предикатами

Содержание учебного материала

2

Кванторы. Отрицание предложений с кванторами. Квантор общности. Квантор существования. Ограниченные и численные кванторы

2

Самостоятельная работа обучающихся

Выполнение операций над предикатами

2

Тема 4.5 Кванторные операции над предикатами

Содержание учебного материала

2

Кванторы. Отрицание предложений с кванторами. Квантор общности. Квантор существования. Ограниченные и численные кванторы

2

Тема 4.6 Формулы и тавтологии логики предикатов

Содержание учебного материала

2

Понятие формулы логики предикатов. Квалификация формул логики предикатов. Тавтологии логики предикатов. Способы получения тавтологий логики предикатов

2

Тема 4.7 Формулы и тавтологии логики предикатов

Содержание учебного материала

2

Понятие формулы логики предикатов. Квалификация формул логики предикатов. Тавтологии логики предикатов. Способы получения тавтологий логики предикатов

2

Тема 4.8 Равносильные преобразования формул и логические следования логики предикатов

Содержание учебного материала

2

Понятие равносильности формул. Приведенная форма для формул логики предикатов.  Предваренная нормальная форма для формул логики предикатов. Логическое следование логики предикатов

2

Самостоятельная работа обучающихся

Решение вариативных задач

2

Тема 4.9 Равносильные преобразования формул и логические следования логики предикатов

Содержание учебного материала

2

Понятие равносильности формул. Приведенная форма для формул логики предикатов.  Предваренная нормальная форма для формул логики предикатов. Логическое следование логики предикатов

2

Практическая работа №7 «Выполнение логических и кванторных операций над предикатами»

2

Тема 4.10 Применение логики предикатов к логико-математической практике

Содержание учебного материала

2

Запись на языке логики предикатов различных предложений. Строение математических теорем. Сравнение логики предикатов и логики высказываний. Логика предикатов и алгебра множеств

2

Самостоятельная работа обучающихся

Умозаключения как форма мышления. Дедуктивные умозаключения и их виды (реферат)

4

Раздел 5. Формальная математическая логика

14

Тема 5.1. Формализованное исчисление высказываний

Содержание учебного материала

2

Система аксиом и теория формального вывода. Понятие вывода и его свойства.

2

Самостоятельная работа обучающихся

Теорема о дедукции и ее применение (сообщение)

2

Тема 5.2 Формализованное исчисление высказываний

Содержание учебного материала

2

Полнота и другие свойства формализованного исчисления высказываний. Независимость системы аксиом формализованного исчисления высказываний

2

Тема 5.3 Формализованное исчисление предикатов

Содержание учебного материала

2

Первоначальные понятия. Язык формализованного исчисления предикатов. Система аксиои формализованного исчисления предикатов.

2

Самостоятельная работа обучающихся

Теория формального вывода (сообщение)

4

Тема 5.4 Формализованное исчисление предикатов

Содержание учебного материала

2

Теорема о дедукции и ее применение. Приведенная форма для формул ФИП. Свойства формализованного исчисления предикатов

2

Раздел 6. Элементы теории алгоритмов

22

Тема 6.1 Понятие алгоритма и алгоритмической системы

Содержание учебного материала

2

Алгоритм. Интуитивное представление об алгоритме. Неформальное определение алгоритма. Свойства алгоритма. Основные требования к алгоритмам. Основная терминология теории алгоритмов

2

Тема 6.2 Вычислимые и частично-рекурсивные функции. Тезис Черча

Содержание учебного материала

2

Вычислимые и частично-рекурсивные функции. Операция суперпозиции. Операция примитивной рекурсии. Операция минимизации. Тезис Черча

2

Тема 6.3 Вычислимые и частично-рекурсивные функции. Тезис Черча

Содержание учебного материала

2

Вычислимые и частично-рекурсивные функции. Операция суперпозиции. Операция примитивной рекурсии. Операция минимизации. Тезис Черча

2

Самостоятельная работа обучающихся

Математическая модель алгоритма Чёрчя (конспект)

2

Тема 6.4 Машина Тьюринга и машина Поста

Содержание учебного материала

2

Неформальное описание машины Тьюринга. Внешний алфавит, алфавит состояний, функциональная схема, принцип работы. Вычислимые по Тьюрингу функции, основная гипотеза теории алгоритмов. Машина Поста.

2

Практическая работа №7 «Чтение и выполнение программ, написанных для машины Тьюринга»

2

Тема 6.5 Машина Тьюринга и машина Поста

Содержание учебного материала

2

Неформальное описание машины Тьюринга. Внешний алфавит, алфавит состояний, функциональная схема, принцип работы. Вычислимые по Тьюрингу функции, основная гипотеза теории алгоритмов. Машина Поста.

2

Практическая работа №8 «Построение программ для машины Тьюринга»

2

Самостоятельная работа обучающихся

Алгоритмически неразрешимые проблемы (конспект)

Примеры работы любых 3-х элементарных машин Тьюринга

2

Тема 6.6. Алгоритмическая система Маркова

Содержание учебного материала

2

Математические модели алгоритмов. Нормальные алгоритмы Маркова. Принцип нормализации Маркова

2

Самостоятельная работа обучающихся

Решение задач на составление программ для машин Тьюринга

2

Дифференцированный зачет

2

Всего:

164

Результаты обучения

(освоенные умения, усвоенные знания)

Формы и методы контроля и оценки результатов обучения

Уметь:

формулировать задачи логического характера и применять средства математической логики для их решения

Экспертная оценка выполненных практических работ 1-8;

Контроль выполнения самостоятельных работ

Знать:

основные принципы математической логики, теории множеств и теории алгоритмов;

формулы алгебры высказываний;

методы минимизации алгебраических преобразований;

основы языка и алгебры предикатов 

Индивидуальный и фронтальный опрос в ходе аудиторных занятий;

Контроль выполнения индивидуальных и групповых заданий;

Контроль выполнения самостоятельных работ,

заслушивание рефератов, сообщений