ПДНФ и ПКНФ — Введение в математическую логику

• Формы в логике
  • Дизъюнктивная нормальная форма (ДНФ)
  • Полная дизъюнктивная нормальная форма (ПДНФ)
  • Конъюнктивная нормальная форма (КНФ)
  • Полная конъюнктивная нормальная форма (ПКНФ)
• Выводы

В отличие от ученых из других научных сфер, математики часто не задумываются о практическом применении того или иного знания. Обычно они ставят теоретические вопросы и находят ответы на них.

Уже позже некоторые ответы оказываются полезными в других разделах математики или в науке в целом. Например, так появились векторы, без которых сложно представить всю современную науку. Сначала математики просто ради интереса занимались кубическими уравнениями и комплексными числами, а уже потом эти темы объединились и привели к векторам.

Как и математика, логика зачастую не имеет практического применения — например, сложно представить практическое применение форм в логике, которые мы изучим сегодня.

Тем не менее пропустить эту тему нельзя. Формы позволят решать задачи минимизации булевых функций и оптимизации на графах, которые мы будем рассматривать в других курсах по математике.

Формы в логике

Ранее в курсе мы научились определять истинность формул двумя способами:

• Через таблицу истинности
• Через доказательство с помощью modus ponens

Эти способы помогают нам доказать общезначимые формулы. Попробуем усложнить задачу и проверить, можно ли доказать общезначимую формулу из аксиом. Чтобы это сделать, нам нужно обратиться к нормальной форме.

В математической логике формулы могут иметь нормальную форму — это значит, что их можно приводить к простейшему виду с помощью эквивалентных преобразований. Другими словами, каждую формулу можно привести к нормальной форме — и тогда нам будет проще доказывать.

В этом уроке мы изучим четыре типа нормальных форм:

• Дизъюнктивная нормальная форма (ДНФ)
• Полная дизъюнктивная нормальная форма (ПДНФ)
• Конъюнктивная нормальная форма (КНФ)
• Полная конъюнктивная нормальная форма (ПКНФ)

В разных источниках полные формы иногда называют совершенными: тогда используются сокращения СДНФ и СКНФ. Между полными и совершенными формами нет никакой разницы — это один и тот же термин.

Дизъюнктивная нормальная форма (ДНФ)

Дизъюнктивная нормальная форма (ДНФ) — это нормализация логической формулы в булевой математике. Любую логическую формулу можно преобразовать в ДНФ. При этом изначальная формула и ее ДНФ будут эквивалентны.

Другими словами, дизъюнктивная нормальная форма — это дизъюнкция нескольких элементарных конъюнкций. В дизъюнктивной нормальной форме используются операторы AND, OR и NOT.

Дизъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из суммы элементарных произведений. Например:

(P ∧ ¬Q)∨(Q ∧ R) ∨ ( ¬P ∧ Q ∧ ¬R)

Логическая формула находится в дизъюнктивной нормальной форме только при таких условиях: если существует чередование одной или нескольких конъюнкций одного или нескольких литералов.

Есть еще несколько способов получить дизъюнктивную нормальную форму для логических формул:

• Метод таблицы истинности
• Метод деревьев истинности
• Таблица логических эквивалентностей

Дизъюнктивная нормальная форма помогает автоматически доказывать теоремы. Это один из важных процессов в разработке и верификации интегральных схем, а еще в теории искусственного интеллекта.

Полная дизъюнктивная нормальная форма (ПДНФ)

У ДНФ есть еще и полная версия. Полная дизъюнктивная нормальная форма — это формула ДНФ, в которой все задействованные переменные представлены только один раз в каждом предложении.

Обратите внимание, что у функции может быть только одна ПДНФ. Это упрощает доказательство и снижает вероятность ошибок. Если есть всего один верный ответ, его намного легче проверить.

ПДНФ относится к сумме произведений. Например:

• P, Q, R — переменные
• (P ∧ ¬Q ∧ ¬R) ∨ (P ∧ ¬Q ∧ R) ∨ ( ¬P ∧ ¬Q ∧ ¬R) — пример выражения в ПДНФ
• ∨ — основной оператор (сумма)

Чтобы не запутаться, рассмотрим основное отличие между ДНФ и ПДНФ:

• ДНФ — длина всех переменных в выражении может быть разной
• ПДНФ — длина всех переменных в выражении должна быть одинаковой

Посмотрим на еще двух примерах:

• Выражение в ДНФ, которое не считается ПДНФ из-за разной длины переменных:

(P ∧ ¬Q ∧ R) ∨ ( ¬P ∧ Q ∧ R) ∨ (P ∧ Q)

• Выражение в ДНФ и ПДНФ одновременно:

(P ∧ ` ¬Q ∧ R) ∨ ( ¬P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R)

Конъюнктивная нормальная форма (КНФ)

В логике есть термин клауза (или клаузула) — это формальная запись доказываемого предложения. Введем это понятие, чтобы отличать объектные высказывания от субъектных.

Для начала вспомним, что в булевой алгебре сложение и умножение — это симметричные операции. Это значит, что всегда можно интерпретировать сложение как умножение, а умножение как сложение. Потому и существует КНФ — форма, симметричная для ДНФ. Как и ДНФ, КНФ полезна для автоматизированного доказательства теорем.

Конъюнктивная нормальная форма (КНФ) — это подход к булевой логике, который выражает формулы в виде конъюнкции клаузул с оператором AND или OR. Каждая клауза соединена конъюнкцией (оператором AND) и при этом должна либо быть литералом, либо содержать дизъюнкцию (оператор OR).

Другими словами, конъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из произведения элементарных произведений. Например:

(P ¬ ∨ Q) ∧ (Q ∨ R) ∧ ( ¬P ∨ Q ∨ ¬R)

В конъюнктивной нормальной форме высказывания в булевой логике представляют собой конъюнкцию клаузул с клаузулами дизъюнкции. Проще говоря, высказывание — это серия OR, соединенных AND, как в примере ниже:

(A OR B) AND (C OR D)

(A OR B) AND (¬C OR B)

Полная конъюнктивная нормальная форма (ПКНФ)

ПКНФ относится к продукту сумм. Например:

• P, Q, R — переменные
• ((P ∨ ¬Q ∨ ¬R) ∧ (P ∨ ¬Q ∨ R) ∧ ( ¬P ∨ ¬Q ∨ ¬R) — пример выражения в ПКНФ
• ∧ — это основной оператор (произведение)

Снова рассмотрим основные отличия между формами:

• КНФ — длина всех переменных в выражении может быть разной
• ПКНФ — длина всех переменных в выражении должна быть одинаковой

Например:

• Выражение в КНФ, но не в ПКНФ: (P ∨ ¬Q∨ R)∧( ¬P∨ Q ∨ R)∧(P ∨ Q).
• Выражение в КНФ и ПКНФ одновременно: (P ∨ ¬Q∨ R)∧( ¬P∨ Q ∨ R)∧(P ∨ Q ∨ ¬R).

Выводы

В этом уроке мы изучили основные свойства ПКНФ и ПДНФ:

1. Каждая ПДНФ или ПКНФ соответствует уникальному булеву выражению и наоборот.
2. Если X и Y — два булевых выражения, то X эквивалентно Y только тогда, когда ПДНФ(X) = ПДНФ(Y) или ПКНФ(X) = ПКНФ(Y).
3. Если ПКНФ имеет m членов и ПДНФ имеет n членов, то количество переменных в булевом выражении log₂(m ⋅ n).

Самостоятельная работа

Задача №1

Найдите КНФ для:

((((A → B) → ¬A) → ¬B) → ¬C)

Задача №2 Из предыдущей задачи найдите ПКНФ.

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты