Булева функція називається лінійною (належить класу L), якщо її поліном Жегалкіна лінійний. Твердження про кількість булевих функцій класу L. Число різних лінійних булевих функцій, що залежать від n змінних, дорівнює 2n+1.
Функція називається лінійною, якщо кожен елементарний твір канонічного полінома Жегалкіна, який представляє цю функціюмає не більше одного співмножника.
Визначення 1 (Бульова функція). Булевою функцією від n аргументів називається функція f з n-ого ступеня множини {0, 1} до множини {0, 1}. Інакше кажучи, бульова функція – це функція, і аргументи і значення якої належить множині {0, 1}.
Визначення: Функція називається лінійної, якщо її поліном Жегалкіна має ступінь не вище за першу, тобто містить кон'юнкції довжиною не більше 1.