Форма И/ИЛИ. 
Символический искусственный интеллект: математические основы представления знаний

Попробуем преобразовать исходные формулы, с помощью которых записано наше знание о предметной области (формулы исчисления первого порядка) не в форму дизъюнктов, а в так называемую форму И/ИЛИ, просто проводя меньшее количество шагов преобразования. Так же, как при сведении к дизъюнктам в методе резолюций, элиминируем импликацию, протаскиваем отрицание, элиминируем квантор существования, строим предваренную форму, убираем квантор всеобщности и разделяем переменные в главных конъюнктах (см. п. 4.1.4).

Если вы обратили внимание, пропущен этап построения конъюнктивной формы. Какая форма была, такая и осталась, мы только избавились от кванторов и разделили переменные. Легко видеть, что в результате элиминации импликации, протаскивания отрицания, элиминации квантора существования, построения предваренной формы, элиминации всеобщности и переименования переменных количество литералов сохраняется.

Заметим, что форма И/ИЛИ может быть получена по любой формуле исчисления предикатов.

Пример 4.8.

Дана формула (рис. 4.1) 3и Ус (Q (v, и) & ((R (v) v P (v)) & S (u, v)). Для использования формы И/ИЛИ предлагается представить формулу в виде гиперграфа следующим образом. Там, где главная операция &, ставится две раздельных 1-дуги, там, где главная операция v, ставится одна 2-дуга. Ход рассуждения достаточно прост. Когда известно, что А & В, можно повести рассуждение в одну сторону, используя го, что дано А, а можно в другую, используя то, что дано В. Когда дано A v В, мы не знаем, в какую сторону конкретно двигаться, нужно двигаться сразу в обе стороны.

Рис. 4.1. Представления формы И/ИЛИ в виде гиперграфа

Очевидно, что множество предложений, в которые преобразуется корневая формула, может быть прочитано как множество концевых вершин всех графов решения, которые есть на этом гиперграфе (см. рис. 4.1). На этом гиперграфе есть три графа решения. Один идет из корня в Q, второй идет из корня на следующий уровень и дальше обязательно завязывается на S, потому что там 2-дуга. Нас интересуют концевые вершины. Если исходную форму свести к дизъюнктам, то их получится три: v —15, —IР v —.5. На рисунке они выписаны в рамочке сбоку от формы И/ИЛИ.

Заметим это обстоятельство: форма И/ИЛИ хранит ту же информацию, которой мы располагали в методе резолюций, а также еще и другую информацию.