Приведення до СКНФ. Алгоритм приведення.
- привести формулу за допомогою рівносильних перетворень до КНФ.
- видалити члени кон'юнкції, що містять змінну разом з її запереченням (якщо такі виявляться);
- з однакових членів кон'юнкції (якщо такі виявляться) видалити всі, крім одного;
- з однакових членів кожної диз'юнкції (якщо такі виявляться) видалити всі, крім одного;
- якщо в якій-небудь диз'юнкції не міститься змінної xi з числа змінних, що входять у вихідну формулу, додати до цієї диз'юнкції член і застосувати закон дистрибутивности диз'юнкції відносно кон'юнкції;
- якщо в отриманій кон'юнкції виявляться однакові члени, скористатися приписом з п. 3.
Отримана формула і є СКНФ даної формули.
Навести такі формули до СКНФ за допомогою рівносильних перетворень:
2-й спосіб - табличний.
Складаємо таблицю істинності для даної функції.
Будуємо таблицю значень формули. Розглядаємо тільки ті рядки, в яких значення формули дорівнює одиниці. Кожній такій рядку відповідає кон'юнкція всіх аргументів (без повторень). Причому, аргумент, що приймає значення 0, входить в неї з запереченням, значення 1 - без заперечення. Нарешті, утворюємо диз'юнкцію усіх отриманих кон'юнкція.
Побудувати СДНФ для даних формул логіки висловлювань.
Будуємо таблицю істинності (табл. 13) для формули F: