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

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

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

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


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

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


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


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

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


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}

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


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


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


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




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


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


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

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


f=\bigwedge\limits_{\widetilde{\alpha}\in C_f^0}D_{\widetilde{\alpha}}\,,

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


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

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




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


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


\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).

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


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\,.

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


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

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


(0,0,0),\quad (0,0,1),\quad (0,1,0),\quad (1,0,0).

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


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

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


(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).
(6.10)

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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