Визначення 1 (Булева функція). Булевою функцією від n аргументів називається функція f з n-ого ступеня множини { 0, 1 } до множини { 0, 1 }. Інакше висловлюючись, булева функція – це функція, і аргументи і значення якої належить множині { 0, 1 }.
Аналітичний запис БФУ у вигляді формули, що використовує логічні операції (базис формули), називається булевою формовий (БФ). У цій роботі розглядаються формули у різних базах, але основна увага приділяється формулам в базисі І, АБО, НЕ.
Теорема про число булевих функцій. Число різних булевих функцій, що залежать від n змінних, дорівнює 22n.
Бульова змінна – це змінна зі значеннями з бульова множини B = {0,1}. Позначаються булеви змінні символами: a, b, c, …, x, y, z або тими ж символами з індексами: x1 x2, …, xn.