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

имеется х, для которого Р(х). Рассмотрим следующие часто встречающиеся предложения и справа от них приведем их символическую запись: {А) все 5 суть Р ~ \lx{S{x) =>Р(х)); {Е) ни одно 5 не есть Р - \fx(S(x) =>1 Р(х)); (Г) некоторые 5 суть Р - 3x{S{x)&P(x))\, (О) некоторые 5 не есть Р - Зл;(5'(х)&1 Р(х)). Символизация приведенных предложений позволяет записывать в символическом виде довольно сложные выводы, использующие все- возмоясные комбинации предложений (А)--(О). До сих пор мы рассматривали приписывание кванторов к одно­ местным предикатам. Далее рассмотрим приписывание кванторов к многоместным предикатам. Пусть Р(хьх2,...,х„) - и-местный (п>2) пре­ дикат, заданный на множестве М. Выражение Vx,p(xb^2,,..,x „), 1 < г< п, (2.1) является (и-1)-местным предикатом, зависящим от (свободных) переменных x\,x2,...,xi.i,xn \,...,Хп, причем высказывание \/хiP(Q\,Cl2, >., ,С1 i.\iX [jCl n) истинно тогда и только тогда, когда для любого значения ai^M истинно высказывание Р(аьа2.-,а/-1.«л«,+ 1.••,«»)• (2-2) Выражение 3ix,p{x\,x2,.,.,x „), \ < i< п, (2.3) является (и-1)-местиым предикатом, зависящим от (свободных) пере- менныхл'ьХ2,..,,Х/.ьл:,+ь--..'^н> причем высказывание истинно тогда и только тогда, когда существует такое значение а„ (а,6Щ переменной Xj, для которого высказывание (2.2) истинно. Также положим, что если Р - нульместный Предикат (высказы­ вание), то записи VxP и ЗхР означают то же, что и Р. 51