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

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

1) любая логическая переменная является формулой (атомарной);

2) если и - формулы, то выражения и другие, представленные в табл. 1, являются формулами;

3) никаких других формул, кроме построенных в пунктах 1 и 2, нет.

Если формула построена из логических переменных, лежащих в множестве 1, x₂,…, x_n>, то будем писать 1, x₂,…, x_n>.

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

На множестве вводится транзитивное отношение < «быть более сильным» и отношение

«быть равносильным» по правилам, представленным на рис. 2. Для равносильных связок расстановка скобок выполняется слева направо.

Все формулы алгебры логики можно разделить на 3 класса:

1) нейтральные, или выполнимые - принимающие как истинное, так и ложное значения;

2) тождественно истинные формулы (или тавтологии) - принимающие истинные значения при любых значениях переменных;

3) тождественно ложные формулы - принимающие ложные значения при любых оценках переменных.

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

Табличный способ определения истинного значения формул имеет ограниченное применение, поскольку при увеличении количества переменных приходится рассматривать слишком много вариантов (2 N ).

Равносильными называются два высказывания, у которых таблицы истинности совпадают.