Эквивалентность формул

Формулы φ(x₁,…,x_n) и ψ(x₁,…,x_n) называются эквивалентными (φ≈ψ), если совпадают их таблицы истинности, т.е. совпадают представляемые этими формулами функции.

Основные эквивалентности:

1) ассоциативность

2) Коммутативность:

3) Идемпотентность:

4) Дистрибутивность: ,

5) Поглощение:

6) Законы де Моргана:

7) Двойное отрицание:

8)

9)

10)

11)

Формула φ(x₁,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значения 1 (соответственно 0).

Формула φ(x₁,…,x_n) называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах значений переменных, т.е. функция f_φ является константой 1 (константой 0).

Утверждения:

1) Формула φ тождественно ложна тогда и только тогда, когда ך φ тождественно истинна.

2) Формула φ опровержима тогда и только тогда, когда она не является тождественно истинной

3) Формула φ выполнима тогда и только тогда, когда она не является тождественно ложной.

Тождественно истинные (тождественно ложные) формулы образуют класс эквивалентности по отношению ≈.

Утверждение: Если формула φ₁ тождественно истинна, φ₀ – тождественно ложна, то справедливы следующие эквивалентности:

1) , 2) , 3) , 4) , 5) , 6) , 7) ,8) , 9) .