Читать онлайн «Дополнительные главы дискретной математики»
Автор В. П. Воронин
Московский Государственный Университет
имени М. В. Ломоносова
Факультет Вычислительной Математики и Кибернетики
Кафедра Математической Кибернетики
Дополнительные главы
дискретной математики
лектор — старший преподаватель В. П. Воронин
составитель — А. Д. Поспелов
Москва 2002
2
Оглавление
1 Комбинаторика 5
Бинарное отношение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1. 1 Простейшие комбинаторные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Принцип включения и исключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Перестановки с ограничениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1. 2 Производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Разбиения множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Рекуррентные соотношения и производящие функции . . . . . . . . . . . . . . . . . . . 34
Основные свойства обычных производящих функций . . . . . . . . . . . . . . . . . . . 40
Основные преобразования обычных производящих функций . . . . . . . . . . . . . . . 41
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1. 3 Простейшие перечислительные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Вводные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Основные леммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Теорема Пойа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1. 4 Частично упорядоченные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Цепи Анселя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Алгебры инцидентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Решетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2 Конечнозначные логики 89
2. 1 Функции конечнозначной логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
Реализация функций формулами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Первая и вторая формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Операция замыкания, свойства замыкания, замкнутые классы . . . . . . . . . . . . . . 93
3
4 ОГЛАВЛЕНИЕ
Полные системы, примеры полных систем . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Теорема о полноте системы Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Функция Вебба . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
2. 2 Теоремы о функциональной полноте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Теорема об алгоритмической разрешимости проблемы распознавания полноты в k-
значной логике . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Теорема Кузнецова о функциональной полноте . . . . . . . . . . . . . . . . . . . . . . . 110
2. 3 Существенные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Леммы о существенных функциях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Теоремы о существенных функциях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
2. 4 Особенности многозначных логик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Представление функции k -значной логики полиномами . . . . . . . . . . . . . . . . . . 118
Теоремы о замкнутых классах в Pk при k > 3 . . . . . . . . . . . . . . . . . . . . . . . . 119
Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3 Теория алгоритмов и рекурсивные функции 125
3. 1 Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3. 2 Классы частично рекурсивных, рекурсивных и примитивно рекурсивных функций . . 125
3. 3 Формула Клини . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4 Детерминированные и ограниченно детерминированные функции 127
4. 1 Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4. 2 Операции над детерминированными и ограниченно детерминированными функциями 127
4. 3 Полные системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5 Конечные поля и самокорректирующиеся коды 129
5. 1 Кольца и поля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5. 2 Идеалы колец . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5. 3 Максимальные идеалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5. 4 Характеристика кольца и поля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5. 5 Кольцо многочленов над кольцом и полем . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5. 6 Коды, обнаруживающие и исправляющие ошибки . . . . . . . . . . . . . . . . . . . . . 129
Глава 1
Комбинаторика
Основным объектом изучения комбинаторики является как правило конечное (хотя, возможно, и
счетное) множество, из элементов которого составляются различные комбинаторные конфигурации.
