Первая теорема Шеннона о представлении булевой функции

Пусть рассматривается k-местная функция f (x₁, …, x_k), не равная тождественно 0. Тогда существует формула алгебры логики F, находящаяся в СДНФ относительно списка переменных <x₁…x_n>, которая представляет функцию f. Формула F определяется однозначно с точностью до порядка дизъюнктивных членов.

Пусть x¹ = x, x⁰ = Øx. Тогда F = Ú (x₁^s1 & … & x_k^sk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 1.

Вторая теорема Шеннона о представлении булевой функции

Пусть рассматривается k-местная функция f (x₁, …, x_k), не равная тождественно 1. Тогда существует формула алгебры логики F, находящаяся в СКНФ относительно списка переменных <x₁…x_n>, которая представляет функцию f. Формула F определяется однозначно с точностью до порядка конъюнктивных членов.

Пусть x¹ = x, x⁰ = Øx. Тогда F = & (x₁^Øs1 Ú … Ú x_k^Øsk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 0.