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

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

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

p	q	~q	(p  ~q)		p	q	(p  q)	~(p  q)
и	и	л	л		и	и	и	л
л	и	л	и		л	и	л	и
и	л	и	и		и	л	л	и
л	л	и	и		л	л	л	и

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

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

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

(~p  (p  q)) и (р  (р  r)).

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

р	q	r	~р	(p  q)	(~p  (p  q))
и	и	и	л	и	л
л	и	и	и	и	и
и	л	и	л	л	л
л	л	и	и	и	и
и	и	л	л	и	л
л	и	л	и	и	и
и	л	л	л	л	л
л	л	л	и	и	и

р	q	r	~р	(~p  r)	(р  (~р  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.