Функции алгебры логики. Стасюк В.В. - 21 стр.

                                                          х     у      х∨ у
                                                          0     0     0 1 1 1
                                                          0     1      1 0 0
                                                          1     0       1 0
                                                          1     1        1

в первой строке которой записываются значения (0111) функции x ∨ y . По ней формируется
«новая строка» (100) : ее значения записываются под пробелами между значениями «старой
строки» (0111) , причем каждое новое значение является прямой суммой двух ближайших
соседних старых значений. По тому же правилу формируется следующая строка и т.д. По-
следняя строка будет состоять из единственного значения, а все строки вместе будут напо-
минать равнобедренный треугольник с вершиной внизу. После построения таблицы много-
член Жегалкина составляется из тех слагаемых, в чьих строках имеется единица на левом
боковом ребре треугольника, а каждое слагаемое является конъюнкцией переменных, в чьих
позициях соответствующей строки стоят единицы.
(Сравните значения на левом боковом ребре построенного треугольника со значениями ко-
эффициентов α i из таблицы примера 34).
       Единицы на левом боковом ребре треугольника соответствуют наборам значений ар-
гументов (0,1) , (1, 0) и (1,1) , поэтому в многочлен Жегалкина войдут слагаемые y , x и xy .
Упорядочив их в привычной для нас форме, получим:

                                                          x ∨ y = x ⊕ y ⊕ xy ,

что согласуется с предыдущим примером.
Заметим, что единица входит в многочлен Жегалкина для функции f ( x1 ,..., xn ) тогда и толь-
ко тогда, когда f (0,..., 0) = 1 .
        Пример 35. x / y = xy = 1 ⊕ xy — многочлен Жегалкина для штриха Шеффера.

       Лемма 2 (О нелинейной функции). Если функция f ( x1 ,..., xn ) ∉ TL , то из неё подстанов-
кой 0, 1, x , x и, быть может, навешиванием отрицания над f можно получить конъюнкцию
x∧ y.

Доказательство. Если f ( x1 ,..., xn ) ∉ TL , то многочлен Жегалкина для f содержит нелиней-
ное слагаемое, представляющее конъюнкцию по крайней мере двух переменных. Пусть, для
определенности, это будут переменные x1 и x2 . Тогда группируя относительно этих пере-
менных слагаемые многочлена Жегалкина, получим

              f ( x1 ,..., xn ) = x1 x2 f 0 ( x3 ,..., xn ) ⊕ x1 f1 ( x3 ,..., xn ) ⊕ x2 f 2 ( x3 ,..., xn ) ⊕ f3 ( x3 ,..., xn ) ,

где f 0 ( x3 ,..., xn ) ≠ 0 . Значит, существует такой набор (α 3 ,..., α n ) , что f 0 (α 3 ,..., α n ) = 1 . Пусть
на этом наборе f1 (α 3 ,..., α n ) = a , f 2 (α 3 ,..., α n ) = b , f3 (α 3 ,..., α n ) = c и

                                ϕ ( x1 , x2 ) = f ( x1 , x2 , α 3 ,..., α n ) = x1 x2 ⊕ ax1 ⊕ bx2 ⊕ c .

Пусть ψ ( x1 , x2 ) = ϕ ( x1 ⊕ b, x2 ⊕ a) ⊕ ab ⊕ c . Тогда