Эвнин А.Ю. Задачник по дискретной математике. - 2-е изд.- Челябинск: Издательство ЮУрГУ, 2002. - 164 с.
Сборник задач соответствует курсу дискретной математики для студентов специальностей "Прикладная математика", "Прикладная математика и информатика" и "Программное обеспечение вычислительной техники и автоматизированных систем". Задачник может быть использован также для проведения практикумов по решению олимпиадных задач. Первое издание вышло в 1998 г.
Оглавление
Предисловие....................................................5
1 Предварительные сведения 6
1.1. Множества и операции над ними ................................6
1.2. Высказывания и предикаты ......................................7
1.3. Метод математической индукции................................8
1.4. Правило произведения ............................................10
2 Элементы теории чисел 13
2.1. Наибольший общий делитель. Простые числа.........13
2.2. Сравнения по модулю..............................................15
2.3. Китайская теорема об остатках ..................................16
2.4. Теоремы Эйлера, Ферма, Вильсона..............................17
2.5. Квадратичные вычеты и невычеты..............................19
2.6. Уравнения в целых числах....................20
2.7. Мультипликативные функции..................22
3 Начальные понятия общей алгебры 24
4 Элементы математической логики 27
4.1. Формулы и их преобразования. Двойственность........27
4.2. Полные системы связок......................29
4.3. Теорема Поста...........................30
4.4. Нормальные формы........................31
4.5. Контактные схемы.........................32
4.6. Булева алгебра...........................34
4.7. Аксиоматические теории.....................35
4.8. Исчисление высказываний....................35
4.9. Исчисление предикатов......................38
4.10. Рекурсивные функции.......................40
4.11. Машина Тьюринга.........................46
5 Комбинаторика 50
5.1. Сочетания..............................50
5.2. Полиномиальная формула. Комбинаторные тождества .... 52
5.3. Формула включения-исключения................53
5.4. Задача о беспорядках и встречах ................54
5.5. Числа Фибоначчи.........................55
5.6. Производящие функции......................58
5.7. Рекуррентные соотношения....................60
6 Теория Пойа 64
7 Введение в теорию графов 67
7.1. Определения и примеры .....................67
7.2. Гамильтоновы и эйлеровы графы................70
7.3. Деревья...............................72
7.4. Укладки графов..........................75
7.5. Ориентированные графы. Алгоритмы..............77
7.6. Турниры ..............................79
7.7. Доминирование, независимость, покрытия, паросочетания . . 81
8 Дополнительные задачи 86
8.1. Инвариант и полуинвариант...................86
8.2. Задачи с целыми числами ....................89
8.3. Числа Кармайкла.........................92
8.4. Формула обращения Мёбиуса ..................93
8.5. Бинарные операции и отношения................96
8.6. Разные комбинаторные задачи..................97
8.7. Тождества .............................100
8.8. Две классические задачи.....................103
8.9. Теорема Рамсея ..........................103
8.10. Ожерелья..............................106
8.11. Графы................................107
Ответы. Указания. Решения..................................109
Литература...................................................160
