Минимизация проблемасы f буль функциясы үшін дизъюнктивті қалыпты форма
жүктеу/скачать 158.3 Kb.
|
| Теорема 5.1. Элементар конъюнкция К f функцясы үшін қарапайым импликант болып табылады, сонда тек сонда, қашан (Кf) = 1, ал қандай да бір литерді жою арқылы К-дан алынған кез-келген элементар конъюнкция К’,бұл қасиетке ие бола алмайды. Қысқарған д.н.ф. барлық қарапайым импликанттардың дизъюнкциясы болып табылады.
дизъюнктивті қалыпты форма және конъюнктивті қалыпты форма Мысал. Төмендегі кесте түрінде берілген функцияға сәйкес кемелденген дизъюнктивті қалыпты формасын (КДҚФ) жазайық. 8-кесте.
► 8- кестеде f(1,0,0), f(1,0,1), f(1,1,1) болған үш жағдайларда ғана f функциясының мәні 1–ге тең. Сондықтан кесте түрінде берілген f функциясына сәйкес келетін кемелденген дизъюнктивті қалыпты формасы (КДҚФ) мынадай түрде болады: .◄ Кемелденген конъюнктивті қалыпты форма (ККҚФ) деп әрбір элементар дизъюнкциясының құрамында барлық айнымалысы бар болатын конъюнктивті қалыпты форманы айтады. Мәні тепе – тең 1-ден өзгеше кез –келген бульдік функция кемелденген конъюнктивті қалыпты форма түрінде жазылады. 8-кестедегі берілген функцияға сәйкес кемелденген конъюнктивті қалыпты формасын (ККҚФ) табайық. ► Бұл функцияның нөлге тең мәндері f(0,0,0), f(0,0,1), f(0,1,0), f(0,1,1), f(1,1,0) жиынтықтарында. Сондықтан берілген f функциясына сәйкес келетін кемелденген конъюнктивті қалыпты форма (КДҚФ) мынадай түрде болады: .◄ Мысал. Берілген функцияларға сәйкес Жегалкин көпмүшелігін құр: а) , б) . Берілген формуланы дизъюнктивті қалыпты формаға (дқф) келтіру керек. ► . ◄ 2. Берілген формуланы конъюнктивті қалыпты формаға (Кқф) келтіру керек. ► Берілген формуланы екі рет терістеумен ауыстырамыз да Де Морган формуласын қолданамыз. ◄ 3. Төмендегі кесте арқылы берілген функцияны кемелденген дизъюнктивті қалыпты форма (КДҚФ) түрінде және кемелденген конъюнктивті қалыпты форма (ККҚФ) түрінде жазу керек. ► f функциясына сәйкес кемелденген дизъюнктивті қалыпты форма (КДҚФ) мен кемелденген конъюнктивті қалыпты форманы (ККҚФ) схема түрінде жазсақ: f функциясының тепе – тең бір болатын мәндерінде КДҚФ-ның және f функциясының тепе – тең нөл болатын мәндерінде ККҚФ-ның сәйкесінше элементар конъюнкцияларын және элементар дизъюнкцияларын жазып көрсетейік. 9-кесте.
Сонымен, f функциясына сәйкес келетін КДҚФ-ның түрі: f= ◄ ал f функциясына сәйкес келетін КKҚФ-ның түрі: f= ( )( )( ).◄ 4. Кесте бойынша берілген функцияның КДҚФ-сын құр: 10-кесте.
► Берілген кестеде үш бірлік жиынтық бар болғандықтан, КДҚФ үш элементар дизъюнкциялардың конъюнкцияларынан тұрады. функциясының құрамында үш айнымалы болғандықтан әр дизъюнкцияда үш айнымалы болады: . конъюнкция белгісінің тиімді түрін қолдансақ, өрнектің түрі ықшамды көрінетінін ескерсек: .◄ КДҚФ- сы болмайтын жалғыз функция ол константасы. 5. ( → )→( ~ ) формуласын элементар түрлендірулердің көмегімен КДҚФ-ға келтіру керек. ►( → )→( ~ ) ◄ 6. ( → )→( ~ ) формуласын элементар түрлендірулердің көмегімен ККҚФ-ға келтіру керек. ККҚФ құру үшін келесі схеманы қолдануға болады. ►( → )→( ~ ) ◄ 7. f(x,y,z) логикалық функциясы формула түрінде берілсін. Формуланы ықшамда және ККҚФ - ға келтір. ► 1)Формуланы ықшамдайық: ◄ жүктеу/скачать 158.3 Kb. Достарыңызбен бөлісу:
|