Разложение функций алгебры логики по к переменным

Теорема. Всякую логическую функцию f(x)=f( x₁,x₂,x₃,…,x_n ) можно представить в виде

(Знак конъюнкции со списком переменных под ним обозначает, что берётся конъюнкция выражения при всех возможных значениях указанных переменных)

где 1 ≤ k ≤ n. Такое представление называется разложением функции по переменным.

Доказательство теоремы основано на том, что выбрав произвольный двоичный набор и подставив его в левую и правую часть мы получим: слева будет f (), а справа

Следствия:

1) Разложение по k-й переменной:

2) Разложение по всем переменным:

Из последнего утверждения следует теорема о представлении любой функции алгебры логики в сигнатуре алгебры логики: всякая функция алгебры логики может быть представлена в виде формулы, содержащей только операции конъюнкции, дизъюнкции и отрицания.