9. Применение принципа двойственности

Из принципа двойственности следует, что если две формулы А и В эквивалентны, то и двойственные им формулы А^* и В^* также эквивалентны, т.е. если А = В, то и А^* = В^*. Это дает возможность легко получать новые тождества из уже имеющихся. Например, из первого закона Де Моргана по этому правилу получается второй закон, а именно: . А из закона противоречия получается закон исключенного третьего:  . Из первого закона поглощения получается второй закон: х & y  x = x  (х  y) & x = x и т.д..

Пользуясь свойством взаимности, легко записать формулу, эквивалентную заданной и, тем самым, получить новое тождество. Действительно, т.к. f^**=f, т.е. , то для получения формулы, эквивалентной заданной, надо записать двойственную формулу, затем заменить в полученной формуле все переменные символы на их отрицание и, наконец, взять отрицание последней формулы.

Так, например, получаются тождества: – закон Де Моргана, или и – законы взаимовыразимости связок & и .

10. Аналитическая запись функций алгебры логики

Выше было показано, что всякая формула реализует некоторую истинностную функцию. Эквивалентные формулы реализуют одну и ту же функцию. Т.е. по формуле всегда можно найти соответствующую ей функцию. Теперь рассмотрим вопрос о том, как записать функцию алгебры логики в виде формулы, т.е. рассмотрим в некотором смысле обратную задачу.

Для этого введем параметризацию, позволяющую охарактеризовать значение переменной в «энке». Обозначим , где параметр  равен нулю или единице. Таким образом, . Т.е. если на наборе значение переменной х равно 0, то будем писать «», а в случае, когда соответствующее значение равно 1, то будем записывать просто «х». Заметим, что х^=1 тогда и только тогда, когда х=.

1. о разложении функции по переменным

Каждую истинностную функцию от n аргументов f(x₁,x₂,…,x_n) при любом m (1  m  n) можно представить формулой вида: (1)  , где дизъюнкция берется по всевозможным наборам значений переменных х₁,…,х_m.

Представление функции в виде (1) называется разложением функции по m переменным х₁,…,х_m.

Доказательство:

Рассмотрим произвольный набор значений переменных (₁, ₂,…, _n). Покажем, что левая и правая части (1) имеют на этом наборе одинаковые значения. Значение левой части равно f(₁, ₂,…, _n). Вычислим значение правой части: . Ненулевые члены в дизъюнкции получаются только в том случае, когда набор ₁,₂,…,_m совпадает с набором ₁,₂,…,_m, т.е. в последнем выражении остается только одно ненулевое слагаемое: . И т.к. , то это слагаемое равно f(₁, ₂,…, _n). Таким образом, значения левой и правой части (1) совпадают на произвольном наборе (₁, ₂,…, _n).

Следствия:

1) О разложении по одной переменной.

Если в выражении (1) m=1, то f(х₁, х₂,…, х_n) = x_n& f(х₁, х₂,…, 1) & f(х₁, х₂,…, 0);

2) О разложении по всем n переменным или совершенные дизъюнктивные нормальные формы (СДНФ).

Если в выражении (1) m=n, то . Если f(х₁, х₂,…, х_n) не равна тождественно нулю, то в последнюю дизъюнкцию будут давать вклад только те компоненты, где f(₁, ₂,…, _n)=1, поэтому . Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ). И, как следует из её определения, для построения СДНФ в таблице истинности функции f надо рассматривать лишь те строки, где функция равна единице. Для каждой такой строки записывается элементарная конъюнкция, состоящая из всех переменных функции. При этом переменная входит в конъюнкцию с отрицанием, если в рассматриваемой строке её значение равно нулю, и без отрицания – в противном случае.

3) Совершенные конъюнктивные нормальные формы (СКНФ).

Совершенная дизъюнктивная нормальная форма есть выражение вида – сумма произведений. Используя принцип двойственности для построения эквивалентных формул, можно получить разложение вида – произведение сумм, которое носит название совершенной конъюнктивной нормальной формы. Так как , то для

, но . Поэтому . Заметим, что при построении последней формулы участвуют лишь такие наборы ₁,₂,…,_n, на которых f(₁,₂,…,_n)=1. Тогда в построении формулы для будут участвовать наборы ₁,₂,…,_n, где , или f(₁,…,_n)=0.

Таким образом, если f(х₁,…,х_n)  1, то – это и есть СКНФ. И, как следует из её определения, для построения СКНФ в таблице истинности функции f надо рассматривать лишь те строки, где функция равна нулю. Для каждой такой строки записывается элементарная дизъюнкция, состоящая из всех переменных функции. При этом переменная входит в дизъюнкцию с отрицанием, если в рассматриваемой строке её значение равно единице, и без отрицания – в противном случае.

Примеры построения СДНФ и СКНФ.

x	у	f(x,у)	СДНФ	СКНФ
0	0	1
0	1	1
1	0	0
1	1	1	x & y
Таблица 14

В таблице 14 в столбце СДНФ показаны элементарные конъюнкции в единичных строках функции, а в столбце СКНФ – элементарная дизъюнкция в строке, где функция равна нулю. Тем самым, СДНФ=    x & y, СКНФ =. Эти формулы эквивалентны между собой и эквивалентны формуле (ху).

x	у	f(x,у)	СДНФ	СКНФ
0	0	1
0	1	0
1	0	0
1	1	1	x & y
Таблица 15

В таблице 15 в столбце СДНФ показаны элементарные конъюнкции в единичных строках функции, а столбце СКНФ – элементарные дизъюнкции в нулевых строках. Тем самым, СДНФ=  x & y, СКНФ =()&(). Эти формулы эквивалентны между собой и эквивалентны формуле (ху).

Таким образом, построение СДНФ и СКНФ – это ещё одна возможность записать тождество.