Конъюнктивная нормальная форма
Как было описано выше, правило резолюции применяется только к дизъюнкциям литералов, поэтому на первый взгляд оно распространяется только на базы знаний и запросы, состоящие из таких дизъюнкций. На каком же основании мы утверждаем, что это правило может служить основой процедуры полного логического вывода для всей пропозициональной логики? Ответ на этот вопрос состоит в том, что каждое высказывание пропозициональной логики логически эквивалентно конъюнкции дизъюнкций литералов. Любое высказывание, представленное как конъюнкция дизъюнкций литералов, называется высказыванием, находящимся в конъюнктивной нормальной форме, или CNF (Conjunctive Normal Form). Кроме того, ниже будет показано, что целесообразно определить также ограниченное семейство высказываний в конъюнктивной нормальной форме, называемое высказываниями в форме k-CNF. Высказывание в форме k-CNF имеет точно к литералов в расчете на каждое выражение:
(4,1 V ... V 4,k) А ... Л (4,1 V ... V 4,к)
Как оказалось, любое высказывание может быть преобразовано в высказывание в форме 3-CNF, которое имеет эквивалентное множество моделей.
Вместо доказательства этих утверждений (см. упр. 7.10) опишем простую процедуру преобразования. Проиллюстрируем эту процедуру, преобразовав высказывание R2, или В1Л <=> (Plt2 v Р2,1), в форму CNF. Ниже описаны соответствующие этапы.
1. Устранить связку <=>, заменив высказывание а <=> Р высказыванием
(ос => Р) л (Р => а):
(JBi,i => (Pl,2 V P2/l)) Л ((Pi,2 V P2,l)=> Bi,i)
2. Устранить связку =>, заменив высказывание а => Р высказыванием
-па v Р:
(-1 V Pi,2 V P2,l) Л (-.(Pl(2 V P2fi)V Bi.i)
3. Конъюнктивная нормальная форма требует, чтобы связка -. появлялась
только перед литералами, поэтому, как принято называть эту операцию,
"введем связку -, внутрь выражения", повторяя операцию применения сле-
дующих эквивалентностей из листинга 7.4:
—I (—I ос) = а (устранение двойного отрицания)
-.(ОС л Р) = (-ice v -iP) (правило де Моргана)
-?(ос v Р) = (-.а л -.Р) (правило де Моргана)
В данном примере требуется применение только одного, последнего правила:
(-,Bi,l V Р1(2 V P2,i) Л ( (-.Pi, 2 Л -nP2,i) V Bi,i)
4. В результате получено высказывание, содержащее вложенные связки л и v,
которые применяются к литералам. Используем закон дистрибутивности,
приведенный в листинге 7.4, распределяя связки v по связкам л везде, где это
возможно.
(-iBi.i v Pi,2 V Р2(1) Л (-iPi.2 v Bi,i) л (-.P2,i V Bi,i)
Теперь первоначальное высказывание представлено в форме CNF, как конъюнкция трех выражений. Это высказывание стало более сложным для чтения, но зато его можно использовать в качестве входных данных для процедуры резолюции.