Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

родитель( ¥ 3,г). Эта программа длинна и, что важнее, работает только в определенных пре­ делах. Она будет обнаруживать предков лишь до определенной глубины фа­ мильного дерева. Существует компактная и корректная формулировка отношения предок, которая работает на любую глубину. Ключевая идея для этого: определить от­ ношение предок через него самого, т.е. ввести рекурсивное определение. Это определение будет следующим: Для всех X иZ Х- предок Z, если существует Y, такой, что (1) X -родитель Y и (2) Y -предок Z. Предложение ПРОЛОГа, имеющее тот же смысл, записывается в виде: предок(Х,г):- родитель(Х, ¥ ), предок( ¥ ,г). Полная программа для отношения предок содержит оба правила: одно для ближайших предков и другое для отдаленных предков. В результате имеем: предок(Х,г): - родитель(Х,г). предок(Х,г):- родитель(Х, ¥ ), (3.23) предок( ¥ ,г). Отметим, что рекурсивное задание правил проводится не единственным образом. Так, предложение (3.23) можно заменить, например, на следующее предок(Х, ¥ ): - родитель(Х, ¥ ). предок(Х,г): - предок(Х, ¥ ), предок( ¥ ,г). Если к рассмотренной в параграфе 12 программе добавить предложение (3.23), то полученную программу можно, например, спросить: «Кто потомки Пам?» Па ПРОЛОГе этот вопрос запишем в виде: ?-предок(пам,Х). Система ответит Х=боб Х=эпи Х=пат Х=джим 87