Лекции_по_ДМ_2часть

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

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

x	y	х	у
0	0	1	1	1	1
0	1	1	0	1	1
1	0	0	1	0	0
1	1	0	0	1	1
Таблица 12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Yandex.RTB R-A-252273-3
Содержание
Yandex.RTB R-A-252273-4