Формула В является логическим следствием формулы А (обозначение: А Þ В), если формула В выполнена на любом наборе в любой интерпретации, на котором выполнена формула А. Формулы А и В логически эквивалентны (обозначение: А = В), если они являются логическим следствием друг друга. Имеют место следующие логические следования и эквивалентности:
1. Ø» x A(x) = $ x ØA(x), Ø$ x A(x) = » x ØA(x),
2. » x (A(x) & B(x)) = » x A(x) & » x B(x), $ x (A(x) Ú B(x)) = $ x A(x) Ú $ x B(x),
3. $ x (A(x) & B(x)) Þ $ x A(x) & $ x B(x), » x A(x) Ú » x B(x) Þ » x (A(x) Ú B(x)),
4. » x » y A(x, y) = » y » x A(x, y), $ x $ y A(x, y) = $ y $ x A(x, y),
5. » x (A(x) & C) = » x A(x) & C, » x (A(x) Ú C) = » x A(x) Ú C,
6. $ x (A(x) & C) = $ x A(x) & C, $ x (A(x) Ú C) = $ x A(x) Ú C,
7. C ® » x A(x) = » x (C ® A(x)), C ® $ x A(x) = $ x (C ® A(x)),
8. » x A(x) ® C Þ $ x (A(x) ® C), $ x A(x) ® C Þ «x (A(x) ® C)
где формула С не содержит никаких вхождений переменной x.
Для всякой формулы А существует логически эквивалентная ей формула А’ в предваренной форме:
,
где — некоторые кванторы, а — бескванторная формула.