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

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

Примеры равносильных формул:

1) ; 2) ; 3) = ;

4) = ; 5) = ; 6) = ;

7) = , где формула Н не содержит переменную х свободно;

8) = , где формула Н не содержит переменную х свободно;

9) = ; 10) = ;

11) = .

Формула А логики предикатов задана в предваренной нормальной форме, если она имеет вид , где - один из кванторов , а формула

не содержит кванторов.

Любую формулу логики предикатов можно привести к предваренной форме.