Предикаты. Операции над предикатами

При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение $P(x) : x^2 + 1 > 2$ с переменной $x \in \mathbb R$. Это предлождение не является высказыванием, так как нельзя сказать истинно оно или ложно. Однако, если заменить переменную $x$ на какое-либо значение, например, $x = 1$, получаем высказывание $2 > 2$, которое является ложным. Заменив переменную $x$ на значение $x = 2$, получим истинное высказывание $5 > 2$. Итак есть выражение $P(x)$ не являющиееся высказыванием, но превращающееся в него при замене переменной $x$ на ее произвольное значение из соответствующего множества.

Определение

Одноместным предикатом, определенным на множестве $D$, называется предложение с переменной, которое превращается в высказывание при замене этой переменной на ее значение из множества $D$. Одноместный предикат будем называть унарным или предикатом от одной переменной.

Примеры

Следующие предложения являются одноместными предикатами:

1. $P(x): x^ 2 + 1 > 2$, где $D$ — множество действительных чисел.
2. $Q(x):$ Длина отрезка равна $1$, где $D$ — множество всех отрезков прямой.

Следующие предложения не являются одноместными предикатами:

1. $1 > 2$.
2. Прямая $x$ параллельна прямой $y$.

$n$-местный предикат

$n$-местым предикатом с областью определения $D = D_1 \times D_2 \times \ldots \times D_n$ называется предикат $P(x_1, x_2, \ldots, x_n)$ от $n$ переменных, который превращается в высказывание при замене переменных $x_1, x_2, \ldots, x_n$ на их значения из множеств $D_1, D_2, \ldots, D_n$ соответственно.

Тогда предложение прямая $x$ параллельна прямой $y$ является двуместным предикатом $P(x, y)$, где $X, Y$ — множество всех прямых.

Область определения предиката

Рассмотрим $n$-местный предикат $P(x_1, x_2, \ldots, x_n)$. В этом случае переменные берутся из множеств $D_1, D_2, \ldots, D_n$ соответственно. Можно рассмотреть множество $D = D_1 \times D_2 \times \ldots \times D_n$ — декартово произведение множеств $D_1, D_2, \ldots, D_n$, элементами которого являются всевозможные упорядоченные $n$-ки $(d_1, d_2, \ldots, d_n)$ элементов исходных множеств.

Множество $D$ называется областью определения предиката.

Область истинности

Областью истинности предиката $P(x_1, x_2, \ldots, x_n)$ называется множество всех $n$-ок $(d_1, d_2, \ldots, d_n) \in D$ таких, что при замене $x_1$ на $d_1$, $x_2$ на $d_2$, ..., $x_n$ на $d_n$ получается истинное высказывание.

Пример

На множестве $D = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ рассмотрим одноместный предикат $P(x): x$ — простое число. Найти область истинности предиката $P(x)$.

Обозначим область истинности буквой $A$. Тогда $A$ состоит из таких элементов, при которых выполняется предикат $P(x)$. Поэтому $A = \{2, 3, 5, 7\}$.

Операции над предикатами

Аналогично операциям для высказываний вводятся операции для предикатов.

Пусть $P(x)$ и $Q(x)$ — одноместные предикаты, определенные на множестве $D$.

Отрицанием предиката $P(x)$ называется новый предикат, обозначаемый $\overline{P(x)}$ и являющийся ложным для тех и только тех $x$, для которых предикат $P(x)$ истинный.

Конъюнкцией предикатов $P(x)$ и $Q(x)$ называется новый предикат, обозначаемый $P(x) \land Q(x)$ и являющийся истинным для тех и только тех $x$, для которых предикаты $P(x)$ и $Q(x)$ истинны.

Дизъюнкцией предикатов $P(x)$ и $Q(x)$ называется новый предикат, обозначаемый $P(x) \lor Q(x)$ и являющийся ложным для тех и только тех $x$, для которых предикаты $P(x)$ и $Q(x)$ ложны.

Импликацией предикатов $P(x)$ и $Q(x)$ называется новый предикат, обозначаемый $P(x) \rightarrow Q(x)$ и являющийся ложным для тех и только тех $x$, для которых предикаты $P(x)$ истинный, а $Q(x)$ ложный.

Эквиваленцией предикатов $P(x)$ и $Q(x)$ называется новый предикат, обозначаемый $P(x) \leftrightarrow Q(x)$ и являющийся истинным для тех и только тех $x$, для которых предикаты $P(x)$ и $Q(x)$ имеют одинаковые значения.

Применяя операции над предикатами, мы получаем составные предикаты, которые будем называть формулами алгебры предикатов.

Предикаты $P(x)$ и $Q(x)$ эквивалентные , если для любого значения переменной $x$ их значения истинности совпадают. Обозначают $$P(x) \equiv Q(x).$$

Законы алгебры предикатов

Для предикатов справедливы все законы, аналогичные законам алгебры логики высказываний¹.

В случае тождественно истинных и тождественно ложных предикатов имеем следующие определения.

Предикат $P(x_1, x_2, \ldots, x_n)$ называется тождественно истинным если при любой замене переменных $x_1, x_2, \ldots, x_n$ на их значения предикат превращается в истинное высказывание.

Предикат $P(x_1, x_2, \ldots, x_n)$ называется тождественно ложным если при любой замене переменных $x_1, x_2, \ldots, x_n$ на их значения предикат превращается в ложное высказывание.

---

Высказывание является частным случаем предиката, когда в предикате нет переменных. То есть высказывание является предикатом $0$ порядка (от $0$ переменных).

---

1. Законы алгебры логики высказываний.