n-местной булевой функцией называется отображение , где n-местность (арность) функции. Это отображение может быть иначе записано как . Переменные  называются пропозициональными переменными.

Множество всех n-местных булевых функций равна . n-местная булева функция может быть представлена таблицей, содержащей  строк, расположенных по возрастанию сверху вниз номера строки. Таким образом, вектор n-местной булевой функции имеет длину . Для задания функции достаточно указать ее вектор, так как последовательность кортежей, обозначающих строку, имеет всегда один и тот же вид. Вектор функции называется логическим значением функции или интерпретацией функции. На каждом наборе значений переменных функция может принять одно из двух значений. Если обозначить множество вершин единичного n-мерного куба, в которых функция равна 1, , а множество вершин, в которых функция принимает значение 0, , то очевидно, что . Для задания полностью определенной булевой функции достаточно указать одно из этих множеств.

Переменная  называется существенной, если выполняется условие: , т.е. существует хотя бы одна пара наборов, соседних по переменной , на которых значения функции различны. В противном случае переменная  называется фиктивной. Фиктивную переменную можно исключить из обозначения функции. При этом длина вектора новой функции будет вдвое меньше длины исходной функции. В теории булевых функций рассматривается отношение равенства булевых функций с точностью до фиктивных переменных. Благодаря этому можно рассматривать при необходимости множество функций одинаковой местности.

Элементарные булевы функции

Элементарными булевыми функциями называются функции с арностью 0, 1 и 2. При этом нужно заметить, что множество функций двух переменных включает в себя все 0-местные и 1-местные функции, в описании которых присутствует две или одна фиктивная переменная соответственно. Множество всех элементарных булевых функций может быть представлено в виде таблицы, содержащей 4 строки и 16 столбцов. Каждый столбец определяет одну из элементарных булевых функций. Наиболее употребимыми являются двуместные функции: {&,Ú,®,«,Å,ê,¯}, одноместные функции f(x)=x и f(x)=`x, и две 0-местные функции: константа 0 и константа 1, не имеющие ни одной существенной переменной (других таких функций в множестве элементарных булевых функций нет).

Элементарные булевы функции используются для аналитического задания булевых функций произвольной местности формулами. При этом используется принцип суперпозиции функций. Согласно этому принципу формула определяется индуктивно:

· Пропозициональная переменная есть формула.

· Если А и В формулы, то любое слово А·В – формула, если ·Î{&,Ú,®,«,Å,ê,¯}. Слово `А также является формулой.

· Других формул нет.

Для формулы может быть построена таблица истинности, которая является ее интерпретацией. Говорят, что пропозициональная формула задает булеву функцию. Соответственно, булева функция реализует ту формулу, которая задает функцию. Очевидно, формула задает единственную булеву функцию. Обратное не справедливо.

Формулы, определяемые суперпозицией функций, могут преобразовываться как алгебраические выражения с использованием множества аксиом и тождеств. Основными из них являются аксиомы тождественности (идемпотентности), коммутативности, ассоциативности, дистрибутивности, поглощения, закон двойного отрицания, правило де-Моргана. Целью преобразования формул является приведение их к каноническому виду. В теории булевых функций используются канонические представления: дизъюнктивная нормальная форма (ДНФ), конъюнктивная нормальная форма (КНФ), полиномиальная нормальная форма. (ПНФ). Для выполнения преобразований используется правило подстановки, которое формулируется следующим образом: если формула образована суперпозицией функций над некоторым множеством функций, то замена вхождения какой-либо функции на равносильную ей не меняет логическое значение функции. Это можно представить как , если  с точностью до фиктивных переменных.