Минимизация проблемасы f буль функциясы үшін дизъюнктивті қалыпты форма
жүктеу/скачать 158.3 Kb.
|
1 2
9апта-Қалыпты формалар (1)- Бұл бет үшін навигация:
- 5.1.2 Буль функцияларын минимизациялау проблемаларын
|
Қалыпты формалар. Минимизация проблемасы f буль функциясы үшін дизъюнктивті қалыпты форма (д.қ.ф. ) деп элементар конъюнкциялрдың дизъюнкциясын, ал элементар конъюнкция деп айнымалылардың немесе олардың терістеулерінің конъюнкциясын айтады. Жоғарыда қарастырылған д.қ.ф.-дың (к.қ.ф.-дың) әрбір элементар конъюнкциясында (дизъюнкциясында) әр литера тек бір рет кездеседі, яғни жетілген д.қ.ф. (к.қ.ф.). Алайда жетілген д.қ.ф. өте күрделі және кең ауқымды. Көп жағдайдафункцияны д.қ.ф. түрінде өте қысқа жолмен жазуға болады. Мысалы, H =g z yz x z = ( y) z x z = 1 z x z = z x z =g G. Немесе одан да қысқарақ: H = z z =g F. Мұндағы А = gВ графикалық теңдік. Осылайша д.қ.ф. F, G және H функция ретінде тең болғанымен (бір ғана функцияны білдіреді, мұны ақиқаттық кестесін құру арқылы көруге болады.), д.қ.ф. ретінде әр түрлі.. Қалыпты формалардың «ұзақ», «қысқа» жазылу ұғымын әр тү.рлі тәсілмен түсіндіруге болады.Соның бір қарапайым түрі: А д.қ.ф. немесе к.қ.ф. құрамына кіретін литералар саны (әріптер, айнымалылар мен олардың терістеулерінің саны, дизъюнкция мен конъюнкция белгілері кірмейді) әріптік қарапайымдылық индексі деп аталады және LБ(A) деп белгіленеді. Жоғарыда берілген д.қ.ф. үшін : LБ(H)=9, LБ(G)=5, LБ(F)=4. 5.1.2 Буль функцияларын минимизациялау проблемаларын әдетте қайсыбір ең кіші мәнді қарапайымдылық индексімен берілген функцияны жүзеге асыратын д.қ.ф.-ны табу деп түсіндіреді. Мұндай д.қ.ф. осы индекс бойынша минимальді деп саналады. Төменде келтірілген әдістер ең алдымен LБ индекске есептелініп алынған, бірақ кейбіреуі кез-келген қарапайымдылық индексі үшін қолданыла береді. А = z xy y және В = xz y д.қ.ф. бір ғана функцияны білдіреді. Мұндағы А д.қ.ф.-дан элементар конъюнкциялардың ешқайсысының ешбір әрпін жойып жіберуге болмайды., сондай-ақ ешбір конъюнкцияны да алып тастуға келмейді. Осылайша А (В) д.қ.ф.-сын әрі қарай ықшамдауға, яғни ешқандай элементті алып тастауға болмайды. Мұндай д.қ.ф. тупиктік деп аталады. LБ(A)=8, а LБ(В)=6. жүктеу/скачать 158.3 Kb. Достарыңызбен бөлісу:
|
1 2