Пусть  – множество булевых функций. Понятие формулы над F определяется индуктивно:

1. Каждая переменная  и каждая булева функция из F являются формулами над F.

2. Если  – формулы над F, то для каждой функции  из F выражение вида  являются формулой над F.

Каждой формуле над F соответствует булева функция, которая называется интерпретацией этой формулы. Интерпретацию, как и формулу, можно определить индуктивно:

1. Интерпретация формулы  сопоставляет элементу  элемент .

2. Интерпретация формулы  принимает значения , где  функции  дополняются, в случае необходимости, фиктивными переменными.

Пример

Пусть . Тогда , ,  и  – формулы над F, ибо

Подставляя  в формулы, получим значения интерпретаций этих формул.

Если интерпретацией формулы g является булева функция f, то формула g называется реализацией функции f. Две формулы называются равносильными, если их интерпретации равны.

Например, формулы  и 1, над , равносильны, ибо функция  принимает значения 1, для всех .

Множество классов равносильных формул составляют булеву алгебру относительно операций:

& ,                     Ú ,                   Ø,

которая называется  алгеброй Линденбаума – Тарского.

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