Зведення формули до кнф і днф.

Кон’юнктивна нормальна форма це кон’юнкція елементарних диз’юнкцій.

Наприклад, (А Ú В) Ù (`А Ú С), (А Ú В) Ù С тощо.

Для того щоб привести певну формулу до КНФ необхідно виконати такі дії:

1) За допомогою відповідних законів потрібно звільнитися від сильної диз’юнкції “Ú”, еквіваленції “«” та імплікації “É”, якщо вони наявні у вихідній формулі;

2) Звільнитися від загального заперечення та подвійного заперечення відповідно до конкретних законів;

До отриманої формули застосувати закон дистрибутивності диз’юнкції по відношенню до кон’юнкції.

За допомогою КНФ розв’язують такі задачі:

· визначення чи є дана формула тотожно-істинною чи ні; та

· встановлення чи є формула С наслідком із формул А₁, А₂, … А_n.

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

Наприклад,

визначимо чи є формула (`В Ù (А É В)) É`А тотожно-істинною, тобто приведемо її до КНФ.

Спочатку за допомогою закону «виключення імплікації» (А É В º`А Ú В) звільняємося від логічного сполучника «імплікація», який є головним знаком формули:

(`В Ù (А É В)) Ú`А;

Далі, за тим самим законом, «виключення імплікації» звільняємося від імплікації, що знаходиться у дужках:

(`В Ù (`А Ú В)) Ú`А;

Наступним нашим кроком буде застосування «першого закону де Моргана»

(А Ù В º`А Ú`В) для того, щоб позбутися загального заперечення:

(`В Ú (`А Ú В)) Ú`А;

Використовуючи «другий закон де Моргана» (А Ú В º А Ù`В) позбуваємося від заперечення підпормули (`А Ú В):

 

(`В Ú (`А Ù`В)) Ú`А;

Застосовуючи «закон подвійного заперечення» (` А º А) звільняємося від подвійних заперечень, які знаходяться над змінними і отримуємо формулу:

(В Ú (А Ù`В)) Ú`А;

І, нарешті, до отриманої формули застосовуємо «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції»: А Ú (В Ù С) º (А Ú В) Ù (А Ú С):

((В Ú А) Ù (В Ú`В)) Ú`А;

Використовуємо цей самий закон ще раз і отримуємо таку формулу:

 

(В Ú А Ú`А) Ù (В Ú`В Ú`А).

Отже, кожна елементарна диз’юнкція має у своєму складі змінну одночасно із її запереченням (А Ú`А) і (В Ú`В), а це означає, що вихідна формула є тотожно-істинною або тавтологією.

Що стосовно другої зачачі, яку розв’язує КНФ то, щоб перевірити чи є формула С наслідком із формул А₁, А₂, … А_n необхідно за допомогою кон’юнкції поєднати формули А₁, А₂, … А_n., а потім приєднати до них за допомогою імплікації формулу С, і отриманий вираз привести до КНФ.

Якщо отримана КНФ буде тотожно-істинною формулою (тавтологією), тоді можна стверджувати, що формула С наслідком із формул А₁, А₂, … А_n.

Переконаємося у цьому на прикладі.

Визначимо чи є формула С наслідком із формул А Ú В, А É С, В É С.

Для цього спочатку поєднаємо дані формули за допомогою логічного сполучника «кон’юнкція»:

(А Ú В) Ù (А É С) Ù (В É С);

Потім за допомогою логічного сполучника «імплікація» приєднаємо до отриманого виразу наслідок С:

((А Ú В) Ù (А É С) Ù (В É С)) É С;

Приведемо отриманий вираз до КНФ:

((А Ú В) Ù (А É С) Ù (В É С)) Ú С

((А Ú В) Ù (`А Ú С) Ù (`В Ú С)) Ú С

((А Ú В) Ú (`А Ú С) Ú (`В Ú С)) Ú С

((`А Ù`В) Ú (`А Ù`С) Ú (`В Ú`С)) Ú С

1 2 3

((`А Ù`В) Ú (А Ù`С) Ú (В Ù`С)) Ú С

Наступним нашим кроком буде застосовання «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції» А Ú (В Ù С) º (А Ú В) Ù (А Ú С):

(((`А Ú А) Ù (`А Ú`С) Ù (`В Ú А) Ù (`В Ú`С)) Ú (В Ù`С)) Ú С

Потім знову використовуємо «закон дистрибутивності диз’юнкції по відношенню до кон’юнкції» А Ú (В Ù С) º (А Ú В) Ù (А Ú С) і отримуємо:

((`А Ú АÚ В) Ù (`А Ú АÚ`С) Ù (`А Ú`С Ú В) Ù (`А Ú`С Ú`С) Ù

Ù (`В Ú А Ú В) Ù (`В Ú А Ú`С) Ù (`В Ú`С Ú В) Ù (`В Ú`С Ú`С)) Ú С;

І ще раз застосовуємо цей самий закон і отримуємо КНФ:

(`А Ú АÚ ВÚ С) Ù (`А Ú АÚ`С Ú С) Ù (`А Ú`С Ú ВÚ С) Ù

Ù (`А Ú`С Ú`СÚ С) Ù (`В Ú А Ú ВÚ С) Ù (`В Ú А Ú`СÚ С) Ù

Ù (`В Ú`С Ú ВÚ С) Ù (`В Ú`С Ú`СÚ С).

Кожна елементарна диз’юнкція, що входить до складу отриманої КНФ має змінну одночасно із її запереченням, а це означає, що вихідна формула є тотожно-істинною тому, можна стверджувати, що формула С є наслідком із формул А Ú В, А É С, В É С.

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

1) у ній немає двох однакових кон'юнктів;

2) жоден кон'юнкт немає двох однакових диз’юнктів (А Ú В Ú А);

3) жоден кон'юнкт немає змінної і її заперечення (А Ú В Ú`А);

У кожному кон'юнкті наявні всі змінні, що входять до складу вихідної формули.

Щоб привести формулу до ДКНФ неохідно виконати такі дії:

а) звести вихідну формулу до КНФ;

б) співставити отриману КНФ із перерахованими ознаками ДКНФ;

в) якщо в якомусь із кон'юнктів відсутняпропозиційна змінна, яка наявна у вихідній формулі, то необхідно за допомогою диз'юнкції приєднати до цього кон'юнкта протиріччя цієї змінної (Х Ù`Х), а потім застосувати закон дистрибутивності диз'юнкції по відношенню до кон'юнкції.

За допомогою ДКНФ розв'язують задачу знаходження всіх логічних наслідків із даних формул.

Розглянемо приклади.

Візьмемо формули ` В і А É В ізнайдемо з них всі логічні наслідки.

Для цього спочатку за допомогою кон'юнкції поєднуємо ці формули:

` B Ù (A É B)

Далі, отримуємо з неї КНФ:

` B Ù (`A Ú B)

Отримали КНФ. Тепер співставимо отриманий вираз із ознаками ДКНФ.

Виявляється, що в першому кон'юнкті відсутня пропозиційна змінна А, яка є у вихідній формулі. Тому, нам необхідно приєднати за допомогою диз'юнкції до першого кон'юнкта протиріччя (А Ù`А):

(`B Ú (A Ù`A)) Ù (`A Ú B)

Знову застосовуємо «закон дистрибутивності диз'юнкції по відношенню до кон'юнкції» і отримуємо вираз:

(`B Ú A) Ù (`B Ú`A) Ù (`A Ú B)

Отже, ми отримали ДКНФ, яка дає можливість оглянути всі логічні наслідки із даних формул.

Цими наслідками є:

1. (`В Ú А);

2. (`В Ú`А);

3. (`А Ú В);

4. (`В Ú А) Ù (`B Ú`A);

5. (`B Ú A) Ù (`A Ú B);

6. (`B Ú`A) Ù (`A Ú B);

7. (`B Ú A) Ù (`B Ú`A) Ù (`A Ú B).

Знайдемо всі наслідки із таких формул: В Ú С, В É`А, В É С.

Поєднаємо ці формули за допомогою кон’юнкції:

(B Ú C) Ù (B É`A) Ù (B É C)

Приведемо триманий вираз до КНФ:

(B Ú C) Ù (`B Ú`A) Ù (`B Ú C)

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

Отже, необхідно приєднати за допомогою диз'юнкції до першого кон'юнкта протиріччя (А Ù`А), до другого – (С Ù`С), до третього – (А Ù`А):

[(B Ú C) Ú (A Ù`A)] Ù [(`B Ú`A) Ú (C Ù`C)] Ù [(`B Ú C) Ú (`A Ù A)]

Застосуємо закон «дистрибутивності диз'юнкції по відношенню до кон'юнкції»:

4. (B Ú C Ú A) Ù (B Ú C Ú`A) Ù (`B Ú`A Ú C) Ù (`B Ú`A Ú`C) Ù

Ù (`B Ú C Ú A) Ù (`B Ú C Ú`A).

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

Скороченою кон'юнктивною нормальною формою(СКНФ) даної формули називається така її КНФ, яка задовольняє таким умовам:

1) Жоден кон'юнкт не має двох однакових диз’юнктів (А Ú В Ú А);

2) У ній відсутні два однакових кон'юнкти;