Сборник задач для самостоятельных занятий, страница 4

Верно ли, чтоинтерпретации 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. ∃x ∀y R(x, y) → ∀y ∃x R(x, y);20Глава 1. УПРАЖНЕНИЯ3. ∀x (P (x) → ∃y R(x, f (y))) → (∃x ¬P (x) ∨ ∀x∃zR(x, z));4. ∀x ∃y ∀z (P (x, y) → P (y, z));5. ∃x ∀y ∃z (P (x, y) → P (y, z));6.

∃x∀y(∀z(P (y, z) → P (x, z)) → (P (x, x) → P (y, x)));7. ∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x));8. ∀x(P (x, x) → (R(x) → ∀x(∀xP (x, x)&R(x))));9. ∃x((∀yP (x, y) ∨ ∃xR(x)) → (∃xP (x, x) ∨ R(x)));10. ∃x(∃y¬P (x, y) → ∀xR(x)) → ∀x(R(x) ∨ ∃xP (x, f (x)));11. ∀x(∀y∃v∀u((A(u, v) → B(y, u))&(¬∃wA(w, u) → ∀wA(w, v))) → ∃yB(x, y));12. ∀x∃u(∃v∀y((E(u, y) → H(y, v))&∃w∀x(H(w, y) → ¬H(x, v))) → ∃y¬E(x, y)).Упражнение 1.82. Докажите, что резолютивный вывод обладает переключательным свойством, которое формулируется так (см. рис.

1.1).Предположим, что дизъюнкты D1 , D2 имеют резольвенту D0 , и дизъюнкты D0 и D3имеют резольвенту D. Тогда один из дизъюнктов Di , i ∈ {1, 2}, и дизъюнкт D3 имеют резольвенту D00 , а дизъюнкты D00 и D3−i имеют резольвенту D0 , которая является вариантомдизъюнкта D.Упражнение 1.83.

Введя необходимые предикаты, запишите формулы логики предикатов,выражающие следующие суждения:«Если в стране есть хоть какие-нибудь граждане, то все политики являются гражданами этойстраны».«А если где-то в мире и есть честные люди, то все граждане страны — честные люди».Используя метод резолюций, докажите, что из этих утверждений следуют выводы:1.