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

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

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

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

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

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

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

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

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

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

Формула φ(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) .