Page 42 - 4496

0 1 1 1 1 1

1 0 0 1 0 0
1 0 1 1 0 0

1 1 0 0 0 1

1 1 1 0 1 1

Якщо змінна в ДДНФ приймає значення нуль, то ми її
позначаємо через x , а якщо – одиницю, то це x i.
i
Отже, на п`ятьох значеннях кортежів {1, 2, 4, 7, 8}
поточна функція приймає значення одиниці.
Тому D( x ) = x 1 x 2 x 3 + x 1 x 2x 3 + x 1x 2x 3 + x 1x 2 x 3 +
x 1x 2x 3.

2.22 Нормальні та досконалі кон`юнктивні нормальні
форми (ДКНФ)

Означення1. Логічна сума будь-якої кількості різих
незалежних змінних, що входять із запереченням, або без
нього, називається елементарною диз`юнкцією.
Приклади елементарних диз`юнкцій:
x 0 + x 2 + x 3;
x 0 + x 1 + x 2 + x 3;
x 1 + x 2 + x 3 і т.д.
0
Як і раніше F = x 1 x 2  x 3  ...  x z – елементарна
диз`юнкція z-го рангу.
Означення 2. Якщо будь-яку функцію задано формулою
у вигляді кон`юнкції елементарних диз`юнкцій, то функцію
задано її кон`юнктивною нормальною формою (КНФ).
Наприклад:
f (x) = (x 0 + x 2 + x 3) (x 0 + x 1 + x 2 + x 3) (x 1 + x 2 + x 3).
Будь-яка перемикальна функція може бути задана і
своєю довершеною кон`юнктивною нормальною формою
(ДКНФ).
39