Заключение

ВВЕДЕНИЕ

3

1.

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

5

1.1.

Основные понятия и определения теории множеств

5

1.2.

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

11

1.3.

Мощность множества

17

1.4.

Взаимно однозначное соответствие между множествами

18

1.5.

Счетные и несчетные множества

19

Задачи и упражнения

23

2.

ЭЛЕМЕНТЫ ТЕОРИИ ОТНОШЕНИЙ

24

2.1.

Бинарные отношения. Свойства отношений

24

2.2.

Отношение эквивалентности и разбиения

29

2.3.

Отношение порядка. Диаграмма Хассе

32

Задачи и упражнения

37

3.

ФУНКЦИИ, ОТОБРАЖЕНИЯ И ОПЕРАЦИИ

39

4.

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

44

4.1.

Основные понятия и определения теории графов

45

4.2.

Типы графов

48

4.3.

Матричные представления графов

53

4.4.

Представление графов в ЭВМ

56

4.5.

Операции над графами

59

4.6.

Метрические характеристики графа. Расстояние в графах

63

4.7.

Графы с заданной последовательностью степеней

65

4.8.

Достижимость и связность

70

4.8.1.

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

70

4.8.2.

Матрицы достижимостей и контрдостижимостей

73

4.8.3.

Нахождение сильных компонент

77

4.8.4.

Базы и антибазы

82

4.9.

Независимые и доминирующие множества

84

4.9.1.

Нахождение всех максимальных независимых множеств

87

4.10.

Покрытия и раскраски

94

4.11.

Деревья, остовы и кодеревья

101

4.11.1.

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

101

4.11.2.

Алгортм построения остова неорграфа

105

4.11.3.

Кратчайшие остовы

108

4.11.4.

Обходы графа по глубине и ширине

112

4.11.5.

Упорядоченные и бинарные деревья

115

4.12.

Эйлеровы циклы. Гамильтонов контур

117

4.12.1.

Метод Флери построения эйлерова цикла

120

4.12.2.

Метод перебора Робертса и Флореса для построения гамильтоновых путей и контуров

121

4.12.3.

Алгебраический метод выделения гамильтоновых путей и контуров

123

4.13.

Плоские и планарные графы

126

4.13.1.

Формула Эйлера

127

4.13.2.

Критерии анализа планарности

129

4.13.3.

Алгоритм укладки графа на плоскости

130

Задачи и упражнения

135

5.

КОМБИНАТОРИКА

140

5.1.

Перестановки

140

5.2.

Перестановки с неограниченными повторениями

143

5.3.

Размещения

144

5.4.

Сочетания

147

5.5.

Сочетания с повторениями

150

5.6.

Производящие функции для сочетаний

151

5.7.

Производящие функции для перестановок

153

5.8.

Циклы перестановок

155

5.9.

Принцип включений и исключений

159

Задачи и упражнения

160

6.

АЛГЕБРА ВЫСКАЗЫВАНИЙ

161

6.1.

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

162

6.2.

Правила записи сложных формул

166

6.3.

Таблицы истинности

169

6.4.

Равносильные формулы

172

6.5.

Дизъюнктивные и конъюнктивные нормальные формы

179

6.5.1.

Алгоритм приведения ПФ к нормальным формам

182

6.5.2.

Аналитический способ приведения к СДНФ

183

6.5.3.

Табличный способ приведения к СБНФ

184

6.5.4.

Табличный способ приведения с СКНФ

185

6.6.

Логическое следствие

187

6.6.1.

Алгоритм проверки правильности рассуждений

187

6.6.2.

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

188

6.6.3.

Алгоритм определения всех посылок, логическим следствием которых является данная формула

189

6.7.

Минимизация булевых функций в классе ДНФ

190

6.8.

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

193

Задачи и упражнения

199

7.

Разрешимые и неразрешимые проблемы

202

ЗАКЛЮЧЕНИЕ

213

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

213