1. Элементы теории множеств 3

1.1 Множества. Основные понятия 3

1.2. Способы задания множеств 6

1.3. Операции над множествами. Диаграммы Венна 9

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

1.5. Прямое (декартово) произведение множеств 16

1.6 Разбиения и покрытия 17

1.7. Замечание о мощности некоторых множеств 18

1.8 Представление множеств в ЭВМ 19

Задачи для самостоятельного решения 21

1.9.Отношения 24

1.9.1.Определения 24

1.9.2 Бинарные отношения 25

1.9.3. Способы задания бинарных отношений 26

1.9.4 Свойства бинарных отношений 27

1.9.5. Отношение эквивалентности 29

1.9.5. Отношение порядка 31

1.9.6.1. Минимальные и максимальные

элементы множества 35

1.9.6.2. Диаграммы Хассе 37

1.9.6.3. Принцип двойственности 39

1.9.7. Представление отношений в ЭВМ 40

1.10. Соответствия. Функции. Операции. Отображения 41

1.10.1. Соответствия и их свойства 41

1.10.2 Функции и отображения 47

1.10.3. Инъекция, сюръекция и биекция 50

1.10.4. Композиция и суперпозиция функций.

Способы задания функций 53

1.10.5. Представление функций в ЭВМ 54

1.10.6. Операции 59

1.10.6.1. Способы задания операций 61

1.11. Алгебраические структуры 66

1.11.1. Основные определения 66

1.11.2. Замыкание и подалгебры 68

1.11.3. Гомоморфизм и изоморфизм 69

1.11.4. Алгебры с одной бинарной операцией 77

1.11.5. Алгебры с двумя бинарными операциями 82

1.11.6.Решетки 85

1.11.7. Булевы алгебры 88

Задачи для самостоятельного решения 91

2. Элементы математической логики

и булевы функции 92

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

2.2. Логические операции (логические связки) 94

2.3. Элементарные булевы функции 96

2.3.1. Функции алгебры логики 96

2.3.2. Равносильность функций.

Существенные и несущественные переменные 99

2.3.3. Реализация функций формулами.

Суперпозиция функций 100

2.3.4. Подстановки и замены 102

2.3.5. Принцип двойственности 103

2.3.6. Нормальные формы в логике высказываний 107

2.3.6.1. Разложение булевых функций по переменным.

Дизъюнктивно-нормалльная форма (ДНФ) 107

2.3.6.2. Совершенная дизъюнктивная

нормальная форма 110

2.3.6.3. Совершенные конъюнктивные

нормальные формы 113

2.3.7. Арифметические операции

в алгебре логики. Полиномы Жегалкина 114

2.3.8. Монотонные функции алгебры логики 120

2.3.9. Функционально замкнутые классы 121

2.4. Полнота системы булевых функций.

Теорема Поста 125

2.5. Элементы логики предикатов 130

2.5.1. Определение предиката 130

2.5.2. Кванторы. Формулы логики предикатов 133

2.5.3. Равносильность формул 134

2.5.4. Предикаты на конечных областях.

Логика одноместных предикатов 136