11. Методы установления общезначимости формул. Равносильные преобразования формул.
Метод истинностных таблиц. С этим методом читатель уже знаком, поэтому мы не будем приводить подробных вычислений всех подформул (формул, входящих в состав) рассматриваемой формулы.
Пример 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
|
A |
B |
C |
A (B C) |
A B A C |
A (B C) (A B A C) |
|
И |
И |
И |
И |
И |
И |
|
И |
И |
Л |
Л |
Л |
И |
|
И |
Л |
И |
Л |
Л |
И |
|
И |
Л |
Л |
И |
И |
И |
|
Л |
И |
И |
И |
И |
И |
|
Л |
И |
Л |
И |
И |
И |
|
Л |
Л |
И |
И |
И |
И |
|
Л |
Л |
Л |
И |
И |
И |
Таблица 4
|
A |
B |
C |
A (B C) |
A B A C |
A (B C) A B A C |
|
И |
И |
И |
И |
И |
И |
|
И |
И |
Л |
Л |
Л |
И |
|
И |
Л |
И |
И |
И |
И |
|
И |
Л |
Л |
И |
И |
И |
|
Л |
И |
И |
Л |
И |
Л |
|
Л |
И |
Л |
Л |
И |
Л |
|
Л |
Л |
И |
Л |
И |
Л |
|
Л |
Л |
Л |
Л |
И |
Л |
Метод от противного. Этот метод связан с решением логических уравнений. Под логическим уравнением будем понимать равенство вида Ф1=Ф2, где Ф1 и Ф2 -формулы алгебры высказываний или одно из истинностных значений (И или Л). Решить логическое уравнение означает найти все те наборы истинностных значений атомов, входящих хотя бы в одну из формул Ф1 или Ф2, при которых имеет место равенство Ф1=Ф2. Указанное же равенство выполняется, если формулы Ф1 и Ф2 имеют одинаковые истинностные значения.
Пример 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. Общезначима ли формула (А В) В А?
Имеет место следующая цепочка равносильностей:
Последняя формула В А в приведенной цепочке равносильностей не является общезначимой: при (А, В)=(Л, И) она принимает значение Л. Значит она не является общезначимой и равносильная ей формула (А В) В А
Указанными методами можно пользоваться и при установлении того, является ли формула необщезначимой, нейтральной, выполнимой, невыполнимой.