Дискретная математика

69 Введем обозначение; \х, если а = 1 X - 1-1X, если а = 0. Очевидно, что x °-a&xvla&lx и 1, если х = а О, если X ^ а. ^ (3.15) Теорема 3.14. (О разложении булевой функции по переменным.) Для любой булевой функции f(xi, ..., xj и любого т, 1< т< п, имеет место следующее равенство: /(Х/, Х2,.... Хт, Х„+1,..., = (3.16) = V xf' &...&x'^f &f(a „ а2 а» х^^, х^, где дизъюнкция берется по всем возможным наборам (д/, Oj..., а,J. Доказательство. Выберем произвольные значения для аргументов Х], Х2 х„, пусть, например, Х/=Ь/, лг2=йг,..., х„=Ьп. Тогда в правой части соотношения (3,16) получим: V Ь"' &Ь°'- &f(a,, а2, ..., (3.17) ("l."! a „J Если хотя бы для одргаго м н о ж и т е л я , 1< г <т , окажется, что Ь, ^Oi, то из (3.15) следует, что 6 f ' =0 и тогда всё слагаемое в (3.17), содержащее Ь,"', обратится в нуль. Следовательно, в выражении (3.17) останется только одно слагаемое, в котором Ь,= а,- для всех i, 1<г<т. В результате получим, что дизъюнкция (3.17) сводится к одному слагаемому: &f(bb b2...., V - Учитывая, что b f '=l , получим, что дизъюнкция (3.17) равна/(Ь/, b,J, т.е. равна левой части равенства (3,16) при выбранных значениях переменных. Представление функции / в виде (3.16) называют разложением Шеннона. Следствие 3.2. Лх/, Xj x „.j, х^ = x „&f(x,, X;, ..., х„./, \) Их„&/(х,, Хз. ..., х„./, 0). Следствие 3.3. Если /(xj, х^, ..., х,^ не тождественно равна О, то;