ПОӘК 042-14. 01. 20. 205/03-2013 02. 09. 20013 №1 басылым



бет11/209
Дата15.09.2017
өлшемі14,91 Mb.
#34004
1   ...   7   8   9   10   11   12   13   14   ...   209


Теорема (функцияның толықтығы туралы теоерема). Кезкелген f буль функциясы үшін f функциясын беретін  формуласы табылады. Егер f0, онда МДҚФ болатын φ формуласы табылады:

,

егер f1, МКҚФ болатын φ формуласы табылады:



.

Мысалы. f(x,y,z) функциясы үшін ақиқат кестесі арқылы берілген МДҚФ және МКҚФ табу керек.




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

f(x,y,z)

1

0

0

1

0

1

0

1


Функцияның толықтығы туралы теоремадан МДҚФ түрі , ал МКҚФ болады.

МДҚФ табудың алгоритмі. Берілген формуланы ДҚФ келтіреміз, содан кейін оның конъюнкцияларын бірлік конституентке төмендегідей ауыстырамыз:

1) егер конъюнктке айнымалы өзінің терістеуімен бірге кірсе, онда оны ДҚФ құрамынан алып тастаймыз;



2) егер конъюнкт құрамында хδ литері бірнеше рет қайталанса, онда хδ литерінің біреуін ғана қалдырып, қалғандарын жоямыз;

3) егер қайсыбір конъюнкт құрамына у айнымалы кірмесе, онда ол конъюнктті эквивалентті формулмасымен ауыстырамыз, дистрибутивті заңды пайдаланып, шыққан формуланы ДҚФ келтіреміз; егер жетпейтін айнымалылар саны бірнешеу болса, онда оның әрқайсысы үшін түріндегі формуланы конъюнктке қосамыз;

4) егер шыққан ДҚФ бірнеше бірдей бірлік конституент болса, онда оның біреуін ғана қалдырамыз.



Нәтижесінде МДҚФ шығады.

Мысал. ДҚФ үшін МДҚФ табамыз. Сонда:

Жегалкин полиномы. Анықтама. хі1∙хі2∙∙∙хіr – түріндегі логикалық көбейтінді монотонды элементарлық конъюнкция деп аталады, егер оның құрамына кіретін аргументтер бір-бірінен өзгеше болатын болса. МЭК құрамындағы аргументтердің саны оның рангісі деп атайды. 1-ді рангісі 0-ге тең МЭК деп атаймыз.



Достарыңызбен бөлісу:
1   ...   7   8   9   10   11   12   13   14   ...   209




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет