ПОӘК 042-14. 01. 20. 205/03-2013 02. 09. 20013 №1 басылым
жүктеу/скачать 14,91 Mb.
|
|
Бұл жерде  . Яғни полиномға кірсе 1, басқа жағдайда 0 болады.
Теорема. Кез-келген f(x1,…,xn) функциясы үшін оны реализациялайтын Жегалкин полиномы бар болады және мұндай полином біреу ғана. Мысалы. 
Функциялар системасының толықтылығы мен тұйықтылығы Р2 символымен барлық Буль функциялар жиыны белгіленсін. Анықтама. Р2 жиынының ішкі жиыны болатын система P={f1,…,fs} толық деп аталады, егер әрбір Буль функциясы Р системасы үстіндегі формуламен реализацияланатын болса. Мысал.  системасының толық екендігін көрсетейік. Ол үшін кезкелген f(x1,…,xn) фукнциясын Р жиыны үстіндегі формуламен реализацияланатындығын дәлелдеуіміз керек. Мынандай екі жағдай болуы мүмкін:
f(x1,…,xn)=0. бұл жағдайда f функциясын  формуласымен реализациялаймыз.
f(x1,…,xn) ≠0 мұндай функциялар үшін мүлтіксіз ДҚФ бар болады. Мүлтіксіз ДҚФ Р жиыны үстіндегі формула. Анықтама. Р системасының тұйығы деп осы жиынның үстіндегі формуламен реализацияланатын барлық Буль функцияларының жиынын айтамыз. [P] символымен Р системасының тұйығын белгілейміз. Тұйықтың мынандай қасиеттері бар: 1.  2. [[P]]=[P] 3. егер , онда 
Анықтама. Р класы тұйық деп аталады, егер [P]=P болса. Анықтама. Р класы толық деп аталады, егер [P]=P2 болса. Өзіне-өзі қосалқы функциялар класы. Анықтама. f функциясын өзіне-өзі қосалқы функция дейміз, егер f*= f болса.  және  қарама-қарсы құрамалар деп атаймыз.
Анықтама. f функциясы өзіне-өзі қосалқы деп аталады, егер ол кезкелген қарама-қарсы құрамалар жұбында қарама-қарсы мән қабылдаса. Функцияның өзіне өзі қосалқылығын тексеру үшін f(x1,…,xn) функциясының мәндер құрамасын табамыз. Табылған құрамадағы бірді нольге, нольді бірге ауыстырып, шыққан құраманы 180 градусқа бұрамыз. Осылайша алынған құрама тексеріліп отырған функцияның мәндер құрамасымен бірдей болса, f(x1,…,xn) функциясы өзіне-өзі қосалқы болады. жүктеу/скачать 14,91 Mb. Достарыңызбен бөлісу:
|