2.7. Досконалі диз’юнктивні й кон’юнктивні нормальні форми

Зауважимо, що, якщо , то цю функцію можна подати у вигляді , а якщо , то — у вигляді .

Нехай величина і нехай .

Розглянемо без доведення важливу теорему.

Теорема 2.1 (про розкладання логічних функцій за змінними). Для будь-якої функції при довільному справедливе подання:

(2.1).

Тут запис означає багаторазову диз’юнкцію, яка береться за всіма можливими інтерпретаціями при .

Подання логічної функції у вигляді (2.1) називають розкладом логічної функції за змінними .

Функцію називають підфункцією функції , яка відповідає заміні змінних константами відповідно.

Наслідок 1 (про розкладання логічних функцій за однією змінною).

. (2.1)

Наслідок 2 (про розкладання логічних функцій за всіма змінними).

.

Наслідок 3 (про розкладання логічних функцій за всіма змінними при ). Якщо , то:

. (2.2)

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

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

1. Форма не містить двох однакових кон’юнктивних одночленів (конституент одиниці).

2. Жодна конституента одиниці не містить двох однакових змінних — кожна змінна ( ) або її заперечення в конституенту входить тільки один раз.

3. Жодна конституента одиниці не містить одночасно деяку змінну і її заперечення .

Конституенти одиниці мають такі властивості:

1. Конституента одиниці дорівнює 1 тільки на відповідній інтерпретації.

2. Конституента одиниці однозначно визначається номером відповідної інтерпретації.

3. Кон’юнкція будь-якої кількості різних конституент одиниці дорівнює 0.

Будь-яка логічна функція, відмінна від константи 0, має єдину ДДНФ.

Якщо функція , то на основі принципу двоїстості її двоїста функція . Ця функція буде мати таку ДДНФ:

.

Знову ж таки, відповідно до принципу двоїстості, замінюючи операцію диз’юнк­­­ції ( ) на операцію кон’юнкції ( ) і навпаки, одержимо двоїсту формулу:

.

За означенням двоїстої функції, якщо , то , а також, враховуючи, що , матимемо:

або, змінивши позначки на , одержимо:

. (2.3)

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

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

1. Форма не містить двох однакових диз’юнктивних одночленів (конституент нуля).

2. Жодна конституента нуля не містить двох однакових змінних — кожна змінна ( ) або її заперечення в конституенту входить тільки один раз.

3. Жодна конституента нуля не містить одночасно деяку змінну і її заперечення .

Конституенти нуля мають такі властивості:

1. Конституента нуля дорівнює 0 тільки на відповідній інтерпретації.

2. Конституента нуля однозначно визначається номером відповідної інтерпретації.

3. Диз’юнкція будь-якої кількості різних конституент нуля дорівнює 1.

Будь-яка логічна функція, відмінна від константи 1, має єдину ДКНФ.

Теорема 2.2. Будь-яку логічну функцію можна подати у вигляді формули через заперечення, диз’юнкцію і кон’юнкцію.

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

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

Приклад 2.15. Для функції , оскільки вона не є тотожною 1 чи 0, побудуємо її ДДНФ і ДКНФ. Для цього запишемо таблицю істинності функції і значенням 1 цієї функції поставимо у відповідність конституенти одиниці, а значенням 0 — конституенти нуля:

ДДНФ функції є диз’юнкцією конституент одиниці і має такий вигляд:

,

а її ДКНФ є кон’юнкцією конституент нуля і має такий вигляд:

.

За заданою ДНФ чи КНФ легко можна побудувати ДДНФ чи ДКНФ. Наведемо відповідні алгоритми.

Алгоритм побудови ДДНФ за заданою ДНФ.

1. Якщо кон’юнктивний одночлен заданої ДНФ містить деяку змінну і її заперечення , то треба видалити весь цей одночлен.

2. Якщо в кон’юнктивний одночлен та сама змінна входить кілька разів, то треба залишити тільки одне її входження.

3. Якщо ДНФ містить кілька однакових кон’юнктивних одночленів, то треба залишити тільки один з них.

4. Якщо в кон’юнктивному одночлені відсутня деяка змінна , то в цей одночлен додаємо відповідний вираз і застосовуємо закон дистрибутивності.

5. Якщо треба, то знову виконуємо пункт 3.

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

_.

Алгоритм побудови ДКНФ за заданою КНФ:

1. Якщо диз’юнктивний одночлен заданої КНФ містить деяку змінну і її заперечення , то треба видалити весь цей одночлен.

2. Якщо в диз’юнктивний одночлен та сама змінна входить кілька разів, то треба залишити тільки одне її входження.

3. Якщо КНФ містить кілька однакових диз’юнктивних одночленів, то треба залишити тільки один з них.

4. Якщо в диз’юнктивному одночлені відсутня деяка змінна , то в цей одночлен треба додати відповідний вираз і застосувати закон дистрибутивності.

5. Якщо треба, то знову виконуємо пункт 3.

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

_.

Приклад 2.18. За заданою ДНФ логічної функції знайдемо її ДДНФ. Спочатку виконаємо спрощення, враховуючи, що , , . Отже:

.

Тут у першому кон’юнктивному одночлені відсутня не одна змінна, а дві — y і z, а в другому — одна змінна х. У перший одночлен послідовно введемо змінні y і z, враховуючи, що і , і скористаємося законом дистрибутивності:

,

у другий одночлен введемо змінну х:

.

Отже, .

Враховуючи, що (у нашому випадку ), одержимо ДДНФ заданої функції:

.

Справедливість одержаної формули легко можна перевірити за допомогою таблиці істинності.

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

;

.

Отже:

.

Враховуючи, що (а в нашому випадку це добутки і ), одержимо ДКНФ заданої функції:

.

Справедливість одержаної формули легко можна перевірити за допомогою таблиці істинності.

Приклад 2.20. Для логічної функції треба записати ДДНФ і ДКНФ на основі її таблиці істинності. Побудуємо таблицю істинності:

За тими інтерпретаціями, на яких функція набуває значення 1, побудуємо ДДНФ:

,

а за тими, на яких набуває значення 0, — ДКНФ:

.