Вторая теорема Шеннона

В силу принципа двойственности для булевых алгебр справедлива

Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x₁, х₂,...,x_п) представима в виде разложения Шеннона:

В предельном случае, когда k = n, для булевой функции f(x₁, х₂,...,x_п), не равной нулю, получаем ее представление в виде совершенной ДНФ:

Аналогично для булевой функции f(x₁, х₂,...,x_п), не равной единице, получаем ее представление в виде совершенной КНФ:

Приведенные формулы позволяют сформулировать следующую теорему о функциональной полноте.