Ещё одни лекции В.А. Захарова, страница 24
Описание файла
PDF-файл из архива "Ещё одни лекции В.А. Захарова", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 24 страницы из PDF
Ясно, что некоторые способы решения могутбыть «хорошими», а некоторые — «плохими».Таким образом, чтобы вычислить все ответы на запрос (или,что то же само, гарантировать вычисление хотя бы одногоответа), нужно уметь просматривать все варианты выборапрограммных утверждений. И нужно правильно организоватьэтот перебор.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММОпределениеДеревом SLD-резолютивных вычислений запроса G0 клогической программе P называется помеченное корневоедерево TG0 ,P , удовлетворяющее следующим требованиям:1.
Корнем дерева является исходный запрос G0 ;2. Потомками каждой вершины G являются всевозможныеSLD-резольвенты запроса G (при фиксированномстандартном правиле выбора подцелей);3. Листовыми вершинами являются пустые запросы(завершающие успешные вычисления) и запросы, неимеющие SLD-резольвент (завершающие тупиковыевычисления).ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММИллюстрация?G0Ptq) @PPR@?'TG0 ,P?GitPt) @PPq t ?Givqqq@R t?G @?G t?Giii$?Gt j?t?&%ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример 1.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@(2), {X1 /c}t?Q(Y1 ), R(b) ??t?R(c)failure(4), {Y1 /c}?R(b) ?t(3), ε?t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Пример 2..t?P(X Y )P : P(X L) ← P(L), R(X );(1), {X1 /X , L1 /Y }P(nil) ←;?t?P(Y ), R(X )R(a) ←;@ (2), {Y /nil}(1), {Y /X2 L2 }@R(c) ←;R t?R(X )@?P(L2 ), R(X2 ), R(X )t.(1), {L2 /X3.L3 }(3), {X /a} @ (4), {X /c}@(2), {L2 /nil}?P(L3 ), R(X3 ),) ?R(X2 ), R(X ) ?ttR(X2 ), R(X )@?@(3), {X1 /a}??Rt?R(X )@tt?R(X )@@ (4), {X /c}(4),{X/c}?R(X3 ), R(X2 ), R(X )(3), {X /a} @ (3), {X /a} @?Rt?Rtt @t @)∞?Rtt @(2), {L3 /nil}(3), {X1 /a}????ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММИтак, деревья вычислений логических программ бываютразные — конечные и бесконечные, с конечным илибесконечным множеством ветвей, и т.
п.Каждая ветвь дерева TG0 ,P соответствует одному извозможных вычислений запроса G0 к логической программе P.Некоторые из ветвей образуют успешное вычисление и даютответ на запрос.Возникает вопрос:Как нам обнаружить ветви успешных вычислений в деревеSLD-резолютивных вычислений программы?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММОпределениеСтратегией вычисления запросов к логическим программамназывается алгоритм построения (обхода) дереваSLD-резолютивных вычислений TG0 ,P всякого запроса G0 кпроизвольной логической программе PСтратегия вычислений называется вычислительно полной ,если для любого запроса G0 и любой логической программы Pэта стратегия строит (обнаруживает) все успешныевычисления запроса G0 к программы PСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММФактически, стратегия вычисления — это одна стратегийобхода корневого дерева.
Как известно, таких стратегийсуществует много, но среди них выделяются две наиболеехарактерные:стратегия обхода в ширину , при которой деревостроится (обходится) поярусно — вершина i-го нестроится, до тех пор пока не будут построены все вершины(i − 1)-го яруса;стратегия обхода в глубину с возвратом , при которойветви дерева обходятся поочередно — очередная ветвьдерева не обохдится, до тех пор пока не будут пройденывсе вершины текущей ветви.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t?P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ??P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ??P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@(2), {X1 /c}?t?R(c)СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ??P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@(2), {X1 /c}?t?R(c)СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ??P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@(2), {X1 /c}?t?R(c)failureСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в ширину.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}?P(U,V ), R(U)t@ (2), {U/X1 , V /X1 }@R t?Q(X1 ), R(X1 )@(2), {X1 /c}t?Q(Y1 ), R(b) ??t?R(c)failure(4), {Y1 /c}t?R(b) ?(3), ε?t?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в ширину является вычислительно полной,поскольку каждый запрос имеет конечное число SLD-резольвент, ипоэтому в каждом ярусе дерева SLD-резолютивныхвычислений имеется конечное число вершин; каждое успешное вычисление завершается на некоторомярусе; и поэтому каждое успешное вычисление будет рано илипоздно полностью построено.Но строить интерпретатор логических программ на основестратегии обхода в ширину нецелесообразно.
При обходедерева в ширину нужно обязательно хранить в памяти всевершины очередного яруса. Это требует большого расходапамяти. Например, в 100-м ярусе двоичного дерева содержится299 вершин. Вычислительных ресурсов всего земного шара нехватит, чтобы хранить информацию обо всех этих вершинах.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратом основана наследующих принципах:1. все программные утверждения упорядочиваются;2.
на каждом шаге обхода из текущей вершины Gосуществляется переходлибо в новую вершину-потомок G , которая являетсяSLD-резольвентой запроса G и первого по порядкупрограммного утверждения D, ранее не использованногодля этой цели;либо в ранее построенную родительскую вершину G (откат), если все программные утверждения уже былиопробованы для построения SLD-резольвент запроса G .СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ?(3), ε?t??P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ?(3), ε?t?6?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ?(3), ε?t?66?P(U,V ), R(U)tСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ?(3), ε?t??P(U,V ), R(U)t666СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}t?Q(Y1 ), R(b) ?(4), {Y1 /c}t?R(b) ?(3), ε?t??P(U,V ), R(U)t666СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );R(b) ←;(1), {U/X1 , V /Y1 }Q(c) ←;?R(X1 ), Q(Y1 ), R(X1 ) t6(3), {X1 /b}t?Q(Y1 ), R(b) ?6(4), {Y1 /c}t?R(b) ?(3), ε6?t??P(U,V ), R(U)t@ @(2), {U/X1 , V /X1 }R t?Q(X1 ), R(X1 )@СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 } @(2), {U/X1 , V /X1 }Q(c) ←;@ t?Q(X1 ), R(X1 )R?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}6t?Q(Y1 ), R(b) ?(4), {Y1 /c}6t?R(b) ?(3), ε6?t?(2), {X1 /c}?t?R(c)СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 } @(2), {U/X1 , V /X1 }Q(c) ←;@ t?Q(X1 ), R(X1 )R?R(X1 ), Q(Y1 ), R(X1 ) t(3), {X1 /b}6t?Q(Y1 ), R(b) ?(4), {Y1 /c}6t?R(b) ?6(3), ε?t?6(2), {X1 /c}?t?R(c)failureСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПример обхода в глубину с возвратом.P : P(X , Y ) ← R(X ), Q(Y );P(X , X ) ← Q(X );?P(U,V ), R(U)tR(b) ←;@(1), {U/X1 , V /Y1 }(2), {U/X1 , V /X1 }@I@@Q(c) ←;R t?Q(X1 ), R(X1 )?R(X1 ), Q(Y1 ), R(X1 ) t@@(3), {X1 /b}6t?Q(Y1 ), R(b) ?(4), {Y1 /c}6t?R(b) ?6(3), ε?t?6(2), {X1 /c}?t?R(c)failureСТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратомимеет эффективную реализацию: в памяти нужно хранитьлишь запросы той ветви, по которой идет обход, и каждыйзапрос должен вести учет использованных программныхутверждений;является, к сожалению, вычислительно неполной.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Обратимся к примеру 2..P : P(X L) ← P(L), R(X );P(nil) ←;R(a) ←;R(c) ←;(1), {X1 /X , L1 /Y }(1), {Y /X2(1), {L2 /X3(1), {L3 /X4(1), {L4 /X5..t?P(X Y )..?t?P(Y ), R(X )L2 }t?P(L2 ), R(X2 ), R(X )L3 }t?P(L3 ), R(X3 ), R(X2 ), R(X )L4 }t?P(L4 ), R(X4 ), R(X3 ), R(X2 ), R(X )L5 }∞ Обход дерева TG ,P уходит в глубинупо бесконечной ветви и не может возвратиться,чтобы обнаружить успешное вычисление.СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММСтратегия обхода в глубину с возвратом чувствительна кпорядку расположения программных утверждений в логическихпрограммах.
Результат вычисления запроса может существенноизмениться при перестановке программных утверждений.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММЕще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;..t?P(X Y )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) tДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?(4), {X /c}?t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t6(4), {X /c}?tt(3), {X /a}??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t*(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}?t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }?t?P(L2 ), R(X2 ), R(X )(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }?t?P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t6(3), {X /a}t?(4), {X /c}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }?t?P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }?t?P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}?t(3), {X /a}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }?t?P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?.И Т.