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

2) Vx(^D(x,2)& -nD(x,3) =>P(x)): 3) \/x(P(x)^ —iD(x,2)v—iD(x,3)); 4) Vx(D(x,y))^^(2)&^(3)); 5) Vx(P(x)^^D(x,2)&^D(x,3)). 5. Формула (3xP(x))&P(y) в интерпретации: М={...,-2,-1,0,1,2,...}, P(x): <a-простое число» является 1) выполнимой; 2) логически общезначимой; 3) ложной; 4) противоречием; 5) истинной. 6. Формула —i3c VyA равносильна формуле: 1) 3c\/^ —iA; 2) УхБу—Л; 3) \/х\/у—Л; 4) УхВуА; 5) УхУуА. 7. Формула -^((ЭхА)& VxD) равносильна формуле: 1) (Зх^А)& Vx —D; 2) (\/ х—Л) v3c —iD; 3) ( ЗсA)^\/x —D; 4) (Vx А)=3c —D; 5) (\/ х—А)&ЗсD. 8. Предваренная нормальная форма для формулы \/уА(у)^ Vx3zB(x,z) равна: 1) VyVx3z( —A(y)vB(x,z)), 2) Vy3xVz(—A(y)vB(x,z)), 3) Зу Vx3z( —A(y) vB(x,z)), 4) ВуВх Vz(-^(y) vB(x,z)), 5) BzVy Vx(-^(y) vB(x,z)). 9. Пусть формула/! не содержит вхождений переменнойх. Какая из следующих формул не является логически общезначимой? \) Зх VyD(x,y)^ Vy3xD(x,y); 2) (А vVxB(x))=Vx(A vB(x)); 3) (А&ЗхВ(х))=Зх(А&В(х)); 4) ((ЗхВ(х)) vBxC(x))=Bx(B(x) vCfxJJ; 5) Vy3xD(x,y)^3xVyD(x,y). 10. Формула -^BxVy3zVuA равносильна формуле: \) Зх Vy3z Vu —А; 2) Vx3y Vz3u А; 2) VxVyVzVu —А; 4) Vx3y Vz3u —A; 5) VxVyBzVuA. Teem no логичеекому еледетеию и методу резолюций (тест Ж» 3) 1. Произвольная формула В является логическим следствием формулы А тогда и только тогда, когда \)А^В - тавтология; 2)А^В - выполнимая формула; 3) А^В - противоречие; 4) А&В - тавтология; 5)AvB- тавтология. 2. Если С является логическим следствием А я В, тогда при любых А, ВжС \)AvBvC- тавтология; 2) А&В^С - противоречие; 248