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

     кнопку, и не нажимал, если он голосует «против», и чтобы в случае, если
     будет большинство человек голосовать «за», – загоралась лампочка.



                       6. ПОЛИНОМ ЖЕГАЛКИНА.
                  ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ ФУНКЦИИ

     Элементарная конъюнкция называется монотонной, если она не со-
держит отрицательных переменных.
     Полиномом Жегалкина, или полиномом по модулю 2, называется
формула:
                          P � x1 , ..., x n � � K 1 � K 2 � K 3 � ... � K l ,
где K i �i � 1, ..., l � — попарно различные монотонные элементарные конъ-
юнкции, составленные из переменных x1 , ..., x n .
     Наибольший из рангов элементарных конъюнкций, входящих в по-
лином, называется степенью этого полинома. Число l называется длиной
полинома. При l � 0 полагаем P � x1 , ..., x n � � 0 .
     Имеет место следующее утверждение.
     Для каждой булевой функции существует, и при этом единст-
венно, представление в виде полинома Жегалкина, который может
быть записан следующим образом:
                      P  x1 ,..., xn  =                            ai1 ...is xi1 ... xis .
                                            i1 ,...,is О1,...,n
         Число возможных монотонных конъюнкций xi1 ... xis равно количе-
ству подмножеств �i1 ,..., i s � множества �1,2 ,..., n�, т.е. 2 n .Коэффициенты
a i ...i принимают значение либо 0, либо 1.
 1   s


          Отметим два способа построения полинома Жегалкина.
1.        Метод неопределенных коэффициентов. Применяется в основном
тогда, когда булева функция f � x1 , ..., x n � задана таблицей истинности или
набором своих значений. При построении полинома Жегалкина методом
неопределенных коэффициентов:
          Во-первых, выписываем общий вид полинома Жегалкина для функ-
ций от n переменных.
          Во-вторых, исходя из того, что f � x1 , ..., x n � и искомый полином
P � x1 , ..., x n � на одинаковых наборах входящих в них переменных прини-
мают одинаковые значения, составляем систему 2 n уравнений с 2 n неиз-
вестными a i ...i .
              1   s


          В-третьих, решаем систему, найденную на предыдущем шаге, на-
ходим коэффициенты a i ...i и выписываем искомый полином.
                               1   s


                                                    42