Методы доказательства тавтологии

Если каждая элементарная сумма, входящая в КНФ, содержит хотя бы одно высказывание вместе со своим отрицанием, то данная формула- тавтология.

В нашем примере так оно и есть, т.е. данная формула ─ тавтология

Таким образом, чтобы установить, к какому виду относится данная формула, нужно ее привести к ДНФ и КНФ.

1. Таблица истинности.

2. Приведение к КНФ.

3. Метод от противного.

Сущность 3-го метода заключается в том, что предполагается истинность противоположного утверждения, и на основании анализа формул мы получаем заключение о том, что она противоречит предположению. Это является доказательством того, что предположение ложно.

Пример:

Пусть имеется формула (pq)(qr) (рr).

Предположим, что эта формула не является тавтологией. Это значит, что существует некоторый набор значений элементарных высказываний, при котором левая часть импликации истинна, а правая ложна. Пусть это: р, q, r

Получим систему

отсюда:

Из 3-его имеем р₀ = 1. Тогда из 1 получим q₀ = 1, а из 2 получим r₀ = 1.

В результате r = 1 и r= 0.

Мы пришли к противоречию, следовательно, наше предположение ложно и формула – тавтология.

Дата добавления: 2014-01-06