Досконала диз’юнктивна нормальна форма. (ДДНФ)

 

Конституентою одиниці основних висловлень називається повний елементарний добуток, який містить усі букви

Конституента одиниці відносно є добутком n множників, кожен з яких дорівнює або (тобто кожне з основних висловлень входить в цей добуток).

Всі множники конституенти одиниці позначаються різними буквами.

Для двох висловлень і можна утворити чотири конституенти одиниці: , , , .

Для трьох висловлень отримуємо вісім конституент одиниці:

 

;

= ;

;

;

 

;

;

;

Кожна конституента одиниці істинна на одному і тільки одному наборі. Між конституентами одиниці для і n -місними наборами існує взаємно-однозначна відповідність:

- кожній конституенті одиниці відповідає єдиний набір на якому вона істинна;

- кожен набір відповідає єдиній конституенті одиниці.

Наприклад:

1)

 

 

=1 на наборі 001, на всіх інших наборах вона хибна

2) -істинна на наборі 100

Висновки:

1) число конституент одиниці відносно дорівнює числу -місних наборів: 2ⁿ

для : 2² = 4 конституенти

для : 2³ = 8 конституент

2) якщо на якомусь наборі істинна, то на цьому наборі всі інші конституенти хибні. =1 на наборі 001 на цьому наборі.

Конституенти одиниці для двох змінних: n=2.

 

Набори	Конституенти одиниці
N0 N1 N2 N3

 

Конституенти одиниці для трьох змінних: n=3.

 

Набори	Конституента одиниці
N0   N1   N2   N3   N4   N5   N6   N7

 

 

Диз`юнктивна нормальна форма називається досконалою, якщо всі її доданки є конституентами одиниці.

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

Щоб отримати ДДНФ треба:

- якщо в „неповний ” елементарний добуток не входить , то домножимо його на =1

- розкривають дужки за першим дистрибутивним законом , у цьому разі дістають диз`юнкцію елементарних добутків з усіма попередніми буквами і ще однією . (Якщо знову не всі букви охоплені, то знову помножають на і знову розкривають дужки)

- після цього повторні доданки видаляють.

Приклад:

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

 

Область хибності знаходять виключивши з усіх можливих наборів область істинності.

=...=

Область істинності: 010;111;110;000;101.

Область хибності: 011;100;001.

 

 

Скорочена ДНФ.

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

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

Наприклад: ДНФ(F)=

Містить 6 літер (а змінних 3) внаслідок того, що А - входить до функції двічі, В -тричі.

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

Імпліканта.

Застосування терміну імпліканта пов’язане з логічною функцією F= , яку ще ще називають імплікацією.

Вираз дорівнює одиниці лише тоді, коли , тобто на наборах де значення відповідно мають вигляд 0-0; 0-1; 1-1.

 

Якщо деяка логічна функція на тих наборах на яких інша функція F=0, то називається імплікантою F. При цьому може дорівнювати 0 і на тих наборах на яких F=1. (але не навпаки).

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

- константа нуля є імплікантою будь-якої логічної функції.

Доведення: Дійсно константа нуля („ F=0 ”) за означенням дорівнює 0 на всіх її можливих наборах і тому обов’язково дорівнює 0 на всіх тих наборах, на яких функція F дорівнює нулю.

- будь-яка логічна функція є імплікантою самої себе.

- будь-яка логічна функція є імплікантою константи одиниці.

Скорочена ДНФ.

Елементарний добуток, одержаний шляхом виключення з початкового добутку

однієї або кількох змінних, називається власною частиною добутку.

Приклад: Власними частинами цього добутку будуть:

Елементарні добутки, які входять до даної функції в ДДНФ, але ніяка їх власна час­тина самостійно, як добуток не входить, називаються простими імплікантами.

Приклад: Нехай добутки , а змінні і самостійно не входять як добутки. Тоді добуток буде простою імплікантою функції F, бо , а . Але добуток не буде простою імплікантою, бо її власна частина .

Прикладом такої функції буде