1 пєнініњ ОЌу программасы syllabus

жүктеу 19,56 Mb.

бет	17/34
Дата	31.05.2018
өлшемі	19,56 Mb.
	#18555

1 ... 13 14 15 16 17 18 19 20 ... 34

Мүлтіксіз дизюнктивті қалыпты форма ( МДҚФ
Мүлтіксіз конъюнктивті қалыпты форма (МКҚФ).
Шеннон жіктелулері.

Мүлтіксіз дизюнктивті, конъюнктивті қалыпты форма (МДҚФ, МКҚФ ).

Анықтама. Кез келген формуланы оған эквивалентті ДҚФ-ті ҚҚФ-ке түрлендірудің алгоритмі.

формулаға түрлендіруге болады, мұндағы

-не айнымалы, не оның терістеуі немесе айнымалы мен оның терістеуінің дизъюнкциясы (конъюнкциясы). Осындай формула берілген формуланың дизъюнктивті ( конъюнктивті). қалыпты түрі деп аталады.

Мүлтіксіз дизюнктивті қалыпты форма (МДҚФ)

Анықтама. Айталық, А формуласы <

> айнымалыларынан тәуелді болсын. Егер төмендегі шарттар орындалса А формуласы берілген айнымалылар тізімінде мүлтіксіз дизъюнктивті қалыпты формада делінеді.

А- дизъюнктивті қалыпты формада (элементар конъюнктер дизъюнкциясы)
А- ның әрбір дизъюнктивті мүшесі к-мүшелі конъюнкция және бұл конъюнкцияның әрбір - орында () не айнымалысы не оның терістеуі орналасады. А- ның барлық дизъюнктивті мушелері өзара әртүрлі. Мысалы, - айнымалылар тізімінде (-дизъюнктивті қалыпты формалар.

Мүлтіксіз конъюнктивті қалыпты форма (МКҚФ).

Анықтама. Айталық, А формуласы <

> айнымалыдан тәуелді болсын. Егер төмендегі шарттар орналаса А- берілген айнымалылар тізімінде мұлтіксіз конъюнктивті қалыпты формада делінеді.

А-конъюнктивті қалыпты формада
А-ң әрбір мұшесі к мүшелі дизъюнкция және бұл дизъюнкцияның - ші орнында () не айнымалысының не өзі, не оның терістеуі тұрса.
А- ның барлық конъюнктивті мүшелері өзара әр түрлі.

Мысалдар.

- МДҚФ

- МДҚФ емес.
Берілген

формулаға эквивалентті МДҚФ, МКҚФ табу есептерін шешу үшін , алдымен

буль функциясы үшін Шеннон жіктеуін қарастырамыз.

Шеннон жіктелулері.

Кез келген Буль функциясы Шеннон жіктелуі түрінде өрнектеледі.

Мысалы,

000, 010, 011 құрамаларында 1-ге тең болсын. Олай болса,

жіктелуі:

; Осыған ұқсас 0-ге тең емес

функциялары төмендегідей болып жіктеледі:

Бұл формулалардан төмендегі теореманы келтіруге болады.

жүктеу 19,56 Mb.

Достарыңызбен бөлісу:

1 ... 13 14 15 16 17 18 19 20 ... 34