![]() ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Правило равносильной заменыИспользуя транзитивность отношения равносильности, мы, зная о равносильности одних формул, можем судить о равносильности других. Например согласно (13) формула p ® q (a) равносильна формуле ~p Ú q. (б) Последняя же, согласно (15), равносильна формуле ~ (~ ~p Ù ~q). (в) В силу транзитивности отношения равносильности отсюда следует, что формулы(а) и (в) равносильны. Поскольку же формула (в) согласно (10) равносильна формуле ~~~ p Ú ~~q, (г) устанавливаем, что формулы (а) и (г) также равносильны. Аналогичным образом, используя транзитивность и симметричность отношения равносильности, на основании соотношений (1), (19), (14), можно установить, например, равносильность формул р и ~р ® ( ~ ~р Ù q) и т. п. Далее, подобно тому как в элементарной алгебре заменой «равного равным» осуществляют тождественные преобразования алгебраических выражений, в логике также пользуются правилом замены, позволяющим осуществлять равносильные преобразования и от одних формул переходить к другим, равносильным им формулам. Имеет место следующая теорема. Теорема. Пусть АB обозначает формулу А с выделенным вхождением подформулыВ, а АB¢ — формулу, которая получается из А заменой выделенного вхождения В в А на формулуВ¢. Тогда если В равносильноВ ¢, то АB равносильно АB ¢. Доказательство. Докажем это утверждение методом математической индукции. Для формулы АB построим ее таблицу Т с перечнем пропозициональных переменных E 1, Е 2 ,...,Еn,содержащим все переменные формул А и В¢, а для формулы АB¢ — ее таблицу Т¢ с таким же перечнем пропозициональных переменных. Рассмотрим случай, когда АB — пропозициональная переменная. В этом случае АB совпадает с В, а АB¢ — с В¢. Поэтому очевидно, что АB равносильно АB¢. Рассмотрим, далее, случаи, когда АB не является пропозициональной переменной. Случай 1. Пусть главным логическим знаком формулы АB является ~. Тогда АB имеет вид ~ СB, а АB¢ имеет вид ~ СB¢. Предположим, что теорема верна для формулы СB, т. е. СB равносильно СB¢. Построим для формул СB и СB¢ соответственно таблицу T 1 с перечнями пропозициональных переменных E 1, Е 2 ,...,Еn,и таблицу T 1¢с тем же перечнем переменных. Можно видеть, что таблица Т 1 содержится в таблице Т, а таблица T 1¢—в таблице Т ¢. Так как по индуктивному предположению СВ равносильно СB ¢, заключительные столбцы логических значений в T 1 и T 1¢ совпадают. На основании таблицы для ~ заключаем, что в этом случае совпадают и заключительные столбцы таблиц Т и Т ¢. Отсюда следует, что ~ СB равносильно ~ СB ¢, т. е. АB равносильно АB ¢. Случай 2. Пусть главным логическим знаком формулы АB является Ù. Тогда АB можно представить в одном из следующих видов: а) СB Ù D; б) С Ù DB, так как выделенное вхождение подформулы В может содержаться только в одном из конъюнктов. Рассмотрим подслучай а). Предположим, что теорема верна для формулы СB, т. е. СB равносильно СB ¢. Построим для формул СB, СB ¢ и D соответственно таблицы T 1, T 1¢ и Т 2, каждую с перечнем пропозициональных переменных E 1, Е 2 ,...,Еn. Можно видеть, что T 1 содержится в Т, T 1¢ — в T ¢, а Т 2 в Т и Т ¢. Так как по индуктивному предположению СB равносильно СB ¢, заключительные столбцы логических значений в T 1 и T 1¢ совпадают. Но тогда на основании таблицы для Ù заключительные столбцы логических значений для СB Ù D в Т и для СB ¢ Ù D в Т ¢ тоже совпадают. Отсюда следует, что СB Ù D равносильно СB ¢ Ù D, т. е. АB равносильно АB ¢. Подслучай б) рассматривается аналогично. В остальных четырех случаях, когда АB содержит в качестве главного логического знака Ú, ®, «и ¹ доказательство того, что если В равносильно В ¢, то АB равносильно АB ¢, протекает сходным образом на основании таблиц для соответствующих логических знаков. Правило, разрешающее в формуле А выделенное вхождение подформулы В заменять равносильной формулой В ¢, называется правилом равносильной замены. Это правило позволяет, опираясь на равносильность одних формул (В и В ¢), устанавливать равносильность других (А и А ¢). Равносильности (1) — (22) были обоснованы с помощью таблиц. Теперь с помощью этих равносильностей, пользуясь правилом замены, мы можем устанавливать равносильность формул уже без обращения к таблицам. Пусть, например, дана формула ~ (p Ù q) ® r. (а) Заменяем, согласно равносильности (10) подформулу этой формулы ~(p Ù q) равносильной ей формулой (~ p Ú ~ q). В результате получаем формулу (~p Ú ~q) ® r. (б) Далее, так как каждая формула рассматривается в качестве подформулы самой себя, то заменяем согласно равносильности (13) формулу (б) формулой ~(~p Ú ~q) Ú r. (в) Затем подформулу этой формулы ~(~ р Ú ~ q) заменяем согласно равносильности (11) формулой (~~ p Ù ~~ q) и получаем формулу (~~р Ù ~~q) Ú r. (г) Заменив теперь согласно равносильности(1) подформулу ~~ р и подформулу ~~q соответственно формулами р и q, получаем формулу (р Ù q) Ú r. (д) Согласно правилу замены формула (а) равносильна формуле (б); формула (б) — формуле (в); формула (в) — формуле (г) и формула (г) —формуле (д), откуда в силу транзитивности отношения равносильности следует, что формула (а) равносильна формуле (д). Упражнения 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. Не нашли, что искали? Воспользуйтесь поиском:
|