Акимов О.Е. Дискретная математика: логика, группы, графы, фракталы

М.: Издатель Акимова, 2005. — 656 с. — ISBN 5-9900342-1-0В учебном пособии излагаются основные разделы дискретной математики, являющейся базовой дисциплиной для специалистов по информатике, программированию, электротехнике, микроэлектронике, компьютерным сетям и технологиям. При изложении материала использовался конструктивный подход - наиболее современная и эффективная форма подачи материала. Текст отличается доступностью и ясностью написания, снабжен большим числом примеров решения задач по логике, группам, графам и фракталам. Предназначается для студентов и преподавателей технических университетов.Предисловие
Логика
Операции логики Буля
Диаграммы Эйлера — Венна
Объединение. Таблицы истинности
Пересечение, двойственность и дополнение
Стрелка Пирса, штрих Шеффера и разность
Симметрическая разность и эквивалентность
Формы представления булевых функций
Совершенные формы представления
Минимизация булевых функций по Куайну
Минимизация по методу сочетания индексов
Минимизация по картам Карно
Базовые наборы булевых функций
Методы доказательства в логике Буля
Основные законы логики Буля
Аксиоматический и конструктивный способы обоснования
Примеры доказательств булевых тождеств
Практические задания по логике Буля
Введение в логику высказываний
Высказывания и операции над ними
Парадоксальные высказывания
Построение доказательств в логике высказываний
Аксиома порядка и ее применение
Табличный способ доказательства
Метод резолюций
Метод Вонга
Метод натурального исчисления (метод Генцена)
Практические задания по логике высказываний
Примеры решения задач
Операции над предикатами и кванторами
О предикатах, кванторах и многоместных функциях
Конкретизация предикатов
Решетки вообще и булеан в частности
Построение доказательств в логике предикатов
Практические задания по логике предикатов
Разбор решений задач по логике предикатов
Группы
Группа и связанные с ней понятия
Линейное преобразование
Определение группы и примеры групп
Действия с 0, Матрицами
Обобщенное комплексное число
Гиперкомплексные числа
Матричные конструкции
Подстановки
Циклическая форма подстановок
Комбинаторные свойства подстановок
Группы на матрицах и подстановках
Представления групп до 11-й порядка
Группа 12-го порядка и групповые закономерности
Отношение эквивалентности
Факторгруппа, инвариант и внутренний автоморфизм
Голоморфы диэдра и кватерниона
Геометрическая интерпретация групповых преобразований
Прямая сумма и прямое произведение
Размерность представления и диаграммы Юнга
Представления группы квадрата
Представления группы кватерниона
Октава и алгебра Клиффорда
Представления диэдров 5-го и 6-го порядков
Представления групп тетраэдра, куба и икосаэдра
Групповые решетки из подгрупп
Отношение порядка
Решетки групп с 1-го по 12-й порядок
Решетки групп 16-го порядка
Группа вращения декартовых координат и ее подгруппы
Решетки групп 18-го и 20-го порядков
Решетки групп 24-го порядка
Решетки групп 27-го порядка
Алгебраические системы на базе групп
Какие бывают алгебраические системы
Числовые поля
Сведения из теории чисел
Поля многочленов
Разложение многочлена на неприводимые множители
Примеры разложения многочленов
Корректирующие коды
Порождающая и проверочная матрицы
Кодовое расстояние и помехозащищенность
Примеры корректирующих кодов
Пространственные группы и двойственность
Группы Ли и Галуа
Симметрия уравнений Максвелла
Инвариантность волнового уравнения
Преобразование комплексной плоскости
Группа проективных преобразований и ее подгруппы
Две симметрии: вращение и перемещение
Двойственность и проецирование
Ортогональные и гиперболические преобразования
Масштаб осей при гиперболическом повороте
Моделирование волновых процессов
Практические задания по группам
Графы
Вводные замечания
Группы цепей графа
Элементарная группа цепей и ее решетка
Группа цепей тетраэдра
Классы эквивалентности группы цепей тетраэдра
Решетка группы цепей тетраэдра
Группа цепей куба
Гиперкуб, образованный из 72-х цепей куба
Классы эквивалентности группы цепей куба
Классы и подгруппы группы цепей Г5
Задача Гамильтона о цепях додекаэдра
Морфология графа
Матрицы смежности и инцидентности
Пути и контуры в графе
Симметрия графа и его дополнения
Виды графов
Разложение графа на базисные составляющие
Реберные и вершинные покрытия
Трансверсаль, матроид и двойственность графов
Отношения эквивалентности и порядка
Оптимальный путь и максимальный поток
Кодирование, автоматы и группы на графах
Типы и назначение кодирования
Оптимальные деревья кодирования
Автоматы задержки и распознавания символов
Автоматы-преобразователи
Ликвидация эквивалентных состояний
Графы кватерниона и тетраэдра
Лингвистические и поисковые графы
Порождающая грамматика
Граф словообразования
Граф словоизменения
Задача о ханойской башне
Другие поисковые задачи
Раскраска графов и вопросы топологии
Задача о раскраске карты
Аналогия с Великой теоремой Ферма
Планарные графы на торе
Многогранники
Формула Эйлера и связанность поверхности
«Кренделя» и странные свойства гептаэдра
Формула для минимального числа цветов
Бутылка Клейна и вывернутые поверхности
Зацепления, узлы и топология
Практические задания по графам
Фракталы
Что такое фрактал
Прямое произведение и фракталы
К вопросу о размерности
Грамматика на службе у фракталов
Аффинные преобразования
Динамические фракталы
Динамика популяций
Бифуркационная диаграмма
Аттрактор «Крепостная стена»
Тригонометрическая функция
Прокол аттрактора
Ноль-аттрактор, тг-аттракторы и квазиаттракторы
Субаттракторы
Хаос
Библиография