double arrow

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


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

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

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

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

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

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

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

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

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

8)

9)

10)

11)

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

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

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

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

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

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

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

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

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


Сейчас читают про: