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

д) Зх Vy(B(y)^A(x,y)). 22. Пусть формула В не содержит свободных переменных, а Р(х) - одноме­ стный предикат. Для области М, состоящей из двух элементов, построить таб­ лицы истинностных значений формул: а) VxB; б) ЗхВ', в) VxP(x); г) ЗхР(х); д) Vx(P(x )^B); о) Зх(Р(х)^В); ж) Vx(P(x )^B )=3cP(x )^B; з) 3c(P(x )^B )=VxP(x )^B. 23. Предикат Р(х,у) задан на множестве целых положительных чисел бес­ конечной таблицей, в которой значения И стоят в первой строке. х/>' 1 2 3 4 5 1 И И и и И 2 И и л л л 3 И л и л л 4 и л л и л 5 и л л л и первом столбце и по диагонали. Выясните, при каких значениях х, у, z следую­ щие формулы принимают значения И: а)Р(х,4); 6) P(x,2)&P(z,5); в) P(x,y)&P(z,5); т) P(x,y)&P(x,z). 24. Пусть предикат Р(х,у) тот же, что и в предыдущей задаче. Выясните, при­ нимают ли значение И следующие формулы: а) 3cVyP(x,y); Q) ЗсР(х,х); в) Vx3yP(x,y)-, г) VxVyP(x,y); д) VxVyP(x,y)^VyP(5,y); Q) 3c(VyP(y,y)^P(x,x)); ж) \/хР(х,2); з) ЗуР(3,у). 25. Истинна ли формула ЗхА \( х ) ^ V j H/( у )\ а) для произвольной одноэлементной области; б) для произвольной двух­ элементной области? 26. Перед следующими предикатами, определенными на множестве всех действительных чисел, поставьте соответствующие кванторы так, чтобы полу­ чить истинное высказывание; а)х^=27; б)х+7>7; в)ху=4; т)х-у^); fl)x+y=z; е) fx>y>OJ^fx>OJ. 27. Выясните, выполнима ли формула Vx3yP(x,y,z) в интерпретации: М=(- оо, оо); P(x,y,z):x+y<z. Является ли эта формула истинной для данной интерпретации? 28. Для формулы VxP(x,y)^P(y,y) найдите интерпретацию, в которой эта формула выполнима. 29. Истинна ли формула VxP(x,y)^ Р(у,у) на произвольной двухэлемент­ ной области? 56