§4. Алгебра предикатов. Логические операции над предикатами

Рассмотрим выражение «х –– простое число». Подставляя вместо х числа 3, 4, получаем высказывания, причем в первом случае оно будет истинным, а во втором –– ложным. Таким образом, каждому натуральному числу соответствует значение «И» и «Л» в зависимости от того, является оно простым или нет.

Аналогично, подставляя в выражение «х < у» вместо х и у конкретные действительные числа, получаем истинные или ложные высказывания. Например, при х = 3, у = 5 получаем истинное высказывание, а при х = 5, у = 3 –– ложное высказывание. Следовательно, выражение «х < у» определяет функцию двух переменных (двухместную) на множестве действительных чисел со значениями в множестве {И, Л}.

Подобным образом выражение «х и у –– родители z» определяет функцию трех переменных (трехместную) на множестве людей со значениями в множестве {И, Л}. Выражение х1 + х2 + … + хn = 0 определяет функцию n переменных (n–местную), заданную на множестве действительных чисел со значениями в множестве {И, Л}:

Такие функции называются предикатами.

Определение 1. n–местным предикатом на множестве М называется n–местная функция, аргументы которой принимают значения из множества М, а область значений есть множество {И, Л}.

Короче, n–местным предикатом на множестве М называется функция типа Мп→{И, Л}.

Для обозначения предикатов используют либо большие латинские буквы, либо символы: А(х, у), В(х), Р(х1, х2,…, хn) и т.д. (к предикантным символам А, В, Р добавляют в скобках символы переменных, от которых зависят данные предикаты). При этом, например, выражение А(10, 8) служит для обозначения (постоянного) высказывания, которое получается, если переменным х, и у предиката А(х, у) придать соответственно значения 10 и 8.

При n = 1 n–местный предикат называют унарным, при n = 2 –– бинарным, а при n = 3 –– тернарным.

Определение 2. Пусть Р(х1, х2,…, хn) –– n–местный предикат, определенный на множестве М. Множеством истинности этого предиката называется совокупность таких упорядоченных n–ок (х1, …, хn), для которых Р(х1, х2,…, хn) принимает значение И.

Определение 3. Два предиката Р(х1, …, хn) и Q(х1, …, хn), определенные на одном и том же множестве М, называются равносильными на множестве М, если они принимают одинаковые значения И или Л при любых значениях х1, …, хn из множества М.

Таким образом, два предиката Р(х1, …, хn) и Q(х1, …, хn) на множестве М называются равносильными на множестве М, если множества истинности этих предикатов совпадают.

Определение 4. Предикат Р(х1, …, хn), определенный на множестве М, называется тождественно–истинным (тождественно–ложным) на М, если при подстановке вместо х1, …, хn любых элементов из множества М он принимает значение И (Л), т.е. множество истинности этого предиката Мn (пустое).

Предикаты, как и высказывания, принимают значения И и Л, поэтому над ними можно производить логические операции, аналогичные операциям логики высказываний.

Пример. Пусть Р(х) и Q(х) –– два одноместных предиката, определенных на множестве М. Тогда Р(х) Ù Q(х) –– предикат на множестве М. Он является истинным для тех и только тех элементов из М, для которых оба предиката Р(х) и Q(х) истинны, т.е. множество истинности предиката Р(х) Ù Q(х) равно пересечению множеств истинности предикатов Р(х) и Q(х).

Аналогично определяется Р(х) U Q(х). Предикат Р(х) U Q(х) задан на том же множестве М и является истинным для тех и только тех элементов х из М, для которых истинен хотя бы один из предикатов Р(х) и Q(х), т.е. множество истинности предиката Р(х) U Q(х) равна объединению множеств истинности предикатов Р(х) и Q(х).

Предикат определен на множестве М и истинен для тех и только тех элементов х из М, для которых Р(х) ложен. Другими словами, множество истинности предиката –– дополнение в М множества истинности предиката Р(х).

Подобным образом вводятся предикаты Р(х) ? Q(х), Р(х) Û Q(х).

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

Пусть Р(х, у) и Q(х, у) –– два двухместных предиката, определенных на множестве М. Тогда Р(х, у) Ù Q(y, z) –– трехместный предикат на множестве М, он принимает значение И для тех и только тех упорядоченных троек (х, у, z) множества М, для которых Р(х, у) и Q(y, z) одновременно принимают значения И.

Отметим еще, что Р(х, у) Ù Q(х, у) –– двухместный, а Р(х, у) Ù Q(z, v) –– четырехместный предикаты, определенные на множестве М.

Если Р(х) и Q(х) –– два одноместных предиката, то не следует смешивать предикаты Р(х) Ù Q(х) и Р(х) Ù Q(у). Первый из них –– одноместный, а второй –– двухместный предикаты.

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

Определение 5. Пусть Р(х) –– одноместный предикат, определенный на множестве М. Символом обозначим высказывание, которое истинно, если Р(х) принимает значение И для любого элемента х множества М, и ложное в противоположном случае, т. е. –– истинное высказывание, если множество истинности предиката Р(х) совпадает со всем множеством М (Р(х) –– предикат, тождественно–истинный на множестве М); в противоположном случае –– ложное высказывание.

Часть в выражении называется квантором общности (всеобщности). Выражение читается «для любого х Р(х)». Символ –– перевернутая первая буква слова all (англ.), allе (нем.).

Пусть Р(х) –– предикат «х –– простое число», определенный на множестве натуральных чисел. Тогда высказывание (х –– простое число) ложно на множестве натуральных чисел. Это же высказывание (х –– простое число) истинно на множестве простых чисел.

Определение 6. Пусть Р(х) –– одноместный предикат, определенный на множестве М. Символом $ обозначим высказывание, которое истинно, когда в множестве М существует такой элемент х0, что Р(х0) = И, и ложно в противоположном случае, т. е. $ –– истинное высказывание, если множество истинности предиката Р(х) непустое; в противном случае $ –– ложное высказывание.

Выражение $ читается «существует х такое, что Р(х)», а часть $х в выражении $ называют квантором существования. Например, высказывание $х (х –– простое число) на множестве натуральных чисел истинно, высказывание $ на множестве действительных чисел ложно.

Символ $ –– перевернутая первая буква слова exist (англ.), existieren (нем.), exister (фр.).

Замечание 1. Применение квантора превращает одноместные предикаты в высказывания (не зависящие от х).

Замечание 2. К одному и тому же предикату можно применять кванторы несколько раз. Например, применив к предикату Р(х, у) квантор существования по х, мы получим одноместный предикат $, к которому опять можем применить квантор существования или квантор общности по переменной у. В результате получим высказывание

$у($ или у($.

Скобки обычно опускают, получая при этом выражения

$у$ или у$.

Замечание 3. Одинаковые кванторы можно переставлять, получая при этом эквивалентные высказывания, т.е. истинные эквиваленции:

ху Û ух;

$х$у Û $у$х.

Рассмотрим четыре часто встречающихся основных типа высказываний. В символической записи этих высказываний (записи на языке логики предикатов) используются кванторы.

Теорема.

Доказательство. Пусть высказывание истинно. Тогда высказывание ложно. Это значит, что не все х обладают свойством Р, т.е. какой–то этим свойством не обладает. Другими словами, существует х, не обладающий свойством Р, т.е. высказывание истинно.

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

Имеют место следующие законы логики:

Û ;

Û ;

Û ;

Û ;

U Û ;

Ù Û .