Алгоритм преобразования формул в нормальную форму

1. Исключить логические связки ↔ и → с помощью формул

F↔G=(F→G) (G→F), F→G=неF G.

2. Использовать закон ненеF=F, законы де Моргана:

не(F G) = неF неG, не(F G) = неF неG,

законы

, ,

чтобы пронести знак отрицания внутрь формулы.

3. Переименовать связанные переменные, если это необходимо.

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

Следовательно, нормальная форма формулы — это .