Ebook: Дискретная математика

Томский государственный университет систем управления и радиоэлектроники, 2003, 120с.
Часть 1 Теория множеств Булева алгебра.
Изложены основные сведения из теории множеств: алгебра множеств, бинарные
отношения, бесконечные множества, теория нечётких множеств. Из булевой алгебры
представлены разделы: минимизация булевых функций в дизъюнктивных и конъюнктивных
нормальных формах с учётом неопределенных состояний, булевы уравнения, первые сведения о булевом дифференциальном исчислении. Во второй части освещены темы: теория конечных автоматов — синтез логических (комбинационных) и многотактных схем, теорема Поста о функциональной полноте; комбинаторика — размещения, сочетания и перестановки с повторениями и без повторений, разбиение множеств и др.; теория графов — графы и ориентированные графы, сети, деревья и др., а также приведены контрольные работы по всему курсу дискретной математики. В первой части более 1500 упражнений, во второй — более 2000.
Все упражнения закодированы, что обеспечивает возможность работы с пособием в режиме
автоматизированного самоконтроля с применением устройств СИМВОЛ или их компьютерных
аналогов (разработки Томского государственного университета систем управления и
радиоэлектроники).
Для студентов технических специальностей вузов и техникумов, школьников старших
классов общеобразовательных школ и для всех желающих самостоятельно пройти вводный курс прикладной дискретной математики.
Содержание
ТЕОРИЯ МНОЖЕСТВ
Алгебра множеств
Множества
Подмножества
Диаграммы Венна. Универсальное множество
Объединение множеств
Пересечение множеств
Дополнение множеств
Законы де Моргана
Разность множеств
Симметрическая разность множеств
Закон поглощения
Закон склеивания
Теоретико-множественные преобразования
Бинарные отношения
Декартово произведение множеств
Степень множества
Понятие бинарного отношения
Симметрия отношений
Транзитивность отношений
Рефлексивность отношений
Отношения эквивалентности
Отношения строгого порядка
Отношения нестрогого порядка
Упорядоченные множества
Отношения соответствия
Функциональные отношения. Отображения
Реляционная алгебра
Бесконечные множества
Вводные замечания
Сравнение бесконечных множеств
Счетные множества
Несчетные множества
Гипотеза континуума
Трансцендентные числа.
Об эквивалентности множеств точек геометрических объектов
Трансфинитные числа
Парадоксы теории множеств
Упражнения на тему «Парадоксы теории множеств»
Элементы теории нечетких множеств
Вводные замечания
Нечеткие множества
Объединение нечетких множеств
Пересечение нечетких множеств
Дополнение нечеткого множества
Разность и симметрическая разность нечетких множеств
Основные свойства операций над нечеткими множествами
БУЛЕВА АЛГЕБРА
Двоичные числа
Понятие высказывания
Аксиомы булевой алгебры
Свойства дизъюнкции и конъюнкции
Теоремы одной переменной
Дизъюнктивные и конъюнктивные формы
Теоремы поглощения, склеивания и де Моргана
Инвертирование сложных выражений
Дизъюнктивные формы булевых функций
Понятие булевой функции
Как задать булеву функцию
Минтермы
Совершенная дизъюнктивная нормальная форма
Теорема разложения для ДНФ
Карта Вейча
Нанесение функций на карту Вейча
Нахождение СДНФ при помощи карт Вейча
Алгебраическое упрощение булевых функций
Понятие импликанты
Метод Квайна
Нахождение простых импликант по карте Вейча
Метод Петрика
Минимизация булевых функций при помощи карт Вейча
Конъюнктивные формы булевых функций
Основной способ нахождения КНФ
Макстермы
Совершенная конъюнктивная нормальная форма
Теорема разложения для КНФ
Нахождение сокращенных КНФ
Нахождение тупиковых и минимальных КНФ
Перевод функций из КНФ в ДНФ
Неполностью определенные булевы функции
Понятие неполностью определенной булевой функции
СДНФ неполностью определенных функций
СКНФ неполностью определенных функций
Минимизация ДНФ неполностью определенных функций
Минимизация КНФ неполностью определенных функций
Формы высших порядков
Понятие порядка булевой функции
Граф-схема булевой функции
Абсолютно минимальные формы
Повышение порядка булевых функций
Классификация форм булевых функций
О классификации форм высших порядков
Симметрические булевы функции
Понятие симметрической функции
Способы представления симметрических функций
Операции над симметрическими функциями
Разложение симметрических функций для ДНФ
Разложение симметрических функций для КНФ
Общий случай симметрии функций
Числовое представление булевых функций
Понятие изображающего числа булевой функции
Операции над изображающими числами
Изображающие числа функций высших порядков
Восстановление булевой функции по изображающему числу
Числовое представление систем булевых функций
Зависимость и независимость булевых функций
Виды зависимости между двумя функциями
Нахождение явного вида логической зависимости
Булевы уравнения
Уравнения с одной неизвестной переменной
Уравнения с несколькими неизвестными переменными
Уравнения конъюнктивного типа
Уравнения дизъюнктивного типа
Другие типы булевых уравнений
Булевы уравнения с несколькими неизвестными функциями
Ещё раз о формах высших порядков
Неразрешимые уравнения
Пороговые функции
Основные понятия
Функции, определяемые порогом при неизменных весах
Теоремы о пороговых функциях
Нахождение пороговых функций
Мажоритарные функции
Симметрические мажоритарные функции
Булево дифференциальное исчисление
Аксиомы алгебры Жегалкина
Перевод булевых выражений в алгебру Жегалкина и наоборот
Применение карт Вейча в алгебре Жегалкина
Понятие производной от булевой функции
Производная первого порядка
Дифференцирование булевых функций с применением карт Вейча
Смешанные производные
Теоремы о разложении булевых функций
Разложение булевых функций в ряд Тейлора
Нахождение отдельных конъюнкций ряда Тейлора
Литература