Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 19 стр.

              f � x1 , x 2 � � x1 � x 2 � x1 � x 2 � x1 x 2 � x1 � 1.
      Равносильность формул доказывается:
1. с помощью таблиц истинности;
2. методом эквивалентных (равносильных) преобразований.
      Существует еще один способ доказательства равносильности фор-
мул, основанный на применении так называемого принципа двойственно-
сти.
      Булева функция f � � x1 ,�, xn � называется двойственной к функции
f � x1 ,� , x n � , если f � � x1 ,�, xn � � f � x1 ,�, xn � . Так, функция f � � x, y � � x & y ,
двойственна к f � x, y� � x � y : f � � x , y � � x � y � x & y � x & y .

        Принцип двойственности. Пусть f � x1 ,� , xm � , g1 � x1 ,�, xn � , …,
g m � x 1 ,� , x n � – булевы  функции     и      пусть       �  x1 ,�, xn  
 f  g1  x1 ,�, xn , �, g m  x1 ,�, xn  – суперпозиция функций f , g1 , � , g m . То-
гда двойственная функция от суперпозиции функций равна суперпозиции
двойственных функций:
                                      �                                          �
          � � � x1 ,� , x n � � f � g1� � x1 ,� , x n �, � , g m� � x1 ,� , x n � .

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

       Пример. Пусть f � x � xy , g � x � y . Доказать, что f � g .
       Доказательство. Построим f � и g � :
 f � � f � x , y � � x � x y � x � x y � x & xy � x & � x � y � � x & � x � y � � x & y ;
 g � � g� x , y � � x � y � x & y � x & y .

Видим, что f � � g � . Следовательно, f � g , т. е. x � xy � x � y .
      Доказывается теорема, что число всех булевых функций от n пе-
                      n
ременных равно 2 2 .
      Действительно, любая булева функция от n переменных однозначно
задается столбцом своих значений, длина которого равна 2 n строк, а число
различных столбцов равно числу всех размещений с повторениями из 0 и
                      n     n
1 длины 2 n , т.е. A22 � 2 2 , что и доказывает теорему.
      Примечание. Задание булевой функции в виде функциональной
схемы будет рассмотрено далее.

                                               19