5.7.4. Хорновские дизъюнкты

Часто в исчислении высказываний возникает следующая задача: нужно проверить какую-то формулу (цель), логически выведенную из множества фактов и правил. Резолюция является методом доказательства от противного – исходя из фактов, правил и отрицания цели приходим к противоречию (пустому дизъюнкту). При этом удобно использовать хорновские дизъюнкты.

Хорновский дизъюнкт – это дизъюнкт, который содержит не более одной позитивной литеры. Например, {ù p, ù q, ù r, s} – хорновский дизъюнкт, он эквивалентен следующей формуле (pÙqÙr)És: (pÙqÙr)És º ù(pÙqÙr) Ú s º ù pÚù qÚù rÚs.

Хорновский дизъюнкт называется точным, если он содержит позитивную литеру, иначе он называется негативным.

Точный дизъюнкт выражает некоторое правило: негативные литеры соответствуют гипотезам, позитивные литеры – заключениям. Унитарный позитивный дизъюнкт – это некоторый факт, т.е. заключение, не зависящее ни от каких гипотез.

Пусть S – множество хорновских дизъюнктов. Выполнимость S можно проверить с помощью следующего алгоритма:

1. Выбрать такие элементы р и с множества S, что р – унитарный позитивный дизъюнкт, а с – дизъюнкт, содержащий ù p.

2. Вычислить резольвенту r.

3. Заменить S на (S \ {c})  {r}.

4. Выполнять эту процедуру до получения пустого дизъюнкта.

Пример. Проверить выполнимость следующего множества хорновских дизъюнктов S={ pÚù rÚù t, q, r, tÚù pÚù r, t Úùq, ù pÚù qÚù r}.

1. Упорядочим множество S: { pÚù rÚù t, q, r, tÚù pÚù r, t Úùq, ù pÚù qÚù r}.

1 2 3 4 5 6

2. Унитарный дизъюнкт q – второй элемент S , с – пятый дизъюнкт.

3. Вычисляем резольвенту r и заменяем S на (S \ {c})  {r}, получим новое множество дизъюнктов: { pÚù rÚù t, q, r, tÚù pÚù r, ù pÚù qÚù r}.

4. Унитарный дизъюнкт q – второй элемент S , с – шестой дизъюнкт.

5. Вычисляем резольвенту r и заменяем S на (S \ {c})  {r}, получим новое множество дизъюнктов: { pÚù rÚù t, q, r, t, tÚù pÚù r, ù p Úù r}.

6. Далее аналогично: { p Úù t, q, r, t, tÚù pÚù r, ù p }.

7. { p, q, r, t, tÚù pÚù r, ù p } – получен пустой дизъюнкт, следовательно, исходное множество S – невыполнимо.

5.8. Применение исчисления высказываний

Модели и алгоритмы исчисления высказываний нашли широкое применение во многих областях: в интеллектуальных системах для построения баз знаний, в теории и практике конструирования релейно-контактных схем, в вычислительных машинах для синтеза и анализа схем и др. Однако существует особенность, которая ограничивает сферу применения исчисления высказываний – высказывания не расчленяются на субъект и свойство субъекта. Поэтому исчисление высказываний достаточно лишь для выражения тех логических связей, в которых высказывания выступают как нераздельное целое.

5.8.1. Пример базы знаний на основе логических высказываний

Пусть необходимо формализовать знания о различных животных. База знаний на основе исчисления высказываний должна состоять из фактов – единичных высказываний и формул исчисления высказываний, которые выражают логические связи между фактами (табл. 7).

Таблица 7

База знаний на основе исчисления высказываний

Факты

Формулы исчисления высказываний

а1 – животное имеет шерсть а2 – животное кормит детенышей молоком а3 – млекопитающее а4 – животное имеет перья а5 – животное летает а5 – животное откладывает яйца а7 – птица а8 – животное ест мясо а9 – животное имеет острые зубы а10 – животное имеет когти а11 – имеет глаза, направленные вперед а12 – хищник а13 – имеет рыже - коричневый цвет а14 – имеет телесные пятна а15 – гепард а16 – имеет черные полосы а17 – тигр а18 – плавает а19 – пингвин а20 – альбатрос

а1Úа2Éa3 a4Ú(a5 Ùa6)Éa7 a3Ù(a8Ú(a9Ùa10Ùa11))Éa12 a12Ùa13Ùa14Éa15 a12Ùa13Ùa16Éa17 a7Ùa5Ùa18Éa19 a7Ùa5Éa20