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

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

Например, в таблицах формул (р ® ~q) и ~(p Ú q)

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

Определение. Пусть А и В — формулы, E₁, Е₂,...,Е_n список всех пропозициональных переменных, входящих по крайней мере в одну из них. Будем говорить, что А и В — равносильные формулы (и писать: А равносильно В ), если при любых логических значениях E₁, Е₂,...,Е_n логические значения А и В совпадают.

Равносильными, следовательно, могут быть не только такие формулы, в которые входят одни и те же пропозициональные переменные, но и такие, в которые входят разные переменные. Рассмотрим, например, формулы

(~ p Ù (p ® q)) и (р ® (р Ù r)).

Построим для каждой из них таблицу с перечнем переменных р, q, r, т. е. с перечнем всех переменных, входящих по крайней мере в одну из этих формул:

Из таблиц видно, что данные формулы равносильны. Говорят, что логические значения формулы А не зависят от пропозициональной переменной E_i, если для любого набора логических значений остальных пропозициональных переменных в таблице формулы А логическое значение А одно и то же, когда E_i истинно и когда E_i ложно. Видно, что логические значения обеих формул не зависят ни от переменной 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.

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