Лекция 17. Отрицание в логическом программировании. Оператор not ... (Лекции 2014), страница 2
Описание файла
Файл "Лекция 17. Отрицание в логическом программировании. Оператор not ..." внутри архива находится в папке "Лекции 2014". PDF-файл из архива "Лекции 2014", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
.., a.b .nil),(X , b .c .nil)). ?t?E (Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1nil}(2)t..?not(E (a, b c nil))/X , L0 /aL00 /bbcnil,nil}..?E (a, b tc nil)(3)6?t.?E (a, c nil)(3)6?t?E (a, nil)failure..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3)Успех.. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t?E (Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1nil}(2)t..?not(E (a, b c nil))/X , L0 /aL00 /bbcnil,nil}..?E (a, b tc nil)(3)6?t.?E (a, c nil)(3)6?t?E (a, nil)failure..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3)..
..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t?E (Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bnil}(2)t..?not(E (a, b c nil))θ3 = ε?tОтвет: {X /a}bcnil,nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t?E (Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bnil}(2)t..?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}bcnil,nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..
.., a.b .nil),(X , b .c .nil)). ?t?E (Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bnil}(2)t..?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}bcnil,nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..
.., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))..nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3)..
....?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1/X , L0 /aL00 /bbc?E (b, b tc nil)nil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ....?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1/X , L0 /aL00 /bbc?E (b, b tc nil)nil,nil}(2)?tnil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3)Неудача..
....?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1/X , L0 /aL00 /bbc?E (b, b tc nil)nil,nil}(2)?tnil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..
.., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))failurenil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)).
?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..?E (X , b nil),not(E (X , b c nil))(2)..6θ5 = {X /b, L3 /nil}?t..?not(E (b, b c nil))failurenil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..nil}?E (X , b nil),not(E (X , b c nil))(2)6.
.@θ5 = {X3 /X , Y3 /b, L3 /nil}θ5 = {X /b, L3 /nil}(3) @?t..?not(E (b, b c nil))failure@ ?E (X , nil),Rt@..not(E (X , b c nil))..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..
.., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..nil}?E (X , b nil),not(E (X , b c nil))(2)6. .@θ5 = {X3 /X , Y3 /b, L3 /nil}θ5 = {X /b, L3 /nil}(3) @?t..?not(E (b, b c nil))failure@ ?E (X , nil),Rt@..not(E (X , b c nil))failure..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..
.., a.b .nil),(X , b .c .nil)). ?t@?E@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3) @ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@..nil}?E (X , b nil),not(E (X , b c nil))(2)6. .@θ5 = {X /b, L3 /nil}(3)@@?tI@..?not(E (b, b c nil))failureθ5 = {X3 /X , Y3 /b, L3 /nil}@@ ?E (X , nil),Rt@@..not(E (X , b c nil))failure..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)).
?t@@I?E@@(Xnot(E(1)θ2 = {X /a, L1 /bθ1 = {X1 /X , L0 /aL00 /bbcnil,nil}nil}(2)t..(3)@@ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@@..nil}?E (X , b nil),not(E (X , b c nil))(2)6. .@θ5 = {X /b, L3 /nil}(3)@@?tI@..?not(E (b, b c nil))failureθ5 = {X3 /X , Y3 /b, L3 /nil}@@ ?E (X , nil),Rt@@..not(E (X , b c nil))failure..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil).. .., a.b .nil),(X , b .c .nil)). ?t@@I?E@@(Xnot(Eθ1 = {X1 /X , L0 /aL00 /b(1) 6θ2 = {X /a, L1 /bbcnil,nil}nil}(2)t..(3)@@ θ?not(E (a, b c nil))6θ3 = ε?tОтвет: {X /a}4= {X2 /X , Y2 /a, L2 /bRt@@..nil}?E (X , b nil),not(E (X , b c nil))(2)6.
.@θ5 = {X /b, L3 /nil}(3)@@?tI@..?not(E (b, b c nil))failureθ5 = {X3 /X , Y3 /b, L3 /nil}@@ ?E (X , nil),Rt@@..not(E (X , b c nil))failureОПЕРАТОР notВ том случае, когда построение дерева SLD-резолютивныхвычислений проводится по стандартной стратегии, операторnot можно выразить через оператор отсечения !.Для этого введем логическую константу fail — 0-местныйпредикат, имеющий постоянное значение false. С точки зренияоперационной семантики, fail — это задача, которая не имеетрешений. Тогда...для обработки запроса ? not(C0 ) в рамках SLD-резолютивноговывода с отсечением достаточно добавить к программе P двадополнительных программных утвержденияnot(C0 ) ← C0 , !, fail;not(C0 ) ← ;ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫХорновские логические программы — это универсальнаямодель вычислений, в которой можно реализовать любойалгоритм.
Однако для удобства пользования логическимипрограммами к ним можно добавлять специальные встроенныефункции и предикаты, операционная семантика которыхопределяется вне рамок SLD- резолютивного вывода.Рассмотрим некоторые наиболее широко используемыевстроенные средства логического программирования.ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат равенства =Предикат равенства t1 = t2 — это 2-х местный предикат,предназначенный для унификации термов. Его операционнаясемантика задается следующими правилами:? tt1 = t2θt?⇔НОУ(t1 , t2 ) 6= ∅θ ∈ НОУ(t1 , t2 )ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат равенства =Предикат равенства t1 = t2 — это 2-х местный предикат,предназначенный для унификации термов.
Его операционнаясемантика задается следующими правилами:? tt1 = t2θt?⇔НОУ(t1 , t2 ) 6= ∅θ ∈ НОУ(t1 , t2 )? t1 t= t2failure⇔НОУ(t1 , t2 ) = ∅ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат равенства =Пример? X + 2t= 3 + Y{X /3, Y /2}t?ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат равенства =Пример? X + 2t= 3 + Y{X /3, Y /2}t?? 3 + 2 t= 2 + 3failureВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат тождества ==Предикат тождества t1 == t2 — это 2-х местный предикат,предназначенный для проверки тождественности(синтаксической идентичности) термов. Его операционнаясемантика задается следующими правилами:? tt == tεt?ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат тождества ==Предикат тождества t1 == t2 — это 2-х местный предикат,предназначенный для проверки тождественности(синтаксической идентичности) термов.
Его операционнаясемантика задается следующими правилами:? tt == tεt?? t1 ==t t2failure⇔t1 , t2 — разныетермыВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат тождества ==Пример? X + 2t== X + 2εt?ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикат тождества ==Пример? X + 2t== X + 2εt?? X + 2t== 2 + YfailureВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикаты неравенства \ =, = \ =Предикаты неравенства t1 \ = t2 , t1 = \ = t2 определяютсяпри помощи оператора отрицания выражениями not(t1 = t2 ) иnot(t1 == t2 ).Пример? 3 + 2 t\ = 2 + 3εt?ВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫПредикаты неравенства \ =, = \ =Предикаты неравенства t1 \ = t2 , t1 = \ = t2 определяютсяпри помощи оператора отрицания выражениями not(t1 = t2 ) иnot(t1 == t2 ).Пример? 3 + 2 t\ = 2 + 3εt?? 3 + X t= \ = 3 + XfailureВСТРОЕННЫЕ ФУНКЦИИ И ПРЕДИКАТЫТипы данныхДля определения более сложных встроенных предикатоввводятся типы данныхinteger, real, boolean, char, и т.