1. буль функциялары анықтама. Функция f X
жүктеу/скачать 32,43 Kb.
|
Буль функциялары
|
1. БУЛЬ ФУНКЦИЯЛАРЫ Анықтама. Функция 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) функциясы өзіне-өзі қосалқы болады. 2. Толықтық және тұйықтық Егер кез-келген Буль функциясы осы жүйенің функциялары арқылы формула түрінде жазылатын болса, онда Р2 жиынындағы {f1,f2,…,fs,…}функциялар жүйесі толық деп аталады. Толық жүйелердің мысалдары: 1. Р2 жүйесі- барлық Буль функцияларынын жиыны -толық жүйе болып табылады. 2. G = { ,x1& х2,x1vx2 } жүйесі толық жүйе. Кез-келген жүйе толық бола бермейді, мысалы G = {0,1} жүйесі толық емес. Келесі теорема бір жүйенің толықтығын негізге ала отырып екінші жүйенің толықтығын анықтауға мүмкіндік береді. Теорема. Айталық Р2 жиынында екі функциялар жүйесі берілсін: G={f1,f2,…}, (I) D={g1,g2,…}, (II) олар туралы мына жағдай белгілі: (I) жүйе толық және оның әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектелген. Онда (II) жүйе толық. Мысал: D ={ ,x1&x2 } жүйесінің толық екендігін дәлелдеңіз. Дәлелдеу: (I) жүйе ретінде 2 мысалдағы жүйені аламыз: { ,x1& х2,x1vx2 }, ал (II) жүйе ретінде - D жүйесін аламыз. x1vx2= тепе-теңдігін пайдаланамыз (элементар функциялардың касиетінен). Сонымен, (I) жүйенің әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектеледі. Яғни, (II) жүйе: { ,х1&х2} толық жүйе болып табылады. Функция f(x1,…, xn) Буль функциясы деп аталады, егер оның аргументтері және өзі екі 0 немесе 1 мәндерін ғана қабылдаса. f(x1,…, xn) функциясының аргументтері x1,…, xn белігілі мәндер қабылдасын: ; ; ...; осы мәндердің белгілі тәртіппен реттелуін аргументтер мәндерінің құрамасы деп атаймыз. Мәндердің санын құраманың ұзындығы деп атаймыз. Ұзындығы n–ге тең құраманы былайша белігілейміз; жүктеу/скачать 32,43 Kb. Достарыңызбен бөлісу:
|