Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

АЛГОРИТМ ПЕРЕТВОРЕННЯ ФОРМУЛИ В КНФ І ДНФ

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

1. Виключення з Л зв'язок -> і =, використовуючи теореми:

2. Внесення зв'язки -> всередину дужок всюди, де це можливо, застосовуючи закони де Моргана:

В результаті цих дій зв'язка буде розставлена у формулі А тільки перед пропозіціональнимі символами або перед їх запереченнями. Внаслідок цього можуть з'явитися вираження виду - • -. / ?.

3. Видалення подвійних заперечень відповідно до закону подвійного заперечення

4. Застосування закону дистрибутивности

необхідне число раз, поки не буде отримана КНФ.

Для отримання ДНФ цим же алгоритмом потрібно на етапі 4 застосовувати другий із законів дистрибутивности

необхідне число раз, поки не буде отримана ДНФ.

Приклад. Наведемо до КНФ наступну формулу:

1. Виняток імплікацій

2. Внесення зв'язки всередину дужок

3. Видалення подвійних заперечень

4. Застосування закону дистрибутивности (av (bAC)) v ((avb) A (avc)) Отже, вихідна формула еквівалентна КНФ D ] aD 2 aD 3 , де

Приведення до ДНФ тієї ж формули виконується точно також, і видно, що вже на етапі 3 шукана ДНФ побудована, т. Е. Вихідна формула еквівалентна ДНФ C 1 vC 2 vC 3 vC 4 , де

Кон'юнктивна нормальна форма грає важливу роль в обробці знань на ЕОМ: диз'юнкт, що входять до КНФ, є посилками в принципі резолюції, використовуваному в якості єдиного правила виведення в механізмі виведення мов логічного програмування. Наприклад, синтаксичної основою мови програмування PROLOG є пропозиції Хорна, а його логічною основою є принцип резолюції.

 
<<   ЗМІСТ   >>