Логические операции над предикатами

Пусть на некотором множестве М определены два предиката Р(х) и Q(х).

Определение 4.6. Конъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат Р(х) Ù Q(x), который принимает значение «истина» при тех и только тех значениях х  М, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Очевидно, что областью истинности предиката P(x) Ù Q(x) является общая часть областей истинности предикатов P(x)и Q(x), то есть пересечение I_р ∩ I_q.

Операции дизъюнкции, отрицания и импликации вводятся аналогично.

Кванторные операции

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

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

Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании х Р(х) переменную х называют связанной квантором .

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

Ясно, что высказывание хР(х) истинно только в том единственном случае, когда Р(х) – тождественно истинный предикат, а высказывание $хР(х) ложно только в том единственном случае, когда Р(х) – тождественно ложный предикат.

Формулы логики предикатов

Расширение логики высказываний до логики предикатов получается за счет включения в формулы утверждений, являющихся предикатами. Но при этом, поскольку предикаты относятся к изучаемым объектам, необходимо включить в теорию и сами объекты а₁,…, а_n,… Поэтому, чтобы дать определение формул в логике предикатов, нужно уточнить принципы описания в логике предикатов объектов. Делается это с помощью понятия терм.

Определение 4.7. Дадим следующее определение терма:

1) переменные х₁,…, х_п ,… для объектов – это термы;

2) если f(∙,…,∙) функция п-переменных, ставящая в соответствие изучаемым объектам объект, и t₁,…, t_n термы, то f(t₁,…, t_n) – терм.

Определение 4.8. Определение формулы логики предикатов:

1) если Р(∙,…,∙) п-местный предикат, a t₁,…, t_n – термы, то Р(t₁,…, t_n) – формула;

2) если А и В формулы, то (А Ù B), (AB), (AB) – формулы;

3) если A формула, то ¬A – формула;

4) если А(х) – формула, содержащая переменную х, то хА(х), хА(х) – формулы.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений термов.

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