Досконала диз'юнктивна нормальна форма

Доскона́лою диз'юнкти́вною норма́льною фо́рмою (ДДНФ) булевої функції називається диз'юнкція тих конституент одиниці, які перетворюються в одиницю на тих самих наборах змінних, що й задана функція. ДДНФ повинна задовольняти наступним умовам:

в ній немає однакових доданків;
жоден із доданків не містить двох однакових співмножників;
жоден із доданків не містить змінну разом із її запереченням;
в кожному окремому доданку є як співмножник або змінна x_i, або її заперечення для будь-якого i = 1, 2, …, n.

Для будь-якої функції булевої алгебри існує своя ДДНФ, причому тільки одна.

Приклад знаходження ДДНФ

Для того, щоб отримати ДДНФ функції, потрібно скласти її таблицю істинності. Наприклад, візьмемо одну з таблиць істинності з статті Метод Куайна, в якій знаходження ДДНФ зустрічається декілька разів:

$\mathbf {x_{1}}$	$\mathbf {x_{2}}$	$\mathbf {x_{3}}$	$\mathbf {x_{4}}$	$\mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

В комірках результату $\mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})$ відмічаються лишень ті комбінації, які приводять логічний вираз до одиниці.
Далі розглядається значення змінних при яких функція дорівнює 1. Якщо значення змінної дорівнює 0, то вона записується з інверсією. Якщо значення змінної дорівнює 1, то вона записується без інверсії. Перший стовпець містить 1 в заданому полі. Відмічаються значення всіх чотирьох змінних це:

$\mathbf {x_{1}}$ = 0
$\mathbf {x_{2}}$ = 0
$\mathbf {x_{3}}$ = 0
$\mathbf {x_{4}}$ = 0

Нульові значення — тут всі змінні представлені нулями — записуються в кінцевому виразі інверсією цієї змінної. Перший член ДДНФ даної функції має такий вигляд: ${\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {\overline {x_{4}}}$
Змінні другого члена:

$\mathbf {x_{1}}$ = 0
$\mathbf {x_{2}}$ = 0
$\mathbf {x_{3}}$ = 0
$\mathbf {x_{4}}$ = 1

$\mathbf {x_{4}}$ в цьому випадку буде представлений без інверсії: ${\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {x_{4}}$

Таким чином аналізуються всі комірки $\mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})$ . ДДНФ цієї функції буде диз'юнкцією всіх отриманих членів (елементарних кон'юнкцій).

Досконала ДНФ цієї функції:

$\mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})=({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {\overline {x_{4}}})$ $\vee$ $({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {x_{4}})$ $\vee$ $({\overline {x_{1}}}\land {\overline {x_{2}}}\land {x_{3}}\land {\overline {x_{4}}})$ $\vee$ $({\overline {x_{1}}}\land {x_{2}}\land {x_{3}}\land {\overline {x_{4}}})$ $\vee$ $({x_{1}}\land {x_{2}}\land {x_{3}}\land {\overline {x_{4}}})$ $\vee$ $({x_{1}}\land {x_{2}}\land {x_{3}}\land {x_{4}})$

Див. також

Примітки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.