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

Приписывание (навешивание) квантора по переменной х связы­ вает переменную х. Приписывая к (п-1)-местным предикатам (2.1) и (2.3) любой квантор по любой из свободных переменных, получим (п-2)-местные предикаты (если п=2, то просто высказывание). Ясно, что- к полученным предикатам можно снова приписать произвольные кванторы и т.д. Очевидно, что, приписав кванторы по всем перемен­ ным, получим высказывание. Например, пусть на множестве дейст­ вительных чисел задан трехместный предикат + У > z^, который можно превратить в двуместный предикат, записав квантор; Vz(x + у к Z ), или в одноместный предикат \/y \fz (x + у ^ z"). или же в высказывание; \/хУуУг(х^ + у^> 2^). (2.4) Можно получить и другие высказывания, например; 3xVyVz(x^+y>z^), (2.5) VxV)'3z(x^ + У S: z^) (2.6) и т.д. Ясно, что высказывание (2.6) истинно, а (2.4) и (2,5) - ложные. Упражнение. Пусть на множестве Ж задан трехместный пре­ дикат P(x,y,z). Определить, какое число одноместных предикатов можно получить из P(x,y,z), приписывая к нему различные кванторы. Пусть множество М состоит из конечного числа элементов. Для определенности положим !М= {а\,а2,...,С!п} и пусть Р{х) - заданный на ! ¥ одноместный предикат. Тогда, очевидно, имеем; \/хР(х) равносильно Р(а\)8сР{а2)&...&Р{а„), (2.7) ЗхР{х) равносильно P(ai)vP (a2 )v...vP(a „). (2.8) Следовательно, квантор всеобщности является обобщением (аналогом) конъюнкции, а квантор существования - обобщением (аналогом) дизъюнкции на произвольное, не обязательно конечное, множество. 52