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

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

((р Ú ~ 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).

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