Спирина, М.С. Дискретная математика

кций, дающих значение, равное нулю, и взять отрицание от F, так как F = F. В нашем случае F(x ь х2, х3) = х,х2х3 v XiX2x3 v X|X2x3 v X!X2x3 v v x tx2x3. С помощью закона Де Моргана отрицание дизъюнкции превратим в конъюнкцию отрицаний и минимизируем выраже­ ние, сохраняя его вид, т.е. конъюнктивную форму. Тогда F(x ,, х2, х3) = F(X|, х2, х3) = = X, Х2 Х3 V X! Х2 Х3 V X, Х2 Х3 V X, Х2 Х3 V Х| х 2 х3 = = Х[ Х2 Х3 •X, Х2 Х3 • Х| Х2 Х3 • Х| Х2 Х3 •Х|Х2Х3 = (х , V Х2 V х 3) • • (X! V Х2 V Х3) • (x i V Х2 V Х3) ■ (x j V Х2 V • (x j V X, V Х3). П о л у ч е н н о е в ы р а ж е н и е я в л я е т с я С К Н Ф д а н н о й ф у н к ц и и F ( x , , х2, х 3). П р а к т и ч е с к и м п о с т р о е н и е м С Д Н Ф п о к а з а н о , ч то л ю б а я б у л е ­ ва ф у н к ц и я , н е я в л яю щ а я с я к о н с т а н т о й , п о т а б л и ц е и с т и н н о с т и р а з л а г а е т с я в с о в е рш е н н ую н о р м а л ь н у ю ф о р м у , т .е . в к о м п о з и ­ ц ию о т р и ц а н и я , к о н ъ ю н к ц и и и д и з ъ ю н к ц и и . А п о с к о л ь к у то ж е б ы л о с д е л а н о и д л я к о н с т а н т , т о у т в е рж д ен и е д о к а з а н о д л я л ю б о й б у л е в о й ф у н к ц и и п р о и з в о л ь н о г о ч и с л а п е р ем е н н ы х . С ущ е с т в о в а н и е С Д Н Ф п о з в о л я е т п р о в е с т и п р о ц е д у р у , н а зы в а ­ ем ую разложением б у л е в о й ф у н к ц и и п о п е р е м е н н о й хк. Р а з л о ж е ­ н и е п о з в о л я е т п р е д с т а в и т ь п р о и з в о л ь н ую ф у н к ц и ю / ( х ь ..., х„) в вид е f(xx, ..., х„) = хк ■ р(х\, . . . , хк_ь хк+ь .... х„) v хк ■ ? ( х , , ..., х**_ ь Э т о л е г к о с д е л а т ь , о т д е л я я в С Д Н Ф все с л а г а ем ы е с хк от хк и в ы н о с я х* и л и хк за с к о б к у . Т о г д а в ы р а ж е н и я в с к о б к а х буду т н е ­ к и м и ф у н к ц и я м и р_ и q,_ ^не з а в и с ящ и м и _ о т х*. В з а д а ч е 21 и м е е м F(Xi, Х2, Х3) =_Х,Х2Х3 V Х,Х2Х3 V Х,Х2Х3 = Х|(ХзХ3 V Х2Х3) V X |(х2х3) = = х , ( х 2) v Х |(х2х 3). С л е д о в а т е л ь н о , мы п р о и з в е л и р а з л о ж е н и е Т ( х , , х 2, х 3) п о х , . А н а л о г и ч н о м о ж н о п р о и з в о д и т ь р а з л о ж е н и е п о г р у п ­ п е п е р е м е н н ы х . П р ощ е в с е г о э т о м о ж н о с д е л а т ь п о с л е д о в а т е л ь ­ н ы м р а з л о ж е н и е м п о о д н о й п е р е м е н н о й , в х о д ящ е й в э т у гр упп у , а з а т ем п р и в е с т и о с т а вш и е с я в ы р а ж е н и я (в ч а с т н о с т и , р и q) к С Д Н Ф о т м е н ьш е г о ч и с л а п е р е м е н н ы х . 4.6.2. Логические схемы О д н о й и з ц е л е й б у л е в о й а л г е б р ы я в л я е т с я о п и с а н и е п о в е д е ­ н и я и с т р у к т у р ы л о г и ч е с к и х сх ем . Логическая схема и м е е т в и д « ч е р н о г о ящ и к а » , в к о т о р о м в х о д — н а б о р б у л е вы х п е р е м е н н ы х , а в ы х о д — б у л е в а ф у н к ц и я F(xu ..., х„) (ри с . 4 .6 ) . Метод «черного ящика» используется в тех случаях, когда предме­ том изучения является поведение сложных систем, а не их устройство. 175