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

Предикаты, так же, как и высказывания, принимают два значения «истина» и «ложь» (1 и 0), поэтому к ним применимы все операции алгебры логики.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

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

Пример.

P(x) – «x – четное число», Q(x) – «x кратно 3». Предикат – «x – четное число и x кратно 3» = «x делится на 6».

Определение. Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат который принимает значение «ложь» при тех и только тех значениях , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката является объединение областей истинности обоих предикатов, то есть .

Определение. Отрицанием предиката P(x) называется новый предикат , который принимает значение «истина» при всех значениях , при которых предикат P(x) принимает значение «ложь», и принимает значение «ложь» при тех значениях , при которых предикат P(x) принимает значение «истина». Областью истинности предиката является дополнение множества истинности предиката P(x) до множества M, то есть .

Определение. Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение «истина», а Q(x) принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Так как при каждом фиксированном x справедлива равносильность ≡Q(x), то область истинности предиката является объединением дополнения области истинности предиката P(x) до множества M и области истинности предиката Q(x), то есть .