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

    Элементарной дизъюнкцией \(n\) переменных называется дизъюнкция переменных или их отрицаний.
    Элементарная дизъюнкция \(n\) переменных может быть записана в виде: $$x^{\delta ^{1}}_{1} \wedge x^{\delta ^{2}}_{2} \wedge ... \wedge x^{\delta ^{n}}_{n},$$
    где \(x_{k}^{\delta _{k}}=\)\(\begin{cases} x_{k}, \text{ если } \delta _{k}=1, \\ \bar{x_{k}}, \text{ если} \delta _{k}= 0. \end{cases}\)
    Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
    Для любой формулы алгебры логики путем равносильных преобразований можно получить ее КНФ, причем не единственную.
    Например, для формулы \(A \equiv \overline{ x \vee y} \leftrightarrow x \wedge y\) имеем: $$A \equiv ( \overline{ x \vee y} \rightarrow x \wedge y ) \wedge ( x \wedge y \rightarrow \overline{x \vee y} ) \equiv$$ $$\equiv ( x \vee y \vee x \wedge y ) \wedge (\overline{ x \wedge y} \vee \overline{x \vee y}) \equiv$$ $$\equiv ( x \vee x \vee y) \wedge ( x \vee y \vee y) \wedge ( \bar{x} \vee \bar{y} \vee \bar{x} ) \wedge ( \bar{x} \vee \bar{y} \vee \bar{y} ),$$
    то есть КНФ будет: $$A \equiv ( x \vee x \vee y) \wedge ( x \vee y \vee y) \wedge ( \bar{x} \vee \bar{y} \vee \bar{x} ) \wedge ( \bar{x} \vee \bar{y} \vee \bar{y}. )$$
    Но так как \(x \vee x \equiv x,\) \(y \vee y \equiv y,\) \(\bar{x} \vee \bar{x} \equiv \bar{x},\) \(\bar{y} \vee \bar{y} \equiv \bar{y},\) то КНФ \(A \equiv ( x\vee y) \wedge ( x \vee y) \wedge ( \bar{x} \vee \bar{y}) \wedge ( \bar{x} \vee \bar{y}) .\)
    А так как \(( x\vee y) \wedge ( x \vee y) \equiv ( x\vee y)\), \(( \bar{x} \vee \bar{y}) \wedge ( \bar{x} \vee \bar{y}) \equiv ( \bar{x} \vee \bar{y}),\) то КНФ \(A \equiv ( x \vee y) \wedge ( \bar{x} \vee \bar{y}).\)
    КНФ \(A\) называется совершенной конъюнктивной нормальной формой формулы \(A\) (СКНФ \(A\)), если для нее выполняются условия:
    1. Все элементарные дизъюнкции, входящие в КНФ \(A\), различны.
    2. Все элементарные дизъюнкции, входящие в КНФ \(A\), содержат все переменные.
    3. Каждая элементарная дизъюнкция, входящая в КНФ \(A\), не содержит двух одинаковых переменных.
    4. Каждая элементарная дизъюнкция, входящая в КНФ \(A\), не содержит переменную и ее отрицание.
    Можно доказать, что каждая не тождественно истинная формула имеет единственную СКНФ.
    Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы \(\bar{A}\).
    Действительно, получив с помощью таблицы истинности СДНФ \(\bar{A}\), мы получим СКНФ \(A\), взяв ее отрицание \(\overline{СДНФ \bar{A}}\), то есть СКНФ \(A \equiv \overline {СДНФ \bar{A}}\).
    Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:
    1. Путем равносильных преобразований формулы \(A\) получают одну из КНФ \(A\).
    2. Если в полученной КНФ \(A\) входящая в нее элементарная дизъюнкция \(В\) не содержит переменную \(x_{i}\), то, используя равносильность \(B \vee ( x_{i} \wedge \bar{x_{i}} ) \equiv B\), элементарную дизъюнкцию \(В\) заменяют на две элементарные дизъюнкции \(B \vee x_{i}\) и \(B \vee \bar{x_{i}}\), каждая из которых содержит переменную \(x_{i}\).
    3. Если в КНФ \(A\) входят две одинаковых одинаковых элементарных дизъюнкций \(В\), то лишнюю можно отбросить, пользуясь равносильностью \(B \wedge B \equiv B\).
    4. Если некоторая элементарная дизъюнкция, входящая в КНФ \(A\), содержит переменную \(x_{i}\) дважды, то лишнюю можно отбросить, пользуясь равносильностью \(x_{i} \vee x_{i} \equiv x_{i}\).
    5. Если некоторая элементарная дизъюнкция, входящая в КНФ \(A\), содержит переменную \(x_{i}\) и ее отрицание, то \(x_{i} \vee \bar{x_{i}} \equiv 1\) и, следовательно, вся элементарная дизъюнкция имеет значение 1, а по-этому ее можно отбросить, как единичный член коньюнкции.
    Ясно, что после описанной процедуры будет получена СКНФ \(A\).
    Например, для формулы \(A \equiv x \vee y \wedge ( x \vee \bar{y})\) КНФ \(A \equiv ( x \vee y ) \wedge ( x \vee x \vee \bar{y})\).
    Так как обе элементарные дизъюнкции различны и содержат все переменные ( х и у), то первое и второе условия СКНФ \(A\) выполнены.
    Элементарная дизъюнкция \(x \vee x \vee \bar{y}\) содержит переменную \(x\) дважды, но \(x \vee x \equiv x\), и по-этому КНФ \(A \equiv ( x \vee \bar{y}) \wedge ( x \vee y)\); причем ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, теперь выполнены все условия СКНФ \(A\), и, следовательно, СКНФ \(A \equiv ( x \vee \bar{y}) \wedge ( x \vee y).\)

---