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

Из основных равенств следует, что для каждой формулы $\Phi \in F_{AB}$ можно указать равносильные ей формулы специального вида, содержащие только символы логических операций.

Определение. Литерой называется пропозициональная переменная $X$ или её отрицание $\lnot X$. Для обозначения литеры используется символ $X^\alpha$, где $\alpha \in \{0, 1\}$ и по определению $X^1 = X$, $x^0 = \lnot X$.

Определение. Конъюнктом (дизъюнктом) называется конъюнкция (дизъюнкция) литер или одна литера.

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктов или один дизъюнкт. Пример ДНФ: $D_1 \land D_2 \land \cdots \land D_m$, где $D_i$ — дизъюнкты.
Дизъюнкция нормальной формой (ДНФ) называется диъюнкция конъюнктов или один конъюнкт. Пример ДНФ: $D_1 \lor D_2 \lor \cdots \lor D_m$, где $D_i$ — конъюнкты.
При этом КНФ (ДНФ) называется совершенной, если все её дизъюнкты (конъюнкты) содержат все пропозициональные переменные рассматриваемой формулы.

Теорема 2. Любая выполнимая формула $\Phi = \Phi(X_1, \dots, X_n) равносильна формуле вида $$\bigvee_{\alpha_1, \dots, a_n} (X_1^{\alpha_1} \land \dots \land X_n^{\alpha_n}),$$ где дизъюнкция берётся по всем упорядоченным наборам $(\alpha_1, \dots, \aloha_n) \in \{0, 1\}^n$, удовлетворяющим условию $F_\Phi(\alpha_1, \dots, \alpha_n) = 1.

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

Теорема 3. Любая выполнимая формула $\Phi = \Phi(X_1, \dots, X_n) равносильна формуле вида $$\bigwedge_{\alpha_1, \dots, a_n} (X_1^{\alpha_1} \land \dots \land X_n^{\alpha_n}),$$ где конъюнкция берётся по всем упорядоченным наборам $(\alpha_1, \dots, \aloha_n) \in \{0, 1\}^n$, удовлетворяющим условию $F_\Phi(\alpha_1, \dots, \alpha_n) = 1.

Такая формула определяется однозначно (с точностью до порядка членов конъюнкций и дизъюнкций) и называется совершенной конъюнктивной нормальной формулой (СКНФ) формулы $\Phi$.