Дискретная математика: логика, группы, графы, фракталы
Аннотация
Предисловие
1. Логика
1.1. Операции логики Буля
a. Диаграммы Эйлера – Венна
b. Объединение. Таблицы истинности
c. Пересечение, двойственность и дополнение
d. Стрелка Пирса, штрих Шеффера и разность
e. Симметрическая разность и эквивалентность
![](ma/pic2/image004.gif)
1.2. Формы представления булевых функций
a. Совершенные формы представления
b. Минимизация булевых функций по Куайну
c. Минимизация по методу сочетания индексов
d. Минимизация по картам Карно
e. Базовые наборы булевых функций
![](ma/pic2/image083.gif)
1.3. Методы доказательства в логике Буля
a. Основные законы логики Буля
b. Аксиоматический и конструктивный способы обоснования
c. Примеры доказательств булевых тождеств
![](ma/pic2/image011.gif)
d. Практические задания по логике Буля
1.4. Введение в логику высказываний
a. Высказывания и операции над ними
b. Парадоксальные высказывания
c. Построение доказательств в логике высказываний
![](ma/pic2/image017.gif)
d. Аксиома порядка и ее применение
e. Табличный способ доказательства
f. Метод резолюций
g. Метод Вонга
![](ma/pic2/image095.gif)
h. Метод натурального исчисления (метод Генцена)
i. Практические задания по логике высказываний
j. Примеры решения задач
1.5. Операции над предикатами и кванторами
a. О предикатах, кванторах и многоместных функциях
![](ma/pic2/image058.gif)
b. Конкретизация предикатов
c. Решетки вообще и булеан в частности
d. Построение доказательств в логике предикатов
e. Практические задания по логике предикатов
f. Разбор решений задач по логике предикатов
![](ma/pic2/image019.gif)
2. Группы
2.1. Группа и связанные с ней понятия
a. Линейное преобразование
b. Определение группы и примеры групп
![](ma/pic2/image067.gif)
c. Действия с 0,1-матрицами
d. Обобщенное комплексное число
e. Гиперкомплексные числа
![](ma/pic2/image105.gif)
f. Матричные конструкции
g. Подстановки
h. Циклическая форма подстановок
i. Комбинаторные свойства подстановок
![](ma/pic2/image108.gif)
2.2. Группы на матрицах и подстановках
a. Представления групп до 11-й порядка
b. Группа 12-го порядка и групповые закономерности
c. Отношение эквивалентности
![](ma/pic2/image055.gif)
d. Факторгруппа, инвариант и внутренний автоморфизм
e. Голоморфы диэдра и кватерниона
f. Геометрическая интерпретация групповых преобразований
g. Прямая сумма и прямое произведение
h. Размерность представления и диаграммы Юнга
i. Представления группы квадрата
j. Представления группы кватерниона
![](ma/pic2/image096.gif)
k. Октава и алгебра Клиффорда
l. Представления диэдров 5-го и 6-го порядков
m. Представления групп тетраэдра, куба и икосаэдра
2.3. Групповые решетки из подгрупп
a. Отношение порядка
![](ma/pic2/image045.gif)
b. Решетки групп с 1-го по 12-й порядок
c. Решетки групп 16-го порядка
d. Группа вращения декартовых координат и ее подгруппы
e. Решетки групп 18-го и 20-го порядков
f. Решетки групп 24-го порядка
![](ma/pic2/image049.gif)
g. Решетки групп 27-го порядка
2.4. Алгебраические системы на базе групп
a. Какие бывают алгебраические системы
b. Числовые поля
c. Сведения из теории чисел
d. Поля многочленов
![](ma/pic2/image015.gif)
e. Разложение многочлена на неприводимые множители
f. Корректирующие коды
g. Порождающая и проверочная матрицы
h. Кодовое расстояние и помехозащищенность
![](ma/pic2/image081.gif)
i. Примеры корректирующих кодов
2.5. Пространственные группы и двойственность
a. Группы Ли и Галуа
b. Симметрия уравнений Максвелла
c. Инвариантность волнового уравнения
![](ma/pic2/image077.gif)
d. Преобразование комплексной плоскости
e. Группа проективных преобразований и ее подгруппы
f. Две симметрии: вращение и перемещение
g. Двойственность и проецирование
h. Ортогональные и гиперболические преобразования
i. Масштаб осей при гиперболическом повороте
j. Моделирование волновых процессов
![](ma/pic2/image091.gif)
k. Эффект сдвига воспринимаемой длины волны в красную область
l. Практические задания по группам
3. Графы
Вводные замечания
3.1. Группы цепей графа
a. Элементарная группа цепей и ее решетка
![](ma/pic2/image076.gif)
b. Группа цепей тетраэдра
c. Классы эквивалентности группы цепей тетраэдра
d. Решетка группы цепей тетраэдра
e. Группа цепей куба
f. Гиперкуб, образованный из 72-х цепей куба
![](ma/pic2/image023.gif)
g. Классы эквивалентности группы цепей куба
h. Классы и подгруппы группы цепей Г5
i. Задача Гамильтона о цепях додекаэдра
3.2. Морфология графа
a. Матрицы смежности и инцидентности
![](ma/pic2/image025.gif)
b. Пути и контуры в графе
c. Симметрия графа и его дополнения
d. Виды графов
e. Разложение графа на базисные составляющие
![](ma/pic2/image029.gif)
f. Реберные и вершинные покрытия
g. Трансверсаль, матроид и двойственность графов
h. Отношения эквивалентности и порядка
i. Оптимальный путь и максимальный поток
![](ma/pic2/image035.gif)
3.3. Кодирование, автоматы и группы на графах
a. Типы и назначение кодирования
b. Оптимальные деревья кодирования
c. Автоматы задержки и распознавания символов
![](ma/pic2/image043.gif)
d. Автоматы-преобразователи
e. Ликвидация эквивалентных состояний
f. Графы кватерниона и тетраэдра
![](ma/pic2/image047.gif)
3.4. Лингвистические и поисковые графы
a. Порождающая грамматика
b. Граф словообразования
c. Граф словоизменения
d. Задача о ханойской башне
e. Другие поисковые задачи
3.5. Раскраска графов и вопросы топологии
![](ma/pic2/image071.gif)
a. Задача о раскраске карты
b. Аналогия с Великой теоремой Ферма
c. Планарные графы на торе
d. Многогранники
![](ma/pic2/image057.gif)
e. Формула Эйлера и связанность поверхности
f. «Кренделя» и странные свойства гептаэдра
g. Формула для минимального числа цветов
![](ma/pic2/image064.gif)
h. Бутылка Клейна и вывернутые поверхности
i. Зацепления, узлы и топология
j. Практические задания по графам
3.6. Приложение. Узел как произведение искусства
4. Фракталы
![](ma/pic2/image101.gif)
4.1. Что такое фрактал
4.2. Прямое произведение и фракталы
4.3. К вопросу о размерности
4.4. Грамматика на службе у фракталов
4.5. Аффинные преобразования
![](ma/pic2/image086.gif)
4.6. Динамические фракталы
4.7. Динамика популяций
4.8. Бифуркационная диаграмма
4.9. Аттрактор «Крепостная стена»
![](ma/pic2/image109.gif)
4.10. Аттракторы от функции косинуса
4.11. Прокол аттрактора
4.12. Ноль-аттракторы, π-аттракторы и квазиаттракторы
4.13. Субаттракторы
![](ma/pic2/image114.gif)
4.14. Хаос
Библиография
Приложение. Фрактал как произведение искусства
![Фрактал как произведение искусства](ma/pic2/13.jpg)