Доказательство. Докажем теорему индукцией по глубине формулы U.

Докажем теорему индукцией по глубине формулы U.

1. Базис индукции.Покажем, что если f = , то представляется формулой . Запишем цепочку равенств:

=

=

= .

2. Индуктивное предположение. Предположим, что доказываемое в свойство выполняется для всех формул, глубина которых не превосходит n.

3.Индуктивный переход. Пусть f = U(g₁,..., g_n), где U(g₁,..., g_n) - это формула глубины n + 1, составленная с помощью символов переменных и функций g₁,..., g_n

Предположим, что U = h(U₁, . . . , U_n), где для формул U₁, . . . , U_n и представляемых ими булевских функций w₁, . . . , w_n справедлива доказываемая теорема.

Тогда аналогично доказательству базиса индукции можно показать, что = .

Поскольку всякая функция представляется формулой , то представляется формулой , т.е. формулой U( ,..., ).