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

51. Для следующих формул найдите равносильные формулы, в которых отри­ цание относится только к элементарным формулам: а) Vx^(By(A(x)^B(y)))\ б) —i3x(VyA(x,y,z)^3uB(x,u))&Vt—i Vv(C(t) vD(v)); в) —1 Vx3z(A(x)^lB(z))-, г) ^—1 Vx(A(x)&B(y))^^3zC(x,y,z). 52. Пусть A(x,y) двухместный предикат на множестве всех вещественных чисел. Через МА обозначим область истинности предиката А(х,у), т.е. множество тех точек (х,у) плоскости R , для которых А(х,у)=И. Рассмотрите предикаты \/хА(х,у) и \/х—Л(х,у) и выясните, как связаны области истинности этих преди­ катов с множеством МА 53. 1) Привести к предваренным нормальным формам формулы из предыдуще­ го упражнения. 2) Приведите к предваренным нормальным формам следующие формулы: а) Vx(A(х)=>В(х,у)) =>((БуА(у)) ^3zB(y,z)); б) BxB(x,y)^(A(x)^^3zB(x,z))\ в) Vx(Vy3zC(x,y,z)^A(x))^VxA(x)\ г) -^ВхА(х)^VzBy VxC(x,y,z). 54. Приведите к предваренным нормальным формам следующие формулы: а) БхА(х) =^VxB(x); б) VxA(x) =^ЗхВ(х); в) VxVy(3z(A(x,y)&B(y,z)) ^3vC(x,y,v)); г) Vx(A(x) =^ЗуВ(х,у)); д) Зх(А(х) ^VyB(x,y)); е) Зх(^(ЗуА(х,у)) ^(3zB(z) =^(х))); ж) Vx3y(VzA(x,y,z)&(3uB(x,u) =^3vC(y,v))).