Определение. Булева функция называется линейной, если она представляется в алгебре Жегалкина каноническим многочленом (полиномом Жегалкина)

Булева функция называется линейной, если она представляется в алгебре Жегалкина каноническим многочленом (полиномом Жегалкина), не содержащем конъюнкций переменных:, где коэффициенты , принимающие значение 0 или 1.

Так как всего коэффициентов , то число различных линейных многочленов будет . В силу однозначности представления функции полиномом Жегалкина это число выражает и количество линейных функций.

Обозначим через класс линейных функций.

Пример.

Отрицание является линейной функцией, т.к. её полином Жегалкина () не содержит конъюнкций переменных. Дизъюнкция является нелинейной функцией, поскольку её полином Жегалкина () содержит конъюнкцию переменных и . Импликация является нелинейной функцией, так как её полином Жегалкина () содержит конъюнкцию переменных и . Эквивалентность является линейной функцией, поскольку её полином Жегалкина ()не содержит конъюнкций переменных.

Дата добавления: 2014-10-22