Лекции по "Дискретная математика"

1.Всякая булева функция f(x1,... ,хп) представима полиномом Жегалкина, т.е. в виде f(x1... хп) = хi1хi2 ... xik с, где в каждом, наборе (i1,.ik) все ij различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов. Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка слагаемых. Полином Жегалкина называется нелинейным (линейным), если он (не) содержит произведения переменных. Т.О, линейность булевой функции равносильна линейности соответствующего полинома Жегалкина.