ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Равносильные формулыИногда различные по своей структуре формулы таковы, что одинаковым наборам логических значений переменных во входных столбцах таблиц этих формул отвечают одинаковые логические значения в соответствующих строках заключительных столбцов. Например, в таблицах формул (р ® ~q) и ~(p Ú q)
одинаковым набором логических знаний переменных р и q во входных столбцах отвечают одинаковые логические значения в соответствующих строках заключительных столбцов. О подобных формулах говорят, что они равносильны. Определение. Пусть А и В — формулы, E1, Е2,...,Еn список всех пропозициональных переменных, входящих по крайней мере в одну из них. Будем говорить, что А и В — равносильные формулы (и писать: А равносильно В ), если при любых логических значениях E1, Е2,...,Еn логические значения А и В совпадают. Равносильными, следовательно, могут быть не только такие формулы, в которые входят одни и те же пропозициональные переменные, но и такие, в которые входят разные переменные. Рассмотрим, например, формулы (~ p Ù (p ® q)) и (р ® (р Ù r)). Построим для каждой из них таблицу с перечнем переменных р, q, r, т. е. с перечнем всех переменных, входящих по крайней мере в одну из этих формул:
Из таблиц видно, что данные формулы равносильны. Говорят, что логические значения формулы А не зависят от пропозициональной переменной Ei, если для любого набора логических значений остальных пропозициональных переменных в таблице формулы А логическое значение А одно и то же, когда Ei истинно и когда Ei ложно. Видно, что логические значения обеих формул не зависят ни от переменной r, ни от переменной q. Отношение равносильности, во-первых, рефлексивно, т. е. А равносильно А; во-вторых, симметрично, т. е. если А равносильно В, то В равносильно А, и, в-третьих, транзитивно, т. е. если А равносильно В и В равносильно С, то А равносильно С. Два высказывания называются равнозначными, если они могут быть получены из равносильных формул А и В в результате замены всех входящих в них переменных конкретными высказываниями. Например, высказывание Если студент плохо знает предмет, то он не сдаст экзамен равнозначно высказыванию Неверно, что студент плохо знает предмет и он сдаст экзамен, так как их можно получить из формул (р ® ~ q) и ~(p Ù q), придавая переменным р и q значения Студент плохо знает предмет и Он сдаст экзамен. Рассмотрим некоторые равносильные формулы, условившись в дальнейшем во всех формулах для упрощения записи опускать внешние скобки. Пусть А — любая формула, тогда ~~ А равносильно A. (l) Эта равносильность означает, что двойное отрицание любой формулы равносильно самой этой формуле: формула ~~ А истинна, когда истинна формула А, и ложна, когда А ложна. В этом легко убедиться, построив таблицу, во входном столбце которой выписаны логические значения формулы А, а в заключительном — логические значения формулы ~~ А.
Равносильность всех приводимых ниже схем формул также может быть обоснована построением соответствующих таблиц. Таблицы для схем формул строятся аналогично таблицам для формул, с той лишь разницей, что везде вместо пропозициональных переменных р, q, r, s... стоят буквы А, В, С, D... Фактическое построение таких таблиц предоставляется читателю. Пусть А, В, С — любые формулы, тогда А Ù В равносильно В Ù А; (2) А Ù (В Ù С) равносильно (А Ù В) Ù С. (3) Равносильности (2) и (3) свидетельствуют о коммутативности и ассоциативности конъюнкции. Учитывая равносильность (3), условимся в дальнейшем употреблять бесскобочную запись А Ù В Ù С. Равносильности А Ú В равносильно В Ú А; (4) А Ú (В Ú С) равносильно (А Ú В) Ú С (5) свидетельствуют о коммутативности и ассоциативности дизъюнкции. Учитывая (5), условимся в дальнейшем употреблять бесскобочную запись А Ú В Ú С. Следующие равносильности: А Ú (В Ù С) равносильно (А Ú В) Ù (А Ú С); (6) (В Ù С) Ú А равносильно (А Ú В) Ù (А Ú С); (6') А Ù (В Ú С) равносильно (А Ù В) Ú (А Ù С); (7) (В Ú С) Ù А равносильно (А Ù В) Ú (А Ù С) (7') свидетельствуют о дистрибутивности дизъюнкции относительно конъюнкции и дистрибутивности конъюнкции относительно дизъюнкции. Проиллюстрируем равносильность (7). Высказывание о погоде за какой-то период Стояли морозные дни, и в то же время был сильный снегопад или дул резкий ветер, которое имеет вид А Ù (В Ú С), равнозначно высказыванию Стояли морозные дни, и был сильный снегопад, или же стояли морозные дни, и дул резкий ветер, которое имеет вид (А Ù В) Ú (А Ù С). Следующие две равносильности: А Ù А равносильно А; (8) А Ú А равносильно А (9) Называются законами идемпотентности конъюнкции и дизъюнкции. Равносильности ~(А Ù В) равносильно ~ А Ú ~ В; (10) ~(А Ú В) равносильно ~ А Ù ~ В (11) называются законами де Моргана. Примером (10) является равнозначность высказывания Неверно, что данный треугольник прямоугольный и что он в то же время равнобедренный высказыванию Или этот треугольник не прямоугольный, или он не равнобедренный. Заметим, что так как дизъюнкция здесь не исключающая, то может быть, что этот треугольник и не прямоугольный, и не равнобедренный. Примером (11) может служить равнозначность высказывания Неверно, что или он изучал логику в школе, или он прослушал курс логики в вузе высказыванию Он не изучал логику в школе и он не слушал курса логики в вузе. Рассмотрим еще ряд равносильностей. А Ù В равносильно ~(А ® ~ В). (12) Например, высказывание Летом он поедет в Ленинград и посетит Эрмитаж равнозначно высказыванию Неверно, что если летом он поедет в Ленинград, то не посетит Эрмитаж. А ® В равносильно ~ A Ú B. (13) Например, высказывание Если взялся за дело, то доведи его до конца равнозначно высказыванию Или не берись за дело, или доведи его до конца. А Ù В равносильно ~(~ A Ú ~ B). (14) Например, высказывание У квадрата стороны равны и углы прямые равнозначно высказыванию Неверно, что у квадрата стороны не равны или углы не прямые. A Ú B равносильно ~(~ А Ù ~ В). (15) Например, высказывание Данный треугольник или равносторонний или равнобедренный равнозначно высказыванию Неверно, что данный треугольник не равносторонний и не равнобедренный. В дальнейшем нам понадобятся также равносильности А «В равносильно (~ А Ú В) Ù (~ В Ú А); (16) А ¹ В равносильно (А Ú В) Ù (~ А Ú ~ В); (17) (А Ú В) Ù (~ А Ú В) равносильно В; (18) А Ù (А Ú В) равносильно А; (19) А Ú (А Ù В) равносильно А; (20) (А Ú C) Ù (В Ú ~ C) равносильно (А Ú C) Ù (В Ú ~ C) Ù (А Ú В); (21) (А Ù C) Ú (В Ù ~ C) равносильно (А Ù C) Ú (В Ù ~ C) Ú (А Ù В). (22) Равносильность (18) называется законом исключения, равносильности (19) и (20) — законами поглощения, а равносильности (21) и (22) — законами выявления. Каждое из соотношений (1) — (22) содержит схемы формул и относится к бесконечному множеству равносильных друг другу формул логики высказываний соответствующего вида. Например, равносильность (13) относится к следующим парам конкретных формул: p ® q и ~p Ú q; ~ p ® ~ q и ~~ р Ú ~q; p ® р и ~p Ú p; ~ q ® ~ q и ~~q Ú ~q; (~p Ù q) ® (r Ú ~s) и ~(~ р Ù q) Ú (r Ú ~s); ((p ® q) ® r) ® s и ~((р ® q) ® r) Ú s и т. д.
Упражнения I. Установить частным случаем какой из равносильностей (1) — (22) являются следующие пары формул: 1) (p ® q) Ú (~r Ú s) и ((p ® q) Ù ~r) Ú ((p ® q) Ù s); 2) (р Ú (q «r)) Ú (~ q Ú ~(p «r)) и (р Ú (q «r)) Ù (~ q Ú ~(p «r)) Ù (p Ú ~ q); 3) ~ р Ú (q Ù r) и р ® (q «r); 4) (~ р Ù ~ q) и ~(~~ p Ú ~~ q); 5) р Ú q Ú r и ~(р Ú q) ® r; 6) р Ú q Ú (r Ù s) и (р Ú q Ú r) Ù (p Ú q Ú s); 7) (р Ù (q Ú r)) Ù s и ~((р Ù (q Ú r)) ® ~ s); 8) 8. (р Ù q) Ú (p Ù ~q) и p Ù (q Ú ~ q). II. С помощью таблиц обосновать следующие равносильности: А ® В равносильно ~ В ® ~ А; (23) А «В равносильно ~ A «~ B; (24) А ¹ В равносильно ~(A «B); (25) А «В равносильно (В ® A) Ù (B ® A); (26) А «В равносильно (A Ù B) Ú (~ A Ù ~ B). (27) III. Проверить, являются ли равносильными следующее формулы: 1) ~p Ú q и p ® ~q; 2) p ® (q ® r) и (р Ù q) ® r, 3) ~ ((р Ù q) Ú r) и (р ® ~ q) Ù ~ r; 4) ~p ® (q ® r) и q ® (~ р ® r); 5) р Ú q и q Ú r; 6) р ® q и r ® s; 7) р ® q и ~ р Ú r. 8) ~(р Ù q) и ~ r Ú ~ s. Не нашли, что искали? Воспользуйтесь поиском:
|