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

Приведенные примеры показывают, что нужно тщательно проводить со­ держательный анализ при записи символьных выражений, чтобы правильно пе­ редать смысл и не выхолащивать содержание. До сих пор мы рассматривали приписывание кванторов к одноместным предикатам. Далее рассмотрим приписывание кванторов к многоместным пре­ дикатам. Пусть P (xi,x2,...,xrj - и-местный (п>2) предикат, заданный на множест­ ве Ж Выражение VxiP(xi ,X2 ,...,Xn), 1 < i < п, ( 2 . 1 ) является -местным предикатом, зависящим от (свободных) переменных Xi,X2,...,Xi.i,Xi+i,...,Xn, причем высказывание VxiP(ai,a2,...,a i.i,x i,a i+i,...,a п) истинно тогда и только тогда, когда для любого значения М истинно высказывание P(aj ,a2 ,...,a i-l I ^ i+1J ••• J ^ nj • (2.2) Выражение 3xiP(xi,X2,...,Xr), 1 < i < n, (2.3) является -местным предикатом, зависящим от (свободных) переменных xi,x2,...,x i .i,x i +i,...,x п, причем высказывание 3ciA(ai,a2,...,a i .i,x i,ai+i,...,aп) истинно тогда и только тогда, когда существует такое значение <2/, (й(/е Ж) переменной Х/, для которого высказывание (2.2) истинно. Также положим, что если Р - нульместный предикат (высказывание), то записи VxP и ЗсР означают то же, что и Р. Приписывание (навешивание) квантора по переменной х связывает пере­ менную X. Приписывая к -местным предикатам (2.1) и (2.3) любой квантор по любой из переменных, по которой еще не записан квантор, получим (п-2)- местные предикаты (если п=2, то просто высказывание). Ясно, что к получен­ ным предикатам можно снова приписать произвольные кванторы и т.д. Оче­ видно, что, приписав кванторы по всем переменным, получим высказывание. Например, пусть на множестве действительных чисел задан трехместный пре­ дикат х^ + > z^, который можно превратить в двуместный предикат, записав 2 2 2 2 2 2 квантор Vz(x + у >z ), или в одноместный предикат Vy Vz(x + у >z), или же в высказывание: VxVyVz(x^ +у^ >z^). (2.4) Можно получить и другие высказывания, например: 3xVyVz(x^ +у^ >z^), (2.5) VxVy3z(x^ +у^ >z^) (2.6) и т.д. Ясно, что высказывание (2.6) истинно, а (2.4) и (2.5) - ложные. Пусть множество М состоит из конечного числа элементов. Для опреде­ ленности положим М= {а1,02,...,On] и пусть Р(х) - заданный на одноместный предикат. Тогда, очевидно, имеем: 32