3.7.Двойственность.

Булева функция называется двойственной к функции , если она получена из функции инверсией всех аргументов и самой функции. Обозначение: (3.1.)

Возьмём отрицания над обеими частями равенства(3.1.) и подставим

вместо , получим = ( ) = ,

то есть функция двойственна к f. Отношение двойственности между функциями симметрично.

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

Пример 3.24. Построить функции двойственные к данным: а)

б) в) ; г) .

Решение.

а) таким образом , дизъюнкция двойственна конъюнкции.

б) ;

в) ;

г) .

Таким образом, дизъюнкция и конъюнкция , двойственны в силу законов де Моргана. Константа 1 и константа 0 двойственны в силу свойств констант: , .

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

Из определения двойственности вытекает следующее утверждение , называемое принципом двойственности.

Принцип двойственности в булевой алгебре. Если в формуле F, представляющую функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции  на конъюнкции, 1 на 0, 0 на 1, то получим формулу , представляющую функцию , двойственную f.

Двойственную функцию можно построить при помощи таблицы истинности.

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

Пример 3.25. Построить функцию двойственную к стрелке Пирса :а)при помощи равносильных преобразований; б) при помощи таблицы истинности.

Решение.

а) Учитывая, что ,

б)Построим таблицу истинности:

0	0	1	1	1	0	1
0	1	1	0	0	0	1
1	0	0	1	0	0	1
1	1	0	0	0	1	0

Оказалось, что для стрелки Пирса двойственной функцией будет штрих Шеффера Действительно ,легко в этом убедиться по таблице, так как на любых двух противоположных наборах, двойственные функции принимают разные значения -

Функция f ( ) называется самодвойственной, если .

Пример 3.26. Показать, что функция =   самодвойственна.

Решение.

=

Для выяснения самодвойственности функции можно использовать и сравнение значений функции в таблице истинности.

Алгоритм построения самодвойственной функции при помощи таблицы истинности.

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

2. Для построения функции необходимо перевернуть (переписать в обратном направлении) столбец получившийся в результате выполнения пункта 1 ,то есть число, стоящее в первой строке, записать в последнюю строку; число, стоящее во второй строке - в предпоследнюю строку и так далее. Для получения функции необходимо инвертировать компоненты столбца .

Пример 3.27. Является ли функция f самодвойственной: а)f=(1011);б) ;в) f=(01110001).

Решение.

а)Зададим f табличным способом и согласно алгоритму получим:

			f ( , )	( , )
0	0	1	1	0
0	1	0	1	0
1	0	1	0	1
1	1	1	1	0

Так как f ( , ) ( , ), следовательно функция не является самодвойственной.

б)Построим таблицу истинности:

0	0	0	1	1	0	1	1	0
0	0	1	1	0	0	1	1	0
0	1	0	1	1	1	1	0	1
0	1	1	1	0	1	0	1	0
1	0	0	0	1	1	1	0	1
1	0	1	0	0	1	0	1	0
1	1	0	0	1	0	1	1	0
1	1	1	0	0	0	1	1	0

Мы видим, что f ( , , ) ( , , ), следовательно функция не является самодвойственной.

в)Построим таблицу истинности:

0	0	0	0	1	0
0	0	1	1	0	1
0	1	0	1	0	1
0	1	1	1	0	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	0	1	0
1	1	1	1	0	1

f ( , , )= ( , , ), следовательно, функция является самодвойственной. Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения - это говорит о самодвойственности.

Задания. Составить таблицу истинности для функций:

1. а) б) ; в) ; г) ; д) ; е) ; ж) ; з) ; и) ; й) ; к) ;

л) .

2. Показать, что формулы эквивалентны (используя таблицы истинности): а) и ; б) и ; в) и ; г) и ; д) и ; е) и .

3.Проверить с помощью таблицы истинности и при помощи равносильных преобразований является ли формула тождественно ложной или тождественно истинной: а) ;

б) ; в) ; г) ; д) ;

е) ;ж) ;з) .

4.Упростить выражение: а) ; б) в) г) ;

д) ; е) ; ж) ; з) ;

и) ; й) ; к) ; л) .

5. С помощью равносильных преобразований приведите к ДНФ формулы:

а)  б) в)   

г) д) е)

6. С помощью равносильных преобразований приведите к КНФ формулы:

а)  б) в) г) 

д) е) 

7.Для следующих формул записать СДНФ и СКНФ используя соответствующую таблицу истинности: а) х у; б)

8.Найти СДНФ и СКНФ функции заданной таблицей истинности:

а)

0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

б)

9.Преобразовать данную функцию в СДНФ с помощью равносильных преобразований: а) б) в)

г) ;д)

10. Преобразовать данную функцию в СКНФ с помощью равносильных преобразований;

а) б) в) ;

г) ;д)

11.Привести следующие формулы к СДНФ и к СКНФ двумя способами (при помощи равносильных преобразований и при помощи таблиц истинности) : а) ;

б) .

12.Построить двойственную формулу: а) ;)б) ; в) ;

г) ;д) е)

13.Является ли функция самодвойственной: а) f=(1011); б) в) г) ; д) е) ж) ; з)

и) ; й) ;к) ;л) ;м)

Ответы:1.а) ;б) ;в) ;д) ;е) ;ж) ; з) ;и) ;й) ;к) ;л) .2. а) эквивалентны; б) эквивалентны; в) эквивалентны; г) эквивалентны; д) эквивалентны ;е) эквивалентны ;ж) 3. а) тождественно ложная; б) тождественно истинная; в) тождественно ложная; г) тождественно истинная; д) - формула не является ни противоречием, ни тавтологией; е) тождественно ложная ;ж) тождественно истинная; з) тождественно ложная.4. а) ; б) ;в) ;г) ;д) ;е) ;ж) ; з) ;и) ;й) ;к) ;л) .5.а) б) ;в) ;г) д) ;е) ;6.а) ;б) ;в) ;г) ;д) е) .7.а) -СКНФ, -CДНФ;б) -СДНФ, -СКНФ.

8.а)

б)

9.а) ;

б) в) ;

г) д)

10.а) ;б)

в) ;г) ;

д)

11.a)

б) 12.а) ;

б) ;в) ;г) д) ;е)

13.а) несамодвойственна; б)самодвойственна; в) несамодвойственна;г) самодвойственна;

д) самодвойственна; е) самодвойственна; ж) несамодвойственна; з)несамодвойственна;и) не самодвойственна; й) несамодвойственна; к) несамодвойственна;м) несамодвойственна.