Лекция №6

Отрицание в логическом программировании

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

Определим отношение not G и опишем его значение. Данное отрицание является частным случаем отрицания в логике первого порядка. Отношение not трактует отрицание как отсутствие. Цель not G считается выводимойиз программыР, если G не выводима из Р.

Опишем отрицание как отсутствие в терминах дерева поиска. Дерево поиска цели G относительно программы Р называется конечно-безуспешным, если в дереве нет успешных вершин и нет бесконечных ветвей. Конечно-безуспешным множеством логической программы Р называется множество тех целей, для которых имеется конечно-безуспешное дерево поиска относительно программы Р.

Цель not следует из программы Р при понимании отрицания как отсутствия, если G входит в конечно-безуспешное множество программы Р.

Рассмотрим простой пример. Возьмем программу, состоящую из двух фактов:

любит (авраам, гранаты).

любит (исаак, гранаты).

Цель not любит (сара, гранаты) следует из программы при понимании отрицания как отсутствия. Дерево поиска любит (сара, гранаты) имеет одну безуспешную вершину.

Использование отрицания как отсутствия позволяет легко определять многие отношения. Например, отношение disjoint (Xs.Ys), означающее, что у двух списков Xs и Ys нет общих элементов, может быть декларативно определено следующим образом:

disjoint(Xs,Ys) ¬ not(member(X,Xs),member(Y,Ys));

Это означает: «список Xs не пересекается со списком Ys, если никакой элемент Xs не является членом обоих списков Xs и Ys».

Программа 5.1 является другим примером программы, использующей отрицание. В программе определяется отношение неженатый_студент (Человек), означающее, что Человек является неженатым студентом. Вопрос неженатый_студент (Х)?. имеет решение Х = билл.

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

неженатый_студент(X) ¬ not женат(X), студент(X),

студент(билл),

женат(джо).

Программа 5.1. Простая программа, использующая not.