ДИСКРЕТНАЯ МАТЕМАТИКА. МАТЕМАТИЧЕСКАЯ ЛОГИКА

(для групп К1-221,222,223,224,281,331,361)

1-2 недели.

Понятие дискретной математики. Основные разделы дискретной математики.

Раздел 1. Множества и отношения

Основные понятия теории множеств: множество, подмножество, надмножество, элемент множества, принадлежность множеству, пустое множество, булеан. Множества конечные и бесконечные. Мощность множества. Способы задания множеств. Диаграммы Эйлера-Венна. Основные операции над множествами: объединение, пересечение, дополнение, симметрическая разность, декартово произведение.

3-4 недели.

Отношения, бинарные и n-арные. Способы задания отношений. Понятие операции и функции как частный случай бинарных отношений: рефлексивность, симметричность, транзитивность. Отношение эквивалентности. Классы эквивалентности. Отношения упорядочивания. Полный порядок. Частичный порядок. Диаграммы Хассе для представления бинарных отношений упорядочивания. Экстремальные характеристики отношения упорядочивания: миноранта, мажоранта, минимальные и максимальные элементы, нижняя и верхняя грани, наименьшие и наибольшие элементы. Отношение толерантности.

Операции над отношениями: объединение, пересечение, дополнение до универсума, декартово произведение, замыкание отношений относительно свойства, композиция, обращение.

5 неделя. .

Раздел 2. Алгебра и алгебраические системы

Понятие алгебры, Носитель. Сигнатура. Фундаментальные алгебры: группоиды, полугруппы, моноиды, поля, тела, кольца, решетки. Алгебра множеств (алгебра Кантора).

6-10 недели.

Алгебра логики. Высказывание. Простые и сложные высказывания. Законы алгебры логики. Теорема Стоуна. Логические (булевы) функции, их таблицы истинности. Эквивалентность булевых функций. Двойственность булевых функций. Двойственность булевых функций.

Нормальные формы представления логических функций: дизъюктивные, конъюктивные, совершенные, сокращенные, тупиковые, минимальные.

Алгоритм Квайна-МакКласки для нахождения минимальных ДНФ.

Построение схем в функциональных базисах.

11 неделя.

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

Замкнутые относительно суперпозиции классы булевых функций. Критерии Поста-Яблонского.

12 неделя.

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

13 неделя.

Раздел 2. Математические теории и исчисления

Термы. Аксиомы. Формулы. Правила вывода.

Исчисление высказываний. Понятие логического высказывания. Простые и сложные высказывания. Логические операции (функции). Аксиоматика исчисления высказываний. Правила вывода.

14-16 недели.

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

Интерпретация формул исчисления предикатов. Общезначимые и выполнимые формулы. Проблема разрешимости.

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

1. Множества. Операции над множествами, Диаграммы Эйлера-Венна.

2. Бинарные отношения. Исследование свойств бинарных отношений.

3. Отношение эквивалентности. Отношение толерантности. Отношение упорядочивание.

4. Экстремальные характеристики отношения упорядочивания. Контрольная работа № 1 (20 мин).

5. Алгебра множеств. Законы алгебры множеств.

6. Алгебра логики. Простейшие логические функции. Построение таблиц истинности логических функций.

7. Построение совершенных ДНФ и совершенных КНФ аналитически и с помощью таблиц истинности.

8. Межсеместровый контроль. Контрольная работа № 2.

9. Алгоритм Квайна-МакКласски для построения минимальных ДНФ.

10. Исследование системы булевых функций на полноту.

11. Переход от одного базиса к другому. Контрольная работа № 3 (20 мин).

12. Формализация логических высказываний.

13. Основные операции над высказываниями.

14. Операции над предикатами.

15. Вывод формул в исчислении предикатов.

16. Контрольная работа № 4.

ОСНОВНАЯ ЛИТЕРАТУРА

519

Г67

В.А. Горбатов, А.В. Горбатов, М.В. Горбатов. Дискретная математика: Учебник для студентов втузов - М.: 000 “Издательство АСТ”: ООО ”Издательство Астрель”, 2003.

519

Н73

Ф.А. Новиков. Дискретная математика для программистов. - СПб.: Питер, 2004.