- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 8.6.Днф, интервалы и покрытия
Теоретико-множественная интерпретация булевой алгебры предлагает очень удобный язык для изучения дизъюнктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связанные с ДНФ.
Введём следующее обозначение: обозначим через множество всех единичных наборов функции. Тогда набор (вектор)из множествапринадлежиттогда и только тогда, когда. Множествоназываетсяединичным множествомфункции, а функцияназываетсяхарактеристической функциеймножества.
Если функция представляется элементарной конъюнкцией всехпеременных, то множествосодержит ровно один элемент множества. Если же функция – элементарная конъюнкцияпеременных, тосодержитдвоичных наборов. Это объясняется тем, что в таком случаепеременных, не входящих в эту конъюнкцию несущественны для функции. Тогда они принимаютзначений, не изменяя значения. Множествотакой функции называется интервалом.
Пример 8.7:Рассмотрим функциюи найдём её интервал.
Прежде всего, заметим, что две переменных являются несущественными. Это позволяет сразу определить количество единичных наборов, содержащихся в множестве(иначе говоря, его мощность). Поскольку в данном случае, то получим.
Далее, очевидно, что только при значениях. При этом переменныемогут принимать любые значения. Теперь перечислим все единичные наборы для данной функции:. Итак,.
В рассматриваемом случае говорят, что конъюнкция (или, точнее, интервал) покрывает множествои все его подмножества.
Представление некоторой функции в виде ДНФ соответствует представлению её единичного множества в виде объединения интервалов; в совокупности все конъюнкции ДНФ покрывают всё единичное множество функции . Обратное также верно: если все элементы некоторого интервалапринадлежат, то существует ДНФ данной функции, содержащая конъюнкцию.
Раздел 9. Функциональная полнота. Алгебра Жегалкина
Ранее нами рассматривались два способа задания логических функций – табличный и аналитический. Таблица задаёт функцию непосредственно как соответствие между двоичными наборами и значениями функции на этих наборах. Этот способ универсален, то есть, пригоден для любых функций, однако слишком громоздок. Формула – гораздо более компактный способ задания функции, но она задаёт функцию через другие функции. Поэтому для любой системы функций возникает естественный вопрос: всякая ли логическая функция представима формулой в этой системе.
Мы уже рассмотрели систему и получили положительный ответ на поставленный вопрос. Покажем, как решать этот вопрос для произвольной системы.
Тема 9.1.Функционально полные системы
Определение. Система функцийназываетсяфункционально полнойсистемой, если любая логическая функция может быть представлена формулой над системой, т.е. является суперпозицией функций этой системы.
Система является функционально полной. Равным образом, функционально полна любая система, через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Действительно, для любой логической функциииз такой системы следует составить булеву формулу, и она обязательно существует и выразить в ней конъюнкцию, дизъюнкцию и отрицание через функции системы. Аналогично обосновывается более общее утверждение.
Теорема:Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.
Пример 9.1:
а) Системы ифункционально полны, поскольку, с помощью законов Де Моргана и двойного отрицания можно выразить в каждой из этих систем функцию, недостающую дочерез остальные две:
.
С точки зрения функциональной полноты систему следует считать избыточной: она сохраняет свойство полноты и при удалении из неё конъюнкции или дизъюнкции. Однако легко видеть из приведённого примера, что, хотя системыине являются избыточными, формулы в них получаются длиннее.
б) Системы (штрих Шеффера) и(стрелка Пирса) являются функционально полными.
Таким образом, система сводится к системе, а система– к системе.
в) Система является функционально полной. Поскольку, данная система сводится к.
На свойствах этой системы остановимся подробнее.