∃ x ¬ F(x) , ¬ ∀ x F(x)= ∀
x ¬ F(x);
2) ∀x(F(x) ∧ G(x)) = ∀xF (x) ∧ ∀xG(x), ∃x(F(x) ∨ G(x))=∃F(x) ∨ ∃xG(x);
3)∀x ∀y F(x, y) =∀y ∀ x F(x, y), ∃ x ∃y F(x, y)= ∃y∃ x F(x, y);
4)∀x (F(x)∧С) = ∀x F(x) ∧ С, ∀x (F(x) ∨ С)= ∀x F(x) ∨ С;
5)∃x (F(x)∧С) = ∃ x F(x) ∧ С, ∃ x (F(x) ∨ С) = ∃ x F(x) ∨ С;
6)С → ∀x F(x) = ∀x ( С → F(x)), С→ ∃ x F(x) = ∃ x (С → F(x)).
Эти равносильности называются также законами логики предикатов.
Формула С не содержит вхождений переменной x.
Применяются также законы:
F↔G: = (F→G) ∧ (G→ F), F→ G: = ¬ F∨ С.
¬ F=F, ¬ (F∨С)= ¬ F∧¬ G, ¬ (F∧G)= ¬ F∨¬ G
С помощью равносильностей можно преобразовывать формулы.
Формула ЛП G называется логическим следствием формулы F, если G
истинна во всех интерпретациях, в которых F истинна. Запись: F→ G.
Имеют место логические следования:
7)∃x(F(x)∧G(x)) ∃xF(x)∧∃xG(x), ∀x F(x)∨∀ ∃xG(x)⇒∀x(F(x)∨G(x)) ;
8)∀ xF(x)→H⇒ ∃x(F(x) → H), ∃xF(x)→H⇒ ∀ x(F(x) → H),
где формула Н не содержит вхождений переменной х.
16