Методы установления общезначимости формул. Равносильные преобразования формул

Метод истинностных таблиц. С этим методом читатель уже знаком, поэтому мы не будем приводить подробных вычислений всех подформул (формул, входящих в состав) рассматриваемой формулы.

Пример 3. Общезначима ли формула A É (B ~ C) ~ (A É B ~ A É C)?

Истинностная таблица формулы A É (B ~ C) ~ (A É B ~ A É C) (табл. 3) в своем последнем столбце содержит только значения И, значит, эта формула общезначима.

Пример 4. Общезначима ли формула A Ù (B É C) ~ A Ù B É A Ù C?

Последний столбец (табл. 4) содержит значения Л, значит, формула A Ù (B É C) ~ A Ù B É A Ù C не общезначима.

Таблица 3

Таблица 4

Метод от противного. Этот метод связан с решением логических уравнений. Под логическим уравнением будем понимать равенство вида Ф₁=Ф₂, где Ф₁ и Ф₂ -формулы алгебры высказываний или одно из истинност­ных значений (И или Л). Решить логическое уравнение означает найти все те наборы истинностных значений атомов, входящих хотя бы в одну из формул Ф₁ или Ф₂, при которых имеет место равенство Ф₁=Ф₂. Указанное же равенство выполняется, если формулы Ф₁ и Ф₂ имеют одинаковые истинностные значения.

Пример 5. Общезначима ли формула (A É B) É ((B É C) É (A É C))

Допустим, что данная формула не общезначима. Тогда должен существовать хотя бы один набор значений формул А, В, С, при кото­ром формула (A É B) É ((B É C) É (A É C)) примет значение Л, т. е. должно иметь решение логическое уравнение

(A É B) É ((B É C) É (A É C)) = Л

По определению импликации имеем:

откуда значит, или

или

Условие И É Л = И последней системы противоречит определению импликации. Значит, наше допущение о том, что формула (A É B) É ((B É C) É (A É C)) не общезначима, следует отклонить.

Пример 6. Общезначима ли формула АÚ В É А Ù В?

Допустим, что данная формула не общезначима, тогда уравнение АÚ В É А Ù В = Л, а значит, и система уравнений , должны иметь решения. Легко видеть, что (А, В) = (И, Л) является таким решением. Итак, имеется набор значений формул А, В, при котором формула АÚ В É А Ù В принимает значение Л. Значит, эта формула не общезначима.

Метод равносильных преобразований. Прежде всего отметим, на общезначимые эквиваленции (14) — (43), (47), (48), (50) предложе­ния 6 можно смотреть и как на равносильности, т. е. к примеру, раз эквиваленция (15) A É B ~ Ø A Ú B обще­значима, то имеет место равносильность A É B º Ø A Ú B. Кроме того, следующие обще­значимые формулы, например, А Ú Ø А мы при необходи­мости, будем заменять на И. Будем также учитывать, что А Ù И º А, А Ù Л º Л, А Ú И º И, А Ú Л º А для любой формулы

Пример 7. Общезначима ли формула (А É В) Ù А É В?

В нижеследующей цепочке равносильностей число над знаком º показывает номер используемой равносильности из предложения 6.

Пример 8. Общезначима ли формула (А É В) Ù В É А?

Имеет место следующая цепочка равносильностей:

Последняя формула В É А в приведенной цепочке равносильностей не является общезначимой: при (А, В)=(Л, И) она принимает значение Л. Значит она не является общезначимой и равносильная ей формула (А É В) Ù В É А

Указанными методами можно пользоваться и при уста­новлении того, является ли формула необщезначимой, нейтральной, выполнимой, невыполнимой.