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

44. 1) Являются ли истинными, ложными или выполнимыми для произ­ вольной двухэлементной области следующие формулы (Л и в не содержат сво­ бодных переменных, а Р является одноместной предикатной буквой): а) 3x(A^P(x))^A^VxР(х)), б) 3c(P(x)^B)^VxР(х)^В), в) Vx(P(x)^B)^3c Р(х)^В), г) Vx(A^P(x))^A^Vx Р(х)). 2) Являются ли формулы а) - г) логически общезначимыми или нет? 45. Являются ли выполнимыми следующие формулы: а) VxVyVz(A(x,x)&(A(x,z)^A(x,y)vA(y,z))) =^3xVyA(x,y); б) Vx3y Vz(A(x,x)&А(у,х)&(A(y,z))^A(x,y))). 46. Пусть A не содержит свободных переменных, Р, Q - одноместные пре­ дикатные буквы. Выясните, являются ли логически общезначимыми следую­ щие формулы: \) A&\/xQ(x)=\/x(A&Q(x)); 2) A&3xQ(x)=3x(A&Q(x))\ 3) VxP(x)&VxQ(x)=Vx(P(x)&Q(x))-, 4) \/xP(x)v\/xQ(x)=\/x(P(x)vQ(x)); 5) \/xP(x)v\/xQ(x)^\/x(P(x)vQ(x)); 6) 3cP(x)&3cQ(x)=3c(P(x)&Q(x)); 7) 3cP(x) v3xQ(x)=3x(P(x) vQ(x)); 8) 3x(P(x)&Q(x))^3xP(x)&3xQ(x). 47. Пусть A не содержит свободных переменных Р, Q - одноместные пре­ дикатные буквы. Какие из следующих формул являются логически общезначи­ мыми: 1) \/х(Р(х)^А)^ЗсР(х)^А); 2) Зс(Р(х)^А)^ЗсР(х)^А); 3) 3x(P(x)^A)^VxP(x)^A); А) Зх(А^Р(х))^А^ЗхР(х))1 48. Какие из приведенных формул являются выполнимыми, а какие из них логически общезначимыми {Р, Q - одноместные предикатные буквы): 1) 3c(P(x)^>Q(x))=\/xP(x)^3cQ(x); 2) 3c(P(x)^>Q(x))=\/x(P(x)& —i3cQ(x)); 3) (VxP(x)^VxQ(x))^Vx(P(x)^Q(x))-, 4) Vx(P(x)vQ(x))^(VxP(x))vVxQ(x))l 49. Являются ли равносильными следующие пары формул {Р, Q - одноме­ стные предикатные буквы, А - произвольная формула, имеющая указанные ар­ гументы): а) \/xP(x)^\/xQ(x) я VxP(x)^VyQ(y)-, 6) VxA(x,y) и VxA(a,y)\ в) ^ Vx(^P(x)^(x)) и ^ Vx(^P(x)^(y)); г) VxVy(P(x)vQ(y)) и VxVy(P(y)vQ(x)); д) Vx(P(x)&Q(x)) и (VxP(x))&Q(x); о)А(х,а) и А(у,а). 50. Пусть Л = Ai & A2&A2, где: AI = Vx3yP(x,y), А2 = VX —P(X,X), Л з = VxVyVz(P(x,y)&P(y,z) ^P(x,z)). а) Покажите, что формула А выполнима в бесконечной области интерпретации, б*) Покажите, что формула А не выполнима в конечной области интерпрета­ ции. 58