§ 2. Логические операции над предикатами и их свойства.

Так как алгебра предикатов является расширением алгебры высказываний, то в ней имеют место пять логических операций алгебры высказываний, которые определяются аналогично.

Кроме них в алгебре предикатов имеются еще две новые операции - операции навешивания квантора общности (- от английского слова all (все)) и квантора существования (- от английского слова exist (существовать)).

Определение 6. Квантором общности называется логическая операция, которая предикату Р(х) ставит в соответствие высказывание (х) Р(х), которое истинно тогда и только тогда, когда предикат Р(х) тождественно истинен и ложно в противном случае.

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

Пример 1. Пусть на множестве R задан предикат Р(х)=(х²+5>0x,y, R). Тогда высказывание (х) Р(х) = (х) (x²+5>0  х,yR) является истинным, так как предикат-неравенство х²+5>0 истинно при любом действительном значении х.

Отметим, что если предикат Р(х) задан на конечном множестве М= {а₁,а₂,...а_n}, то операцию навешивания квантора общности можно выразить через операцию конънкция по следующему соотношению

(х) Р(х)  Р(а₁)Р(а₂)...Р(а_n) (*)

Соотношение (*) является правилом вывода, лежащим в основе доказательства предложений методом полной индукции!

Определение 7. Квантором существования называется логическая операция, которая предикату Р(х) ставит в соответствие высказывание (х)Р(х), которое истинно тогда и только тогда, когда предикат Р(х) выполним и ложно в противном случае.

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

Пример 2. Пусть на множестве Z задан предикат Р(х)=(x>3Z). Тогда высказывание (х)Р(х) = (х)(х>3xZ) истинно, так как предикат x>3 выполним, например при х=4 имеем истинное неравенство 4>3.

Заметим, что если предикат Р(х) задан на конечном множестве М = {a₁, а₂, ..., а_n}, то операцию навешивания квантора существования можно выразить через операцию дизъюнкция по следующему соотношению

(х) Р(х)  Р(а₁)Р(а₂)...Р(а_n) (**)

Теорема. Если предикат Р(х) задан на одноэлементном множестве М = {a}, то высказывания (х) Р(х) и (х) Р(х) равносильны между собой.

Доказательство. Так как предикат Р(х) задан на множестве М = {a}, то по соотношению(*) (х)Р(х)Р(а), а по соотношению (**) (х)Р(х)  Р(а)  (х)Р(х) (х) Р(х).

Замечание. Так как предикаты задаются на множествах, то логические операции над предикатами можно определять через операции над множествами: пересечение, объединение.