Понятие нормальных форм.

Конъюнктивным одночленом от переменных $X_1,X_2, \ldots, X_n$ называется конъюнкция этих переменных или их отрицаний. Здесь "или" употребляется в неисключающем смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Приведем несколько примеров конъюнктивных одночленов:

$X_1\land X_1,\quad X_1\land\lnot X_2\land X_3,\quad X_2\land\lnot X_1\land X_3\land\lnot X_2\land X_5,\quad X_1\land X_2\land\lnot X_1\land X_3\land X_1.$

Дизъюнктивным одночленом от переменных $X_1,X_2,\ldots,X_n$ называется дизъюнкция этих переменных или их отрицаний (и здесь союз "или" употребляется в неисключающем смысле). Приведем примеры дизъюнктивных одночленов:

$\lnot X_1\lor X_2\lor X_3,\quad X_2\lor X_2,\quad X_1\lor X_2\lor\lnot X_3\lor\lnot X_1\lor X_4\lor X_2,\quad \lnot X_2\lor X_1\lor\lnot X_4\lor X_1\lor X_4.$

Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных одночленов, т.е. выражение вида $K_1\lor K_2\lor \ldots\lor K_p$ , где все $K_i,~ i=1,2,\ldots,p$ , являются конъюнктивными одночленами (не обязательно различными). Аналогично конъюнктивной нормальной формой называется конъюнкция дизъюнктивных одночленов $D_1\land D_2\land \ldots\land D_q$ , где все $D_j,~ j=1,2,\ldots,q$ , являются дизъюнктивными одночленами (не обязательно различными). Будем также называть дизъюнктивной (конъюнктивной) нормальной формой указанные выражения при $p=1~(q=1)$ .

Нормальную форму, представляющую формулу $F$ (то есть равносильную $F$ ), будем называть просто нормальной формой этой формулы.

Нетрудно понять, что всякая формула обладает как дизъюнктивной, так и конъюнктивной нормальными формами. В самом деле, всякую формулу можно выразить через конъюнкцию, дизъюнкцию и отрицание. Используя законы де Моргана (теорема 4.4, пункты р) и с)) и свойство дистрибутивности конъюнкции относительно дизъюнкции (теорема 4.4, пункт м)), можем преобразовать равносильным образом полученное выражение к дизъюнкции конъюнктивных одночленов (к дизъюнктивной нормальной форме). Если же к исходному выражению применить свойство дистрибутивности дизъюнкции относительно конъюнкции (теорема 4.4, пункт н)), то его можно свести к конъюнкции дизъюнктивных одночленов (к конъюнктивной нормальной форме).

Очевидно, что у данной формулы $F$ существует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие и сложные, другие — более простые.

Здесь мы можем продолжить до некоторого момента аналогию со школьной алгеброй. В школьной алгебре выражения типа $ax,\,xyz,\,(a+b)uv$ (последнее действие в них — умножение) называются одночленами, а выражения типа $a+b,$ $ax+b,$ $xy+uv+p$ (последнее действие — сложение) называются многочленами. В алгебре логики логическое умножение (конъюнкция) и логическое сложение (дизъюнкция) равноправны по своим свойствам. Поэтому выражения типа $X\land Y,$ $X\land Y\land Z$ называются конъюнктивными одночленами, а выражения типа $X\lor Y,$ $X\lor Y\lor Z$ — дизъюнктивными одночленами. Образования из одночленов выражений типа

$(X\land Y)\lor (P\land Q\land R),\qquad (P\lor Q)\land (X\lor Y\lor Z)$

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

Совершенные нормальные формы.

Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм, которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма(среди конъюнктивных форм — совершенная конъюнктивная нормальная форма).

Определение 5.1. Одночлен (конъюнктивный или дизъюнктивный) от переменных $X_1,X_2,\ldots,X_n$ называется совершенным, если в него от каждой пары $X_i,\,\lnot X_i$ $(i=1,2,\ldots,n)$ входит только один представитель ( $X_i$ или $\lnot X_i$ ). Нормальная форма (дизъюнктивная или конъюнктивная) от переменных $X_1,X_2,\ldots,X_n$ называется совершенной от этих переменных, если в нее входят лишь совершенные одночлены (конъюнктивные или дизъюнктивные соответственно) от $X_1,X_2,\ldots,X_n$ .

Приведем пример совершенной конъюнктивной нормальной формы от четырех переменных $X_1,X_2,X_3,X_4:$

$\bigl(X_1\lor X_2\lor X_3\lor X_4\bigr)\land \bigl(\lnot X_1\lor X_2\lor\lnot X_3\lor X_4\bigr)\land \bigl(X_1\lor\lnot X_2\lor\lnot X_3\lor X_4\bigr).$

Вот несколько примеров совершенных дизъюнктивных нормальных форм:

$\begin{gathered}(X\land Y)\lor (\lnot X\land Y)\lor (X\land\lnot Y)\\[2pt] (X\land Y\land\lnot Z)\lor (\lnot X\land Y\land\lnot Z)\lor (X\land\lnot Y\lor Z)\lor (X\land\lnot Y\land\lnot Z)\lor (X\land Y\land Z),\\[2pt] (X_1\land X_2\land X_3\land X_4)\lor (\lnot X_1\land\lnot X_2\land X_3\land X_4)\lor (X_1\land X_2\land\lnot X_3\land X_4).\end{gathered}$

Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами.

Введем обозначение, которое будет удобно в дальнейшем:

$X^{\alpha}= \begin{cases}X,& \text{if}\quad \alpha=1,\\ \lnot X,& \text{if}\quad \alpha=0.\end{cases}$

Легко проверить, что $0^0=1,~ 0^1=0,~ 1^0=0,~ 1^1=1$ , т.е. $X^{\alpha}=1$ тогда и только тогда, когда $X=\alpha$ , и $X^{\alpha}=0$ тогда и только тогда, когда $X\ne\alpha$ (см. пояснения о значении формулы перед теоремой 2.2).

Введем еще одно обозначение. Вместо дизъюнкции $X_1\lor X_2\lor \ldots\lor X_n$ будем писать $\bigvee\limits_{i=1}^{n}X_i$ . В частности, запись $\bigvee_{\alpha_1,\alpha_2,\ldots,\alpha_n} H(X_1,\ldots,X_n,\alpha_1,\ldots,\alpha_n)$ обозначает дизъюнкцию всевозможных выражений (формул) $H(X_1,\ldots,X_n, \alpha_1,\ldots,\alpha_n)$ , зависящих от переменных ${ X_1,\ldots,X_n}$ , когда индексы суммирования (дизъюнктирования) ось $\alpha_1,\ldots,\alpha_n$ пробегают всевозможные упорядоченные наборы длины $n$ , составленные из нулей и единиц. Например,

$\begin{aligned} \bigvee\limits_{(\alpha,\beta)} \bigl(X^{\alpha}\land X^{\beta}\bigr)&= \bigl(X^0\land Y^0\bigr)\lor \bigl(X^0\land Y^1\bigr)\lor \bigl(X^1\land Y^0\bigr)\lor \bigl(X^1\land Y^1\bigr)=\\ &=(\lnot X\land\lnot Y)\lor (\lnot X\land Y)\lor (X\land\lnot Y)\lor (X\land Y).\end{aligned}$

Лемма 5.2. Для всякой формулы алгебры высказываний $F(X_1,X_2,\ldots,X_n)$ справедливо разложение

$F(X_1,X_2,\ldots,X_n)\cong \bigvee\limits_{(\alpha_1,\alpha_2,\ldots,\alpha_n)} \Bigl(F(\alpha_1,\alpha_2,\ldots,\alpha_n)\lor X_1^{\alpha_1}\lor X_2^{\alpha_2}\lor \ldots\lor X_n^{\alpha_n}\Bigr).$

Доказательство. Возьмем произвольный набор из нулей и единиц $\xi_1,\xi_2,\ldots,\xi_n$ (каждое $\xi_i$ , где $1 \leqslant i \leqslant n$ , есть либо 0, либо 1) и вычислим значения формул, стоящих в правой и левой частях доказываемой равносильности, при $X_1=\xi_1,X_2=\xi_2,\ldots,X_n=\xi_n$ .

С одной стороны, в правой части доказываемого равенства получим

$\bigvee\limits_{(\alpha_1,\alpha_2,\ldots,\alpha_n)} \Bigl(F(\alpha_1,\alpha_2,\ldots,\alpha_n)\lor \xi_1^{\alpha_1}\lor \xi_2^{\alpha_2}\lor \ldots\lor \xi_n^{\alpha_n}\Bigr).$

что представляет собой дизъюнкцию нескольких конъюнктивных одночленов. Каждый конъюнктивный одночлен характеризуется индексным набором нулей и единиц $\alpha_1,\alpha_2,\ldots,\alpha_n$ . Если для данного конъюнктивного одночлена набор $\alpha_1,\alpha_2,\ldots,\alpha_n$ нулей и единиц таков, что $\alpha_1\ne\xi_1$ или $\alpha_2\ne\xi_2,\ldots$ , или $\alpha_n\ne\xi_n$ , то согласно определению формулы $X^{\alpha}$ , введенному в начале пункта, будем иметь или $\xi_1^{\alpha_1}=0$ , или $\xi_2^{\alpha_2}=0,\ldots$ или $\xi_n^{\alpha_n}=0$ . Но тогда и весь данный конъюнктивный одночлен будет равен нулю и потому на результат дизъюнкции влияния не окажет, а значит, из числа дизъюнктивных "слагаемых" может быть безболезненно исключен. Только один конъюнктивный одночлен окажется не равным нулю — тот, что характеризуется таким набором $(\alpha_1,\alpha_2,\ldots,\alpha_n)$ , который равен взятому в начале набору $(\xi_1,\xi_2,\ldots,\xi_n)$ , т.е. для которого $\alpha_1=\xi_1, \alpha_2=\xi_2, \ldots, \alpha=\xi_n$ . Только для этого конъюнктивного одночлена будем иметь

$\begin{aligned}F(\alpha_1,\alpha_2,\ldots,\alpha_n)\land \xi_1^{\alpha_1}\lor \xi_2^{\alpha_2}\lor \ldots\lor \xi_n^{\alpha_n}&= F(\xi_1,\xi_2,\ldots,\xi_n)\lor \xi_1^{\xi_1}, \xi_2^{\xi_2}, \ldots,\xi_n^{\xi_n}=\\ &=F(\xi_1,\xi_2,\ldots,\xi_n)\lor1\lor1\lor \ldots\lor1=\\ &=F(\xi_1,\xi_2,\ldots,\xi_n).\end{aligned}$

Таким образом, конъюнктивный одночлен, соответствующий индексному набору $(\xi_1,\xi_2,\ldots,\xi_n)$ , равен $F(\xi_1,\xi_2,\ldots,\xi_n)$ . Этому же значению равна и вся дизъюнкция, потому что, как показано выше, все остальные конъюнктивные одночлены равны нулю.

С другой стороны, формула, стоящая в левой части доказываемого равенства, обратится при $X_1=\xi_1,X_2=\xi_2,\ldots,X_n=\xi_n$ в то же самое значение $F(\xi_1,\xi_2,\ldots,\xi_n)$ . Набор нулей и единиц $\xi_1,\xi_2,\ldots,\xi_n$ был выбран произвольно. Следовательно, формулы в левой и правой частях равносильности действительно равносильны. Лемма доказана.

Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами.

Понятия и теоремы этого пункта носят двойственный характер по отношению к соответствующим понятиям и теоремам предыдущего пункта. Вводится следующее обозначение:

${}^{\beta}X= \begin{cases}\lnot X,& \text{if}\quad \beta=1,\\ X,& \text{if}\quad \beta=0.\end{cases}$

Легко проверяется, что ${}^{0}0=0,~{}^{1}0=1,~{}^{0}1=1,~ {}^{1}1=0$ , т.е. ${}^{\beta}X=1$ тогда и только тогда, когда $X\ne\beta$ ; и ${}^{\beta}X=0$ тогда и только тогда, когда $X=\beta$ .

Вместо конъюнкции $X_1 \land X_2\land \ldots\land X_n$ будем писать $\textstyle{\bigwedge\limits_{i=1}^{n} X_i}$ . В частности, запись $\textstyle{\bigwedge\limits_{(\beta_1,\ldots,\beta_n)} H(X_1, \ldots,X_n,\beta_1,\ldots,\beta_n)}$ обозначает дизъюнкцию всевозможных выражений (формул) $H(X_1, \ldots,X_n,\beta_1,\ldots,\beta_n)$ , зависящих от переменных $X_1, \ldots,X_n$ , когда индексы произведения (конъюнктирования) $\beta_1,\ldots, \beta_n$ пробегают всевозможные упорядоченные наборы длины $n$ , составленные из нулей и единиц. Например,

$\begin{aligned} \bigwedge\limits_{(\alpha,\beta)} \bigl({}^{\alpha}X\lor {}^{\beta}X\bigr)&= ({}^{0}X\lor {}^{0}Y)\land ({}^{0}X\lor {}^{1}Y)\land ({}^{1}X\lor {}^{0}Y)\land ({}^{1}X\lor {}^{1}Y)=\\[-10pt] &=(X\lor Y)\land (X\lor\lnot Y)\land (\lnot X\lor Y)\land (\lnot X\lor\lnot Y).\end{aligned}$

Лемма 5.4. Для всякой формулы $F(X_1,X_2, \ldots,X_n)$ алгебры высказываний справедливо разложение

$F(X_1,X_2,\ldots,X_n)\cong \bigwedge\limits_{(\beta_1,\ldots, \beta_n)} \Bigl(F(\beta_1,\beta_2,\ldots, \beta_n)\lor {}^{\beta_1}X_1,{}^{\beta_2}X_2,\ldots, {}^{\beta_n}X_n \Bigr).$

Теорема 5.5 (о представлении формул алгебры высказываний совершенными конъюнктивными нормальными формами). Каждая формула алгебры высказываний от п переменных, не являющаяся тавтологией, имеет единственную (с точностью до перестановки конъюнктивных членов) совершенную конъюнктивную нормальную форму.