Метод равносильных преобразований

TÙ		FÙ

Пример. Установить, является ли формула

общезначимой.

Выпишем итоговые таблицы:

1){TA,FB,TA,FB} незамкнутая;

2){TA,FB,FA,TB} замкнутая;

3){FB,TA,FB} незамкнутая;

4){TA,TA,FB} незамкнутая;

5){FA,FA,TB} замкнутая;

6){TA,FB,TB} замкнутая.

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

Если все итоговые таблицы формулы с индексом F-замкнуты, то формула является общезначимой.

Пример. Проверить, является ли логическим противоречием формула ?

1){FA} незамкнута;

2){TB,FA,TA} замкнута. Следовательно, - не есть логическое противоречие

Замечание:Метод аналитических таблиц используется обычно для формул, в которых число атомов больше трех-четырех (тогда не строятся таблицы истинности).

Пример.Доказать, что формула общезначима

1) {FA,TB,FC,FA,FB} – замкнутая;

2) {FA,TB,FC,TA} – замкнутая;

3) {FA,TB,FC,TC} – замкнутая;

4) {TA,TA,FA,FC} – замкнутая;

5) {TA,TB,FA,FC} – замкнутая;

6) {FB,TA,FA,FC} – замкнутая;

7) {TC,TA,FA,FC} – замкнутая;

8) {FB,TB,FA,FC} – замкнутая;

9) {TC,TB,FA,FC} – замкнутая.

Все таблицы замкнутые, значит, формула является общезначимой.

Если при исследовании формул на общезначимость, итоговые таблицы этой формулы с индексом Fвсе замкнуты, то она является общезначимой. Аналогично, если формула исследуется с индексом Т и все итоговые таблицы замкнуты, то она является противоречием. В противном случае формула является нейтральной.

3.3.3 Метод от противного связан с решением логических уравнений.

Логическое уравнение - это равенство вида: Ф=Ф,где Фи Ф-формулы алгебры высказываний, или одно из значений «И», «Л». Решить логическое уравнение - означает найти все те наборы истинностных значений атомов, входящих в хотя бы одну из формул Фи Ф, при котором имеет равенство:

Ф=Ф.

Пример: проверить, общезначима ли формула (АÞВ) Þ ((ВÞ С)Þ (АÞС)).

Предположим противное. Пусть формула не является общезначимой, т.е. существует набор атомов, на котором она принимает значение Л:

(АÞВ) Þ ((ВÞ С)Þ (АÞС))=Л.

Полученное противоречие свидетельствует о том, что формула «И» во всех интерпретациях, т.е. общезначима.