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

 

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

Определение 3. Пусть Р – предикат, определенный на W. Отрицанием предиката Р называется предикат, обозначаемый , определенный на W следующим образом:

                               

Пусть P и Q – предикаты, определенные на W.

Дизъюнкцией (конъюнкцией, импликацией, эквиваленцией) предикатов P и Q называется предикат, определенный на , обозначаемый , ( (,, PQ), , ) и определяемый следующим:

()

()

()

 

Определение 4. Предикаты P и Q, определенные на , называются равносильными (пишут PQ), если Р( x1, x2, …, xn )  Q( x1, x2, …, xn ) для любого набора ( x1, x2, …, xn ) предметных переменных из .

 

Теорема 1. Множество n – местных предикатов, определенных на  , образуют булеву алгебру предикатов, т. е. для них справедливы 19 основных равносильностей булевой алгебры:

 

0.

1.

2.

3.

4.

5.

6.

7.

8.

9.

 

10.

11.

12.

13.

14.

15.

16.

17.

18.

 

Здесь 1 – обозначение тождественно истинного предиката на , 0 – обозначение тождественно ложного предиката на .

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