Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

а) { Q{a,x,g(f{x))), Q{z,f{y),f(y))}; б) {P(f{x),a), Р{уА^))}; в) {P(fix),z), Piy,a)] г) {Pifia),gix)), P(y,y). 25. Найти общий унификатор для следующего множества формул: {P(a,x,f(g(y))), P(z,f(z),f(u))}. 26. Пусть задано 27. Дано множество формул: { Vx(P(x)^(Q(x)&R(x))), 3c(P(x)&S(x))}. Методом резолюций выяснить, будет ли формула 3c(S(x)&R(x)) логиче­ ским следствием из заданного множества формул. 28. Дано множество дизъюнктов: {Р(а), Е(а), —iS(a,y) vP(y), - пР(х) v —iR(x), —Р(х) v —iC(y), —iE(x) vR(x) vS(x,f(x)), -nE(x)vR(x)vC(f(x))}. Лок-резолюцией показать, что данное множество дизъюнктов не выполни­ мо. 29. Дано множество формул: {Зс(Р(х)& Vy (Q(x)^R(x,y))), Vx(P(x)^Vy(S(y)^^R(x,y)))]. Методом резолюций выяснить: будет ли формула Vx(Q(x)^ —^S(x)) логиче­ ским следствием из заданного множества формул. 30. Методом резолюций показать, что формула Vx(3yS(y)&V(x,y)) 3z(C(z)&V(x,z))) является логическим следствием формулы Vy(S(y)^>C(y)). 31. Докажите при помощи метода резолюций: а) {3x{P{x)8iVy{R{x,y) Q{x,y))\ Vx{P{x)^ Vy{S{y) ^-^Q{x,y)))] h Vx{R{x,y) —iS{x))); б) { Vx{P{x)^Q{x)&R{x))), 3x{P(x)&S{x)) |=^ )& Q{x)). 32. С помощью метода резолюций установить, правильны ли следующие силлогизмы (модусы) Аристотеля: Barbari, Ferio, Baroco. Напомним, что глас­ ные, участвующие в приведенных названиях силлогизмов, определяют вид сил­ логизма, см. параграф 10. 33. Вводя подходящие обозначения, записать в виде формул предложения, участвующие в следующих выводах, и выяснить, в каких случаях конъюнкция посылок логически влечет заключение. Результаты проиллюстрировать диа­ граммами Эйлера-Венна: 1) некоторые А суть В. Ни одно В не есть не С. Следовательно, некоторые А суть С; 2) все А суть В. Ни один С не есть не В. Следовательно, ни один С не есть 3) некоторые А суть не В. Все не С суть В. Следовательно, некоторые А суть С; 4) все А суть В. Ни один С не есть В. Следовательно, все А суть не С; 95