Эквивалентные формулы логики предикатов

Формулы φ и ψ сигнатуры называются эквивалентными (обозначается φ ≡ ψ), если φψ или ψ .

Утверждение 1.В логике предикатов выполнимы все эквивалентности ИВ из теоремы 3.

Утверждение 2. Пусть φ, ψ – формулы сигнатуры переменная x не является свободной переменной формулы ψ, переменная у не является свободной переменной формулы φ. Тогда

1) ¬ xφ≡ x¬φ, 1΄) ¬ xφ≡ x¬φ,

2) x(φ∧ψ)≡ xφ∧ψ, 2΄) x(φ∨ψ)≡ xφ∨ψ,

3) x(φ∨ψ)≡ xφ∨ψ, 3΄) x(φ∧ψ)≡ xφ∧ψ,

4) xφ≡ x(φ) 4΄) xφ≡ x(φ)

здесь запись (φ) обозначает результат подстановки y вместо всех свободных вхождений в φ переменной x.