1. Доказать с помощью метода резолюций, что формула G есть логическое следствие формул F₁,…F_n:

а) F₁=XÚY, F₂=X®Z, G=(Y®Z)®Z;

б) F₁=X, F₂=X&Y®Z, G=Y®Z;

в) F₁=X®YÚZ, F₂=Z®W, F₃=ØW, G=X®Y;

г) F₁=XÚYÚØZ, F₂=X®X1, F₃=Y®Y1, F₄=Z, G=X1ÚY1;

д) F₁=X&Y® ØX&Z, F₂=Ø(X&ØY)ÚZ, G=X®Z;

e) F₁=X®[ØY&(ØY®Z)], F₂=(X® ØY)&Ø(ØX&ØW), G=WÚZ.

2. Запишите следующие рассуждения в виде последовательности формул логики высказываний. Если рассуждение логично, то докажите это методом резодлюций; если нелогично, то постройте интерпретацию, при которой посылки истинны, а заключение ложно.

2.1. Если конгресс отказывается принять новые законы, то забастовка не будет окончена, кроме случая, когда она длится более месяца и президент фирмы уйдет в отставку. Допустим, что конгресс отказывается действовать и забастовка заканчивается. Следовательно, забастовка длилась более месяца.

2.2. Если подозреваемый совершил эту кражу, то она была тщательно подготовлена или он имел соучастника. Если бы кража была тщательно подготовлена, то если бы он имел соучастника, был бы украден дорогой компьютер. Компьютер остался на месте. Следовательно, подозреваемый невиновен.

2.3. Рассуждение из задачи 2.1 темы 1.

2.4. Рассуждение из задачи 2.2 темы 1.

2.5. Рассуждение из задачи 2.3 темы 1.

3. Пусть s=(x₁=f(x₂),x₂=d,x₃=f(x₁)) – подстановка, F=P(x₁,f(x₂))ÚØØQ(x₃), G=P(x₃,x₂)ÚR(x₁,g(x₂)). Найти s(F) и s(G).

4. Определить, унифицируемы ли следующие множества атомарных формул:

а) M={P(a,y,y), P(z,x,f(x))},

б) M={P(x,y,z), P(u,h(y,y),y), P(a,b,c)},

в) M={P(a,f(x),g(x,y)), P(u,y,g(f(a),h(y))}?

5. Определить, имеют ли следующие дизъюнкты склейки. Если имеют, то найти их:

а) P(x)ÚP(a)ÚQ(f(x)),

б) P(x)ÚQ(f(x))ÚP(f(x)),

в) P(a)ÚP(b)ÚP(x).

6. Найти все возможные резольвенты (если они есть) следующих пар дизъюнктов:

a) C=ØP(x)ÚQ(x,b), D=P(a)ÚQ(a,b),

б) C=ØP(x)ÚQ(x,x), D=ØQ(a,(a)),

в) C=ØP(x)ÚØØP(a)ÚØQ(y,f(b)), D=P(u)ÚQ(c,f(v)).

7. Найти Н₀,Н₁,Н₂, если

а) S={P(f(x),a), ØP(y,g(x))},

б) S={P(a,g(x)), P(u,b)},

в) S={P(x,y), P(h(u,v),z)}.

8. Построить замкнутое семантическое дерево, если

а) S₁={P,ØPÚQ,ØQ},

б) S₂={P(x),ØP(f(y))},

в) S={P,QÚR,ØPÚØQ,ØPÚØR}.

9. Найти невыполнимое множество S_i^/ основных примеров дизъюнктов множества S_i (1£i£3), если

а) S₁={P(x,a,g(x,b)), ØP(f(y),z,g(f(a),b)},

б) S₂={P(a),ØD(y)ÚL(a,y),ØP(x)ÚØQ(y)ÚØL(x,y), D(b),Q(b)},

в) S₃={ØK(x,y)ÚØØL(y)ÚM(f(x)),ØK(x,y)ÚØL(y)ÚN(x,f(x)),ØM(z),K(a,b),L(b)}.

10. Доказать с помощью метода резолюций, что формула G есть логическое следствие формул F₁,…,F_k:

а) F₁=("x)(P(x)®Q(x)&R(x)), F₂=($x)(P(x)&T(x)), G=($x)(R(x)&T(x)),

б) F₁=("x)[($y)(M(y)&S(X,y))®($z)(I(z)&E(x,z))], G=Ø($x)I(x)®("u)(""v)(S(u,v)®ØM(v)).

в) F₁=("x)[P(x)®($y)(Q(y)&S(x,y))], F₂=($x)[R(x)&(""y)(Q(y)®ØS(x,y))], F₃=($x)P(x), G=($x)(ØP(x)ÚR(x)).

11. Используя метод резолюций в логике предикатов, докажите логичность следующих рассуждений.

11.1. Все студенты нашей группы – члены клуба «Спартак». А каждый член клуба «Спартак» занимается спортом. Следовательно, все студенты нашей группы занимаются спортом.

11.2. Все студенты нашей группы – болельщики «Спартака», а некоторые занимаются спортом. Следовательно, некоторые из болельщиков «Спартака» занимаются спортом.

11.3. Некоторые пациенты любят сврих докторов. Ни один пациент не любит знахаря. Следовательно, никакой доктор не является знахарем.

11.4. Если деталь обрабатывалась на токарном станке, то она обрабатывалась и на фрезерном. Деталь D1 обрабатывалась на токарном станке С1. Следовательно, она обрабатывалась на фрезерном станке.

12. Будут ли логичны следующие рассуждения? Если логичны, то доказать это методом резолюций. Если нет, то построить интерпретацию, при которой посылки истинны, а заключение ложно.

12.1. Если кто-нибудь может решить эту задачу, то и любой математик может ее решить. Олег – математик, но не может решить эту задачу. Следовательно, задачу не сможет решить никто.

12.2. Всякий, кто может решить эту задачу – математик. Олег – математик, но не может решить эту задачу. Следовательно, задачу не может решить никто.

12.3. Если кто-нибудь может решить эту задачу, то и какой-нибудь математик может ее решить. Олег – математик, но не может решить задачу. Следовательно, задачу не может решить никто.

12.4. Некоторые из первокурсников знакомы со всеми спортсменами института. Ни один первокурсник не знаком ни с одном любителем подледного лова. Следовательно, ни один спортсмен не является любителем подледного лова.

12.5. Каждый из первокурсников знаком с кем-либо из спортсменов. Некоторые из первокурсников не знакомы ни с одним любителем подледного лова. Следовательно, ни один спортсмен не является любителем подледного лова.