Буль функциялары. Буль функциялары
 Скачать 39.61 Kb.
|
|
БУЛЬ ФУНКЦИЯЛАРЫ Анықтама. Функция f(x1,…, xn) Буль функциясы деп аталады, егер оның аргументтері және өзі екі 0 немесе 1 мәндерін ғана қабылдаса. f(x1,…, xn) функциясының аргументтері x1,…, xn белігілі мәндер қабылдасын:  ;  ; ...;  осы мәндердің белгілі тәртіппен реттелуін аргументтер мәндерінің құрамасы деп атаймыз. Мәндердің санын құраманың ұзындығы деп атаймыз. Ұзындығы n–ге тең құраманы былайша белігілейміз;  .Ноль және бірден тұратын құраманы  натурал санның  екілік системадағы жазылуы деп қарастыруға болады. Бұл жағдайда санын құраманың номері деп атаймыз. Номер мынандай формуламен анықталады: ..  формуласын Жегалкин полиномы деп атайды. х1,...,хn аргументтерінен құралған кез-келген Жегалкин полиномын былай жазуға болады:  .Бұл жерде  . Яғни полиномға кірсе 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) функциясы өзіне-өзі қосалқы болады. |