Размножение литералов. 
Символический искусственный интеллект: математические основы представления знаний

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

Пример 4.7.

Власенко отлично учится в группе 5057.

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

Отличники умные.

Попробуем показать следующий факт: существует студент, который знает метод резолюций и является либо программистом, либо умником.

Введем соответствующие предикаты и запишем формулы:

• (1) Зх Р (х) л (Щх) v У (лг)) цель
• (2) 5057 (Власенко) факт
• (3) О (Власенко) факт
• (4) V. r 5057(х) -> С (х) правило
• (5) V. r С (дг) —> Р (х) правило
• (6) Vx О (х) -> У (х) правило

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

• (1) -пР (х) v-^Щх)
• (2) -iP (x) v -, У (х)
• (3) —
• (4) -.5057(x)v С (дг)
• (5) 5057 (Власенко)
• (6) —|(л:)0 v У (.г)
• (7) О (Власенко)
• (8) -пП (х) v -, С (х) 1−3
• (9) -, П (*) v 5057(х) 8−4
• (10) -, П (лг) 9−5
• (11) -.У (.г) v -*С (х) 2−3
• (12) -iY (.r) vi5057(.r) 11−4
• (13) -пУ (Власенко) 12−5
• (14) -«0(Власенко) 16−6
• (15)? 14−7

Дизъюнкты (8), (9) и (10) — это результативные выводы, резольвенты, полученные самым простым образом. Берем два первых подходящих дизъюнкта и начинаем резольвировать. Дизъюнкты (8), (9) и (10) в этом примере — это первые подходящие, однако легко сообразить, что полученный дизъюнкт -.П (.г) нам совсем нс нужен. Этот результат потом негде будет использовать. Программисты вообще в исходных данных не упоминались. Это бессмысленно потраченные машинное время и память на выполнение вывода, который не нужен. Начинать следовало сразу с дизъюнкта (11), резольвируя дизъюнкты (2) и (3), первый дизъюнкт не нужно было рассматривать. Атомарная формуланР (х), которая появилась в предложении (1), произошла в результате размножения литералов и, безусловно, оказалась вредна для решения задачи.

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