Теорема. Кез келген Буль функциясын өрнектейтін формула табылады Егер
болса оны МДҚФ түрінде өрнектейтін жалғыз ғана формула бар.
Егер болса оны МКҚФ түрінде өрнектейтін жалғыз ғана формула бар.
Мысалы, ақиқаттық кестемен берілген функциясының МДҚФ, МКҚФ табу керек. Функцияның толықтығы туралы теорема бойынша
|
x
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
y
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
z
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
|
-МДҚФ; -МКҚФ
Сонымен МДҚФ , МКҚФ - белгілері.
дизъюнкцияның (конъюнкцияның ) мүшелері әр түрлі
конъюнктердің (дизъюнктердің ) мүшелері әр түрлі
бір де бірі конъюнкте (дизъюнкте)айнымалының әрі өзі ,әрі оның терістеуі бірге болмайды.
Әрбір конъюнктің (дизъюнктің ) құрамында формулаға енетін барлық айнымалылар болуы керек, яғни х1 х2... х3 мұндағы хі не өзі , не .
Мысалы, -өрнегі формуласының – дизъюнктивті қалыпты формаларының бірі. Бұл МДҚФ-ң алдыңғы үш талабын қанағаттандырады, ал төртіншісін қанағаттандырмайды. Сондықтан оған түрлендірулер жүргіземіз ( көбейтміз).
Кез келген F (х1,х2...хn ) формуласын МДҚФ (МКҚФ ) түріне келтіру үшін мына ережені қолдануға болады.
F (х1,х2...хn ) формуласын қандайда бір дизъюнктивті (конъюнктивті) қалыпты формаға түрлендіру.
Егер конъюнктке қандай да бір айнымалы өзінің терістеуімен бірге кірсе оны ДҚФ- тан жою керек. (х 0)
Егер конъюнктке бір литер х бірнеше рет кірсе, олардың біреуін ғана қалдырып калғандарын қысқарту керек. (х х х)
Егер конъюнктердің біріне ( ) y айнымалыc кірмей тұрса, онда бүл конъюнктті оған эквивалентті формуламен алмастырамыз да, дистрибутивті заңды (x (yz)) = xy xz қолданып ДҚФ түріне келтіреміз. Егер толық емес конъюнкт бірнешеу болса олардың әрқайысысы үшін сәйкес формуласын қосамыз.
Алынған ДҚФ- да бірдей бірнеше конъюнктер болса олардың ( хх) біреуін ғана қалдырамыз.Нәтижесінде МДҚФ шығады.
Мысалы, ДҚФ –ны МДҚФ-қа түрлендіру керек.
КҚФ-ны МКҚФ түрлендірудің алгоритмі де осындай. Мысал арқылы көрейік. формуланы МКҚФ ға келтіру керек болсын.
1. Формуланы қандайда бір конъюнктивті қалыпты формаға (КҚФ) келтіреміз.
2). Бірдейлерін жоямыз. Айнымалының терістеуімен бірге қатысып тұрған конъюнкция мүшесі, 3 қайталанып тұрған конъюнкция мүшесі 1 мен 4.
Негізгі әдебиет: 2[180-185]; 3[172-193].
Қосымша әдебиет:: 7[50-80]
Бақылау сұрақтары:
Буль функцияларының негізгі қасиеттерін атаңыз.
Логикалық функцияларды жіктеу туралы Шеннон теоремасы қандай?
Буль алгебрасындағы негізгі эквиваленттік түрлендірулерді атаңыз.
Функцияның МДҚФ,МКҚФ қалай табуға болады ?
Қандай логикалық функцияда МДҚФ болмайды?
Достарыңызбен бөлісу: |