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

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

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

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

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


Дизъюнктивные и конъюнктивные нормальные формы

Дизъюнктивные и конъюнктивные нормальные формы


Любая формула вида [math]x[/math] или [math]\overline{x}[/math] над стандартным базисом, где [math]x[/math] — произвольное переменное, называется литералом. Таким образом, литерал есть обозначение либо самого переменного [math]x[/math], либо его отрицания. Часто используют такое обозначение: для [math]\sigma\in\{0;1\}[/math] пишут [math]x^{\sigma}[/math], понимая под этим само переменное [math]x[/math], если [math]\sigma=1[/math], и отрицание [math]x[/math], если [math]\sigma=0[/math], то есть


[math]x^{\sigma}= \begin{cases}x,& \text{if}\quad \sigma=1;\\ \overline{x},& \text{if}\quad \sigma=0.\end{cases}[/math]
(6.8)

Подставляя в (6.8) 0 и 1 вместо [math]x[/math], получаем


[math]0^{\sigma}= \begin{cases}0,& \text{if}\quad \sigma=1;\\ 1,& \text{if}\quad \sigma=0;\end{cases}\qquad 1^{\sigma}= \begin{cases}1,& \text{if}\quad \sigma=1;\\ 0,& \text{if}\quad \sigma=0.\end{cases}[/math]

Часто используют также обозначение [math]\widetilde{x}[/math], понимая под этим любой из двух литералов — [math]x[/math] или [math]\overline{x}[/math].


Формула вида [math]\widetilde{x}_1\widetilde{x}_2\ldots\widetilde{x}_m[/math] (соответственно вида [math]\widetilde{x}_1\lor \widetilde{x}_2\lor \ldots\lor \widetilde{x}_m[/math]), где все фигурирующие в ней переменные попарно различны, называется элементарной конъюнкцией (соответственно элементарной дизъюнкцией).


Определение 6.4. Дизъюнктивная нормальная форма (ДНФ) от переменных [math]x_1,\ldots,x_n[/math] — это формула вида [math]K_1\lor\ldots\lor K_m[/math], где [math]K_i,~i=\overline{1,m}[/math], — элементарная конъюнкция, содержащая некоторые из литералов [math]x_1,\ldots,x_n[/math]. В том случае, когда в каждую конъюнкцию [math]K_i[/math] для каждого номера [math]j=\overline{1,n}[/math] входит в точности один из литералов [math]\widetilde{x}_j[/math], ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).


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




Теорема 6.2. Любая булева функция, отличная от константы 0 (соответственно от константы 1) представима в виде СДНФ (соответственно в виде СКНФ).


Докажем первое из двух (взаимно двойственных) утверждений теоремы. Для функции [math]f\in \mathcal{P}_{2,n}[/math], не равной тождественно 0, рассмотрим множество [math]C_f^1= \{\widetilde{\alpha}\colon\, f(\widetilde{\alpha})=1\}[/math]. Каждый набор из [math]C_f^1[/math] называется конституентой единицы функции [math]f[/math]. Так как по условию [math]f\ne0[/math] тождественно, то множество [math]C_f^1[/math] не пусто. Каждому набору [math]\widetilde{\alpha}\in C_f^1[/math] поставим в соответствие элементарную конъюнкцию [math]K_{\widetilde{\alpha}}= x_{1}^{\alpha_1} x_{2}^{\alpha_2}\ldots x_{n}^{\alpha_n}[/math], которую также называют конституентой единицы функции [math]f[/math]. Ясно, что [math]K_{\widetilde{\alpha}}[/math] обращается в единицу только на наборе [math]\widetilde{\alpha}[/math]. Тогда искомой СДНФ для функции [math]f[/math] будет


[math]f=\bigvee\limits_{\widetilde{\alpha}\in C_f^1}K_{\widetilde{\alpha}}\,.[/math]

Согласно принципу двойственности, СКНФ для той же функции будет иметь вид


[math]f=\bigwedge\limits_{\widetilde{\alpha}\in C_f^0}D_{\widetilde{\alpha}}\,,[/math]

где множество наборов [math]C_f^0= \{\widetilde{\alpha}\colon\, f(\widetilde{\alpha})=0\}[/math], и каждый набор [math]\widetilde{\alpha}[/math] из [math]C_f^0[/math] называют конституентой нуля функции [math]f[/math]; при этом элементарная дизъюнкция [math]D_{\widetilde{\alpha}}[/math] сопоставляется конституенте нуля [math]\widetilde{\alpha}[/math] по следующему правилу:


[math]D_{\widetilde{\alpha}}= x_{1}^{\overline{\alpha}_1}\lor x_{2}^{\overline{\alpha}_2}\lor \ldots\lor x_{n}^{\overline{\alpha}_n}\,,[/math]

т.е. если в наборе i-я компонента равна 0, то в [math]D_{\widetilde{\alpha}}[/math] ставим само переменное [math]x_i[/math], если иначе — отрицание переменного [math]x_i[/math] (таким образом, дизъюнкция [math]D_{\widetilde{\alpha}}[/math] обращается в нуль только на наборе [math]\widetilde{\alpha}[/math]).




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


Рассмотрим в качестве примера построение СДНФ и СКНФ для мажоритарной функции. Конституентами единицы для нее служат наборы:


[math]\widetilde{\alpha}_1= (0,1,1),\quad \widetilde{\alpha}_2= (1,0,1),\quad \widetilde{\alpha}_3= (1,1,0),\quad \widetilde{\alpha}_4= (1,1,1).[/math]

Им соответствуют элементарные конъюнкции:


[math]K_{\widetilde{\alpha}_1}= \overline{x}_1x_2x_3,\quad K_{\widetilde{\alpha}_2}= x_1 \overline{x}_2x_3,\quad K_{\widetilde{\alpha}_3}= x_1x_2 \overline{x}_3,\quad K_{\widetilde{\alpha}_4}= x_1x_2x_3\,.[/math]

Тогда СДНФ, представляющая мажоритарную функцию, имеет вид


[math]\overline{x}_1x_2x_3\lor x_1 \overline{x}_2x_3\lor x_1x_2 \overline{x}_3\lor x_1x_2x_3\,.[/math]
(6.9)

Для получения СКНФ для той же функции выпишем все конституенты нуля данной функции:


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

Сопоставим им элементарные дизъюнкции:


[math]x_1\lor x_2\lor x_3,\quad x_1\lor x_2\lor \overline{x}_3,\quad x_1\lor \overline{x}_2\lor x_3,\quad \overline{x}_1\lor x_2\lor x_3[/math]

В результате получим СКНФ для мажоритарной функции в виде


[math](x_1\lor x_2\lor x_3)\cdot (x_1\lor x_2\lor \overline{x}_3)\cdot (x_1\lor \overline{x}_2\lor x_3)\quad (\overline{x}_1\lor x_2\lor x_3).[/math]
(6.10)

Заметим, что если в формуле СКНФ (6.10) мы раскроем скобки и преобразуем полученное выражение согласно законам булевой алгебры, проведя тем самым эквивалентные преобразования СКНФ, то придем к формуле СДНФ (6.9).


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


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

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