§ 8. Закон двойственности

Знаки  и , а также знаки  и  являются двойственными логическими знаками.

Определение. Пусть  формула, в которую не входит знак . Формулой, двойственной А, называют формулу А*, которая получается из А заменой каждого вхождения знаков  и  соответственно двойственными им знаками  и  и заменой каждого вхождения знаков  и  в А соответственными им знаками  и .

Например, если А — формула

((р  ~q)  r)  ~(~р  (r  s)),

то двойственная ей формула А* будет иметь вид

((р  ~q)  r)  ~(~р  (r  s)).

Ясно, что если формула А* двойственна формуле А, то и, наоборот, формула А двойственна формуле А*.

Рассмотрим таблицы для конъюнкции и дизъюнкции. Можно видеть, что если в таблице для конъюнкции во всех трех столбцах для А, В и (А  В) все логические значения «истина» заменить логическими значениями «ложь», а все логические значения «ложь» — логическими значениями «истина», то получим таблицу формулы (A  B). Если же в таблице формулы (A  B) аналогичным образом во всех трех столбцах для А, В (А  В) поменять все логические значения на противоположные, то получим таблицу формулы (А  В). Эти соотношения находят выражение в равносильностях (15) и (14).

То же самое имеет место в отношении таблиц для эквивалентности и строгой дизъюнкции: таблица формулы (А  В) переходит при взаимной замене логических значений во всех трех столбцах в таблицу формулы (А  В), а таблица формулы (А  В) — в таблицу формулы (A  В). Эти соотношения находят выражение в равносильностях (32) и (31).

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

Лемма. Пусть А — формула, не содержащая знака , А* — двойственная ей формула, a E₁, Е₂, ..., E_n — список, всех входящих в эти формулы пропозициональных переменных. Пусть, далее, А —формула, которая получается из А заменой всех вхождений переменных E₁, Е₂, ... E_n в формулу А соответственно их отрицаниями ~E₁, ~Е₂, ..., ~E_n. Тогда ~А равносильно А*.

Теорема (закон двойственности). Если А* и В* — формулы, двойственные соответственно формулам А и В и если А равносильно В, то А* равносильно В*.

Доказательство. Пусть А и В — формулы, которые получаются из не содержащих знака  формул А и В заменой всех переменных в А и В соответственно отрицаниями этих переменных. Тогда, если А равносильно В, то А равносильно В, так как согласно определению равносильности А и В принимают одинаковые логические значения при любых логических значениях общего списка своих переменных, а значит, и при любых логических значениях их отрицаний. Но если А равносильно В, то ~А равносильно ~В. А так как двойственная А формула А* равносильна ~А и двойственная В формула В* равносильна ~В, то в силу транзитивности отношения равносильности А* равносильно В*.

Формула А называется самодвойственной, если А равносильно А*. Например, самодвойственной является формула

(р  q)  (p  r)  (q  r).

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

Упражнения

I. Построить, если возможно, формулы, двойственные следующим:

1. (р  q)  ((q  r)  (р  r));

2. (((p  q)  r)  s)  (((р  q)  r)  s);

3. ~((р  q)  (~р  ~q)).

II. Используя равносильности (10), (11), (33) и (34), обосновать следующее соотношение: ~A* равносильно А, где А* в А означают то же, что на с. 37 — 38.

III. Установить, какие из следующих логических знаков , , , ,  и  образуют двойственные пары.