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

27. Выяснить, выполнима ли формула \ix3yP{x,y^) в интерпре­ тации: Л/=(-оо,оо); Р(х,у^) :x+y<z; является ли эта формула истинной для данной интерпретации? 28. Для формулы \/ХР{Х,У)=>Р(УУ) найти интерпретацию, в кото­ рой эта формула выполнима. 29. Истинна ли формула \fхР{х,у):::^Р(уУ) на произвольной двух­ элементной области? 30. Показать, что формула \/хЗуА{х,у)=>\/уЗхА{х,у) не является логически общезначимой. Выполнима ли эта формула? 31. Является ли выполнимой формула \fy\/x{p{x,y^):=>p(y,x,zyp. 32. Доказать, что, если формула логики предикатов А, содержа­ щая свободно только переменную х, является логически общезначи­ мой, то формула \/хА также является логически общезначимой, и обратно. Обобщить сформулированное утверждение на формулы, содержащие любое конечное число свободных переменных. 33. Если формула логики предикатов содернсащая только сво­ бодную переменную х, является логически общезначимой, то 3x4 таюке является логически общезначимой. Верно ли обратное? 34. Доказать; а) если формула логики предикатов является логически общезначимой, то формулы VjCi4=^VxB и ЗУА=!>ЗХВ также являются логически общезначимыми; б) если формула логики предикатов AsB является логически общезначимой, то формулы \/хА=\/хВ и ЗхА=ЗхВ также являются ло­ гически общезначимыми, 35. Показать, что формула V^:V>'(P(^:)v1 Р(у)) является истинной для одноэлементной области и только для нее, здесь Р является одно­ местной предикатной буквой. 85