Математическая логика и теория алгоритмов

36. Докажите, что формула ЗхУуА:=>\^уЗхЛ является логически общезначимой. 37. Является ли выполнимой формула Ъх\/уР{х,у):=>\/уЗхР{({х),уУ> Будет ли эта формула логически общезначимой? 38. 1) являются истинными, ложными или выполнимыми для произвольной двухэлементной области следующие формулы (/4 и В не содержат свободных переменных, а Р является одноместной преди­ катной буквой): а) Зх(А=> Р(х))={А=>\/х P(x)); б) Зх{Р{х)-=^В)={\/х Р(х)-=^в в) Vx(P(x)=?fi)s(3x Р(.х)=>В); г) P(x))s{A:=i>\fx Р{х)); 2) являются ли формулы а) - г) логически общезначимыми или нет? 39. Являются ли выполнимыми следующие формулы; а) V^:yyVz(^(x,x)&(^(x,z)=>^(3:,>')v^(;y,z))) =^Зх\/уА{х,уУ, б)ухзу\/2{а(х^)&\4(у;х)&{а(у,2у)=>а{х^)у). 40. Пусть А не содержит свободных переменных (Р, Q - одно­ местные предикатные буквы). Выяснить, являются ли логически общезначимыми следующие формулы: 1) Л&Ухб(д:)=Уд:(Л&е(;с)); 2) A8l3 X Q(x)=3x{A&Q(x)); 3) \fxP(x)&\/xQ(x)=\/x(P{x)ScQ{x)); 4) VxP(x)vVxQ(x)^Vx(P(x)vQ(x)); 5) VxP(x)vVxQ(x)=>Vx(P(x)vQ(x)); 6) 3xP(x)&3xQ(x)s3xfP(x)&Q(x)); 7) 3xP(x)v3xQ(x)=3x(P(x)vQ(x)); 8) Зх(Р(д:)&^(л:))=з>Э xP(x)&3xQ(x). 41. Пусть A не содержит свободных переменных (Р, Q - одно­ местные предикатные буквы). Какие из следующих формул являются логически общезначимыми: 1) '^х{Р(х)=>АМЗхР(х)=>А)1 2) 3x(P(x)=>A)s(3xP{x )=>Ay, 3) Зх(Р(х)-=^А)=(\/хР(х)=>АУ, 4) 3x(A-=^P(x))s(A=>3xP(x)) 86