Математическая логика - Логика предикатов

Понятие предиката

В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

Определение 18.1. Определенным на множествах $M_1,M_2,\ldots,M_n$ n-местным предикатом называется предложение, содержащее $n$ переменных $x_1,x_2,\ldots,x_n$ , превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств $M_1,M_2,\ldots,M_n$ соответственно.

Для n-местного предиката будем использовать обозначение $P(x_1,x_2,\ldots,x_n)$ . Переменные $x_1,x_2,\ldots,x_n$ называют предметными, а элементы множеств $M_1,M_2,\ldots,M_n$ , которые эти переменные пробегают, — конкретными предметами. Всякий n-местный предикат $P(x_1,x_2,\ldots,x_n)$ , определенный на множествах $M_1,M_2,\ldots,M_n$ , представляет собой функцию п аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием.

Рассмотрим пример. Предложение "Река $x$ впадает в озеро Байкал" является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной $x$ название "Баргузин", получим высказывание "Река Баргузин впадает в озеро Байкал". Это высказывание истинно. Подставив вместо предметной переменной $x$ название "Днепр", получим ложное высказывание "Река Днепр впадает в озеро Байкал".

Другой пример. Предложение (выражение) " $x^2+y^2 \leqslant 9$ " является двухместным предикатом, заданным над множествами $\mathbb{R},\mathbb{R}$ . Множества, на которых задан двухместный предикат, совпадают (говорят, что "двухместный предикат задан на множестве $\mathbb{R}^2$ "). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: " $2^2+2^2 \leqslant 9$ ", а пара чисел 2, 3 — в ложное: " $2^2+3^2 \leqslant 9$ ".

Отметим еще один подход к понятию предиката. Как отмечалось, предикат $P(x_1,x_2,\ldots,x_n)$ , определенный на множествах $M_1,M_2,\ldots,M_n$ , превращается в конкретное высказывание $P(x_1,x_2,\ldots,x_n)$ , если вместо предметных переменных $x_1,x_2,\ldots,x_n$ подставить в него конкретные предметы (элементы $a_1,a_2,\ldots,a_n$ ) из множеств $M_1,M_2,\ldots,M_n$ соответственно. Это высказывание может быть либо истинным, либо ложным, т. е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию $n$ аргументов, заданную на множествах $M_1,M_2,\ldots,M_n$ принимающую значение в двухэлементном множестве $\{0;1\}$ . Иногда эту функцию и называют предикатом.

Классификация предикатов

Определение 18.2. Предикат $P(x_1,x_2,\ldots,x_n)$ , заданный на множествах $M_1,M_2,\ldots,M_n$ , называется:

а) тождественно истинным, если при любой подстановке вместо переменных $x_1,x_2,\ldots,x_n$ любых конкретных предметов $a_1,a_2,\ldots,a_n$ из множеств $M_1,M_2,\ldots,M_n$ соответственно он превращается в истинное высказывание $P(a_1,a_2,\ldots,a_n)$ ;

б) тождественно ложным, если при любой подстановке вместо переменных $x_1,x_2,\ldots,x_n$ любых конкретных предметов из множеств $M_1,M_2,\ldots,M_n$ соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов $a_1,a_2,\ldots,a_n$ из множеств $M_1,M_2,\ldots,M_n$ соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат $P(x_1,x_2,\ldots,x_n)$ последний превратится в истинное (ложное) высказывание $P(a_1,a_2,\ldots,a_n)$ .

Приведем примеры предикатов.

Одноместный предикат "Город $x$ расположен на берегу реки Волги", определенный на множестве названий городов, является выполнимым, потому что существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката (продумайте!).

В другом примере одноместный предикат " $\sin^2x+\cos^2x=1$ ", определенный на множестве действительных чисел, тождественно истинный. Наконец, двухместный предикат " $x^2+y^2<0$ ", заданный также на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему).

Отметим некоторые достаточно очевидные закономерности взаимосвязей между предикатами различных типов (рекомендуется осмыслить их):

1) каждый тождественно истинный предикат является выполнимым, но обратное неверно;
2) каждый тождественно ложный предикат является опровержимым, но обратное неверно;
3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным;
4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

Множество истинности предиката

Определение 18.3. Множеством истинности предиката $P(x_1,x_2,\ldots,x_n)$ , заданного на множествах $M_1,M_2,\ldots,M_n$ , называется совокупность всех упорядоченных n-систем $(a_1,a_2,\ldots,a_n)$ , в которых $a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n$ , таких, что данный предикат обращается в истинное высказывание $P(a_1,a_2,\ldots,a_n)$ при подстановке $x_1=a_1,x_2=a_2,\ldots,x_n=a_n$ . Это множество будем обозначать $P^{+}$ . Таким образом,

$P^{+}= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda \bigl(P(a_1,a_2, \ldots, a_n)\bigr)= 1\bigr\}.$

Множество $P^{+}$ истинности "-местного предиката $P(a_1,a_2,\ldots,a_n)$ представляет собой n-арное отношение между элементами множеств $M_1,M_2,\ldots,M_n$ . Если предикат $P(x)$ — одноместный, заданный над множеством $M$ , то его множество истинности $P^{+}$ является подмножеством множества $M\colon\, P^{+}\subseteq M$ .

Например, множеством истинности двухместного предиката "Точка $x$ принадлежит прямой $y$ ", заданного на множестве $E$ всех точек плоскости и на множестве $F$ всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости. Другой пример. Множество истинности двухместного предиката $S(x,y)\colon~ x^2+y^2=9$ , заданного на множестве $\mathbb{R}^2$ , есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиуса 3. Наконец, если $A(x)\colon$ " $|a|>2$ " — одноместный предикат над $\mathbb{R}$ , то $A^{+}= (-\infty;-2)\cup(2;+\infty)$ , или $A^{+}= \mathbb{R} \setminus[-2;2]$ .

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов (определение 18.2). В самом деле, n-местный предикат $P(x_1,x_2,\ldots,x_n)$ , заданный на множествах $M_1,M_2,\ldots,M_n$ , будет:

а) тождественно истинным тогда и только тогда, когда $P^{+}=M_1\times M_2\times \ldots\times M_n$ ;
б) тождественно ложным тогда и только тогда, когда $P^{+}=\varnothing$ ;
в) выполнимым тогда и только тогда, когда $P^{+}\ne\varnothing$ ;
г) опровержимым тогда и только тогда, когда $P^{+}\ne M_1\times M_2\times \ldots\times M_n$ .

На языке множеств истинности еще более отчетливо проясняются закономерности взаимосвязей между предикатами различных типов, отмеченные в конце предыдущего пункта. Проанализируйте их еще раз.