Равносильные формулы логики предикатов

Две формулы логики предикатов и называются равносильными, если они равносильны во всякой области.

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

Закон де Моргана:

1.

2.

Закон двойного отрицания:

3.

4.

5.

6.

7.

Для произвольного высказывания (предиката, не связанного по переменной ) справедливы следующие формулы равносильности:

8.

9.

10.

11.

12.

13.

Формулы замены переменных (где и из одной предметной области):

14.

15.

Предваренная нормальная форма предиката

Формула предиката имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции, и кванторные операции, а операция отрицания отнесена к элементарному предикату.

ПРИМЕР

Пусть дан предикат . Привести данный предикат к нормальной форме