Правило равносильной замены

Используя транзитивность отношения равносильности, мы, зная о равносильности одних формул, можем судить о равносильности других. Например согласно (13) формула

p ® q (a)

равносильна формуле

~p Ú q. (б)

Последняя же, согласно (15), равносильна формуле

~ (~ ~p Ù ~q). (в)

В силу транзитивности отношения равносильности отсюда следует, что формулы(а) и (в) равносильны.

Поскольку же формула (в) согласно (10) равносильна формуле

~~~ p Ú ~~q, (г)

устанавливаем, что формулы (а) и (г) также равносильны.

Аналогичным образом, используя транзитивность и симметричность отношения равносильности, на основании соотношений (1), (19), (14), можно установить, например, равносильность формул р и ~р ® ( ~ ~р Ù q) и т. п.

Далее, подобно тому как в элементарной алгебре заменой «равного равным» осуществляют тождественные преобразования алгебраических выражений, в логике также пользуются правилом замены, позволяющим осуществлять равносильные преобразования и от одних формул переходить к другим, равносильным им формулам. Имеет место следующая теорема.

Теорема. Пусть А_B обозначает формулу А с выделенным вхождением подформулыВ, а А_B¢ — формулу, которая получается из А заменой выделенного вхождения В в А на формулуВ¢. Тогда если В равносильноВ ¢, то А_B равносильно А_{B ¢}.

Доказательство. Докажем это утверждение методом математической индукции. Для формулы А_B построим ее таблицу Т с перечнем пропозициональных переменных E ₁, Е ₂ ,...,Е_n,содержащим все переменные формул А и В¢, а для формулы А_B¢ — ее таблицу Т¢ с таким же перечнем пропозициональных переменных.

Рассмотрим случай, когда А_B — пропозициональная переменная. В этом случае А_B совпадает с В, а А_B¢ — с В¢. Поэтому очевидно, что А_B равносильно А_B¢.

Рассмотрим, далее, случаи, когда А_B не является пропозициональной переменной.

Случай 1. Пусть главным логическим знаком формулы А_B является ~. Тогда А_B имеет вид ~ С_B, а А_B¢ имеет вид ~ С_B¢. Предположим, что теорема верна для формулы С_B, т. е. С_B равносильно С_B¢. Построим для формул С_B и С_B¢ соответственно таблицу T ₁ с перечнями пропозициональных переменных E ₁, Е ₂ ,...,Е_n,и таблицу T ₁¢с тем же перечнем переменных. Можно видеть, что таблица Т ₁ содержится в таблице Т, а таблица T ₁¢—в таблице Т ¢. Так как по индуктивному предположению С_В равносильно С_{B ¢}, заключительные столбцы логических значений в T ₁ и T ₁¢ совпадают. На основании таблицы для ~ заключаем, что в этом случае совпадают и заключительные столбцы таблиц Т и Т ¢. Отсюда следует, что ~ С_B равносильно ~ С_{B ¢}, т. е. А_B равносильно А_{B ¢}.

Случай 2. Пусть главным логическим знаком формулы А_B является Ù. Тогда А_B можно представить в одном из следующих видов:

а) С_B Ù D; б) С Ù D_B,

Упражнения

I. Пользуясь одним только свойством транзитивности отношения равносильности с помощью (1)—(22), доказать равносильность следующих формул:

1) p Ù (q Ú r) и ~ (р Ú q) ® (р Ù r);

2) ~ (р Ú q) и ~(~ р ® ~~ q);

3) ~р ® (q Ù r) и (~~ р Ú q) Ù (~~ р Ú r);

4) (~~ q Ú ~ p) Ù (~~ p Ú ~ q) и ~~(~ q «~ р);

5) ~ (р ® ~ q) и ~(~ р Ú ~ q);

6) p Ú q и (р ® q) Ù (q ® р).

II. Используя (1)—(27) и правило замены, доказать следующие равносильности:

А Ú В равносильно ~ А ® В; (28)

А ® В равносильно ~(А Ù ~ В); (29)

~(А ® В) равносильно (А Ù ~ В); (33)

А «В равносильно ~(~ А ¹ ~ В); (31)

А ¹ В равносильно ~(~ А «~ В); (32)

~(А «В) равносильно ~(А ¹ ~ В ); (33)

~(А ¹ В) равносильно (~ А «~ В). (34)

III. Используя равносильности (1)—(34), с помощью правила замены доказать равносильность следующих формул:

1) (p Ú q) Ù (p Ú p) и p Ù (q Ú p);

2) ~(~ р ® ~ q) и ~ р Ù q;

3) р ® ~ q и q ® ~р;

4) ((p ® q) ® p) ® q и p ® q;

5) ~(р «q) и (р Ù ~ q) Ú (q Ù ~ p);

6) ~(р ¹ q) и р «q;

7) р ¹ q и ~ р ¹ ~ q.

Не нашли, что искали? Воспользуйтесь поиском: