Суперпозицией булевых функций f0 и f1,...,fn называется функция f(x1,...,xm) = f0(g1(x1,...,xm),...,gk(x1,...,xm)), где каждая из функций либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,fn.

Пример: функция f(x,y) = ¬(x & y) является суперпозицией функций ¬ и &.

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

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) → C.

Особо отметим равносильные формулы, которые реализуют логическую константу 1 (истина). Для таких формул используют общее называние тавтология.

Список равенств, выражающих равносильность некоторых логических формул:

    – коммутативность; 

(xÚy)Úz = xÚ(yÚz),   (x&y)&z = x&(y&z) – ассоциативность; 

xÚ0 = x,          x&0 = 0,         xÚ1 = 1,          x&1 = x; – свойства констант;

– двойное отрицание;

            – закон исключенного третьего;      

– закон противоречия;

– идемпотентность;

x&(yÚz) = (x&y)Ú(x&z),  xÚ(y&z) = (xÚy)&(xÚz)  – дистрибутивность; 

    – правила де Моргана.