Первая теорема Шеннона

Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x₁, х₂,...,x_п) по k; переменным (для определенности по x₁, х₂,...,x_k) — разложения Шеннона.

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

Доказательство. Прежде всего, заметим, что . Подставим произвольно вместо первых k переменных их значения: . Тогда левая часть доказываемой формулы равна Правая часть представляет собой дизъюнкцию 2^k конъюнкций вида , которые этой подстановкой разбиваются на два класса. К первому классу относится конъюнкция, у которой набор (δ₁, δ₂,...,δ_k) совпадает с набором :

=

= 1 1... 1 =

Эта конъюнкция равна левой части формулы. Ко второму классу относится 2^k-1 конъюнкций, у каждой из которых хотя бы в одной переменной x_i, выполнено условие . Следовательно, каждая из них равна нулю. Используя закон , получаем, что левая и правая части формул равны при любой подстановке переменных x₁, x₂..., x_n.