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

Таблица 12

x	y	Øх	Øу

Рассмотрим формулы: и . Их таблицы истинности представлены таблице 12.

Как видно из таблицы 12, на одинаковых наборах значений переменных обе формулы принимают одинаковые истинностные значения, т.е. реализуют одну и ту же истинностную функцию.

Две формулы А и В называются эквивалентными, если функции f_A и f_B, соответствующие им, эквивалентны или равны, т.е. f_A=f_B. Для обозначения эквивалентных формул традиционно используется запись А=В, которую называют тождеством.

Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, Ø, &, Ú}. (Обозначим «∘» любую из функций: {&, Ú, Å}.)

1) ((x∘y)∘z)=(x∘(y∘z)) – свойство ассоциативности;

2) (x∘y)=(y∘х) – коммутативность;

3) конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x Ú y) & z) = ((x & z) Ú (y & z))
((x & y) Ú z) = ((x Ú z) & (y Ú z));

4) – закон двойного отрицания;

5) – законы Де Моргана для конъюнкции и дизъюнкции;

6) (х & х) = x; (x Ú x) = x – законы идемпотентности;

7) – закон исключенного третьего;

8) – закон противоречия;

9) (х & 0) = 0, (x Ú 0) = x – умножение на ноль и сложение с нулем;

10) (х & 1) = х, (x Ú 1) = 1 – умножение на единицу и сложение с единицей;

11) ((х & y) Ú x) = x, ((х Ú y) & x) = x – законы поглощения.

Все тождества легко проверяются с помощью таблиц истинности.