- •Содержание
- •1 Элементы теории множеств. Комбинаторика. 5
- •Математическая логика: Булева аллгебра 88
- •Теория алгоритмов 129
- •Теория графов 162
- •Математическая логика: Исчисления высказываний и предикатов 207
- •Элементы теории множеств. Комбинаторика.
- •Введение
- •Примеры задач.
- •Задача о расположении конвертов
- •Задача о Ханойской башне
- •Базовые обозначения
- •Правило суммы и правило произведения
- •Основы теории множеств
- •Понятие множества
- •Парадокс Рассела
- •Подмножества
- •Операции над множествами
- •Диаграммы Эйлера-Венна
- •Прямое произведение множеств
- •Бинарные отношения и функции
- •Бинарные отношения
- •Функции
- •Специальные бинарные отношения: Отношение эквивалентности
- •Специальные бинарные отношения: Отношение порядка
- •Лексикографический порядок
- •Выборки с повторениями и без повторений
- •Размещения и сочетания
- •Треугольник Паскаля
- •Связь сочетаний и (0,1)-векторов
- •Перебор сочетаний
- •Бином Ньютона
- •Мультимножества
- •Связь мультимножеств и (0,1)-векторов
- •Полином Ньютона
- •Разбиения множеств.
- •Приложение: программа перебора сочетаний
- •Перестановки
- •Понятие перестановки
- •Группа перестановок
- •Циклы перестановки
- •Тип перестановки
- •Разложения и разбиения натуральных чисел
- •Разложения натуральных чисел
- •Разбиения натуральных чисел
- •Принцип включения-исключения
- •Принцип включения-исключения
- •Задача о беспорядках
- •Мощность объединения множеств
- •Число целочисленных решений системы неравенств
- •Математическая логика: Булева аллгебра
- •Булева алгебра. Функции алгебры логики.
- •Булевы функции
- •Формулы
- •Основные тождества
- •Разложение функции по переменным
- •Дизъюнктивная и конъюнктивная нормальные формы
- •Полином Жегалкина
- •1 ⊕ X1 ⊕ x2x3 - полином Жегалкина.
- •Полнота системы функций
- •Функции, сохраняющие ноль
- •Функции, сохраняющие единицу
- •Двойственность
- •Монотонность
- •Линейность
- •Критерий полноты системы функций
- •Теория алгоритмов
- •Машины Тьюринга
- •Понятие алгоритма
- •Машина Тьюринга
- •Способы записи машины Тьюринга
- •Стандартные конфигурации
- •Вычислимые функции
- •Алгоритмически неразрешимые задачи
- •Сложность алгоритма
- •Полиномиальная сводимость
- •Классы задач в форме распознавания свойств
- •4 Теория графов
- •4.1 Определения графа
- •Общее определение
- •Виды графов
- •Обыкновенный граф
- •Примеры графов
- •Графы Бержа
- •4.2 Изоморфизм графов
- •4.2.1 Инварианты графа
- •Операции
- •Основные операции над графами
- •Подграфы
- •Дополнение графа
- •Маршруты и связность
- •Деревья
- •Матрицы, связанные с графом
- •Матрица смежности
- •Матрица инцидентности
- •Список ребер
- •Обходы графов
- •Эйлеров цикл
- •Гамильтонов цикл
- •Задачи и алгоритмы
- •Остов минимального веса
- •Алгоритм 4.8.1 (Алгоритм Краскала).
- •Задача коммивояжера
- •Задача о клике
- •Задача о вершинном покрытии
- •Задача о гамильтоновом цикле
- •Снова задача коммивояжера
- •Алгоритм дерева
- •Математическая логика: Исчисления высказываний и предикатов
- •Исчисление высказываний
- •Пример задачи логики высказываний
- •Формальные теории
- •Формальная теория исчисление высказываний
- •Теоремы исчисления высказываний
- •Теорема о полноте исчисления высказываний
- •Независимость аксиом исчисления высказываний
- •Исчисление предикатов
- •Пример задачи логики предикатов
- •Формальная теория исчисление предикатов
- •Алфавит.
- •Формулы.
- •Аксиомы.
- •Правила вывода.
- •Интерпретация
- •Литература
Конспект курса: Основы дискретной математики
Е.В. Просолупов. 29th May 2009
Содержание
1 Элементы теории множеств. Комбинаторика. 5
1.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Примеры задач. . . . . . . . . . . . . . . . . . . . . . . . . . 6
Задача о расположении конвертов . . . . . . . . . . 6
Задача о Ханойской башне . . . . . . . . . . . . . . 11
Базовые обозначения . . . . . . . . . . . . . . . . . . 15
Правило суммы и правило произведения . . . . . . 16
1.3 Основы теории множеств . . . . . . . . . . . . . . . . . . . 18
1.3.1 Понятие множества . . . . . . . . . . . . . . . . . . 18
1.3.2 Парадокс Рассела . . . . . . . . . . . . . . . . . . . . 19
1.3.3 Подмножества . . . . . . . . . . . . . . . . . . . . . 19
Операции над множествами . . . . . . . . . . . . . . 20
Диаграммы Эйлера-Венна . . . . . . . . . . . . . . . 22
Прямое произведение множеств . . . . . . . . . . . . 23
1.4 Бинарные отношения и функции . . . . . . . . . . . . . . . 24
1.4.1 Бинарные отношения . . . . . . . . . . . . . . . . . 24
1.4.2 Функции . . . . . . . . . . . . . . . . . . . . . . . . . 25
Отношение эквивалентности . . . . . . . . . . . . . 29
Отношение порядка . . . . . . . . . . . . . . . . . . 31
Лексикографический порядок . . . . . . . . . . . . . 35
1.5 Выборки с повторениями и без повторений . . . . . . . . . 38
-
1.5.1
Размещения и сочетания . . . . . . .
.
.
.
.
.
.
.
.
.
38
1.5.2
Треугольник Паскаля . . . . . . . .
.
.
.
.
.
.
.
.
.
41
1.5.3 Связь сочетаний и (0,1)-векторов . . . . . . . . . . . 43
-
1.5.4
Перебор сочетаний . . . . . . . . . . . .
.
.
.
.
.
.
.
44
1.5.5
Бином Ньютона . . . . . . . . . . . . . .
.
.
.
.
.
.
.
45
1.5.6
Мультимножества . . . . . . . . . . . .
.
.
.
.
.
.
.
50
1.5.7
Связь мультимножеств и (0,1)-векторов
.
.
.
.
.
.
.
53
1.5.8
Полином Ньютона . . . . . . . . . . . .
.
.
.
.
.
.
.
54
1.5.9
Разбиения множеств. . . . . . . . . . . .
.
.
.
.
.
.
.
55
1.5.10 Приложение: программа перебора сочетаний . . . . 58
1.6 Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Понятие перестановки . . . . . . . . . . . . . . . . . 61
Группа перестановок . . . . . . . . . . . . . . . . . . 62
Циклы перестановки . . . . . . . . . . . . . . . . . . 63
1.6.4 Тип перестановки . . . . . . . . . . . . . . . . . . . . 68
Разложения и разбиения натуральных чисел . . . . . . . . 71
Разложения натуральных чисел . . . . . . . . . . . 71
Разбиения натуральных чисел . . . . . . . . . . . . 73
Принцип включения-исключения . . . . . . . . . . . . . . . 77
Принцип включения-исключения . . . . . . . . . . . 77
Задача о беспорядках . . . . . . . . . . . . . . . . . 78
Мощность объединения множеств . . . . . . . . . . 80
Число целочисленных решений системы неравенств 81