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

30. Истинна ли формула VxP(x,x)^Vx3yP(x,y) на произвольной двухэле­ ментной области? 31. Покажите, что формула Vx3yA(x,y)^Vy3xA(x,y) не является логически общезначимой. Выполнима ли эта формула? 32. Найдите интерпретацию с областью, состоящей из двух элементов, в которой формула ЭхЭуР(х,у) была бы истинной, а формула Vx3yP(x,y) - лож­ ной. 33. Покажите, что формула VxA(x) А(а) является логически общезначи­ мой. 34. Покажите, что формула ВхВу(А(х) & —AfyJJ выполнима только на об­ ласти интерпретации содержащей не менее двух элементов. 35. Покажите, что формула Vx(A(x) В(х)) {VxA(x)^VxB(x)) является логически общезначимой, а обратная импликация уже не является логически общезначимой. 36. Постройте интерпретацию в которой ложна формула ЗхА(х)^А(а). 37. Является ли выполнимой формула Vx(P(x,y,z)^P(y,x,z))l 38. Докажите, что если формула логики предикатов А, содержащая сво­ бодно только переменную х, является логически общезначимой, то: а) формула VxA также является логически общезначимой, и обратно; б) формула ЗхА также является логически общезначимой. Верно ли обрат­ ное? 39. Каким формулам равносильны формулы: а) Vx3xP(x); 6) Зс\/хР(х); в) VxP(y); т) ЗхР(у). 40. Доказать: а) если формула логики предикатовА ^ В является логически общезначи­ мой, то формулы VxA^VxB и ВхА^ВхВ также являются логически общезна­ чимыми; б) если формула логики предикатов А=В является логически общезначи­ мой, то формулы VxA=VxB и ВхА=ВхВ также являются логически общезначи­ мыми. 41. Показать, что формула Vy(P(x) v —P(y)) является истинной для одно­ элементной области и только для нее, здесь Р является одноместной предикат­ ной буквой. 42. Докажите, что формула BxVyA^VyBxA является логически общезна­ чимой. 43. Является ли выполнимой формула Зх VyP(x,y)^Vy3xP(f(x),y)l Будет ли эта формула логически общезначимой? 57