В отличие от ученых из других научных сфер, математики часто не задумываются о практическом применении того или иного знания. Обычно они ставят теоретические вопросы и находят ответы на них.
Уже позже некоторые ответы оказываются полезными в других разделах математики или в науке в целом. Например, так появились векторы, без которых сложно представить всю современную науку. Сначала математики просто ради интереса занимались кубическими уравнениями и комплексными числами, а уже потом эти темы объединились и привели к векторам.
Как и математика, логика зачастую не имеет практического применения — например, сложно представить практическое применение форм в логике, которые мы изучим сегодня.
Тем не менее пропустить эту тему нельзя. Формы позволят решать задачи минимизации булевых функций и оптимизации на графах, которые мы будем рассматривать в других курсах по математике.
Формы в логике
Ранее в курсе мы научились определять истинность формул двумя способами:
-
Через таблицу истинности
-
Через доказательство с помощью modus ponens
Эти способы помогают нам доказать общезначимые формулы. Попробуем усложнить задачу и проверить, можно ли доказать общезначимую формулу из аксиом. Чтобы это сделать, нам нужно обратиться к нормальной форме.
В математической логике формулы могут иметь нормальную форму — это значит, что их можно приводить к простейшему виду с помощью эквивалентных преобразований. Другими словами, каждую формулу можно привести к нормальной форме — и тогда нам будет проще доказывать.
В этом уроке мы изучим четыре типа нормальных форм:
-
Дизъюнктивная нормальная форма (ДНФ)
-
Полная дизъюнктивная нормальная форма (ПДНФ)
-
Конъюнктивная нормальная форма (КНФ)
-
Полная конъюнктивная нормальная форма (ПКНФ)
В разных источниках полные формы иногда называют совершенными: тогда используются сокращения СДНФ и СКНФ. Между полными и совершенными формами нет никакой разницы — это один и тот же термин.
Дизъюнктивная нормальная форма (ДНФ)
Дизъюнктивная нормальная форма (ДНФ) — это нормализация логической формулы в булевой математике. Любую логическую формулу можно преобразовать в ДНФ. При этом изначальная формула и ее ДНФ будут эквивалентны.
Другими словами, дизъюнктивная нормальная форма — это дизъюнкция нескольких элементарных конъюнкций. В дизъюнктивной нормальной форме используются операторы AND, OR и NOT.
Дизъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из суммы элементарных произведений. Например:
Логическая формула находится в дизъюнктивной нормальной форме только при таких условиях: если существует чередование одной или нескольких конъюнкций одного или нескольких литералов.
Есть еще несколько способов получить дизъюнктивную нормальную форму для логических формул:
-
Метод таблицы истинности
-
Метод деревьев истинности
-
Таблица логических эквивалентностей
Дизъюнктивная нормальная форма помогает автоматически доказывать теоремы. Это один из важных процессов в разработке и верификации интегральных схем, а еще в теории искусственного интеллекта.
Полная дизъюнктивная нормальная форма (ПДНФ)
У ДНФ есть еще и полная версия. Полная дизъюнктивная нормальная форма — это формула ДНФ, в которой все задействованные переменные представлены только один раз в каждом предложении.
Обратите внимание, что у функции может быть только одна ПДНФ. Это упрощает доказательство и снижает вероятность ошибок. Если есть всего один верный ответ, его намного легче проверить.
ПДНФ относится к сумме произведений. Например:
-
— переменные
-
— пример выражения в ПДНФ
-
— основной оператор (сумма)
Чтобы не запутаться, рассмотрим основное отличие между ДНФ и ПДНФ:
-
ДНФ — длина всех переменных в выражении может быть разной
-
ПДНФ — длина всех переменных в выражении должна быть одинаковой
Посмотрим на еще двух примерах:
-
Выражение в ДНФ, которое не считается ПДНФ из-за разной длины переменных:
-
Выражение в ДНФ и ПДНФ одновременно:
Конъюнктивная нормальная форма (КНФ)
В логике есть термин клауза (или клаузула) — это формальная запись доказываемого предложения. Введем это понятие, чтобы отличать объектные высказывания от субъектных.
Для начала вспомним, что в булевой алгебре сложение и умножение — это симметричные операции. Это значит, что всегда можно интерпретировать сложение как умножение, а умножение как сложение. Потому и существует КНФ — форма, симметричная для ДНФ. Как и ДНФ, КНФ полезна для автоматизированного доказательства теорем.
Конъюнктивная нормальная форма (КНФ) — это подход к булевой логике, который выражает формулы в виде конъюнкции клаузул с оператором AND или OR. Каждая клауза соединена конъюнкцией (оператором AND) и при этом должна либо быть литералом, либо содержать дизъюнкцию (оператор OR).
Другими словами, конъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из произведения элементарных произведений. Например:
В конъюнктивной нормальной форме высказывания в булевой логике представляют собой конъюнкцию клаузул с клаузулами дизъюнкции. Проще говоря, высказывание — это серия OR, соединенных AND, как в примере ниже:
OR AND OR
OR AND ¬ OR
Полная конъюнктивная нормальная форма (ПКНФ)
ПКНФ относится к продукту сумм. Например:
-
— переменные
-
— пример выражения в ПКНФ
-
— это основной оператор (произведение)
Снова рассмотрим основные отличия между формами:
-
КНФ — длина всех переменных в выражении может быть разной
-
ПКНФ — длина всех переменных в выражении должна быть одинаковой
Например:
-
Выражение в КНФ, но не в ПКНФ:
-
Выражение в КНФ и ПКНФ одновременно:
Выводы
В этом уроке мы изучили основные свойства ПКНФ и ПДНФ:
-
Каждая ПДНФ или ПКНФ соответствует уникальному булеву выражению и наоборот
-
Если и — два булевых выражения, то эквивалентно только тогда, когда ПДНФ ПДНФ или ПКНФ ПКНФ
-
Если ПКНФ имеет членов и ПДНФ имеет членов, то количество переменных в булевом выражении
Самостоятельная работа
Задача №1
Найдите КНФ для:
Нажмите, чтобы увидеть ответ
-
Сначала упростим данное выражение, используя законы де Моргана и правило
-
Получаем:
-
Теперь приведем выражение к КНФ:
-
Приведем к ПКНФ:
Задача №2
Из предыдущей задачи найдите ПКНФ.
Нажмите, чтобы увидеть ответ
Приведем к ПКНФ:
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
