Наведемо приклад знаходження досконалої кон’юнктивної нормальної форми (ДКНФ) для формули .

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

Етап 1. Для формули складається таблиця істинності.

Етап 2. У таблиці істинності виділяються ті набори , для яких значення формули не є істинним (тобто є хибним, дорівнює 0).

Етап 3. Для кожного виділеного набору складається елементарна диз'юнкція виду .

Етап 4. Формується кон’юнкція елементарних диз'юнкцій.

 

 

 

У підсумку, буде отримано наступний результат:

 

.

 

Також можна отримати розв'язок завдання прикладу аналітичним методом.

ДКНФ називають ДКНФ булевої функції f=f(x1…xn), якщо:

– ДКНФ тотожно дорівнює данiй булевiй функції (приймає ті самі значення на тих самих наборах значень змінних);

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

 

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

Разом iз тим, важливу роль вiдiграє наступна властивість щодо існування й єдиності ДКНФ заданої булевої функції: для будь-якої булевої функцiї f(x1,…,xn), існує тільки одна ДКНФ, яка тотожно дорівнює їй.

Констітуентами нуля називають елементарні диз'юнкції, що містять в прямому або інверсному вигляді всі змінні заданої множини М.

 

Для множини М={x1, …, xn} довільну констітуенту нуля можна представити у вигляді 1 Ú 2 Ú… Ú n, де і дорівнює хі або , і=1, 2, ..., n.

Визначною властивістю констітуент нуля є те, що для будь-якої констітуенти нуля R= 1 Ú 2 Ú… Ú n існує один і тільки один відповідний даній констітуенті набір b=(b1,…,bn) значень змінних x1, …, xn, на якому дана констітуента приймає значення 0.

 

Розглянемо приклад констітуент нуля (для M={x1, x2, x3}) 1Úx2Ú 3, x1Ú 2Ú 3, якi приймають значення 0 на наступних наборах:

‒ 1Úx2Ú 3 – на наборі (1,0,1);

‒ x1Ú 2Ú 3 – на наборі (0,1,1).

Досконалою КНФ (ДКНФ) називають КНФ, у якої всі елементарні диз’юнкції, із яких вона складається, є констітуентами нуля.

 

Наприклад, для M={x1, x2, x3}:

- досконалою КНФ буде вираз (x1Ú 2Ú 3)( 1Úx2 Ú 3)( 1Ú 2Úx3);

- вираз (x1 2)(x2 3)( 1Ú 2Úx3) є тiльки КНФ, а не ДКНФ.

 

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

Крок 1.Обираємо з таблиці ті набори значень двійкових змінних, на яких дана булева функцiя приймає значення 0.

Крок 2. Записуємо відповідні вказаним наборам констітуенти 0.

Крок 3. Об’єднуємо отримані констітуенти 0 знаками кон’юнкції.

 

Наведемо пояснювальний приклад.

Нехай булеву функцiю задано наступною таблицею істинності:

 

Х Y Z F(х, y, z)

 

 

Знайдемо ДКНФ, яка дорiвнює заданiй булевiй функцiї:

f(x,y,z)=(xyz)(xy )( y )

Існує алгоритм знаходження для визначеної булевої функцiї, що задана аналітично, тотожно рiвної ДКНФ

Алгоритм, який дозволяє для будь-якого виразу булевої алгебри знайти ДКНФ, яка тотожно дорiвнює йому, наведено нижче.

Етап 1. Приводимо довільний вираз булевої алгебри до КНФ.

Етап 2. Доки не всі елементарні диз’юнкції, що входять до КНФ, є констітуентами нуля, здiйснюємо наведенi нижче дії.

Крок 2_1. Обираємо елементарну диз’юнкцію q, яка входить до КНФ, та яка не містить в собі деякої зi змінних хi (i= 1,…,n), від яких залежить булева функцiя.

Крок 2_2. У КНФ замінюємо диз’юнкцію q виразом, який дорівнює їй у силу наступних тотожностей: g = gÚx i = (gÚxi)(gÚ i)

 

Наведемо пояснювальний приклад, в якому потрібно привести до ДКНФ вираз f(x, y, z) = (x Ú z):

f(x, y, z) = (x Ú z) = ( )(x Ú z) = ( Ú )(x Ú z) =

= ( Ú y )(x Ú z)(x Ú y Ú z) =

= ( Ú y )( Ú )(x Ú Ú z )( Ú Ú z)(x Ú y Ú z )(x v v z).