Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


Для каждой формулы алгебры высказываний можно указать равносильную ей формулу, содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Для этого нужно, используя равносильности теоремы 4.4, пункты у), ч), выразить все имеющиеся в формуле импликации и эквивалентности через отрицание, конъюнкцию и дизъюнкцию. Так, для формулы [math]\bigl(\lnot X\land(X\to)\bigr)[/math] равносильной ей формулой, не содержащей логических связок [math]\to[/math] и [math]\leftrightarrow[/math], будет, например, формула [math]\lnot\bigl(\lnot X\land (\lnot X\lor Y)\bigr)\lor Y[/math]. Выразить данную формулу через отрицание, конъюнкцию и дизъюнкцию возможно не одним способом, а многими. К примеру, рассматриваемая формула равносильна также следующим формулам, содержащим из логических связок лишь [math]\lnot,\,\land[/math] и [math]\lor:[/math]


[math]\begin{gathered}\lnot\lnot X\lor Y,\quad X\lor Y,\quad (X\lor Y)\land (\lnot Y\lor Y),\quad (X\land\lnot Y)\lor Y,\\[2pt] (X\land\lnot Y)\lor \bigl((X\lor\lnot X)\land Y\bigr),\quad (X\land\lnot Y)\lor (X\land Y)\lor (\lnot X\land Y).\end{gathered}[/math]

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




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


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


[math]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.[/math]

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


[math]\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.[/math]

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


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


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


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


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


[math](X\land Y)\lor (P\land Q\land R),\qquad (P\lor Q)\land (X\lor Y\lor Z)[/math]

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



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


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


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


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


[math]\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).[/math]

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


[math]\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}[/math]



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


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


[math]X^{\alpha}= \begin{cases}X,& \text{if}\quad \alpha=1,\\ \lnot X,& \text{if}\quad \alpha=0.\end{cases}[/math]

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


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


[math]\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}[/math]

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


[math]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).[/math]

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


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


[math]\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).[/math]

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


[math]\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}[/math]

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


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




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


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


Доказательство. Существование. Всякая формула [math]F(X_1,X_2,\ldots,X_n)[/math] обладает указанным в предыдущей лемме разложением. Поскольку формула [math]F(X_1,X_2,\ldots,X_n)[/math] не тождественно ложна, то существуют такие наборы [math](\alpha_1,\alpha_2,\ldots,\alpha_n)[/math] нулей и единиц, что [math]F(\alpha_1, \alpha_2, \ldots, \alpha_n)=1[/math]. Наборы [math](\alpha_1, \alpha_2,\ldots, \alpha_n)[/math], обращающие формулу [math]F[/math] в нуль, будут обращать в нуль также и конъюнктивные одночлены, входящие в дизъюнкцию и соответствующие данным индексным наборам. Поэтому все такие одночлены исключим из дизъюнкции. Итак, в дизъюнкции остаются конъюнктивные одночлены, соответствующие лишь индексным наборам [math](\alpha_1, \alpha_2, \ldots, \alpha_n)[/math] нулей и единиц, для которых [math]F(\alpha_1, \alpha_2, \ldots, \alpha_n)=1[/math]. Тогда разложение для формулы [math]F[/math] принимает следующий вид:


[math]\begin{aligned}F(X_1,X_2,\ldots,X_n)&\cong \bigvee\limits_{\substack{(\alpha_1, \ldots, \alpha_n)\\ F(\alpha_1, \ldots, \alpha_n)=1}} \Bigl(F(\alpha_1, \alpha_2, \ldots, \alpha_n)\land X_1^{\alpha_1}\land X_2^{\alpha_2}\land \ldots\land X_n^{\alpha_n}\Bigr)\cong\\ &\cong \bigvee\limits_{F(\alpha_1, \ldots, \alpha_n)=1} \Bigl(X_1^{\alpha_1}\land X_2^{\alpha_2}\land \ldots\land X_n^{\alpha_n}\Bigr)= \bigvee\limits_{F(\alpha_1, \ldots, \alpha_n)=1} \bigwedge\limits_{i=1}^{n}X_{i}^{\alpha_i}.\end{aligned}[/math]

где дизъюнкция ("суммирование") ведется по всем индексным наборам [math](\alpha_1, \alpha_2, \ldots, \alpha_n)[/math] нулей и единиц, для которых [math]F(\alpha_1, \alpha_2, \ldots, \alpha_n)=1[/math]. Выражение, стоящее в правой части полученной равносильности, есть не что иное, как совершенная дизъюнктивная нормальная форма от переменных [math]X_1,X_2, \ldots,X_n[/math], потому что каждый конъюнктивный одночлен [math]X_1^{\alpha_1}\land X_2^{\alpha_2}\land \ldots\land X_n^{\alpha_n}[/math], входящий в дизъюнкцию, совершенен (каждая переменная [math]X_1,X_2, \ldots,X_n[/math] входит в него точно один раз: либо сама, либо со знаком отрицания в зависимости от значения ее показателя степени).


Единственность. Предположим, что некоторая формула [math]F(X_1,X_2, \ldots,X_n)[/math] имеет два представления совершенными дизъюнктивными нормальными формами:


[math]\begin{aligned}F(X_1,X_2, \ldots,X_n)&\cong K_1\lor K_2\lor \ldots\lor K_q\,;\\[2pt] F(X_1,X_2, \ldots,X_n)&\cong K_1^{\ast}\lor K_2^{\ast}\lor \ldots\lor K_r^{\ast}\,. \end{aligned}[/math]

где [math]K_i,~1 \leqslant i \leqslant q[/math], и [math]K_j,~1 \leqslant j \leqslant r[/math], есть совершенные конъюнктивные одночлены от переменных [math]X_1,X_2, \ldots,X_n[/math]. Причем, не нарушая общности, считаем, что ни один из одночленов [math]K_1,K_2, \ldots,K_n[/math] не повторяется в этом наборе, потому что повторяющиеся одночлены можно исключить ввиду идемпотентности дизъюнкции (теорема 4.4, пункт ж)). Аналогична ситуация в форме [math]K_1^{\ast}\lor K_2^{\ast}\lor \ldots\lor K_r^{\ast}[/math]. Тогда имеет место равносильность


[math]K_1\lor K_2\lor \ldots\lor K_q\cong K_1^{\ast}\lor K_2^{\ast}\lor \ldots\lor K_r^{\ast}\,.[/math]

Пусть, например, совершенный конъюнктивный одночлен [math]K_1[/math] имеет вид [math]K_1\cong (X_1^{\alpha_1}\land X_2^{\alpha_2}\land \ldots\land X_n^{\alpha_n})[/math]. Придадим переменным [math]X_1,X_2, \ldots,X_n[/math] значения [math]\alpha_1, \alpha_2, \ldots, \alpha_n[/math] соответственно. Тогда совершенный конъюнктивный одночлен [math]K_1[/math] примет значение 1, и, следовательно, вся совершенная дизъюнктивная нормальная форма, стоящая в левой части равносильности, станет равна единице. Тогда и правая часть данной равносильности обратится в единицу, и для набора [math]alpha_1, \alpha_2, \ldots, \alpha_n[/math] значений переменных одна из совершенных элементарных конъюнкций [math]K^{\ast}[/math], например [math]K_{j}^{\ast}[/math], также станет равной единице. Если [math]K_{j}^{\ast}[/math] имеет вид [math]K_{j}^{\ast}\cong (X_1^{\beta_1}\land X_2^{\beta_2}\land \ldots\land X_n^{\beta_n})[/math], то доказанное означает, что [math]\alpha_1^{\beta_1}\land \alpha_2^{\beta_2}\land \ldots\land \alpha_n^{\beta_n}=1[/math]. Последнее равенство возможно в том и только в том случае, когда [math]\alpha_1^{\beta_1}=1, \alpha_2^{\beta_n}=2, \ldots, \alpha_n^{\beta_n}=1[/math], что может быть лишь тогда и только тогда, когда [math]\beta_1=\alpha_1, \beta_2=\alpha_2, \ldots, \beta_n=\alpha_n[/math]. Следовательно, [math]K_{j}^{\ast}\cong (X_1^{\beta_1}\land X_2^{\beta_2}\land \ldots\land X_n^{\beta_n})[/math], т.е. [math]K_{j}^{\ast}=K_1[/math]. Таким образом, совершенная элементарная конъюнкция [math]K_1[/math] встречается среди совершенных элементарных конъюнкций [math]K_1^{\ast},K_2^{\ast},\ldots,K_r^{\ast}[/math]. Тем же самым способом устанавливается, что любая из совершенных элементарных конъюнкций [math]K_1, K_2,\ ldots, K_q[/math] встречается среди [math]K_1^{\ast}, K_2^{\ast}, \ldots, K_r^{\ast}[/math], и обратно, любая из совершенных элементарных конъюнкций [math]K_1^{\ast}, K_2^{\ast}, \ldots, K_r^{\ast}[/math] встречается среди [math]K_1^{\ast},K_2^{\ast},\ldots,K_r^{\ast}[/math]. Ввиду того что одночлены в данных наборах не повторяются, то [math]q=r[/math] и обе части равносильности


[math]K_1\lor K_2\lor \ldots\lor K_q\cong K_1^{\ast}\lor K_2^{\ast}\lor \ldots\lor K_r^{\ast}\,.[/math]

отличаются самое большее порядком членов дизъюнкции.

Доказанная теорема — одна из важнейших в алгебре высказываний. Если вы до конца разобрали обе части доказательства (существование и единственность), то значит вы начали понимать категории и методы математической логики как математической науки. Доказательство существования состоит из двух частей: леммы и собственно теоремы. Доказательство единственности полностью содержится в теореме и не опирается на лемму.




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


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


[math]{}^{\beta}X= \begin{cases}\lnot X,& \text{if}\quad \beta=1,\\ X,& \text{if}\quad \beta=0.\end{cases}[/math]

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


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


[math]\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}[/math]

Аналогично доказательству леммы 5.2 доказывается лемма 5.4.


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


[math]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).[/math]

Подобно теореме 5.3 выводится теорема 5.5.


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


Доказательство этой теоремы можно восстановить, руководствуясь доказательством теоремы 5.3.




Два способа приведения формулы алгебры высказываний к совершенной нормальной форме


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


Если формула задана таблицей своих значений, то из доказательств теорем 5.3 и 5.5 о представлении формул совершенными нормальными формами необходимо вынести формулу (в некоем обычном понимании смысла этого термина) разложения формулы алгебры высказываний в совершенную нормальную форму. Для случая СДН-формы эта формула имеет следующий вид:


[math]F(X_1,\ldots,X_n)\cong \bigvee\limits_{F(\alpha_1,\ldots,\alpha_n)=1} \Bigl(X_{1}^{\alpha_1}\land \ldots\land X_{n}^{\alpha_n}\Bigr)[/math], где [math]X^{\alpha}= \begin{cases}X,& \text{if}\quad \alpha=1,\\ \lnot X,& \text{if}\quad \alpha=0.\end{cases}[/math]

По сути, эта формула описывает правило (алгоритм) отыскания совершенной дизъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 1; для каждого такого набора выписать совершенный конъюнктивный одночлен, принимающий значение 1 на этом наборе и только на нем; полученные совершенные конъюнктивные одночлены соединить знаками дизъюнкции. Для случая СКН-формы эта формула имеет вид


[math]F(X_1,\ldots,X_n)\cong \bigwedge\limits_{F(\beta_1,\ldots,\beta_n)=0} \Bigl({}^{\beta_1}X_1,\ldots,{}^{\beta_n}X_n\Bigr)[/math], где [math]{}^{\beta}X= \begin{cases}X,& \text{if}\quad \beta=0,\\ \lnot X,& \text{if}\quad \beta=1.\end{cases}[/math]

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



Пример 5.6. Пусть, например, формула [math]F(X,Y,Z)[/math] задана следующей таблицей своих значений:


[math]\begin{array}{|c|c|c||c|}\hline X& Y& Z& F(X,Y,Z)\\\hline 0&0&0&1\\ 0&0&1&0\\ 0&1&0&1\\ 0&1&1&1\\ 1&0&0&1\\ 1&0&1&0\\ 1&1&0&0\\ 1&1&1&1\\\hline \end{array}[/math]

Таким образом, она принимает значения 1 на следующих наборах значений своих переменных (или при следующих конкрети-зациях):


[math](0, 0, 0),\quad (0, 1, 0),\quad (0, 1, 1),\quad (1, 0, 0),\quad (1, 1, 1).[/math]

Запишем предыдущую формулу разложения в СДН-форму для случая [math]n=3[/math] и применим ее в нашей ситуации:


[math]\begin{aligned}F(X,Y,Z)&\cong \bigvee\limits_{F(\alpha,\beta,\gamma)=1} \bigl(X^{\alpha}\land Y^{\beta}\land Z^{\gamma}\bigr)\cong\\ &\cong \bigl(X^0\land Y^0\land Z^0\bigr)\lor \bigl(X^0\land Y^1\land Z^0\bigr)\lor \bigl(X^0\land Y^1\land Z^1\bigr)\lor \bigl(X^1\land Y^0\land Z^0\bigr)\lor \bigl(X^1\land Y^1\land Z^1\bigr)\cong\\ &\cong (\lnot X\land\lnot Y\land\lnot Z)\lor (\lnot X\land Y\land\lnot Z)\lor (\lnot X\land Y\land Z)\lor (X\land\lnot Y\land\lnot Z)\lor (X\land Y\land Z).\end{aligned}[/math]
(5.1)



Пример 5.7. Для формулы [math]F(X,Y,Z)[/math] из предыдущего примера найдем ее СКН-форму. Для этого сначала отметим все те наборы значений переменных, на которых она принимает значение 0: [math](0;0;1),[/math] [math](1;0;1),[/math] [math](1;1;0)[/math]. Теперь запишем формулу разложения в СКН-форму для случая [math]n=3[/math] и применим ее в нашей ситуации:


[math]\begin{aligned}F(X,Y,Z)&\cong \bigwedge\limits_{F(\alpha,\beta,\gamma)=0} \bigl({}^{\alpha}X\lor {}^{\beta}Y\lor {}^{\gamma}Z\bigr)\cong\\ &\cong \bigl({}^{0}X\lor {}^{0}Y\lor {}^{1}Z\bigr)\land \bigl({}^{1}X\lor {}^{0}Y\lor {}^{1}Z \bigr)\land \bigl({}^{1}X\lor {}^{1}Y\lor {}^{0}Z \bigr)\cong\\ &\cong (X\lor Y\lor\lnot Z)\land (\lnot X\lor Y\lor\lnot Z)\land (\lnot X\lor\lnot Y\lnot Z).\end{aligned}[/math]
(5.2)

Еще раз обращаем внимание на то, что для каждой формулы алгебры высказываний СДН-форма единственна и СКН-форма единственна (если они существуют). СДН-форма (5.1) отмечает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение 1, а СКН-форма (5.2) отмечает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение 0. Тем не менее необходимо отчетливо осознавать, что две полученные формулы (5.1) и (5.2) равносильны. Так, формула (5.1) принимает значение 0 на тех и только тех наборах значений переменных, на которых принимает значение 0 и формула (5.2). Аналогично формула (5.2) принимает значение 1 на тех и только тех наборах значений переменных, на которых принимает значение 1 формула (5.1).


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


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved