Скільки лінійних булевих функцій?

Визначення. Булева функція називається лінійною (належить класу L), якщо її поліном Жегалкіна лінійний. Твердження про кількість булевих функцій класу L. Число різних лінійних булевих функцій, що залежать від n змінних, дорівнює 2ⁿ⁺¹.

Число різних булевих функцій, що залежать від n змінних, дорівнює 22n.

Число різних самодвійних булевих функцій, що залежать від n змінних, дорівнює 22n -1. Теорема про замкнутість класу S. Багато всіх самодвійних булевих функцій є замкнутим класом.

Визначення Функція називається лінійною, якщо кожен елементарний твір канонічного полінома Жегалкіна, який представляє цю функціюмає не більше одного співмножника.