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

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

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

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

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

Перетворюємо ДНФ пф на ДДНФ:

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