Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

43 равны 1. В силу этого между 1  ~ и 1 ~  можно вставить t-1 промежуточных наборов t 2   ~ ,..., ~ : 1 2 1 ... , t     причем наборы, стоящие рядом, будут соседними. Т.к. ) ~ ( ~ ) ( 1 1 f f    , то, по крайней мере, на какой-то одной паре соседних наборов (обозначим их  ~ и ) ~ ) ( ~ ) ( ~    f f  . Пусть  ~ и  ~ – соседние по i -ой координате, т.е. ) ,..., , , ,..., ( ~ ), ,..., , , ,..., ~ ( n i 1 i 1 1 n i 1 i 1 1 1 0                 Рассмотрим функцию ). ,..., , , ,..., ( ) ( n i 1 i 1 1 x f x         Имеем ) ( ). ,..., , , ,..., ( ) ~ ) ( ~ ) ( ,..., , , ,..., ( ) ( 1 1 f f f 0 f 0 n i 1 i 1 1 n i 1 i 1 1                       Следовательно . , . . ( ) , ( ) ( ) 0 1 а 1 0 т е x x       Класс логических функций L Последним классом является класс L всех линейных функций. Он содержит константы 0 и 1 ,функции x, x , x y  и не содержит функций x  y, x&y . Ранее было показано, что этот класс замкнут. Лемма (о нелинейной функции). Если f(x 1 ,…,x n )  L , то из нее путем подстановки констант 0 и 1 и функций x и x ,а также, быть может, путем навешивания отрицания над f можно получить функцию x 1 & x 2 . Замечание. Любая формула, построенная из констант 0,1 и функций x 1 & x 2 и x 1  x 2 , после раскрытия скобок и несложных алгебраических преобразований переходит в полином по mod2 – полином Жегалкина. Доказательство. Возьмем полином Жегалкина для нелинейной функции f :