СДНФ и СКНФ

Нормальные формы

Начнём с пары терминов. Предположим, что есть некий набор правил преобразования формул. Например:

• \(\lnot\lnot x\) разрешается заменить на \(x\)
• \(\lnot(x\land y)\) разрешается заменить на \(x\lor y\)
• \(\lnot(x\lor y)\) разрешается заменить на \(x\land y\)

Нормализацией формулы при помощи набора правил называется последовательное применение этих правил к подформулам этой формулы.

Нормальной формой называется формула, ни к одной подформуле которой нельзя применить ни одно из правил набора.

Например, формула \(x\land\lnot y\) является нормальной формой относительно вышеприведённого набора правил.

А вот формула \(\lnot(x\land\lnot y)\) не является. При этом её можно нормализовать, получив нормальную форму \(\lnot x\lor y\).

Отметим несколько важных моментов:

• поскольку процесс нормализации зачастую определён неоднозначно, потенциально из одной и той же формулы можно получить несколько разных нормальных форм
• конкретно вышеприведённая тройка правил гарантирует завершение процесса нормализации и единственность результирующей нормальной формы

Совершенная дизъюнктивная нормальная форма

Рассмотрим следующую задачу: имея некий набор операций, научиться выражать произвольную операцию в виде комбинации имеющихся. Оказывается, для набора \(\land,\lor,\lnot\) эта задача решается особенно легко: если \(f(x) = 1\) только для \(x=(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)\), то

\[ f(x_1,x_2,\ldots,x_n)= (\lnot^{\lnot a_1} x_1)(\lnot^{\lnot a_2} x_2)\ldots (\lnot^{\lnot a_n} x_n) \]

В общем случае достаточно взять дизъюнкцию таких выражений для всех \(a\), для которых \(f(a)=1\).

Говоря русским языком, достаточно найти все наборы входов, на которых исследуемая операция даёт единицу, и для каждого такого набора составить (единственную возможную) конъюнкцию входов и их отрицаний, которая на этом наборе обращается в 1. После чего достаточно просто взять дизъюнкцию всех таких конъюнкций.

Результатом такой манипуляции является штуковина (дизъюнкция конъюнкций), называемая совершенной дизъюнктивной нормальной формой (коротко СДНФ) операции \(f\). Например, импликация имеет СДНФ

\[ x\Rightarrow y = \overline{x}\,\overline{y}\lor \overline{x}y\lor xy \]

Нетрудно заметить, что СДНФ определена с точностью до перестановки конъюнктов внутри дизъюнктов и перестановки самих дизъюнктов.

Совершенная конъюнктивная нормальная форма

Аналогичным образом можно построить «двойственный» объект — СКНФ.

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

Написанные дизъюнкции следует соединить операциями конъюнкции.

Например, для XOR СКНФ имеет вид

\[ x\oplus y = (\overline{x}\lor\overline{y})\land (x\lor y) \]

А для импликации СКНФ следует запомнить наизусть:

\[ x\Rightarrow y = \overline{x}\lor y \]

И опять NAND

Наличие СДНФ и СКНФ у произвольной зависимости показывает, что любую зависимость можно реализовать лишь комбинируя дизъюнкции с отрицаниями (или конъюнкции с отрицаниями).

Тем не менее, при некотором желании можно обойтись и одной операцией. К таким универсальным операциям относятся, например, NAND (и заодно его двойственная операция — NOR).

Это следует из (тривиально проверяемых) соотношений

• \(\lnot x = x\,|\,x\)
• \(x\land y = \lnot(x\,|\,y) = (x\,|\,y)\,|\,(x\,|\,y)\)