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

42. Какие из приводимых далее формул являются выполнимы­ ми, а какие из них логически общезначимыми (Р, Q - одноместные предикатные буквы); 1) 3x{P{x.)=>Q{x))sVxP{x)=>3xQ(x)', 2) Зд:(Р(х)=>2(х))^Уд:(Р(д:)&1 Зхе(х)); 3) {\/xP(x)=^\/xQ(x))-=>\/x{P{x)-=> Q{x))\ 4) \/x{P{x)wQ{x))-=^{\/xP{x))\/\fxQ{x)). 43. Выяснить, являются ли равносильными следующие пары формул {Р, Q - одноместные предикатные буквы, А - произвольная формула, имеющая указанные аргументы): а) VxP(x)=^Vxg(jc) и \/xP{x)-=^yyQ{y)\ б) VxA{x,y) и \/хА{а,у); в) 1VJC(1 P(x)=>Q(X)) И 1VX(1 P{X)=>Q(}')); г) ' •^x\/y{P(x)vQ(y)) и \/x'^y(P(y)vQ(x)); д) \/xP(x)&Q(x) и \/xP(x))&Q(x); е)А(х,а) wA{y,d). 44. Для следующих формул найти равносильные формулы, в которых 1 относится только к элементарным формулам: а) Vxl(3_y(^(x)=>-B(y))); б) 1Эд:(VjM (x,y,z)=>3 иВ(х, м))&VЛVv(C(?)vi)(v)); в) 1\/д:Зг(И[(.х)=>1В(г)); г) 3;'lVx(H[(x)&5(>'))=:^>l3zC(xj',2), 45. Пусть А(х,у) - двухместный предикат на множестве всех ве­ щественных чисел. Через МА обозначим область истинности предика­ та J(x,y), т,е. множество тех точек (x,>') плоскости для которых А(х,у)=И. Рассмотреть предикаты VxA(x,y) и Vxl А(х,у) и выяснить, как связаны области истинности этих предикатов с множеством МА Формула Q]X\Q2X2...QnXiJS, где QjXj - квантор всеобщности или существования, Xi и xj различны, если и Л не содержат кванторов, называется формулой в предваренной нормальной форме (иногда - 87