§ 10. Представление произвольной булевой функции в виде формул

Известно, что булеву функцию можно задавать табличным и графическим способами, словесным описанием, порождающей процедурой или в аналитическом виде, т.е. в виде формул. Спрашивается, всегда ли можно для булевой функции f(x1,x2,…,xn) найти такую формулу, чтобы значения функции и формулы совпадали при одинаковых значениях переменных, т.е. можно ли представить f(x1,x2,…,xn) посредством формулы.

Введем обозначение:

Очевидно, что $x^a=a\& x∨¬a\&¬x$ и

Теорема 3.14.(О разложении булевой функции по переменным.) Для любой булевой функции f(x1, x2,…, xn) и любого m, 1≤ m≤ n, имеет место следующее равенство:

где дизъюнкция берется по всем возможным наборам (a1, a2…, am).

Доказательство. Выберем произвольные значения для аргументов x1, x2,…, xn, пусть, например, x1=b1, x2=b2,…, xn=bn. Тогда в правой части соотношения (3.16) получим:

Если хотя бы для одного множителя $b_i^{a_i}$ 1≤ i≤ m , окажется, что bi ≠ ai, то из (3.15) следует, что biai =0 и тогда всё слагаемое в (3.17), содержащее ai bi , обратится в нуль. Следовательно, в выражении (3.17) останется только одно слагаемое, в котором bi= ai для всех i, 1≤ i≤ m. В результате получим, что дизъюнкция (3.17) сводится к одному слагаемому:

Учитывая, что bibi =1, получим, что дизъюнкция (3.17) равна f(b1, b2,…, bn), т.е. равна левой части равенства (3.16) при выбранных значениях переменных.

Представление функции f в виде (3.16) называют разложением Шеннона.

Следствие 3.2.

Следствие 3.3. Если f(x1, x2,…, xn) не тождественно равна 0, то:

Здесь дизъюнкция берется только по тем наборам (a1, a2…, an), для которых f(a1, a2…, an)=1.

Доказательство. Очевидно, что в правой части соотношения (3.16) слагаемые с f(a1,a2…,an)=0 можно отбросить, в результате получим (3.18).

Теорема 3.15. Для любой булевой функции f(x1, x2…, xn) и любого m, 1≤ m ≤ n, имеет место следующее равенство:

где конъюнкция берется по всевозможным наборам (a1, a2…, am).

Доказательство проводится аналогично доказательству теоремы 3.17.

Следствие 3.4. Если f(x1, x2,…, xn) не тождественно равна 1, то

Здесь конъюнкция берется только по тем наборам (a1, a2…, an), для которых f(a1, a2…, an)=0.