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

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

Утверждение 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.