Студенты обязаны сдавать все задания в сроки, установленные преподавателем. Работы, предоставленные с опозданием, не оцениваются, коллоквиумы не переписываются. Контрольные работы переписываются однократно по правилам, установленным на факультете. Студенты, получившие в течение семестра, оценку 3 или 4 (зачет) и желающие повысить свою оценку, допускаются к экзамену (итоговая аттестация). Экзаменационная работа оценивается из 20 баллов независимо от оценки, полученной в семестре. Оценка менее 51 балла (<3), полученная при итоговой аттестации, является неудовлетворительной.

Студенты, набравшие менее 31 балла в течение семестра не допускаются к итоговой аттестации.

7. Темы лекций, семинарских занятий, лабораторных работ

Темы лекций

Тема 1. Введение в алгебру логики

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

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

Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.

71

Тема 3. Полнота и замкнутость систем логических функций

Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций.

Определение и лемма о несамодвойственной функции. Класс монотонных функций. Определение и лемма о немонотонной функции. Класс линейных функций. Определение и лемма о нелинейной функции.

Тема 4. Исчисление высказываний и предикатов

Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие. Метод резолюций для исчисления высказываний. Понятие предиката. Кванторы. Алфавит. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации. Метод резолюций в исчислении предикатов.

Темы лабораторных занятий

Тема 1. Алгебра логики

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

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

Минимизация функций. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.

Тема 3. Полнота и замкнутость систем логических функций

Решение задач на доказательство замкнутости класса. Класс самодвойственных функций. Решение задач с

72

несамодвойственными функциями. Класс монотонных функций. Решение задач с немонотонными функциями. Класс линейных функций. Решение задач с нелинейными функциями.

Тема 4. Исчисление высказываний и предикатов

Решение задач с использованием метода резолюций для исчисления высказываний. Применение кванторов. Поиск предваренной нормальной формы (ПНФ). Поиск скулемовской стандартной формы. Подстановка и унификация для ПНФ. Применение алгоритма унификации. Применение метода резолюций в исчислении предикатов.

4.Учебно-методические материалы, используемые для реализации курса на обеспечивающей кафедре: учебники, учебные пособия, конспекты лекций, методические указания (в т.ч. в электронном виде)

Список обязательной литературы.

1.Гаврилов Г.П., Сапоженко А.А. «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 2007.

2.Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А. «Лекции по дискретной математике. Часть I. Математическая логика». Учебное пособие. // М.: Изд-во РУДН, 2011.

3.Новиков Ф.А. «Дискретная математика для программистов». Учебник. // Cпб.: Изд. дом «Питер», 2000.

4.Лавров И.А., Максимова Л.Л. «Задачи по теории множеств, математической логике и теории алгоритмов». Учебное пособие. 5-ое изд., // М:, Изд-во Физматлит, 2006

Список дополнительной литературы.

1.Игошин В.И. «Математическая логика и теория алгоритмов». 3-е изд. Учебное пособие для ВУЗов, // М:, Изд-во Физматлит, 2006

73

2.Просветов Г.И. «Дискретная математика: задачи и решения». Учебное пособие. //М. Изд-во «Бином. Лаборатория знаний», 2008.

5.Методические указания и рекомендации по выполнению лабораторных работ, практических или семинарских занятий, курсовых работ (проектов)

Общие правила выполнения контрольных заданий

Требования к оформлению работы

Постановка задачи.

1.Краткая формулировка задачи.

2.Развернутая постановка задачи с указанием основных режимов работы и их сценариев.

Алгоритм решения.

1.Математическое описание алгоритма.

2.Структура алгоритма ядра программы (укрупненная блоксхема).

Тестирование.

1.Описание основных режимов тестирования алгоритма и программы и результатов работы программы.

2.Список возможных ошибок и аномалий, описание реакции программы на них.

Заключение.

Содержит общие комментарии и замечания исполнителя о выполненной работе.

Приложение.

Приложение должно содержать текст программы (полная

74