Т. А. Сливина математическая логика и теория алгоритмов

Двухместным предикатом Р(x, y) называется функция двух переменных x и y, определенная на множестве M = M₁ M₂ и принимающая значения из множества {1, 0}.
Пример.
1. Бинарное отношение «меньше» на множестве целых чисел Z.
Это отношение между двумя предметами, оно может быть записано в виде высказывания «x < y», где x, yZ, т. е. является функцией двух переменных Р(х, y), определенный на множестве Z Z с множеством значений {1, 0}.
2. Q(x, y) – «x = y» предикат равенства, определенный на множестве
R² = R R.
Аналогично определяется n – местный предикат.
Далее рассмотрим логические и кванторные операции над предикатами. Формулы логики предикатов, основные равносильности.
Предикаты, так же, как высказывания, принимают значения «и» и «л» (или 1 и 0), поэтому к ним применимы все операции логики высказываний.
Коньюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x) Q(x), который принимает значение «и» при тех и только тех значениях x M, при которых каждый из предикатов принимает значение «и», и принимает значение «л» во всех остальных случаях.
Областью истинности предиката P(x) Q(x) является общая часть областей истинности предикатов P(x) и Q(x), т. е. пересечение
Пример.
P(x) – «х – четное число», Q(x) – «х кратно 3», тогда P(x) Q(x) – «х – четное число и кратное 3», или «х – делится на 6».
Дизьюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x) Q(x), который принимает значение «л» при тех и только тех значениях x M, при которых каждый из предикатов принимает значение «л» и принимает значение «и» во всех остальных случаях.
Областью истинности предиката P(x) Q(x) является объединение областей истинности предикатов P(x) и Q(x), т. е.
Отрицанием предиката P(x) называется новый предикат который принимает значение «и» при всех значениях x M, при которых предикат P(x) принимает значение «л» и наоборот.
Областью истинности предиката является
Импликацией предикатов P(x) и Q(x) называется новый предикат P(x) Q(x), который является «л» при тех и только тех значениях x M, при которых одновременно P(x) принимает значение «и», а Q(x) – значение «л» и принимает значение «и» во всех остальных случаях.
Областью истинности будет


Квантор всеобщности.
Пусть Р(х) – предикат, определенный на множестве М. Выражение – есть высказывание, которое является «и» для каждого x M и «л» в противном случае. Это высказывание уже не зависит от х. Оно читается следующим образом: «Для всякого х, Р(х) истинно». Символ называется квантором всеобщности. Переменную х в предикате Р(х) называют свободной, а в высказывании называют связанной квантором всеобщности


Квантор существования.
Пусть Р(х) – предикат, определенный на множестве М. Выражение – есть высказывание, которое является истинным, если существует элемент x M, для которого Р(х) истинно, и ложно, в противном случае.
Читается: «Существует х для которого Р(х) истинно». Символ называется квантором существования. В высказывании переменная х считается связанной квантором существования .
Примеры употребления кванторов.
Пусть на множестве N задан предикат Р(х) – «число х кратно 5».
Используя кванторы и можно получить следующие высказывания:
1) – «Все натуральные числа кратны 5». Это высказывание всегда ложно;
2) – «Существует натуральное число, кратное 5». Это высказывание всегда истинно.
Очевидно, что высказывание истинно тогда и только тогда, когда Р(х) – тождественно-истинный предикат, а высказывание ложно тогда и только тогда, когда Р(х) – тождественно-ложный предикат.
Рассмотрим предикат Р(х), определенный на множестве М=а₁, а₂, …, а_n, содержащем конечное число элементов.
Если предикат является тождественно-истинным, то истинными будут
и коньюнкция .
Если же, хотя бы для одного элемента а_kМ, – ложно, то ложными будут и коньюнкция .
Отсюда следует равносильность  .
Аналогично можно показать, что справедлива и равносильность
 . Эти две равносильности можно оспользовать в дальнейшем для преобразований формул.
Кванторные операции можно применять и к многоместным предикатам.
Например, на множестве М задан 2-местный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х,у) одноместный предикат (или одноместный предикат ), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:
, , , .
Например, рассмотрим предикат Р(х,у): «х делится на у», определенный на множестве N. Применение кванторных операций к предикату Р(х,у) приводит к восьми возможным высказываниям:
1. – «Для всякого у и для всякого х, у является делителем х»;
2. – «Существует у, которое является делителем всякого х»;
3. – «Для всякого у существует х такое, что х делится на у»;
4. – «Существует у и существует х такие, что у является делителем х»;
5. – «Для всякого х и для всякого у , у является делителем х»;
6. – «Для всякого х существует такое у, что х делится на у»;
7. – «Существует х и существует у такие, что у является делителем х»;
8. – «Существует х такое, что для всякого у, х делится на у».
Высказывания 1, 5 и 8 – ложны, а 2, 3, 4, 6, и 7 – истинны.
Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит и его логическое значение (например 3 и 8).