Равносильности, выражающие основные законы алгебры логики.

3.1. - коммутативные законы конъюнкции и дизъюнкции.

3.2.

- ассоциативность конъюнкции и дизъюнкции.

3.3.

- законы дистрибутивности конъюнкции и дизъюнкции и дизъюнкции относительно конъюнкции.

Любая из равносильностей может быть доказана с помощью таблиц истинности, хотя часто оказывается легче провести доказательство с помощью логического рассуждения и упрощения формулы с использованием равносильностей (1 - 3).

Отношение равносильности есть отношение эквивалентности, т.е. оно рефлексивно ( ), симметрично и транзитивно .

Примеры.

1.Доказать равносильность

Используя равносильность (1 - 3) запишем цепочку равносильных формул

2.Упростить формулу

.

Запишем цепочку равносильных формул

3. Доказать равносильность

Пусть и - произвольная формула.

Тогда

Формула называется тавталогией ( тождественно истинной), если она принимает значение 1 при всех значениях входящих в нее переменных. Формула называется тождественно логичной(противоречивой ), если она равна 0 при всех значениях входящих в нее переменных.

Формула называется выполнимой, если при каком – то наборе входящих в нее переменных она принимает значение 1.

Формула называется опровержимой, если при каком – то наборе входящих в нее переменных она принимает значение 0.

С точки зрения логики тавталогии это логические законы, т.к. они принимают истинные значения пи любом наборе переменных.

В практических вычислениях часто используют следующие тавталогии ( , - произвольные формулы).

1. .

2. .

3.

4.

5.

6.

7.

8.

9.

10. - закон Пирса.

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

Доказательство выполняется по следующей схеме:

Приведем еще две более простые схемы доказательства от противного

Примеры.

1. Доказать тождественную истинность формулы

Запишем цепочку равносильных формул:

2.Проверить, что формула является тождественно истинной.

Составим таблицу истинности ( табл. 13 )

Таблица 13.

p	q

Последний столбец состоит из всех единиц, что соответствует тождественной истине.

3. При каких значениях p, q, r формула , логична?

Составим таблицу истинности (табл. 14)

Таблица 14

p	q

Из таблицы видно, что p = 1, q = 0.