Математическая логика и теория алгоритмов

пpeдoк(X,Z);- родитель (Х,г). предок (Х,г): - родитель(Х,У), родитель(У,г). предок (Х,г):- родитель(Х,У1), родитель(У1,У2), poдитeль(Y2,Z). предок (Х,г):- родитель(Х,У1), родитель(У1,У2), родитель( ¥ 2,УЗ), poдитeль(YЗ,Z). Эта программа длинна и, что важнее, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева. Существует компактная и корректная формулировка отношения предок, которая работает на любую глубину. Ключевая идея для это­ го: определить отношение предок через него самого, т.е. ввести рекур­ сивное определение, Это определение будет следующим: Для всех X и Z Х- предок Z, если существует Y, такой, что (1) X-родительY и (2) Y-предок Z. Пред1Южение ПРОЛОГа, имеющее тот нее смысл, записывается в виде: пpeдoк(X,Z):- родитель(Х,У), предок(У,г). 124