- •1. Предикаты и кванторы
- •Определение
- •Примеры
- •Операции над предикатами
- •Логические операции
- •Кванторные операции
- •Примеры
- •Введение в понятие
- •Кванторы в математической логике
- •Свободные и связанные переменные
- •Операции над кванторами
- •2. Комбинаторные правила. Правило птичьих гнёзд. Правило сложения
- •Тема 2. Элементы теории множеств и комбинаторика
- •3. Общие правила комбинаторики
- •Пример 1
- •Пример 2
- •3. Правило умножения
- •4. Размещение с повторениями и без повторений
- •Количество размещений
- •Размещение с повторениями
- •Размещения без повторений
- •Где все это применяется, уже очевидно. Осталось только привести несколько хитрых примеров:
- •5. Сочетания без повторений
- •6. Сочетания с повторениями. Разбитие множеств на части
- •Определение
- •Разбиения конечных множеств
- •Примеры
- •7. Отношения. Представления и свойства отношений
- •8. Отношения эквивалентности. Связь отношений эквивалентности и разбиений множеств
- •Связанные определения
- •Примеры отношений эквивалентности
- •Факторизация отображений
- •9. Отношение эквивалентности. Связь отношений эквивалентности и разбиений множеств Отношение частичного порядка
- •10. Отношения линейного порядка Отношение линейного порядка
- •Упорядоченные множества
- •11. Логические функции. Задание и элементарные функции
- •Основные сведения
- •Нульарные функции
- •Унарные функции
- •Бинарные функции
- •Тернарные функции
- •[Править]Полные системы булевых функций Суперпозиция и замкнутые классы функций
- •Тождественность и двойственность
- •Полнота системы, критерий Поста
- •Представление булевых функций
- •Дизъюнктивная нормальная форма (днф)
- •Конъюнктивная нормальная форма (кнф)
- •Элементарные функции по Лиувиллю
- •Дифференцирование элементарных функций
- •Интегрирование элементарных функций
- •12. Дизъюнктивные нормальные формы
- •Примеры и контрпримеры
- •Построение днф Алгоритм построения днф
- •Пример построения днф
- •Переход от днф к сднф
- •13. Минимизация днф
- •14. Монотонные функции
- •Определения
- •Другая терминология
- •Свойства монотонных функций
- •Условия монотонности функции
- •15. Графы. Представления графов. Пути в графах
- •Путь и цикл в графе. Эйлеровые линии
Тождественность и двойственность
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
-
(законы де Моргана)
(дистрибутивность конъюнкции и дизъюнкции)
Функция называется двойственной функции , если . Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Полнота системы, критерий Поста
Система булевых функций называется полной, если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыканиеданной системы совпадает с множеством P2.
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
Функции, сохраняющие константу T0 и T1;
Самодвойственные функции S;
Монотонные функции M;
Линейные функции L.
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с P2, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
Представление булевых функций
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций . Тогда каждая булева функция сможет быть представлена некоторымтермом в сигнатуре Σ, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
Как построить по данной функции представляющую её формулу?
Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?
Положительные ответы на эти и другие вопросы существенно увеличивают прикладное значение выбранной системы функций.