Рекурсия. Декларативная и процедурная семантики.

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

13) родитель(Х,Y) :– отец(Х,Y).	15) предок(Х,Y) :– родитель(Х,Y).
14) родитель(Х,Y) :– мать(Х,Y).	16) предок(Х,Y) :– родитель(Х,Z), предок(Z,Y).

Особого внимания заслуживает правило 16. Оно утверждает, что X является предком Y, если он является родителем некоторого Z, а тот, в свою очередь, – предком Y. Это – пример рекурсивного правила, в котором правая часть содержит предикат из левой части (естественно, с другими компонентами). Такие правила широко используются для представления в БЗ отношений, задаваемых рекурсивно. Другой пример рекурсивного правила был приведен выше в фрагменте описания предметной области «Дифференцирование».

Необходимым условием использования для описания отношения рекурсивного правила является наличие в БЗ хотя бы одного нерекурсивного правила для этого отношения. В нашем случае таким нерекурсивным правилом является правило 15. При использовании рекурсивных правил нужно важно соблюдать рекомендации относительно следования предложений в базе знаний и предикатов в правых частях рекурсивных правил. Рекомендации здесь простые, они формулируются на основе принципа «от простого к сложному». Во-первых, для каждого заданного рекурсивно отношения рекомендуется сначала указать нерекурсивные предложения, а затем – рекурсивные. Во-вторых, в правой части каждого рекурсивного правила предикат, образующий рекурсию, должен находиться после нерекурсивных предикатов (исключение – только для некоторых встроенных предикатов, о которых речь пойдет ниже).

Вы можете легко убедиться, что предложения 15 и 16 удовлетворяют этим рекомендациям.

Введем в рассмотрение предложение 16¢:

предок(Х,Y) :– предок(Z,Y), родитель(Х,Z).

Теперь рассмотрите различные варианты предложений 15, 16 и 16¢. В базе знаний нашего примера это предложения 15, 16 и этот вариант можно считать эталонным. Другие варианты: а) 16, 15; б) 15, 16¢; в) 16¢, 15. Убедитесь, что в них выводы целей, представленных предикатом предокв случае а значительно усложнятся; в случае ббудут найдены только если цель не содержит переменных; в случае в не будут найдены ни при каких значениях термов. Причина неудач для вариантов б и в в том, что алгоритм логического вывода будет выполнять бесконечный цикл.

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