Определение 3.2.

1. Базис индукции. Каждая переменная X_i V и каждая константа c является формулой глубины 0, т.е. dep(X_i)= dep(c)=0 . Множество ее подформул состоит из нее самой.
2. Шаг индукции. Пусть и A₁, … , A_m - формулы, и max {dep(A_i) | i = 1,…, m} = k . Тогда выражение Φ = f(A₁,… , A_m) является формулой, ее глубина dep(Φ) равна k+1, а множество подформул Φ включает саму формулу Φ и все подформулы формул A₁, …, A_m.

Каждой формуле Φ(X₁,…, X_n) сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

Базис индукции. Пусть dep(Φ)=0. Тогда Φ = X_i V или Φ =c . В первом случае Φ задает функцию f_Φ(X_i)=X_i, во втором - функцию, тождественно равную константе c.

Шаг индукции. Пусть Φ - произвольная формула глубины dep(Φ)= k+1. Тогда Φ(X₁,…, X_n)= f_i(A₁,…, A_m) , где f_i и A₁, …, A_m - формулы, для которых max_{1 i m}{dep(A_i)}=k . Предположим (по индукции), что этим формулам уже сопоставлены функции g₁(X₁,…, X_n), … , g_m(X₁,…, X_n) . Тогда формула Φ задает функцию f_Φ(X₁,…, X_n) = f_i(g₁(X₁,…, X_n), … , g_m(X₁,…, X_n)) .

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