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

И с п о л ь зу я р а в н о с и л ь н о с т и а л г еб ры л о г и к и , з а м е н и т ь в се и м е ­ ю щ и е с я о п е р а ц и и н а к о н ъ ю н к ц и ю , д и з ъ ю н к ц и ю и о т р и ц а н и е . П р и м е н я я з а к о н ы Д е М о р г а н а , с н я т ь о т р и ц а н и е с л о г и ч е с к и х о п е р а ц и й к о н ъ ю н к ц и и и д и з ъ ю н к ц и и . И с п о л ь зу я р а с п р е д е л и т е л ь н ы й и др у ги е з а к о н ы , п р и в е с т и ф у н к ­ ц и и к н о р м а л ь н о й ф о рм е . И с п о л ь з у я з а к о н ы и д е м п о т е н т н о с т и , с к л е и в а н и я и д р . , м и н и ­ м и з и р о в а т ь п о л у ч е н н ы е б у л е вы вы р аж е н и я . П р и м е н я я п р а в и л а о п е р а ц и й с к о н с т а н т а м и , п р и в е с т и м и н и ­ м и з и р о в а н н ы е н о р м а л ь н ы е ф о р м ы к с о в е р ш е н н о м у в и д у . Р а с с м о т р и м п р и м е р . П р и в е с т и б ул еву ф у н к ц и ю F= ( х ь х2, х3) = = х, - » х 2х 3 ■ (х 2 - » (**! -> х 3)) к с о в е р ш е н н о й н о р м а л ь н о й ф о рм е . С н а ч а л а п р и в е д ем ф у н к ц и ю к виду С К Н Ф . И м е ем : F(xu х2, х3) = =х, -> х 2х 3 ■ ( х 2 - > (х , - » х 3) ) = х1 V х 2х 3 • (х2 V ( x i V х 3) ) = ( х , ■Х2Х3) • • ( Х^ V х| v Х3) = Х,(х2 V_X3) • (Х2 V X | V Хъ) =_(*1 у_0) • (О V Х2 V х3) • • ( х 2 v x , v х3) = (х, V _x2x 2)_(X iX , V Xg V хД • (х2 V X, V х 3) = (х, V хД • • {Х\ V Xj) ■ (X [_v Х2 V Х3) _ ( Х ! V х 2 у_х3) _(х2 V_X, V Хз) = (х, V Х2 V Х3Х3) • • (Xi V Х2 V Х3Х3) • (Xi_V Х2 V Х3) _ (Х| V Х2 V Хз) • ( Х2 V Х|_ V Хз) = (х, V V Хз V Хз) •(X! V х 2 V х 3) •(х , V х 2 V х3) •(х , V Х2 V х 3) ■ (х , V Х2 V х 3) ■ ■ ( х 2 V X] V х3). П р и в е д ем у п р о щ е н н у ю ф у н к ц и ю к вид у _СД НФ : F(X i ,X2, X j ) = Х , ( х 2 V Х3) • (X|_V_X2 VX3)_=_(X,X2V X ,*3) • ( X | V х 2 v_x3) = = XiX^Xi V XiX3X2 V X iX 2X3 У ^ Х з Х ] V _X jX3X2 V _XiX3X3 =_X|X2 V X,X2X3 V V X j 3 ^ X 3 = X !X2(X 3 V X3) V X iX2X3 V X ]X2X3 = X )X2X3 V X jX2X3. П о л у ч е н н о е булево в ы р аж е н и е д ей с т в и т е л ь н о им е е т в и д С Д Н Ф , т а к к а к к аж д а я э л е м е н т а р н а я к о н ъ ю н к ц и я с о д е р ж и т в с е п е р е м е н ­ ны е э т о й б у л е в о й ф у н к ц и и , к о т о р ы е в с т р е т и л и с ь по о д н о м у р а зу . З н а я С Д Н Ф , м о ж н о с о с т а в и т ь т а б л и ц у и с т и н н о с т и с о о т в е т с т в ую ­ щ ей ф у н к ц и и . П у с т ь ,F (x i, х 2, х3) = Х]Х2х 3 v Х]Х2х3. Д л я п о л у ч е н и я т а б л и ц ы и с ­ т и н н о с т и п о д с т а в и м в ф у н к ц и ю з н а ч е н и я л о г и ч е с к и х п е р е м е н н ы х в к аж д о й с т р о к е и , в ы п о л н и в д е й с т в и я с л о г и ч е с к и м и к о н с т а н т а ­ м и , н а й д ем з н а ч е н и е ф у н к ц и и . Э то г о р а зд о п р о щ е , ч ем р а с п и с ы ­ в ать к аж д ы й с т о л б е ц в и с х о д н о й ф у н к ц и и (т аб л . 4.20). С о в е р ш е н н ы е н о р м а л ь н ы е ф о р м ы н у ж н ы , н а п р и м е р , в т е х с о д е рж а т е л ь н ы х з а д ач а х , где н е о б х о д и м о р а с см о т р е т ь в с е в о з м о ж ­ ны е в а р и а н т ы и н ф о р м а ц и и о к аж д о й и з п е р е м е н н ы х , в х о д ящ и х в д а н н ую б ул еву ф у н к ц и ю . Любая булева функция , не являющаяся тождественным нулем или единицей, имеет только одну СДНФ с точностью до расположения переменных. М ы р а с с м о т р е л и п р и м е р ы , к о г д а б ул е в а ф у н к ц и я бы л а у ж е в ы р аж е н а ч е р е з л о г и ч е с к и е о п е р а ц и и . Т е п е р ь п о с м о т р и м , к а к с о ­ с т а в и т ь с о в е р ш е н н ы е н о р м а л ь н ы е ф о р м ы т о г д а , к о г д а и з в е с т н а л и ш ь т а б л и ц а з н а ч е н и й . 173