Скільки існує різних булевих функцій від n змінних?Скільки існує різних булевих функцій від n змінних?

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

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

Визначення 1 (Бульова функція). Булевою функцією від n аргументів називається функція f з n-ого ступеня множини {0, 1} до множини {0, 1}. Інакше кажучи, бульова функція – це функція, і аргументи і значення якої належить множині {0, 1}.

Визначення: Безліч булевих функцій називається повною системою (англ. complete set), якщо замикання цієї множини збігається з безліччю всіх функцій.