Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

106 5. Содержание дисциплины 5.1. Содержание разделов дисциплины № п/п Наименование раздела дисциплины Содержание раздела 1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично. 2. Минимизация булевых функций Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов. 3. Полнота и замкнутость систем логических функций Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций. Определение и лемма о несамодвойственной функции. Класс монотонных функций. Определение и лемма о немонотонной функции. Класс линейных функций. Определение