Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Рекурсивные правила





До сих пор описывались правила, определяющие новые отношения в терминах существующих отношений. Важным расширением множества подобных правил являются рекурсивные определения, в которых отношения определяются в терминах этих же отношений.Один из способов перехода к рекурсивным правилам состоит в обобщении множества нерекурсивных правил.

Рассмотрим правила, описывающие прародителей, прапрародителей и т.д.:

прародитель(Предок, Потомок) ¬

родитель(Предок, Человек),

родитель(Человек, Потомок).

прапрародитель(Предок, Потомок) ¬

родитель(Предок, Человек),

прародитель(Человек, Потомок).

прапрапрародитель(Предок, Потомок) ¬

родитель(Предок, Человек),

прапрародитель(Человек, Потомок).

Можно заметить простую схему, которую мы опишем в правиле, задающем отношение предок(Предок, Потомок):

предок(Предок, Потомок) ¬

родитель(Предок, Человек), предок(Человек, Потомок).

Это правило представляет собой обобщение введенных ранее правил.

Логическая программа для отношения предок требует также и нерекурсивного правила, выбор которого влияет на значение программы. Если использовать факт предок(Х,Х), приводящий к рефлексии отношения предок, то каждый человек будет своим собственным предком. Это не соответствует интуитивному пониманию слова предок. Программа 2.5 является логической программой, определяющей отношение предок, в ней родители считаются предками.

предок (Предок, Потомок) ¬

Предок является предком субъекта Потомок.

 

предок(Предок, Потомок) ¬

родитель(Предок, Потомок).

 

предок(Предок, Потомок) ¬

родитель(Предок, Человек), предок(Человек, Потомок).

Программа 2.5. Отношение предок.

 

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

Рассмотрим программу проверки связности в ориентированном графе. Ориентированный граф может быть задан в виде логической программы с помощью набора фактов. Факт edge(Node1, Node2) входит в программу, если в графе существует ребро, ведущее из вершины Node1 в вершину Node2. На рис. 2.4 изображен некоторый граф, а программа 2.6 дает его представление в виде логической программы



 

Рис. 2.4. Простой граф.

 

edge(a,b). edge(a,c). edge(b,d).

edge(c,d). edge(d,e). edge(f,g).

Программа 2.6. Ориентированный граф.

 

Две вершины графа связаны, если существует последовательность ребер, ведущая из первой вершины во вторую. Таким образом, отношение connected(Node1,Node2), являющееся истинным, если вершины Node1 и Node2 связаны, есть транзитивное замыкание отношения edge. Например, в графе на рис.2.4 вершины а и е связаны, а b и f – нет. Программа 2.7 описывает требуемое отношение. Значение программы совпадает с множеством целей вида connected(X,Y), где X и Y – связанные вершины. Заметим, что ввиду выбора исходного факта connected является транзитивным рефлексивным отношением

connected(Node1,Node2) ¬

вершина Node1 связна с вершиной Node2 в графе, заданном отношением edge/2.

 

connected(Node,Node).

соnnected(Nodel,Node2) ¬

edge(Nodel,Link), connected(Link,Node2).

Программа 2.7.Транзитивное замыкание отношения edge.

 





Дата добавления: 2014-01-07; Просмотров: 208; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.