Формула логики булевых функций определяется индуктивно следующим образом:
1. Любая переменная, а также константы 0 и 1 есть формула.
2. Если A и B – формулы, то A, AVB, A&B, A B, A ~ B есть формулы.
3. Ничто, кроме указанного в пунктах 1–2, не есть формула.
Функция f есть суперпозиция функций f1, f2, ... , fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.
Порядок подстановки задается формулой.
Всякая формула задает способ вычисления функции, если известны значения переменных.
Таким образом, формула каждому набору аргументов ставит в соответствие значение функции.