Линейные функции
Для данной функции многочлен Жегалкина имеет вид:
f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.
Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:
f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.
Булева функция из рассмотренного выше примера не является линейной.
Теорема. Класс L = {f | f = a0+a1x1+…+anxn, aiО{0, 1}} линейных функций замкнут относительно суперпозиций.
предыдущаяследующая