Лекція №6 Форми представлення логічних функцій

Тема 2.2 Представлення логічних функцій

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

2. Перехід від ДНФ та КНФ до ДНДФ та ДКНФ.

 

Диз’юнктивна нормальна форма (ДНФ) – це є булева сума елементарних добутків. Наприклад:

f = x1Úх1·2Ú1·х2·3 – нормальна диз’юнктивна форма.

f = x1Úх1·2Ú2·х2·3·х1 – ненормальна диз’юнктивна форма.

Кон’юктивна нормальна форма (КНФ) – це є булевий добуток елементарних сум.

КНФ: f = (x1Ú2)·(х 1Úх2Ú3)

не є КНФ: f = (x1Ú2)·(х 1·х2Ú3)

Довершена ДНФ (ДДНФ) – ДНФ функції n – аргументів, яка складається з елементарних добутків ранга n (тобто з мінтермім).

Приклад: f = x1·х2·3Ú1·3·х2Úх1·2·3 – ДДНФ

f = x2·3Ú3Úх1·2·3 – не є ДДНФ.

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

Приклад: f = (х1Úх2Ú3)·(х1Ú2Ú3)·(х1Ú2Ú3) – ДКНФ

f = (х1Úх2)·(х1Úх2Ú3)·(х1Ú3) – не є ДКНФ

Запис ДДНФ і ДКНФ за таблицею істинності

х3 х2 х1 f
22 21 20  

ДДНФ

f = 3·х2·х1Úх3·2·1Úх3·х2·х1 функція =1

ДКНФ

f = (х3Úх2Úх1)·(х3Úх2Ú1)·(х3Ú2Úх1). (3Úх2Ú1)·(3Ú2Úх1) функція =0

 

х3 х2 х1 f
22 21 20  

Приклад:

 

ДДНФ

f = 3·2·1Ú3·2·х1Úх3·2·1Úх3·2·х1

 

ДКНФ

f = (х3Ú2Úх1)·(х3Ú2Ú1)·(3Ú2Úх1)·(3·2·1)

 

Запис функції ДДНФ і ДКНФ за допомогою аналітичних перетворень.

f (х3, х2, х1) = х1·(2Ú3)Ú 2·х1 = х1·2Ú3·х1Ú2·х1 = х1·2·(х3Ú3) Úх1·3·(х2Ú2) Ú2·х1·(х3Ú3) = х1·2·х3Úх1·2·3 Úх1·3·х2 Úх2·3·2 Ú2·х1·х3 Ú2·х1·3= х1·2·х3 Úх1·2·3 Úх1·3·х2

Висновки: Для переходу до ДДНФ необхідно:

1. розкрити душки (розподільчий закон).

2. кожний з добутків домножити на вираз типу (хÚ), аргумент взяти з індексом, який не входить в даний добуток (тотожність х·1=х, хÚ=1).

3. Розкрити всі дужки і привести подібні члени. (розподільчий, переставний, і закон хÚх=х)

 

Приклад:

f (х1, х2, х3, х4) = х1•х3•х2Ú3•х2Ú3•х4•2•1 = х1•х2•х3•(х4Ú 4)Ú3•х2•(х1Ú1)Ú 3•х4•2•1 = х1•х3•х2•х4Ú х1•х2•х3•4Ú х2•3•х1Ú3•1•х2Ú3•х4•2•1= х1•х3•х2•х4 Úх1•х2•х3•4 Úх2•3•х1•(х4Ú4)Ú3•1•х2•(х4Ú4)Ú1•2•3•х4 = х1•х3•х2•х4 Úх1•х2•х3•4 Úх2•3•х1•х4 Úх2•3•х1•4 Ú13•2•х4 Ú3•1•х2•4 Ú1•2•3•х4