упражнения 2 (1162151), страница 4
Текст из файла (страница 4)
Если формула ϕ выполнима в каждой эрбрановской интерпретации сигнатуры σ, тоформула ϕ общезначима.4. Если формула ϕ не имеет эрбрановских моделей, то формула ϕ не имеет никаких моделей.Упражнение 1.56. Каждая эрбрановская интерпретация I сигнатуры полностью определяется множеством всех тех основных атомов сигнатуры σ, которые выполняются в интерпретации I. В последующих упражнениях будет использоваться теоретико-множественныйспособ представления эрбрановских интерпретаций, при котором эрбрановская интерпретация I отождествляется с тем множеством основных атомов, которые в ней выполняются,т. е.I = {A : A ∈ Bσ , I |= A}.Предположим, что замкнутая формула ϕ имеет эрбрановские модели I1 и I2 .
Верно ли, чтоинтерпретации I1 ∪ I2 и I1 ∩ I2 будут также являться эрбрановскими моделями для формулыϕ?Упражнение 1.57. Предположим, что замкнутая формула ψ является сколемовской стандартной формой и имеет эрбрановские модели I1 и I2 . Верно ли, что интерпретации I1 ∪ I2 иI1 ∩ I2 будут также являться эрбрановскими моделями для формулы ψ?Упражнение 1.58. При каких условия обе эрбрановские интерпретации BH и ∅ будуттакже являться эрбрановскими моделями для системы дизъюнктов S?Упражнение 1.59. Пусть известно, что ϕ(x1 , x2 , .
. . , xn ) — бескванторная формула, в которой не содержатся ни константы, ни функциональные символы. Докажите, что16Глава 1. УПРАЖНЕНИЯ1. формула ∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn ) общезначима тогда и только тогда, когда онаистинна в любой интерпретации, предметная область которой состоит из n элементов;2. формула ∃x1 ∃x2 . .
. ∃xn ϕ(x1 , x2 , . . . , xn ) общезначима тогда и только тогда, когда онаистинна в любой интерпретации, предметная область которой состоит из одного элемента.Упражнение 1.60. Отыщите наименьшее противоречивое множество основных примеровдля следующих систем дизъюнктов (переменные обозначены заглавными буквами, а константы и функциональные символы — прописными):1. S1 = { ¬P (X) ∨ Q(f (X), X), P (g(b)), ¬Q(Y, Z) };2. S2 = { P (X, a, f (X, b)) ∨ ¬Q(Y, f (b, Y )), ¬P (f (Y ), Z, Y ), Q(X, Y ) ∨ Q(a, Z) }.Упражнение 1.61. При помощи правила резолюции докажите противоречивость системосновных дизъюнктов1.
S1 = { ¬R, ¬Q, ¬P ∨ R, P ∨ Q ∨ R };2. S2 = { P ∨ Q, ¬P ∨ R, ¬P ∨ Q, ¬R }.1.7Задача унификацииУпражнение 1.62. Докажите, что подстановка θ = {x1 /t1 , x2 /t2 , . . . , xn /tn } является переименованием тогда и только тогда, когда {t1 , t2 , . . . , tn } = {x1 , x2 , . . . , xn }.Упражнение 1.63. Вычислите композицию подстановок θ1 θ2 , где1. θ1 = {x/f (x), y/g(x, z), u/v, v/f (c)}, θ2 = {x/f (y), y/c, z/g(y, v), v/u};2. θ1 = {x/y}, θ2 = {y/z} {z/x}{x/y}.Упражнение 1.64.1. Докажите, что операция композиции подстановок обладает свойством ассоциативности,т.
е. θ1 (θ2 θ3 ) = (θ1 θ2 )θ3 .2. Докажите, что для любой подстановки θ верны равенства θ = θε = εθ.3. Подстановка θ называется обратимой, если существует такая подстановка η, для которой справедливо равенство θη = ε. Докажите, что подстановка θ обратима тогда итолько тогда, когда θ — переименование.1.7. Задача унификации17Упражнение 1.65. Подстановка θ называется идемпотентной, если она удовлетворяет равенству θθ = θ. Докажите, что подстановка {x1 , x2 , . . . , xn } является идемпотентной тогда иnSтолько тогда, когда {x1 , x2 , . .
. , xn } ∩V arti = ∅. Является ли композиция двух идемпоi=1тентных подстановок идемпотентной подстановкой?Упражнение 1.66. Определим на множестве конечных подстановок Subst отношение сравнения следующим образом: подстановка η является примером подстановки θ (обозначаетсяη θ), если существует такая подстановка ρ, для которой выполняется равенство η = θρ.Какими из перечисленных ниже свойств обладает отношение :1.
транзитивность: если θ1 θ2 и θ2 θ3 , то θ1 θ3 ;2. рефлексивность: θ θ;3. антисимметричность: если θ1 θ2 и θ1 θ2 , то θ1 = θ2 ;4. существовует такой наибольший элемент θmax , что η θmax для любой подстановки η;5. существовует такой наименьший элемент θmin , что θmin η для любой подстановки η.Упражнение 1.67. Найти наиболее общий унификатор следующих пар атомарных формул(заглавными буквами обозначены переменные, а прописными — константы и функциональные символы):P (c, X, f (X)),P (f (X, Y ), Z, h(Z, Y )),P (f (Y ), W, g(Z)),P (f (Y ), W, g(Z)),R(Z, f (X, b, Z)),P (X, f (Y ), h(Z, X)),P (a, X, h(g(Z)),P (X1 , X2 , X3 , X4 ),P (c, Y, Y );P (f (Y, X), g(Y ), V );P (U, U, V );P (V, U, V );R(h(X), f (g(a), Y, Z));P (f (Y ), X, h(f (Y ), f (Z)));P (Z, h(Y ), h(Y ));P (f (c, c), f (X1 , X1 ), f (X2 , X2 ), f (X3 , X3 )).Упражнение 1.68.
При каких условиях НОУ(E1 , E2 ) является конечным множеством?Упражнение 1.69. При каких условиях каждый унификатор двух выражений E1 и E2является наиболее общим унификатором?Упражнение 1.70. Пусть θ1 и θ2 — две подстановки, и при этом θ1 ∈ НОУ(E1 , E2 ). Докажите, что θ2 ∈ НОУ(E1 , E2 ) тогда и только тогда, когда существует такое переименованиеη, для которого справедливо равенство θ2 = θ1 η. При каких условиях НОУ(E1 , E2 ) являетсяконечным множеством?Упражнение 1.71. Докажите, что НОУ(E1 , E2 ) = ∅ тогда и только тогда, когда НОУ(E1 θ, E2 η) =∅ для любых примеров E1 θ, E2 η логических выражений E1 и E2 . Приведите пример двухнеунифицируемых выражений E1 и E2 , имеющих унифицируемые примеры E1 θ, E2 η.18Глава 1.
УПРАЖНЕНИЯУпражнение 1.72. Докажите, что если логические выражения E1 и E2 неунифицируемыи при этом V arE1 ∩ V arE2 = ∅, то и любые примеры E1 θ, E2 η логических выражений E1 иE2 также неунифицируемы.Упражнение 1.73. Докажите, что любая подстановка, которую вычисляет алгоритм унификации Мартелли-Монтанари, является идемпотентной (см. упражнение 1.65). Верно ли,что любой наиболее общий унификатор двух атомов A1 и A2 является идемпотентной подстановкой?Упражнение 1.74. Подстановка θ называется унификатором конечного множества атомовM = {A1 , A2 , . .
. , An }, если она удовлетворяет равенству A1 θ = A2 θ = · · · = An θ. Унификаторθ множества атомов M называется наиболее общим унификатором, если любой унификатормножества атомов M является примером θ. Предложите алгоритм вычисления наиболее общего унификатора множества атомов M .Упражнение 1.75. Вычислите наиболее общий унификатор следующего множества атомов:M = { R(h(X), Y, Z), R(Y, h(Z), h(U )), R(h(h(U )), h(c), X) }.Упражнение 1.76.
Пусть M = {A1 , A2 , . . . , An } — произвольное непустое множество атомов. Докажите, что в M существует такая пара атомов Ai и Aj обладающая следующимсвойством: всякая подстановка θ является унификатором множества атомов M тогда и только тогда, когда она является унификатором пары атомов Ai и Aj .Упражнение 1.77. Предложите алгоритм вычисления наиболее общего унификатора двухбескванторных формул логики предикатов ϕ(x1 , x2 , .
. . , xn ) и ψ(x1 , x2 , . . . , xn ).1.8Метод резолюций в логике предикатовУпражнение 1.78. Постройте всевозможные резольвенты следующих пар дизъюнктов (заглавными буквами обозначены предикатные символы и переменные, а строчными — константы и функциональные символы).1. D1 = ¬P (f (X1 , Y1 ), Z, h(Z1 , Y1 )) ∨ R(Z1 , V1 ),D2 = Q(X2 ) ∨ P (f (Y2 , X2 ), g(Y2 ), V2 );2.
D1 = P (X1 , Y1 , h(Y1 , X1 )) ∨ R(Y1 , f (X1 )),D2 = ¬P (X2 , f (X2 ), h(X2 , Y2 )) ∨ ¬P (Y2 , g(X2 ), h(Y2 , Y2 ));3. D1 = ¬R(X1 , Y1 , X1 ) ∨ ¬P (X1 , Y1 , Y1 ) ∨ R(X2 , X2 , X2 ),D2 = R(g(X2 , Y2 ), X2 , Y2 ) ∨ R(c, Z2 , f (Z2 , Z2 ));4. D1 = ¬Q(X, Y ) ∨ ¬Q(Y, X),D2 = Q(U, V ) ∨ Q(V, U ).Упражнение 1.79. Постройте склейки следующих дизъюнктов.1.8. Метод резолюций в логике предикатов191. ¬P (f (X)) ∨ R(Z, V ) ∨ P (X);2. P (X) ∨ Q(f (X)) ∨ P (a) ∨ Q(f (a));3.
¬Q(X, f (X)) ∨ ¬Q(Z, Z) ∨ ¬Q(a, Z).Упражнение 1.80. Построив резолютивный вывод, доказать противоречивость следующихмножеств дизъюнктов.1. S = {D1 , D2 , D3 , D4 , D5 }D1D2D3D4D5=====P (X, f (X)),R(Y, Z) ∨ ¬P (Y, f (a)),¬R(c, X),R(X, Y ) ∨ R(Z, f (Z)) ∨ ¬P (Z, Y ),P (X, X).=====¬E(b, U ),H(U, g(U )),H(U, U ),E(U, V ) ∨ ¬H(U, g(a)),E(U, V ) ∨ E(Z, g(Z)) ∨ ¬H(Z, V ).2. S = {D1 , D2 , D3 , D4 , D5 }D1D2D3D4D53.
S = {D1 , D2 , D3 , D4 , D5 , D6 , D7 }D1D2D3D4D5D6D7=======E(x) ∨ V (y) ∨ C(f (x)),E(x) ∨ S(x, f (x)),¬E(a),P (a),P (f (x)) ∨ ¬S(y, x),¬P (x) ∨ ¬V (g(x)) ∨ ¬V (y),¬P (x) ∨ ¬C(y);4. S = {D1 , D2 , D3 , D4 }D1D2D3D4Упражнение 1.81.формул.====P (y, f (x)),¬Q(y) ∨ ¬Q(z) ∨ ¬P (y, f (z)) ∨ Q(v),Q(b),¬Q(a);Используя метод резолюций, обосновать общезначимость следующих1. ∃x P (x) → ¬∀x ¬P (x);2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
