Дискретная математика: логика, группы, графы, фракталы
Аннотация
Предисловие
1. Логика
1.1. Операции логики Буля
a. Диаграммы Эйлера – Венна
b. Объединение. Таблицы истинности
c. Пересечение, двойственность и дополнение
d. Стрелка Пирса, штрих Шеффера и разность
e. Симметрическая разность и эквивалентность
1.2. Формы представления булевых функций
a. Совершенные формы представления
b. Минимизация булевых функций по Куайну
c. Минимизация по методу сочетания индексов
d. Минимизация по картам Карно
e. Базовые наборы булевых функций
1.3. Методы доказательства в логике Буля
a. Основные законы логики Буля
b. Аксиоматический и конструктивный способы обоснования
c. Примеры доказательств булевых тождеств
d. Практические задания по логике Буля
1.4. Введение в логику высказываний
a. Высказывания и операции над ними
b. Парадоксальные высказывания
c. Построение доказательств в логике высказываний
d. Аксиома порядка и ее применение
e. Табличный способ доказательства
f. Метод резолюций
g. Метод Вонга
h. Метод натурального исчисления (метод Генцена)
i. Практические задания по логике высказываний
j. Примеры решения задач
1.5. Операции над предикатами и кванторами
a. О предикатах, кванторах и многоместных функциях
b. Конкретизация предикатов
c. Решетки вообще и булеан в частности
d. Построение доказательств в логике предикатов
e. Практические задания по логике предикатов
f. Разбор решений задач по логике предикатов
2. Группы
2.1. Группа и связанные с ней понятия
a. Линейное преобразование
b. Определение группы и примеры групп
c. Действия с 0,1-матрицами
d. Обобщенное комплексное число
e. Гиперкомплексные числа
f. Матричные конструкции
g. Подстановки
h. Циклическая форма подстановок
i. Комбинаторные свойства подстановок
2.2. Группы на матрицах и подстановках
a. Представления групп до 11-й порядка
b. Группа 12-го порядка и групповые закономерности
c. Отношение эквивалентности
d. Факторгруппа, инвариант и внутренний автоморфизм
e. Голоморфы диэдра и кватерниона
f. Геометрическая интерпретация групповых преобразований
g. Прямая сумма и прямое произведение
h. Размерность представления и диаграммы Юнга
i. Представления группы квадрата
j. Представления группы кватерниона
k. Октава и алгебра Клиффорда
l. Представления диэдров 5-го и 6-го порядков
m. Представления групп тетраэдра, куба и икосаэдра
2.3. Групповые решетки из подгрупп
a. Отношение порядка
b. Решетки групп с 1-го по 12-й порядок
c. Решетки групп 16-го порядка
d. Группа вращения декартовых координат и ее подгруппы
e. Решетки групп 18-го и 20-го порядков
f. Решетки групп 24-го порядка
g. Решетки групп 27-го порядка
2.4. Алгебраические системы на базе групп
a. Какие бывают алгебраические системы
b. Числовые поля
c. Сведения из теории чисел
d. Поля многочленов
e. Разложение многочлена на неприводимые множители
f. Корректирующие коды
g. Порождающая и проверочная матрицы
h. Кодовое расстояние и помехозащищенность
i. Примеры корректирующих кодов
2.5. Пространственные группы и двойственность
a. Группы Ли и Галуа
b. Симметрия уравнений Максвелла
c. Инвариантность волнового уравнения
d. Преобразование комплексной плоскости
e. Группа проективных преобразований и ее подгруппы
f. Две симметрии: вращение и перемещение
g. Двойственность и проецирование
h. Ортогональные и гиперболические преобразования
i. Масштаб осей при гиперболическом повороте
j. Моделирование волновых процессов
k. Эффект сдвига воспринимаемой длины волны в красную область
l. Практические задания по группам
3. Графы
Вводные замечания
3.1. Группы цепей графа
a. Элементарная группа цепей и ее решетка
b. Группа цепей тетраэдра
c. Классы эквивалентности группы цепей тетраэдра
d. Решетка группы цепей тетраэдра
e. Группа цепей куба
f. Гиперкуб, образованный из 72-х цепей куба
g. Классы эквивалентности группы цепей куба
h. Классы и подгруппы группы цепей Г5
i. Задача Гамильтона о цепях додекаэдра
3.2. Морфология графа
a. Матрицы смежности и инцидентности
b. Пути и контуры в графе
c. Симметрия графа и его дополнения
d. Виды графов
e. Разложение графа на базисные составляющие
f. Реберные и вершинные покрытия
g. Трансверсаль, матроид и двойственность графов
h. Отношения эквивалентности и порядка
i. Оптимальный путь и максимальный поток
3.3. Кодирование, автоматы и группы на графах
a. Типы и назначение кодирования
b. Оптимальные деревья кодирования
c. Автоматы задержки и распознавания символов
d. Автоматы-преобразователи
e. Ликвидация эквивалентных состояний
f. Графы кватерниона и тетраэдра
3.4. Лингвистические и поисковые графы
a. Порождающая грамматика
b. Граф словообразования
c. Граф словоизменения
d. Задача о ханойской башне
e. Другие поисковые задачи
3.5. Раскраска графов и вопросы топологии
a. Задача о раскраске карты
b. Аналогия с Великой теоремой Ферма
c. Планарные графы на торе
d. Многогранники
e. Формула Эйлера и связанность поверхности
f. «Кренделя» и странные свойства гептаэдра
g. Формула для минимального числа цветов
h. Бутылка Клейна и вывернутые поверхности
i. Зацепления, узлы и топология
j. Практические задания по графам
3.6. Приложение. Узел как произведение искусства
4. Фракталы
4.1. Что такое фрактал
4.2. Прямое произведение и фракталы
4.3. К вопросу о размерности
4.4. Грамматика на службе у фракталов
4.5. Аффинные преобразования
4.6. Динамические фракталы
4.7. Динамика популяций
4.8. Бифуркационная диаграмма
4.9. Аттрактор «Крепостная стена»
4.10. Аттракторы от функции косинуса
4.11. Прокол аттрактора
4.12. Ноль-аттракторы, π-аттракторы и квазиаттракторы
4.13. Субаттракторы
4.14. Хаос
Библиография
Приложение. Фрактал как произведение искусства
Предлагаемая читателям работа не является учебником или законченной статьёй, поскольку находится в стадии исследования. Автор старается использовать простой математический язык, давая определения вводимым объектам исследования и пояснения вводимым обозначениям. Публикуются только результаты исследования, и раскрывается их взаимосвязь. Для понимания механизма получения результатов автор приводит примеры в основном без промежуточных выкладок. Давая оценки или утверждения, анализируя те или иные результаты, автор исходит из результатов имеющихся у него на сегодняшний день. Если в процессе дальнейшего исследования, появляются результаты, противоречащие существующим утверждениям, автор делает исправления. Но это не важно. Важно то, что все математические результаты, публикуемые в статье, автором проверены и переНепроверены (возможны опечатки и ошибки при наборе, но по мере их обнаружения, сразу идет исправление). А как трактовать полученные результаты, пока теория находится в стадии разработки, личное дело любого человека. ...
Заслуга автора изящной геометрии состоит в том, что он разработал вполне оригинальную конструктивную теорию, основанную на базе окружностей и сфер с опорой на симметричные, групповые и фрактальные преобразования. Им были указаны правила построения эстетически привлекательных конструкций и доказано немало строгих теорем. Его теоретические разработки и компьютерные программы могут быть с успехом использованы для обучения учащихся и студентов специальным разделам математических дисциплин, тесно связанных с компьютерной графикой, программированием и дизайном. Проделанная Револьтом Пименовым работа, несомненно, имеет важное прикладное значение. Она выполнена на хорошем методическом и дидактическом уровне. Рекомендую, Олег Акимов.
