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

• Базис индукции. 0, 1 и каждая переменная X_i V являются формулами глубины 0.
• Шаг индукции. Пусть Φ₁ и Φ₂ - формулы, ˆ { , , , +, ~, |, }.

Тогда выражения Φ₁ и (Φ₁ ˆ Φ₂) являются формулами. При этом dep( Φ₁)=1 + dep( Φ₁) , а dep((Φ₁ ˆ Φ₂))= 1 + max {dep(Φ₁), dep(Φ₂)} .

В соответствии с этим определением выражения Φ₁(X₁,X₂) = (X₁ X₂) и Φ₂(X₁,X₂,X₃) = ( (X₁ X₂) (X₃ ~ (X₁ X₂))) являются формулами. Глубина Φ₁ равна 3, а глубина Φ₂ равна 4. Выражения же X₁ +( X₂ X₃) , (X₁ X₂) и (X₁ + X₂ + X₃) формулами не являются (почему?).

Для определения функции, задаваемой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующей подформулой. Например, для формулы Φ₂ функция f_Φ2 задается выделенным столбцом следующей таблицы.

Таблица 3.4. Функция f Φ2

X1

X2

X3

((X1

X2)

(X3

~

(X1

X2)))