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

70 f(Xi, Х2, — V' х"' &Х2^ &...&Х°" . (3-1®) (",'"2 " J ' • 1 /(<^[•"2 Здесь дизъюнкция берется только по тем наборам (а/, aj..., а,J, для которых f(a,, ay.... а,) = \. Доказательство. Очевидно, что в правой части соотношения (3.16) слагаемые cf(ai,a2...,aj=0 можно отбросить, в результате получим (3.18). Теорема 3.15. Для любой булевойф у н к ц и и x j . . . , xj и любого т, l i ' т <п, имеет место следующее равенство: f(Xj, Х2, ..., Х„ XJ = (3.19) t, ' v j j " I где конъюнкция берется по всевозможным наборам (а;, a j . & (X,""' VX2 V... vx, „yf(ai, 02,..., fl„„ х„,+ /,..., xj), (щ."1 " „J Доказательство проводится аналогично доказательству теоремы 3.17. Следствие 3.4. Если/(л:/, Х2,..., х,) не тождественно равна 1, то ^^1-°, (3.20) /(Щ .а-, «„ j=0 f(Xi, Х2...., Хп)= & (Х, Vx\ "• V...VX „ "") ( "1,(12 а„Л Здесь конъюнкция берется только по тем наборам fa/, а:..., а„), для которых /(а/, 02..., я^=0. § 11. Совершенные нормальные формы Правая часть разложения (3.18) называется совершенной дизъюнктивной нормальной формой (с.д.н.ф.) для f г.е. с.д.н.ф. это представление функции/в виде: f (Xj,X2,...,Xn)= V х"^ A x j - . I "I ."2 а„л / ( а , .«2 "г М Очевидно, что с.д.н.ф. функции/('л:/, х^. удовлетворяющая следующим условиям: - нет одинаковых слагаемых; Хц) это д.н.ф. этой функции,