Тема 2.5 Равносильные формулы. Свойства.

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

Основы равносильности:

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

а) (для конъюнкции);

б) (для дизъюнкции).

2. Ассоциативность.

а) (для конъюнкции);

б) (для дизъюнкции).

3. Дистрибутивность.

а) (для конъюнкции относительно дизъюнкции);

б) (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) ^┐┐┐(отрицание конъюнкции есть дизъюнкция отрицаний);

б) ^┐┐┐(отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) (для конъюнкции);

б) (для дизъюнкции).

6. Поглощение.

.

^┐

7. Расщепление (склеивание).

а) (1–ый закон расщепления);

б) (2–ой закон расщепления).

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

^┐┐х=х

9. Свойства констант.

а)

б)

в)

г)

д)

е) .

10. Закон противоречия.

11. Закон “исключенного третьего”.

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “”. Докажем, например, равносильность 4а. Для этого составим таблицу.

Таблица

х	у					Ø

Из таблицы видно, что º Ø, что и требовалось доказать.