Функцияның айнымалыға қатысты кеңею теоремасы. Айнымалылардағы логикалық функциялардың декомпозициясы

арқылы белгілеңіз. Содан кейін

x с=

Атап айтқанда, егер және тек егер .

Көмегімен » қуат функциясы” кез келген логикалық функция ретінде көрсетуге болады:

шақырды Логикалық функцияның декомпозициясы айнымалы бойынша.

Шынында да, егер , онда , және

Егер , онда және

4-мысал

Функцияны кеңейтіңіз айнымалы бойынша. Ол үшін алдымен функциялар кестесін құрастырамыз:

Кестеден көруге болады және .

Айнымалыға қатысты кеңейту формуласын қолданып, табамыз

5-мысал

Функцияны кеңейтіңіз 4-мысалдан барлық айнымалылар үшін. Функция үш жиында 1 мәнін қабылдайтындықтан: , онда ыдырау теоремасының нәтижесіне сәйкес, бізде

Анықтама 3.

Логикалық функцияның ыдырауы пішіндегі барлық айнымалылардың үстінен

шақырды мінсіз дизъюнктивті қалыпты форма(SDNF).

6-мысал

- Функция үшін SDNF (5 мысалды қараңыз).

2-теорема.

Әрбір логикалық функцияда (0-ден басқа) бірегей SDNF бар.

Дәлелдеу.Ыдырау теоремасының қорытындысы бойынша

Пікір.Егер бір мүшенің дизъюнкциясы деп бұл терминнің өзін түсінетін болсақ, онда нөлдік мүшелердің дизъюнкциясы болмайды, сондықтан 0 функциясы үшін SDNF жоқ.

SDNF құрастыру кезінде келесілер орын алады

бірлік ережесі. 1 мәнін қабылдайды; SDNF-дегі әрбір осындай жинақ үшін жиынтық дайындалады . Егер кірсе бұл жиынтықаргументтер, содан кейін дайындалған терминдегі айнымалыға терістеу ілінеді: .

Теорема 3.

Кез келген логикалық функцияны дизъюнкция, конъюнкция және терістеу арқылы көрсетуге болады:

Дәлелдеу.

Егер , содан кейін . Егер , содан кейін

Теорема 4.

Кез келген логикалық функция (1-ден басқа) тамаша конъюнктивтік қалыпты форма (CKNF) түрінде бірегей түрде өрнектелуі мүмкін:

Дәлелдеу.

Егер , содан кейін және

Соңғы сәйкестікке қосарлылық принципін қолдана отырып, біз табамыз

SKNF құрастыру кезінде келесілер орын алады

Нөлдік ереже.Функция орындалатын аргументтер жиыны ғана қарастырылады 0 мәнін қабылдайды; SKNF-дегі әрбір осындай жиынтық үшін коэффициент дайындалады. Егер берілген аргументтер жиынында , онда дайындалған фактордағы айнымалыға терістеу ілінеді: .

7-мысал

Импликация үшін функция құрастырайық: . Көрсеткіш бір жиында 0 мәнін қабылдайды:

Осы жиында болғандықтан және , онда нөл ережесі бойынша аламыз

.

Сонымен, импликация үшін қажетті функция болып табылады.

Жүйенің толықтығы

Анықтама 4.Функционалдық жүйе ( f 1 , f 2 , ..., f s , ...)М П 2 толық деп аталады Р 2, егер қандай да бір функция f(x 1 , ..., x n) Î П 2-ні осы жүйенің функциялары арқылы формула түрінде жазуға болады.

Толық жүйелер

1. П 2 – толық жүйе.

2. Жүйе М={x 1 &x 2 , x 1 U x 2 , ) толық жүйе, өйткені логика алгебраның кез келген функциясын осы функциялар тұрғысынан формула түрінде жазуға болады.

8-мысалТолық емес жүйелер: ( }, {0,1}.

Лемма (жеткілікті шарттолықтығы)

Жүйеге рұқсат етіңіз У = {f 1 , f 2 , ..., fs, ...) толық Р 2. Болсын Б = {g 1 , g 2 , ..., г к, ...) -ның кейбір жүйесі Р 2 және кез келген функция fi Î Уформула түрінде көрсетуге болады Б, содан кейін жүйе Бтолық Р 2 .

7. Жүйе ( x 1 &x 2 , x 1 Å x 2 , 0, 1) ішінде аяқталды Р 2 , У = {x 1 &x 2 , }, = x 1 Å1.

Жегалкин көпмүшесі

f(x 1 , ..., x n) Î П 2 , біз оны 0 және 1 сандарын пайдалана отырып, қосылғыш және қосынды модулі бойынша формула ретінде көрсетеміз. Мұны жасауға болады, өйткені ( x 1 &x 2 , x 1 Å x 2 , 0, 1) ішінде аяқталды Р 2. Меншікке байланысты x & (жÅ z) = xy Å xzсіз барлық жақшаларды аша аласыз, ұқсас шарттарды келтіре аласыз және сіз көпмүшені аласыз nпішін мүшелерінен тұратын айнымалылар X X ...X, Å белгісімен байланысады. Мұндай көпмүшені Жегалкин көпмүшесі деп атайды.

Жалпы формаЖегалкин көпмүшесі:

қайда , с = 0, 1, ..., n, және at с= 0 еркін терминді аламыз а 0 .

Функцияны Жегалкин көпмүшесі түрінде көрсету

1. Кез келген функцияны формуладан асатын етіп көрсетейік. x 1 &x 2 , ) және = ауыстыруын жасаңыз xÅ1. Бұл әдіс, егер функция формула арқылы берілсе ыңғайлы.

9-мысал. (x 1 (x 2 x 3))(x 1 U x 2) x 3 = (x 1 U x 2 u x 3)(x 1 U x 2) x 3 = (`x 1 x 2 u x 1 x 3 u x 1 x 2 u x 2 u x 2 x 3)x 3 = (`x 1 x 3 u x 2)x 3 = x 1 x 3 x 2 x 3 = ((x 1 x 3 Å1) x 2 Å1) x 3 = x 1 x 2 x 3 Å x 2 x 3 Å x 3 .

Қосындысында бірдей терминдердің жұп саны болатынын есте ұстаған жөн мод 2 0 береді.

2. Белгісіз коэффициенттер әдісі. Функция кесте арқылы берілсе, ыңғайлы.

10-мысал.

Коэффиценттері анықталмаған үш айнымалы функция үшін Жегалкин көпмүшесін жазайық. f(x 1 , x 2 , x 3) = (01101001) = а 0 Å а 1 X 1 Å а 2 X 2 Å а 3 X 3 Å б 1 x 1 x 2 Å б 2 x 2 x 3 Å б 3 x 1 x 3 Å cx 1 x 2 x 3 . Содан кейін барлық жиындардағы функция мәндерін пайдаланып коэффициенттерді табамыз. Жиында (0, 0, 0) f(0, 0, 0) = 0, керісінше, осы жиынды көпмүшеге ауыстырсақ, біз аламыз f(0, 0, 0) = а 0, демек а 0 = 0. f(0, 0, 1) = 1, көпмүшеге (0, 0, 1) жиынын қойып, мынаны аламыз: f(0, 0, 1) = а 0 Å а 3, өйткені а 0 = 0, демек а 3 = 1. Сол сияқты, f(0, 1, 0) = 1 = а 2 , f(0, 1, 1) = 0 = а 2 Å а 3 Å б 2 б 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å б 3 , б 3 = 0; 0 = а 1 Å а 2 Å б 1 , б 1=0; 1 = 1 Å 1 Å 1 Å в; в= 0; онда бұл функция үшін Жегалкин көпмүшесі келесі түрге ие болады: f(x 1 , x 2 , x 3) = x 1 Å x 2 Å x 3 .

Жегалкин көпмүшесін Паскаль үшбұрышының сол жағының бірліктері арқылы төмендегі кесте бойынша алуға болады. функциясы үшін Жегалкин көпмүшесін тұрғызайық f= (10011110). Үшбұрыштың жоғарғы жағы функция болып табылады f. Үшбұрыштың кез келген басқа элементі екінің модульдік қосындысы болып табылады көршілес элементтералдыңғы жол. Функция үшін үшбұрыштың сол жағы fалты бірліктен тұрады. Жегалкин көпмүшесі алты мүшеден тұрады. Үшбұрыштың бірінші бірлігі жиынға (000) сәйкес келеді. Көпмүшенің бірінші мүшесі 1. Үшбұрыштың сол жағындағы төменгі жағынан үшінші бірлік (101) жиынына сәйкес келеді. Көпмүшенің мүшесі ретінде аламыз x 1 x 3 . Үшбұрыштың басқа бірліктері үшін де солай. Жиындардың сол жағында Жегалкин көпмүшесінің мүшелері көрсетілген.

Жегалкин теоремасы

Әрбір функцияны бірегей жолмен Жегалкин көпмүшелігі түрінде беруге болады.

Мұнда бірегейлік қосындыдағы мүшелердің реті мен қосылыстардағы көбейткіштердің ретіне дейін түсініледі:

, с = 0, 1, ..., n.

Дәлелдеу.

Кез келген функциядан Р 2 жоғары формуламен ұсынылуы мүмкін ( x 1 & x 2 , x 1 Å x 2, 0, 1) және бұл формула барлық жақшаларды ашып, ұқсас мүшелерді азайтқаннан кейін Жегалкин көпмүшесін береді. Өкілдіктің бірегейлігін дәлелдеп көрейік. Функцияларды қарастырыңыз f(x 1 , ..., x n) бастап nайнымалылар. Біз мұндай функциялардың жиынтығы бар екенін білеміз, яғни. олардың ақиқат кестелері, 2 n. Әртүрлі Жегалкин көпмүшелерінің санын есептейік nайнымалылар, яғни. түрлердің вариация саны: . Жиындар саны жиынның барлық ішкі жиындарының санына тең ( x 1 , ..., x n), бұған бос жиын да кіреді (егер с= 0). n элементтен тұратын жиынның ішкі жиындарының саны 2-ге тең n, және әрбір жиын екі мәнді қабылдайтын коэффициентпен қамтылғандықтан: 0 немесе 1, онда мүмкін көпмүшелердің саны болады. Әрбір көпмүше бір функцияға сәйкес келетіндіктен, бастап функциялар саны nайнымалылар көпмүшелердің санына тең болса, онда әрбір функция бір көпмүшеге сәйкес болады.

Анықтама.

Функция f(x 1 , ..., x n), айнымалыларға қатысты келесі сызықты болатын Жегалкин көпмүшесі: f = а 0 Å а 1 X 1 Å а 2 X 2Å ... Å a n x n, сызықтық деп аталады.

Лемма сызықтық емес функция туралы .

Конъюнктураны алу үшін сызықты емес функцияның суперпозициясы, терістеу және тұрақты 1 қолданылуы мүмкін.

Дәлелдеу.

Болсын f(x 1 , ..., x n) сызықты емес функция болып табылады. Сонда Жегалкин көпмүшесінде туындысы бар оның мүшесі бар x i x j. Қарапайымдылық үшін солай делік x 1 xЖегалкин көпмүшесінде 2 бұл көбейтінді. Терминдерді топтағаннан кейін функция fтүрінде көрсетеді

Функция h 0 бірдей нөл емес, әйтпесе Жегалкин көпмүшесінің туындысымен мүшесі жоқ. x 1 x 2. Сонда жиынтық бар ( а 3 , …, а п) 0 және 1, ол үшін h 0 (а 3 , …, а п) = 1. Көрейік h 1 (а 3 , …, а п) = а, h 2 (а 3 , …, а п) = б, h 3 (а 3 , …, а п) = в. Содан кейін

Функцияны құрастырайық:

Қайда г = аб Å в. Егер г= 0, онда h(x 1 , x 2) = x 1 x 2. Егер г= 1, онда h(x 1 , x 2) = x 1 x 2 Å 1, содан кейін Лемма дәлелденген.

Функция f(x 1 , ..., x n) тұрақты болады аО (0, 1) егер f(а, …, а) = а.

11-мысал.

Функция xy 0 сақтау, 1 сақтау. Функция x® ж 1 сақтайды және 0 сақтамайды.

Логикалық функцияларды азайту

Қалыпты пішіндерді кішірейту

Ең аз DNF (MDNF)функциялары f(x 1 , ... ,x n) функцияны жүзеге асыратын DNF деп аталады fжәне функцияны жүзеге асыратын барлық басқа DNF түрлерімен салыстырғанда айнымалы таңбалардың ең аз санын қамтиды f.

Егер кез келген жиынтық үшін = ( а 1 , ..., а п) айнымалылар шартының мәндері g()=1 дегенді білдіреді, содан кейін функция gфункцияның бөлігі деп аталады f(немесе функция fфункциясын қамтиды g). Егер, қосымша, кейбір жиынтық үшін = ( в 1 , ..., c n) функциясы g()=1, онда функция деп айтамыз gфункция бірлігін қамтиды fжиынтықта (немесе кез келген gфункцияның бірлік құрамдас бөлігін қамтиды f). Функцияның құрамдас бірлігін ескеріңіз fфункцияның бөлігі болып табылады fфункцияның бірегей бірлігін қамтиды f.

Бастауыш жалғау Қфункцияның импликанты деп аталады f, егер кез келген жиын үшін =( а 1 , ..., а п) 0 және 1 шарты Қ()=1 білдіреді f()=1.

импликант Қфункциялары fегер одан кез келген факторларды алып тастау арқылы алынған өрнек функцияның импликанты болмаса, жай деп аталады f.

Функцияның әрбір импликанты екені анық fфункцияның бөлігі болып табылады f.

5-теорема.

Кез келген функция оның барлық қарапайым импликанттарының (PI) дизъюнкциясы арқылы жүзеге асады.

Демек, f = А. Теорема дәлелденді.

Қысқартылған DNFфункциялары fбарлық жай импликантты функциялардың дизъюнкциясы болып табылады f. Кез келген функция fқысқартылған DNF арқылы жүзеге асырылады. Нөлге тең емес әрбір функция үшін бірегей қысқартылған DNF бар.

Болсын Ажәне Беркін формулалар болып табылады. Логикалық операциялардың қасиеттері келесі қайтымды DNF түрлендіру ережелерін білдіреді:

1) – толық желімдеу (орналастыру);

2) - толық емес байланыстыру;

3) - жалпылама желімдеу;

4) – сіңіру;

5) – импотенттілік (қайталанатын мүшелерді алып тастау).

Квин теоремасы. SDNF функцияларында болса fтолық емес желімдеудің барлық операцияларын, содан кейін қайталанатын терминдерді сіңіру және жоюдың барлық операцияларын орындаңыз, содан кейін нәтиже DNF функциясының төмендеуі болады. f.

Дәлелдеу.

Бізде қысқартылған DNF функциясы болсын f. Біз қысқартылған DNF әрбір дизъюнктивті мүшесінде жетіспейтін айнымалыларды алу үшін әрбір жай импликантқа барлық кеңейту операцияларын орындаймыз. Алынған өрнекте бірнеше бірдей дизъюнктивтік мүшелерден әрқайсысына бір ғана дананы қалдырамыз. Нәтижесінде SDNF функцияларын аламыз f. Енді алынған SDNF негізінде біз кері ретпен бірдей дизъюнктивті мүшелерді қосу (идемпотенттілік ережелерін қолдану), толық емес желімдеу және сіңіру операцияларын орындаймыз. Нәтижесінде біз түпнұсқалық қысқартылған DNF аламыз.

Шеннонның кеңеюі xi айнымалысына қатысты f (x 1, x 2, . . , xn) логикалық функциясының кеңеюін қарастырайық. Шеннонның кеңеюі: f (x 1, x 2, ... .., xi 1, 0, xi+1, .. , xn). Дәлелдеу (жалпылықты сұраусыз, i =1 үшін). Егер x 1 = 0 болса, f(0, x 2, ... f (0, x2, .., xn). Егер x 1 = 1 болса, f(1, x 2, ... f(0, x2, .., xn). CTD мысалы. z айнымалысында f (x, y, z) = xy / yz логикалық функциясын кеңейтеміз: f (x, y, z) = z(xy / y 1) z (xy / y 0)= [қасиеттері бойынша 0 және 1 ]=zz(xy/y). Шеннон формуласындағы f (x 1, . . . , xi -1, 1, xi+1, . . . , xn ) коэффициенті f (x 1, x 2, . . .) функциясының кеңею коэффициенті деп аталады. , xn) xi кезінде xi айнымалысында, ал f (x 1, . . . , xi -1, 0, xi+1, . . , xn) коэффициенті f (x 1,) функциясының кеңею коэффициенті болып табылады. x 2, . . . , xn) xi ішіндегі xi кезінде. Мысал. f (x, y, z) = x y / y = y (x 1 / 0) y (x 0 / 1). x 1 / 0 - y кезінде f (x, y, z) функциясының кеңею коэффициенті y ; x 0 / 1 - f (x, y, z) функциясының y-дегі y-дегі кеңею коэффициенті.

Функцияның кеңеюі k айнымалылар Дәлелдеу. Теңдіктің сол және оң бөліктеріне ерікті 1 a 2 жиынын қоямыз. . ан: Оң жағын былайша дәлелдей отырып, жеңілдетейік. 1 тек ai = 0 = 1, 11 = 1, бірақ 0 1 = 0 және 10 = 0), ci (шынында: 0, сондықтан конъюнктура бірегей жағдайда ғана біреуге тең болатынын тексеру оңай. a 1 a 2... ak және c1 c2... ck жиындары сәйкес келгенде, бұл оның оң жақтағы бір ғана мүшесі жойылмайтынын білдіреді, ол үшін a 1 a 2... ak = c1 c2... сk және оның өзі 1 болады. Пайда болған мүшеге c1 с2...сk орнына 1 a 2...ak мәнін қойып, аламыз.

Мінсіз дизъюнктивті қалыпты форма (Сов. DNF) Буль функциясының кеңею формуласын k = n үшін k айнымалылардағы f (x 1, x 2, .. , xn) қолданып, мынаны аламыз: Кеңейту коэффициенттері f (c 1 болғандықтан) , c 2, . . . , cn) бұл формуладағы f (x 1, x 2, .., xn) функциясының барлық мүмкін c 1 c 2. жиындарындағы мәндері. . cn, онда екі жағдай мүмкін: егер жинақ c 1 c 2. . . cn M 0 (f), онда f (c 1, c 2, . . , cn) = 0 және, демек, оң жақтағы сәйкес мүше жойылады; егер c 1 c 2 жиыны. . cn M 1 (f), содан кейін f(c 1, c 2, . . , cn)=1 және термин жеңілдетеді. Нәтижесінде бізде: Буль функциясының тамаша дизъюнктивті қалыпты түрі немесе Сов. DNF - бұл пішіннің формуласы:

Сов. бірегейлігін бекіту. DNF 0 тұрақтысынан басқа кез келген логикалық функцияны тамаша дизъюнктивті қалыпты формамен көрсетуге болады және ол осы функция үшін бірегей болып табылады. Үкілерді құру алгоритмі. DNF (ақиқат кестесіне сәйкес) Сов анықтамасынан шығады. DNF және келесі қадамның циклдік орындалуынан тұрады: келесі 1 функция мәндерінің векторлық бағанында таңдалады және осы жолдың аргументтерінің мәндерінің жиынына сәйкес барлық аргументтердің конъюнкциясы құрылады. келесі ережені сақтай отырып: егер жиынның i-ші құрамдас бөлігі 0 болса, онда xi айнымалысы конъюнкцияға 0 дәрежелі (инверсиямен), әйтпесе 1 дәрежесіне (инверсиясыз) енеді; алынған қосылыс формулаға келесі мүше ретінде қосылады. Мысал. Функцияны көрсетудің кестелік тәсілінен формулаға алғаш рет көшкенімізге назар аударайық!

Сов. бірегейлігін бекіту. CNF 1 тұрақтысынан басқа кез келген логикалық функция тамаша конъюнктивтік қалыпты формамен ұсынылуы мүмкін және ол осы функция үшін бірегей. Үкілерді құру алгоритмі. Ақиқат кестесіне сәйкес CNF Сов анықтамасынан шығады. CNF және келесі қадамның циклдік орындалуынан тұрады: функция мәндерінің векторлық бағанында келесі 0 таңдалады және осы жолдың аргументтерінің мәндерінің жиыны негізінде барлық аргументтердің дизъюнкциясы қалыптасады. келесі ережені сақтау: егер жиынның i-ші құрамдас бөлігі 0 болса, онда xi айнымалысы дизъюнкцияға 1 дәрежеге (инверсиясыз), әйтпесе 0 дәрежесіне (инверсиямен) енеді; нәтижесінде алынған дизъюнкция Сов. Басқа фактор ретінде CNF. Мысал.

Элементар конъюнкция және DNF x 1, x 2, айнымалылар жиынын қарастырайық. . . , xn. Элементар конъюнктура деп әр айнымалысы бір реттен көп болатын (инверсиясы бар немесе инверсиясыз) болатын конъюнктураны айтады. Мысалдар. x 1 x 2 x 3 x 4, x 1 x 2 x 4 , x 3 - элементар жалғаулар, x 1 x 2 x 4, x 1 x 3 - элементар емес. Атап айтқанда, 1 - айнымалысы жоқ элементар конъюнктура. Элементар конъюнктураны құрайтын айнымалылар саны оның рангі деп аталады. Мысал. x 1 x 2 x 4 элементар конъюнктураның дәрежесі үш. Толық конъюнктура - барлық айнымалылардан тұратын элементар конъюнктура, яғни n дәрежелі конъюнктура. Мысал. n = 4 үшін x 1 x 2 x 3 x 4 конъюнкциясы аяқталды. Дизъюнктивтік қалыпты форма (DNF) әртүрлі элементар конъюнкциялардың дизъюнкциясы болып табылады. Мысал. x 1 x 2 x 4 x 1 x 2 x 3 x 4 x 3 - DNF. Әлбетте, тамаша DNF - бұл DNF ерекше жағдайы. DNF ұзындығы - берілген DNF ішіндегі қосылыстар саны. DNF дәрежесі - оның конъюнктураларының қатарларының қосындысы. Мысал. Алдыңғы мысалдағы DNF ұзындығы үш және дәрежесі сегіз.

Екі екілік амал (конъюнкция және дизъюнкция) және бір унарлы амал (терістеу) анықталатын және 0 және 1 екі элементі бөлінген В жиыны буль алгебрасы деп аталады.

Сонымен қатар, бұл операциялар үшін келесі қасиеттер орындалуы керек:

Ассоциативтілік

коммутативтілік

Дизъюнкцияға қатысты конъюнктураның үлестірімділігі

Дизъюнкцияның конъюнкцияға қатысты үлестірімділігі

Импотенция

Екі рет жоқ

Тұрақты қасиеттер

Де Морган басқарады

Қарама-қайшылық заңы

Шығарылған орта заңы

Логика алгебрасында бұл заңдар эквиваленттілік деп аталады.

Керемет қалыпты пішіндер

Керемет дизъюнктивті қалыпты форма

Белгілеуді енгізейік:

; A A =1; X=A болса X A =1, XA болса X A =0.

X A 1…… X A n формуласы, мұндағы A=- кез келген екілік жиын және Xi айнымалылары арасында бірдей болуы мүмкін элементар конъюнкция деп аталады.

Элементар қосылыстардың кез келген дизъюнкциясы дизъюнктивтік қалыпты форма (DNF) деп аталады.

Элементар конъюнктура дұрыс деп аталады, егер әрбір айнымалы құрамында бір реттен көп кездессе (оның терістеу таңбасының астындағы кездесуін қоса алғанда).

Мысалы: 1) (бұл жағдайда қосылыс белгішесі түсірілген).

1),4) тұрақты бастауыш болып табылады;

2) - х айнымалысы терістеу белгісімен бір рет өздігінен және екінші рет енеді;

y айнымалысы үш рет пайда болады: бір рет өздігінен және екі рет терістеу белгісінің астында.

Дұрыс элементар конъюнктура x 1 ... .. x n айнымалыларына қатысты толық деп аталады, егер ол осы айнымалылардың әрқайсысын қамтитын болса және тек бір рет болса (болмау белгісі де болуы мүмкін).

Мысалы: алдыңғы мысалда келтірілген жалғаулардың 4-і ғана толық) қатысты x,y,z айнымалылары,т; және айнымалыларға қатысты x,y,z аяқталдытек 1).

x 1 .....xn айнымалыларына қатысты тамаша дизъюнктивтік қалыпты форма (PSNF) - бірдей элементар қосылыстар жоқ және барлық элементар қосылыстар x 1 айнымалыларына қатысты дұрыс және толық болатын дизъюнктивті қалыпты форма. ....xn

Айнымалы кеңейту

Теорема 1. SDNF-де кез келген логикалық функцияны көрсетуге болады:

мұндағы m, ал дизъюнкция x 1 ,…x m айнымалылар мәндерінің барлық 2 м жиындарынан алынады. f функциясы бірінші n-айнымалыларда кеңейтілген. Бұл теңдік айнымалылардағы кеңею деп аталады. x 1 ,… x м . Мысалы, n=4, m=2 үшін ыдырау келесідей болады:

теорема барлық n-айнымалылардың ерікті жиынын (b 1 ,…,b m , b m+1 ,…,b n) теңдіктің екі жағына (1) ауыстыру арқылы дәлелденеді.

m = 1 үшін (1) функциясының бір айнымалыдағы кеңеюін аламыз:

Әлбетте, ұқсас кеңейту кез келген n-айнымалылар үшін жарамды.

Тағы бір маңызды жағдай n=m болғанда. Бұл жағдайда (1) оң жағындағы барлық айнымалылар тұрақты мәндерді алады және оң жақтың қосылымындағы функциялар 0 немесе 1-ге тең болады, бұл:

мұндағы дизъюнкция f=1 болатын барлық жиындарға (b 1 …b n) алынады. f=0 үшін оң жақтағы жалғаулар жиыны бос. Мұндай ыдырау мінсіз дизъюнктивті қалыпты форма деп аталады. f функциясының SDNF құрамында f-тің ақиқат кестесінде қанша қосылғыш болса, сонша конъюнктура бар. Әрбір бірлік жиыны (b 1 ,…, b n) барлық айнымалылардың конъюнкциясына сәйкес келеді, онда x i егер b i =0 b болса терістеумен, ал b i =1 болса терістеусіз қабылданады. Осылайша, f функциясының ақиқат кестесі мен оның SDNF арасында бір-бір сәйкестік бар, демек, кез келген логикалық функция үшін SDNF бірегей болып табылады. SDNF жоқ жалғыз функция - тұрақты 0.

2-теорема. Кез келген логикалық функцияны логикалық формула ретінде көрсетуге болады.

Шынында да, 0 тұрақтысынан басқа кез келген функция үшін оның SDNF мұндай ұсыну ретінде қызмет ете алады. 0 тұрақты мәнін логикалық формуламен көрсетуге болады.

Өкілдік мәселесін қарастырыңыз n-жергілікті логикалық функция f(x 1 ,x 2 ,…,x n) кейбір ұсыныс алгебра формуласы бойынша.

Белгілеуді енгізейік, мұндағы параметр 0 немесе 1-ге тең.

Ол анық

Теорема 1.1. Логика алгебраның әрбір функциясыf(x 1 , x 2 ,…, x n ) кез келген үшінм(1£ м £ n) келесі формада көрсетілуі мүмкін:

мұнда дизъюнкция айнымалы мәндердің барлық мүмкін жиындарынан алынады.

Дәлелдеу. Берілген функцияның барлық айнымалы мәндерінің ерікті жиынын қарастырайық. Бұл жиында (1) формуланың сол және оң бөліктері бірдей мән алатынын көрсетейік. Сол жағы , дұрыс

өйткені , егер тек , егер болса, онда сәйкес логикалық терминді алып тастауға болады.

Пікір. Теоремада көрсетілген функцияның бейнеленуі функцияның шартты түрде кеңеюі деп аталады майнымалылар.

Қорытынды 1(бір айнымалыдағы кеңею).

Бұл жағдайда функциялар және шақырды ыдырау компоненттері.

Салдары 2(барлық айнымалылардағы кеңею).

Бұл анық, егер , содан кейін

Сонымен, егер функция f(x 1 ,x 2 ,…,x n) бірдей жалған функция емес, онда ол , түрінің әртүрлі туындыларының логикалық қосындысы болып табылатын эквивалентті формуламен өрнектелуі мүмкін және мұндай ұсыну бірегей болады.

Формула (2) формасын айтарлықтай жеңілдетуге болады. Логика алгебраның кез келген формуласын тек конъюнкция мен терістеу немесе дизъюнкция мен терістеу бар формулаға эквивалентті түрлендірулер арқылы келтіруге болатыны белгілі. Эквивалентті түрлендірулерді жүргізу нәтижесінде бірнеше формулаларды алуға болады, алайда олардың тек біреуі ғана келесі қасиеттерге ие болады:

1. Әрбір логикалық термин формулаға енгізілген барлық айнымалыларды қамтиды f(x 1 ,x 2 ,…,x n).

2. Ешбір логикалық терминде айнымалы да, оны терістеу де болмайды.

3. Формуладағы барлық логикалық терминдер әртүрлі.

4. Ешбір логикалық термин бірдей айнымалыны екі рет қамтымайды.

Бұл төрт қасиет деп аталады кемелдік қасиеттері(немесе С қасиеттері).

Егер f(x 1 ,x 2 ,…,x n) ақиқат кестесімен берілген, онда сәйкес логикалық алгебра формуласын өте қарапайым қалпына келтіруге болады. Барлық аргумент мәндері үшін x 1 ,x 2 ,…,x n, онда f 1 мәнін қабылдайды, конъюнкция мүшесін алып, ұсыныстардың элементар айнымалыларының конъюнкциясын жазу керек x i, егер x i=1, және егер x i=0. Барлық жазылған конъюнкциялардың дизъюнкциясы қажетті формула болады. Құндылықтар туралы f 0 уайымдаудың қажеті жоқ, өйткені формуладағы сәйкес термин 0-ге тең болады және эквиваленттілікке байланысты жойылуы мүмкін fÚ 0 ≡ f.

Мысалы, функция болсын f(x, ж, z) келесі ақиқат кестесіне ие:

Ақиқат кестесін пайдаланып айнымалылардың логикалық функцияларын орнату, формуланы анықтау, логика алгебраның маңызды эквиваленттіктерінің (заңдарының) түрлерін анықтау. Эквивалентті формулалар, теңдік заңдары, логикалық теңдеулер. Айнымалылардағы логикалық функциялардың декомпозициясы.

«Архивті жүктеп алу» түймесін басу арқылы сіз өзіңізге қажетті файлды тегін жүктейсіз.
Жүктеп алу алдында берілген файлсол жақсы эсселерді, бақылауды, курстық жұмыстарды есте сақтаңыз, тезистер, мақалалар және компьютеріңізде талап етілмеген басқа құжаттар. Бұл сіздің еңбегіңіз, ол қоғамның дамуына атсалысып, адамдарға пайдасын тигізуі керек. Осы жұмыстарды тауып, білім қорына жіберіңіз.
Біз және барлық студенттер, аспиранттар, білім қорын оқуда және жұмыста пайдаланатын жас ғалымдар сіздерге алғысымыз шексіз.

Мұрағатты құжатпен жүктеп алу үшін төмендегі өріске бес таңбалы санды енгізіп, «Мұрағатты жүктеп алу» түймесін басыңыз.

Ұқсас құжаттар

Логика алгебраның негізгі аксиомалары мен сәйкестіктері. Бульдік функцияларды ұсынудың аналитикалық формасы. Логика алгебраның элементар функциялары. Бір аргумент логикасы алгебрасының функциялары және оны жүзеге асыру формалары. Логикалық операциялардың қасиеттері, ерекшеліктері және түрлері.

аннотация, 12/06/2010 қосылған


Логика алгебрасы туралы түсінік, оның мәні мен ерекшеліктері, негізгі ұғымдары мен анықтамалары, зерттеу пәні мен әдістемесі. Логика алгебрасы заңдары және одан шығатын салдарлар, берілген ақиқат кестесі бойынша формулаларды құру әдістері. Бульдік функцияларды бейнелеу формалары.

оқу құралы, 29.04.2009 қосылған


Логикалық алгебралар – логиканы (адамның ойлау логикасы да, цифрлық компьютерлік логика да), сондай-ақ коммутациялық тізбектерді зерттеуде қолданылатын ерекше типтегі торлар. Бульдік көпмүшелердің минималды формалары. Абстрактілі бульдік алгебраның теоремалары.

курстық жұмыс, 05/12/2009 қосылған


Логикалық мәлімдемелердегі амалдар: логикалық функциялар және осы тәуелділіктердің кейбірін басқалары арқылы өрнектеу. Ұсыныс формулалары және ұсыныс логикасының кейбір заңдары. Табиғи тілдегі өрнектерді логика алгебрасының символдық сөйлеуіне аудару.

сынақ, 26.04.2011 қосылған


Логика – ойлаудың заңдылықтары мен формалары туралы ғылым, ал логика алгебраның негізгі ұғымы – мәлімдеме. Буль алгебрасының негізгі ұғымдары мен сәйкестіктері. Бульдік функцияларды минимизациялау әдістерін зерттеу. Екі негізгі қатынасты қолдануға негізделген Квин әдісі.

сынақ, 20.01.2011 қосылған


Логика алгебрасының негізгі түсініктері. Дизъюнктивтік және конъюнктивтік қалыпты формалар. Шеннон теоремасының мәні. Екі айнымалының логикалық функциялары. Тұрақты және параллель байланысекі қосқыш. Логика алгебраның элементар функцияларының қасиеттері.

сынақ, 29.11.2010 қосылған


Логика алгебрасында логикалық айнымалы. Логикалық амалдар: терістеу, конъюнкция, дизъюнкция, импликация, эквиваленттілік. Логика алгебраның негізгі заңдары. Логикалық функцияны минимизациялау ережелері (импликация және эквиваленттік операциялардан құтылу).

курстық жұмыс, 16.01.2012 қосылған