Доказательство. Докажем теорему индукцией по глубине формулы 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 (,..., ).