Принцип двойственности

Список основных равносильностей алгебры высказываний состоит из двух столбцов, один из которых получается заменой дизъюнкции на конъюнкцию и наоборот в другом столбце (0 на 1 и 1 на 0). Это не случайно, а является следствием закона двойственности.

Определение. Пусть F булева формула, т.е. формула, не содержащая импликаций, двойственной F* формулой называется формула, полученная из F заменой дизъюнкции на конъюнкцию и наоборот, а также 0 заменяется на 1 и 1 - на 0. Ясно, что (F^*)^*= F.

Теорема 1. Пусть F(x₁,...,x_k) - булева формула алгебры высказываний, зависящая от элементарных высказываний x₁, x₂,...,x_k. Тогда отрицание формулы равносильно двойственной формуле от отрицаний, т.е. =F^*( ₁, ₂,..., _k)

Теорема 2. Две формулы равносильны FºG тогда и только тогда, когда равносильны двойственные им F^*ºG^*.

Доказательство этих теорем основывается на законах де Моргана, которые являются частным случаем теоремы 1. Заметим, что F^*(х₁, х₂,...,х_k)ºF^*( ₁, ₂,..., _k)= F . Это позволяет проще строить двойственную функцию для функции F, заданной своими значениями.

Пример 1. Для функции F=(0,0,1,0) построить двойственную.

1 способ. Функция F принимает значение 1 только для набора с номером 2, т.е. (1, 0). Значит, F=x`y. Тогда F<sup>*</sup>=xÚ`y. F^* принимает значение 1 для наборов (0, 0), (1, 0), (1, 1), т.е. F^*=(1, 0, 1, 1).

2 способ. Если F зависит от k переменных, то набор их значений мы условились располагать, используя двоичную запись порядка набора, начиная с 0 до 2^k-1. Для набора переменных (`х<sub>1</sub>, `х₂,...,`х<sub>k</sub>) эта последовательность будет в обратном порядке. Так, для k=2 последовательность значений вектора (x<sub>1</sub>, x<sub>2</sub>) будет (0, 0), (0, 1), (1, 0), (1, 1). Для вектора (`х₁,`х<sub>2</sub>) ей будет соответствовать последовательность значений (1, 1), (1, 0), (0, 1), (0, 0). Кроме того, если F=1, то`F=0 и наоборот. Отсюда такое правило: последовательности значений F сопоставим последовательность, для которой в обратном порядке 0 заменится на 1, а 1 - н а 0. Для данной функции F это будет (1, 0, 1, 1), и это функция F^*. Получаем тот же результат.

Пример 2. Для функции F=(0, 1, 0, 1, 1, 1, 0, 1) построить двойственную.

Ответ: F*=(0, 1, 0, 0, 0, 1, 0, 1).

Замечание. Теоремы двойственности упрощают построение КНФ, если ДНФ, равносильная данной формуле, уже построена.

Итак, пусть FºF₁, где F₁ - ДНФ. Тогда F₁^* - КНФ. Раскрыв скобки, приведём F₁^* к равносильной ей ДНФ. F₁^*ºF₂ и F₂ - ДНФ. Тогда F₁=(F₁^*)^*ºF₂^*. Значит FºF₁ºF₂^* уже КНФ.

Пример 3. Найти ДНФ и КНФ, равносильные формуле F=(x`y«z)Úyz.

Решение. Найдём сначала равносильную булеву формулу.

Fº(x`yzÚ z)Úyzº(x`yzÚ(`xÚ )`z)Úyzºx`yzÚ`x`zÚy`zÚyzºx`yzÚ`x`zÚy=F1 это ДНФ.

Здесь y Úyz=y(`zÚz)ºy×1ºy.

F₁^*=(xÚ`yÚz)(`xÚ`z)yº(x`xÚx`zÚ`y`xÚ`y`zÚz`xÚz`z)yºx`zyÚ`y`xyÚ`y`zyÚz`xyºxy`zÚ`xyz=F<sub>2</sub>[`xx=z`z=`y`xy=`y`zy=0]. Теперь F<sub>2</sub><sup>*</sup>=(xÚyÚ`z)(`xÚyÚz)º(F₁^*)^*=F₁ºF

F₂^* - КНФ и СКНФ.