Пусть имеется предикат \(P (x)\) определенный на множестве \(M\). Если \(a\) – некоторый элемент из множества \(M\), то подстановка его вместо \(x\) в предикат \(P (x)\) превращает этот предикат в высказывание \(P (a)\). Такое высказывание называют единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание.
1. Квантор всеобщности. Пусть \(P (x)\) – предикат, определенный на множестве \(M\). Под выражением \( \forall\) \(x P(x)\) понимают высказывание, истинное, когда \(P (x)\) истинно для каждого элемента \(x\) из множества \(M\) и ложное в противном случае. Это высказывание уже не зависит от \(x\). Соответствующее ему словесное выражение будет: "Для всякого \(x\) \(P (x)\) истинно". Символ \( \forall\) называют квантором всеобщности.
Переменную \(x\) в предикате \(P (x)\) называют свободной (ей можно придавать различные значения из \(M\)), в высказывании \(\forall\)\(x\) \(P (x)\) переменную \(x\) называют связанной квантором \(\forall\).
2. Квантор существования. Пусть \(P (x)\) – предикат, определенный на множестве \(M\). Под выражением \( \exists\) \(x P(x)\) понимают высказывание, которое является истинным, если существует элемент \(x \epsilon M\), для которого \(P (x)\) истинно, и ложным в противном случае. Это высказывание уже не зависит от \(x\). Соответствующее ему словесное будет: "Существует \(x\), при котором \(P (x)\) истинно". Символ \(\exists\) называется квантором существования. В высказывании \(\exists\)\(x\) \(P (x)\) переменная \(x\) связана квантором \(\exists\).
Приведем пример употребления кванторов. Пусть на множестве \(N\) натуральных чисел задан предикат \(P (x)\): "Число \(x\) кратно 5". Используя кванторы, из данного предиката можно получить высказывания: \(\forall\)\(x \epsilon N P (x)\) - "Все натуральные числа кратны 5"; \(\exists\)\(x \epsilon N P (x)\) — "Существует натуральное число, кратное 5". Очевидно, первое из этих высказываний ложно, а второе истинно.
Ясно, что высказывание \(\forall\)\(x P (x)\) истинно только в том единственном случае, когда \(P (x)\) - тождественно истинный предикат, а высказывание \(\exists\)\(x P (x)\) ложно только в том единственном случае, когда \(P (x)\) — тождественно ложный предикат.
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве \(M\) задан двухместный предикат \(P ( x,y)\). Применение кванторной операции к предикату \(P ( x,y)\) по переменной \( x\) ставит в соответствие двухместному предикату \(P ( x,y)\) одноместный предикат \(\forall\)\( x\) \(P ( x,y)\) (или одноместный предикат \(\exists\)\( x\) \(P ( x,y)\)), зависящий от переменной \( y\) и не зависящий от переменной \( x\). К ним можно применить кванторные операции по переменной \( y\), которые приведут уже к высказываниям следующих видов:
Например, рассмотрим предикат \(P (x,y)\): "\(x : y\)", определенный на множестве \(N\). Применение кванторных операций к предикату \(P (x,y)\) приводит к восьми возможным высказываниям:
1. \(\forall\)\(y\)\(\exists\)\(x\)\(P(x,y)\) - «Для всякого \(y\) и для всякого \(x\) \(y\) является делителем \(x\)».
2. \(\exists\)\(y\)\(\forall\)\(x\)\(P(x,y)\) - «Существует \(y\), которое является делителем всякого \(x\)».
3. \(\forall\)\(y\)\(\exists\)\(x\)\(P(x,y)\) - «Для всякого \(y\) существует \(x\) такое, что \(x\) делится на \(y\)».
4. \(\exists\)\(y\)\(\exists\)\(x\)\(P(x,y)\) - «Существует \(y\) и существует \(x\) такие, что \(y\) является делителем \(x\)».
5. \(\forall\)\(x\)\(\forall\)\(y\)\(P(x,y)\) - «Для всякого \(x\) и для всякого \(y\) \(y\) является делителем \(x\)».
6. \(\forall\)\(x\)\(\exists\)\(y\)\(P(x,y)\) - «Для всякого \(x\) существует такое \(y\), что \(x\) делится на \(y\)».
7. \(\exists\)\(x\)\(\exists\)\(y\)\(P(x,y)\) - «Существует \(x\) и существует \(y\) такие, что \(y\) является делителем \(x\)».
8. \(\exists\)\(x\)\(\exists\)\(y\)\(P(x,y)\) - «Существует \(x\) такое, что для всякого \(y\) \(x\) делится на \(y\)».
Легко видеть, что высказывания 1, 5 и 8 ложны, а высказывания 2, 3, 4, 6 и 7 истинны.
Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и его логическое значение (например, высказывания 3 и 8).
Рассмотрим предикат \(P(x)\), определенный на множестве \(M = \begin{Bmatrix} a_{1}, a_{2}, ...,a_{n} \end{Bmatrix}\), содержащем конечное число элементов. Если предикат \(P(x)\) является тождественно истинным, то истинными будут высказывания \(P(a_{1}), P( a_{2}), ..., P(a_{n})\). При этом истинными будут высказывание \(\forall\)\(x P(x)\) и конъюнкция \(P(a_{1}) \wedge P( a_{2})\wedge ... \wedge P(a_{n})\).
Если хотя бы для одного элемента \(a_{k} \epsilon M\) \(P( a_{k})\) окажется ложным, то ложными будут высказывание \(\forall\)\(x P(x)\) и конъюнкция \(P(a_{1}) \wedge P( a_{2})\wedge ... \wedge P(a_{n})\). Следовательно, справедлива равносильность:
Нетрудно показать, что справедлива и равносильность:
Отсюда видно, что кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции на случай бесконечных областей.
Пример 1. Даны предикаты \(P (x)\): \(x ^{2} +x + 1\succ 0\) и \(Q (x)\): \(x ^{2} - 4x + 3 = 0\), определенные на множестве \(R\). Требуется установить, какие из следующих высказываний истинны и какие ложны:
1) \(\forall\)\(x P (x)\);
2) \(\exists\)\(x P (x)\);
3) \(\forall\)\(x Q (x)\);
4) \(\exists\)\(x Q (x)\).
Решение. Так как \(x^{2} + x+1 =\left(x +\frac{1}{2} \right)^{2} + \frac{3}{4} \succ 0\) при всех \(x\), то будут истинными высказывания \(\forall\)\(x P (x)\) и \(\exists\)\(x P (x)\). Так как \(x ^{2} - 4x + 3 = 0\) имеет только два действительных корня \(x_{1} =3\) и \(x_{2} =1\), то предикат \(Q (x)\) принимает значение 1 только при \(x=3\) и \(x=1\) и 0 в остальных случаях. Но тогда высказывание \(\forall\)\(x Q (x)\) ложно, а высказывание \(\exists\)\(x Q (x)\) истинно.
Пример 2. Пусть предикат \(Q ( x, y)\): "\(x:y\)" определен на множестве \(N \times N\). Показать, что высказывания \(\forall\)\(y\)\(\exists\)\(x\)\(Q (x, y)\) и \(\exists\)\(x\)\(\forall\)\(y\)\(Q (x, y)\) имеют различные логические значения.
Решение. Так как высказывание \(\forall\)\(y\)\(\exists\)\(x\)\(Q (x, y)\) означает, что для всякого натурального числа \(y\) существует натуральное число \(x\) такое, что \(y\) является делителем \(x\), то это высказывание истинно.
Высказывание \(\exists\)\(x\)\(\forall\)\(y\)\(Q (x, y)\) означает, что есть натуральное число \(x\), которое делится на любое натуральное число \(y\). Это высказывание, очевидно, ложно.
