Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Формальная логика.doc
Скачиваний:
7
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

I. Установить частным случаем какой из равносильностей (I)—(22) являются следующие пары формул:

  1. (p->q)A(~r Vs) и ((р ->?) Л ~ г) V ((р ->?) Л s);

  2. (р V (<7 •*-»• г)) Л (~ Я V ~(Р •*-»• /■))

и (р v (<?•*-»•/■)) Л (~ Я V ~ (р *->•/■)) Л (р V ~ <7);

3. ~ р V (<7 Л г) и р -> (<7 Л /■);

4- (~р Л ~ <?) и ~(~~р V ~ ~

5. р V <7 V /■ и ~ (р V <7) -> /■;

6. р V <7 V (г Л «) и (р V <7 V г) Л (р V <7 V s); 7- (р Л (<7 V /■)) Л s и ~ ((р Л (<7 V г)) -> ~s); 8. (р Л <7) V (р Л ~ <7) н р Л (<7 V ~ <?)■

II. С помощью таблиц обосновать следующие равносильности:

а -> в равносильно ~ в -> ~ а; (23)

а •*->-в равносильно ~a-*-»-~b; (24)

а в равносильно ~ (а ■*->■ в); (25)

а -«-*• в равносильно (а -> в) Л (в -> а); (26)

а •*->• в равносильно (а Л в) V (~ а Л ~ в). (27)

III. Проверить, являются ли равносильными следующие формулы:

  1. ~р V? и р -> ~

  2. р->(я->г) и (р Л <7)-»■/■;

3- ~ ((р Л <7) V г) и (р -> ~ <7) Л ~ /■;

  1. ~ р ->((/->/■) и <7 -> (~ р -> /■);

  2. рЛ<7 и <7ЛП

  3. р -> ? и /■->«;

  4. р -><7 и ~pVir,

  5. ~ (р Л ?) и ~ г V ~ а.

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

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

Р -* q (а)

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

~pVq. (б)

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

~ ( р Л ~ ?)• (в)

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

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

r>sr>sr>sp\fr*'~q) (г)

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

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

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

Теорема. Пусть Ав обозначает формулу А с выделенным вхождением подформулы В, а АВ' формулу, которая получается из А заменой выделенного вхождения о в К на формулу В'. Тогда, если В равносильно В', то Ав равносильно Ав'.

Доказательство. Докажем это утверждение методом математической индукции. Для формулы Ав построим ее таб­лицу Т с перечнем пропозициональных переменных Еь Е2, ... .... Е„, содержащим все переменные формул А и В', а для фор­мулы АВ'—ее таблицу Т' с таким же перечнем пропозициональ­ных переменных.

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

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

Случай 1. Пусть главным логическим знаком формулы Ав является ~. Тогда Ав имеет вид ~ Св, а Ав' имеет вид ~ Св'. Предположим, что теорема верна для формулы Св, т. е. Св равносильно Св'. Построим для формул Св и СВ' соответственно таблицу,- Ti с перечнями пропозициональных переменных Е,, Е2 ... Е„ и таблицу Т{ с тем же перечнем переменных. Можно видеть, что таблица Т[ содержится в таблице Т, а таблица Т| в таблице Т'. Так как по индуктивному предположению Св равносильно Св', заключительные столбцы логических значе­ний в Ti и Т' совпадают. На основании таблицы для ~ заклю­чаем, что в этом случае совпадают и заключительные столбцы таблиц Т и Т'. Отсюда следует, что ~ Св равносильно ~ Св', т. е. Ав равносильно АВ'.

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

a) CbAD; b) С Л DB,

так как выделенное вхождение подформулы В может содер­жаться только в одном из конъюнктов.

Рассмотрим подслучай а). Предположим, что теорема верна для формулы Св, т. е. Св равносильно СВ'. Построим для фор­мул Св, Св' и D соответственно таблицы Ti, Та и Тг, каж­дую с перечнем пропозициональных переменных Ei, Е2, ..., Е„. Можно видеть, что Ti содержится в Т, Т[-в Т', а Тг в Т и Т'. Так как по индуктивному предположению Св равносильно Св'. заключительные столбцы логических значений в Ti и Т' совпа­дают. Но тогда на основании таблицы для Л заключительные столбцы логических значений для Св Л D в Т и для Св' Л D в Т' тоже совпадают. Отсюда следует, что Св Л D равно­сильно Св'Л D, т. е. Ав равносильно АВ'.

Подслучай Ь) рассматривается аналогично.

В остальных четырех случаях, когда Ав содержит в качестве главного логического знака V, ->, •*-*■ и -ф- доказательство того, что если В равносильно В', то Ав равносильно АВ', про­текает сходным образом на основании таблиц для соответ­ствующих логических знаков.

Правило, разрешающее в формуле А выделенное вхождение подформулы В заменять равносильной формулой В', назы­вается правилом равносильной замены.

Это правило позволяет, опираясь на равносильность одних формул (В и В'), устанавливать равносильность других (А и А'). Равносильности (1) — (22) были обоснованы с помощью таблиц. Теперь с помощью этих равносильностей, пользуясь правилом замены, мы можем устанавливать равносильность формул уже без обращения к таблицам.

Пусть, например, дана формула

~(рЛ?)-*г. (а)

Заменяем, согласно равносильности (10) подформулу этой формулы ~(рЛ<7) равносильной ей формулой (~pV~<7), В результате получаем формулу

(~pV ~q)-»r. (б)

Далее, так как каждая формула рассматривается в качестве подформулы самой себя, то заменяем согласно равносильности (13) формулу (б) формулой

~(~pV ~q)V г. (в)

Затем, подформулу этой формулы ~(~р V ~<7) заменяем со­гласно равносильности (11) формулой (~~рЛ~~<7) и по? лучаем формулу

( Р Л ~ ~ <?) V г, (г)

Заменив теперь согласно равносильности (1) подформулу ~ ~р и подформулу ~~q соответственно формулами р и q, полу­чаем формулу

(Р Л q) V г. (д)

Согласно прагилу замены формула (а) равносильна фор­муле (б); формула (б)—формуле (в); формула (в) — фор­муле (г) и формула (г) — формуле (д), откуда в силу транзи­тивности отношения равносильности следует, что формула (а) равносильна формуле (g).

Упражнения: