Буль функциялары. Буль функциялары
![]()
|
БУЛЬ ФУНКЦИЯЛАРЫ Анықтама. Функция f(x1,…, xn) Буль функциясы деп аталады, егер оның аргументтері және өзі екі 0 немесе 1 мәндерін ғана қабылдаса. f(x1,…, xn) функциясының аргументтері x1,…, xn белігілі мәндер қабылдасын: ![]() ![]() ![]() ![]() Ноль және бірден тұратын құраманы ![]() ![]() ![]() ![]() ![]() ![]() . ![]() х1,...,хn аргументтерінен құралған кез-келген Жегалкин полиномын былай жазуға болады: ![]() Бұл жерде ![]() Теорема. Кез-келген f(x1,…,xn) функциясы үшін оны реализациялайтын Жегалкин полиномы бар болады және мұндай полином біреу ғана. Мысалы. ![]() Функциялар системасының толықтылығы мен тұйықтылығы Р2 символымен барлық Буль функциялар жиыны белгіленсін. Анықтама. Р2 жиынының ішкі жиыны болатын система P={f1,…,fs} толық деп аталады, егер әрбір Буль функциясы Р системасы үстіндегі формуламен реализацияланатын болса. Мысал. ![]() f(x1,…,xn)=0. бұл жағдайда f функциясын ![]() f(x1,…,xn) ≠0 мұндай функциялар үшін мүлтіксіз ДҚФ бар болады. Мүлтіксіз ДҚФ Р жиыны үстіндегі формула. Анықтама. Р системасының тұйығы деп осы жиынның үстіндегі формуламен реализацияланатын барлық Буль функцияларының жиынын айтамыз. [P] символымен Р системасының тұйығын белгілейміз. Тұйықтың мынандай қасиеттері бар: 1. ![]() ![]() ![]() Анықтама. Р класы тұйық деп аталады, егер [P]=P болса. Анықтама. Р класы толық деп аталады, егер [P]=P2болса. Өзіне-өзі қосалқы функциялар класы. Анықтама. f функциясын өзіне-өзі қосалқы функция дейміз, егер f*= f болса. ![]() ![]() Анықтама. f функциясы өзіне-өзі қосалқы деп аталады, егер ол кезкелген қарама-қарсы құрамалар жұбында қарама-қарсы мән қабылдаса. Функцияның өзіне өзі қосалқылығын тексеру үшін f(x1,…,xn) функциясының мәндер құрамасын табамыз. Табылған құрамадағы бірді нольге, нольді бірге ауыстырып, шыққан құраманы 180 градусқа бұрамыз. Осылайша алынған құрама тексеріліп отырған функцияның мәндер құрамасымен бірдей болса, f(x1,…,xn) функциясы өзіне-өзі қосалқы болады. |