Правило відшукання ДКНФ.

Дану пф за рівносильностями (25°) і (22°), застосовуючи їх необхідне число разів, можна перетворити на їй рівносильну, що не має символів ↔ і →, якщо вони в ній були. Потім, застосовуючи визначене число разів рівносильності (1°), (8°) — (12°), отримуємо КНФ даної пф.

Більше того, якщо вихідна пф не є тавтологією, то можна отримати її КНФ, що має різні диз’юнктивні одночлени, у кожному з яких немає входжень одних і тих самих змінних, які повторюються. Така КНФ не буде ДКНФ тільки в тому випадку, якщо який-небудь диз’юнктивний одночлен її не має усіх змінних, що входять до вихідної пф. Але якщо, наприклад, диз’юнктивний одночлен не має змінної , то наступні рівносильні перетворення

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

Приклади. Знайдемо КНФ пф и . Маємо:

Перетворимо КНФ пф на ДКНФ:

Правило написання ДДНФ (ДКНФ) для формули, заданої своїми значеннями:

1) необхідно вибрати всі ті набори значень її змінних, на яких формула приймає значення 1 (значення 0);

2) для кожного такого набору виписати досконалі кон’юнктивні (диз’юнктивні) одночлени, що приймають значення 1 (значення 0) лише на цьому наборі;

3) отримані досконалі кон’юнктивні (диз’юнктивні) одночлени з’єднати знаком диз’юнкції (кон’юнкції).

Приклад.

X	Y	Z

ДДНФ:

ДКНФ:

Поиск по сайту: