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

Формулы логики предикатов первого порядка рекурсивно определяются следующим образом:

1. атом есть формула;

2. если A и B - формулы, то ~A, AÙB, AÚB, A® B, A«B - тоже формулы;

3. если A(x) - есть формула, а x - свободная переменная в A(x), то ("x)A(x) и ($x)A(x) - тоже формулы;

4. других формул, кроме составленных с помощью правил (1) - (3), нет.

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

Формулы, равносильные на любых областях, называются просто равносильными и могут заменять друг друга. Все равносильности, имеющее место в алгебре высказываний переносятся и в логику предикатов. Кроме равносильности

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

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

Каждая формула логики предикатов имеет нормальную формулу.