ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Зведення формули до КНФ і ДНФ.

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

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

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

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

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

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

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

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

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

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

Наприклад,

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

 

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

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

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

Якщо отримана КНФ буде тотожно-істинною формулою (тавтологією), тоді можна стверджувати, що формула С наслідком із формул А1, А2, … А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) У ній відсутні два однакових кон'юнкти;

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти