Екіжақтылық принципі. айнымалылардағы логикалық функцияларды кеңейту

Болсын с 0 немесе 1 мәндерін қабылдайды, яғни. с {0, 1}.

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

x с = Ø x, егер с = 0, x с = x, егер с = 1.

Анау. x 0 = Ø x, x 1 = x.

Ол анық x с= 1 егер x = сжәне x с= 0 егер x с.

4.5 теорема(айнымалылардағы логикалық функцияның кеңеюі туралы).

Әрбір логикалық функция f(x 1 , x 2 , ... , x n) келесі түрде көрсетілуі мүмкін:

f(x 1 , x 2 , ... , x n) = f(x 1 , x 2 , ... , x м, x м +1 , ... , x n) =

В x 1 с 1 &x 2 с 2 &...&х м см& f(с 1 , с 2 , ... с м, x м +1 , ... , x n), (4.1)

м n, мұнда барлық жиындар бойынша дизъюнкция қабылданады ( с 1 , с 2 , ... , с м) (2 бар м).

Мысалы, үшін м = 2, n= 4 кеңейту (4.1) төрт (2.) қамтиды м= 2 2 =4) конъюнктура және мына түрге ие:

f(x 1 , x 2 , x 3 , x 4) = x &x &f(0, 0, x 3 , x 4) V x &x &f(0, 1, x 3 , x 4) V x & x &f(1, 0, x 3 , x 4) V x & x &f(1, 1, x 3 , x 4) = Ø x 1&Ø x 2 &f(0, 0, x 3 , x 4) V x 1 &x 2 &f(0, 1, x 3 , x 4) V x 1&Ø x 2 &f(1, 0, x 3 , x 4) V x 1 &x 2 &f(1, 1, x 3 , x 4).

4.5 теореманы дәлелдеу.

Теорема дәлелденетін болады, егер теңдік (4.1) айнымалылардың ерікті жиыны үшін орындалатынын көрсетсек ( ж 1, ж 2 , ... , ж м, ж м +1 , ... , ж н) .

Бұл айнымалылардың ерікті жиынын теңдіктің сол және оң жақтарына ауыстырамыз (4.1).

Сол жақта біз аламыз f (ж 1, ж 2 , ... , ж н) .

Т. у с= 1 болғанда ғана ж = с, содан кейін 2 арасында мжалғаулықтар ж 1 с 1 &ж 2 с 2 &...&ж м см(4.1) оң жағында тек біреуі 1-ге айналады - онда бір ж 1 = с 1 ,…, ж м = с м. Барлық қалған қосылыстар 0-ге тең. Сондықтан (4.1) оң жағында мынаны аламыз:

ж 1 ж 1 &ж 2 ж 2 &...&ым ым&f(ж 1, ж 2 , ... , ж м, ж м +1 , ... , ж н) = f(ж 1, ж 2 , ... , ж н) .

4.5 теоремасы дәлелденді.

4.6 теорема(SDNF-те логикалық функцияны формуламен көрсету туралы),

Кез келген логикалық функция f(x 1 , x 2 , ... , x n), ол 0-ге бірдей тең емес, SDNF-дегі формуламен ұсынылуы мүмкін, ол дизъюнктивті мүшелердің ауыстырылуына дейін бірегей түрде анықталады.

Дәлелдеу.

Сағат м = n 4.5 теоремасының маңызды нәтижесін аламыз:

f(x 1 , x 2 , ... , x n) = V x 1 с 1 &x 2 с 2 &...&x n sn, (4.2)

f(с 1 , с 2 , ... , s n) = 1

мұнда барлық жиындар бойынша дизъюнкция алынады ( с 1 , с 2 , ... , s n), қайда f = 1.

Кеңейту (4.2) формуланың SDNF-інен басқа ештеңе емес екені анық fмәндер кестесінде қанша бірлік болса, сонша конъюнктура бар f. Демек, кез келген логикалық функция үшін SDNF оның дизъюнктивті шарттарының ауыстырылуына дейін бірегей болып табылады.

Бұл логикалық функция үшін де анық f(x 1 , x 2 , ... , x n) бірдей 0-ге тең, кеңейту (2) жоқ.

Жоғарыда айтылғандарды ескере отырып, логикалық функцияның формуласын алу f(x 1 , x 2 , ... , x n) SDNF-де біз келесі алгоритмді пайдалана аламыз.

Алгоритм 4.3. (Кесте арқылы берілген логикалық функцияны көрсету алгоритмі, SDNF-дегі формула).

1-қадам. с 1 , с 2 , ... , s n, ол үшін мән f 1-ге тең, яғни. f (с 1 , с 2 , ... , s n) = 1.

2-қадамӘрбір осындай жиынтыққа (кесте жолдары) біз жалғау құраймыз x 1 с 1 &x 2 с 2 &...&x n sn, қайда x i si = x i, егер с мен= 1 және x i si =Ø x i, егер с мен = 0, мен = 1, 2, ... ,n.

3-қадамБарлық шыққан жалғаулардың дизъюнкциясын жасаймыз. Нәтиже SDNF ішіндегі осы функцияның формуласы болып табылады.

4.15-мысал.

Функция үшін SDNF формуласын табыңыз f(x 1 , x 2 , x 3) 4.4-кестеде келтірілген.

f(x 1 , x 2 , x 3) =1. Бұл 4-ші, 5-ші. 6 және 8 жолдар.

2. Әрбір таңдалған жол үшін 2-қадамда көрсетілген ережеге сәйкес жалғауларды жасаймыз. Таңдалған төрт жол үшін сәйкесінше аламыз:

x 1 0 &x 2 1 &x 3 1 = Ø x 1 &x 2 &x 3 .

x 1 1 &x 2 0 &x 3 0 = x 1&Ø x 2&Ø x 3 .

x 1 1 &x 2 0 &x 3 1 = x 1&Ø x 2 &x 3 .

x 1 1 &x 2 1 &x 3 1 = x 1 &x 2 &x 3 .

3. Барлық шыққан қосылыстарға дизъюнкция жасап, SDNF табамыз:

f(x 1 , x 2 , x 3) = Ø x 1 &x 2 &x 3V x 1&Ø x 2&Ø x 3V x 1&Ø x 2 &x 3V x 1 &x 2 &x 3 .

Біз бұл өрнектің 4.13-мысалда бұрын алынған SDNF-дегі формуламыздың көрінісімен сәйкес келетініне көз жеткіземіз.

Пікір.Егер логикалық функция SDNF-де формуламен берілсе, 4.3 алгоритмін кері ретпен қолдану арқылы біз бұл функцияның мәндер кестесін оңай ала аламыз.

Теорема 4.7(СКНФ-те логикалық функцияны формуламен көрсету туралы),

Кез келген логикалық функция f(x 1 , x 2 , ... , x n) бірдей 1-ге тең емес, SKNF формуласымен ұсынылуы мүмкін, ол дизъюнктивті мүшелердің ауыстырылуына дейін бірегей түрде анықталады.

Дәлелдеу.

Ø функциясын қарастырайық f(x 1 , x 2 , ... , x n). 4.6 теоремасы бойынша, егер ол 0-ге бірдей тең болмаса, онда SDNF-де оның формуласы бар. Бұл формуланы белгілейік Фбір . Ø функциясының шарты анық f(x 1 , x 2 , ... , x n) бірдей 0-ге тең емес, функцияның шартына тең f(x 1 , x 2 , ... , x n) 1-ге бірдей тең емес. Сонымен қатар, де Морган заңына сәйкес формула Ф 2ºØ Ф 1 SKNF-де (конъюнктураны терістеу - терістеулердің дизъюнкциясы). Қос теріске шығару заңы бойынша

Ф 2ºØ Ф 1ºØØ f(x 1 , x 2 , ... , x n) º f(x 1 , x 2 , ... , x n),

бұл теореманы дәлелдейді.

Логикалық функция формуласын алу үшін f(x 1 , x 2 , ... , x n) SKNF-де келесі алгоритмді қолдану керек.

Алгоритм 4.4. (СКНФ-дегі кесте, формула арқылы берілген логикалық функцияны көрсету алгоритмі)

1-қадам.Кестедегі барлық айнымалылар жиынын таңдаңыз с 1 , с 2 , ... , s n, ол үшін мән f (с 1 , с 2 , ... , s n) = 0.

2-қадамӘрбір осындай жиынтық үшін (кесте жолдары) біз дизъюнкция жасаймыз

x 1Ø с 1V x 2 Ø с 2V...V x n Ø sn, қайда x i Ø си = x i, егер с мен= 0 және x i Ø си = Ø x i, егер с мен = 1, мен = 1, 2, ... , n.

3-қадамБарлық шыққан дизъюнкциялардың конъюнкциясын құрастырамыз. Нәтиже – SKNF.

4.16-мысал.

Функция үшін SKNF формуласын табыңыз f(x 1 , x 2 , x 3) 4.4-кестеде келтірілген.

1. Кестедегі жолдарды таңдаңыз f(x 1 , x 2 , x 3) = 0. Бұл 1-ші, 2-ші және 3-ші және 7-ші жолдар.

2. Әрбір таңдалған жол үшін 2-қадамда көрсетілген ережеге сәйкес ажыратулар жасаймыз. Таңдалған үш жол үшін сәйкесінше аламыз:

x 1 1В x 2 1В x 3 1 = x 1V x 2В x 3 .

x 1 1В x 2 1В x 3 0 = x 1V x 2В x 3 .

x 1 1В x 20В x 3 1 = x 1V x 2В x 3 .

x 1 0В x 20В x 3 1 = Ø x 1V x 2В x 3 .

3. Барлық алынған дизъюнкциялардың конъюнкциясын жасап, СКНФ-ны табамыз:

f(x 1 , x 2 , x 3) = (x 1V x 2В x 3)&(x 1V x 2В x 3)&(x 1V x 2В x 3)&(Ø x 1V x 2В x 3).

Бұл өрнек 4.14-мысалда бұрын алынған SKNF-дегі формуламыздың көрінісімен сәйкес келеді.

Пікір.Өйткені функционалдық кестеде 2 жол бар n, онда SDNF-дегі дизъюнктивті мүшелердің саны тең болса б, ал SKNF-дегі конъюнктивтік мүшелердің саны тең q, содан кейін б+q=2n.

Сонымен, 4.15 және 4.16 мысалдарында қарастырылған функция үшін, n = 3, б = 4, q = 4, б + q = 8 = 2 3 .

Бұл теорема конструктивті сипатқа ие, өйткені ол әрбір функция үшін оны тамаша d.s түрінде жүзеге асыратын формуланы құруға мүмкіндік береді. f. Ол үшін әрбір функция үшін ақиқат кестесінде барлық жолдарды белгілейміз

Егер бұл жұмыс сізге сәйкес келмесе, беттің төменгі жағында ұқсас жұмыстардың тізімі бар. Сондай-ақ іздеу түймесін пайдалануға болады

Аранов Виктор Павлович Дискретті математика.

4-бөлім Функционалдық жүйелероперациялармен. Логика алгебрасы.

Дәріс 21. Екіжақтылық принципі. Айнымалылардағы функциялардың декомпозициясы. Керемет DNF және CNF

Дәріс 21 ДУАЛИЯЛЫҚ ПРИНЦИП. БУЛЬДІК ыдырау

Айнымалылардағы Функциялар. КЕРЕМЕТ ДИЪЮНКТИВТІ ЖӘНЕ

КОНЮКТИВТІК ҚАЛЫПТЫ ФОРМАЛАР

Дәріс жоспары:

1. Екіжақтылық принципі.
2. Ыдырау логикалық функцияларайнымалылар бойынша. Мінсіз дизъюнктивті және конъюнктивті қалыпты формалар.

1. Екіжақтылық принципі

тең функция шақырыладықос жұмыс істеу үшін функция.

Айнымалылар мен функцияның мәндерін инверсиялау (яғни, 0-ді 1-ге және 1-ді 0-ге ауыстыру) функцияның ақиқат кестесінен қосарлы функция үшін ақиқат кестесінен алынғаны анық. Мысалы, .

0, 1 функциялары үшін орнату оңай

1. 0 функциясы 1-ге қосарланған;
2. 1 функциясы 0-ге қосарланған;
3. функция екі жақты;
4. функция екі жақты;
5. функция екі жақты;
6. функциясы қос.

Екіжақтылықтың анықтамасынан шығатыны

яғни, функция екі жақты (өзара қасиеті).

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

Формула k-ге қосарланған формула деп аталады.

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

Мысалы, функция келесі ауыспалы алмастыру нәтижесінде функциядан алынсын:

Содан кейін

яғни функция бірдей айнымалыны алмастыру нәтижесінде алынған.

Мысал арқылы қадам үшін екі жақтылық принципінің дұрыстығын дәлелдеп көрейік. Болсын

Содан кейін

яғни функция және -дан алынған функция сияқты және -дан алынған.

Екілік принципі негізгі тавтологияларды шығаруды жеңілдетуге мүмкіндік береді және бар тұтас сызықтөменде талқыланатын пайдалы қолданбалар.

1-мысал Сәйкестік сәйкестіліктен туындайды.

Шынымен,

;; .

2-мысал Функцияны теріске шығару формуласын құру.

Қос функцияның анықтамасынан ол шығады

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

Функцияның терістеуін табыңыз.

Сол уақыттан бері.

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

Дизъюнктивтік және конъюнктивтік қалыпты формалар

Белгілеуді енгіземіз

мұндағы параметр 0 немесе 1-ге тең. Әлбетте,

Бұл 1-ді, егер және егер болса ғана көру оңай.

Айнымалылардағы функциялардың кеңеюі туралы теорема. Кез келген () үшін логикалық алгебраның әрбір функциясын келесі түрде көрсетуге болады:

, (1)

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

Бұл презентация деп аталадыфункцияның айнымалылардағы кеңеюі.

Дәлелдеу. Айнымалы мәндердің ерікті жиынын қарастырыңыз және қатынастың сол және оң жақ бөліктері (1) ондағы бірдей мәнді қабылдайтынын көрсетіңіз. Сол жағы береді. Оң -

Теореманың қорытындылары ретінде біз ыдыраудың екі ерекше жағдайын қарастырамыз.

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

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

1. Барлық айнымалылардағы кеңейту:

Бірдей 0-ге тең болмаса, оны түрлендіруге болады:

Нәтижесінде біз ақырында аламыз

. (2)

Мұндай ыдырау деп аталадымінсіз дизъюнктивті қалыпты форма(Ғылымдардың тамаша докторы).

Тікелей мінсіз д.с. тұжырымдамасына. f. келесі теоремаға қосылады.

Теорема. Логика алгебраның әрбір функциясын базистегі формуламен көрсетуге болады.

Дәлелдеу 1) Болсын. Сонда анық

1. Ол бірдей 0-ге тең болмауы керек. Сонда оны (2) формуламен көрсетуге болады.

Бұл теорема конструктивті, өйткені ол әрбір функция үшін оны тамаша d.s түрінде жүзеге асыратын формуланы құруға мүмкіндік береді. f. Ол үшін әрбір функция үшін ақиқат кестесінде барлық жолдарды белгілейміз. Әрбір осындай жол үшін біз логикалық туынды құраймыз, содан кейін барлық алынған қосылыстарды дизъюнкция белгісімен байланыстырамыз.

3-мысал Керемет д.с. табыңыз. f. функциясы үшін.

Керемет д.с. f. P түрінің өрнегі болып табылады. 1 бірдей 1-ге тең болмаса, оны пішінде көрсетуге болатынын көрсетейік. Қос функция үшін (0-ге бірдей емес екені анық) кеңеюді тамаша d.s түрінде жазайық. f.:

Екіжақтылық принципінен ол шығады

Осылайша, біз деп аталатын ыдырауды аламызмінсіз конъюнктивтік қалыпты форма(мінсіз Ph.D):

. (3)

4-мысал Мінсіз Ph.D дәрежесін жасаңыз. f. функциясы үшін.

Бізде бар.

Өкілдік мәселесін қарастырыңыз 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) келесі ақиқат кестесіне ие:

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

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 аламыз.

Жиын алгебрасы мен логикалық алгебра арасындағы байланыс 2 изоморфтық жүйенің болуы.

БИЛЕТ 25

Екіжақтылық туралы түсінік. Екіжақтылық принципі.

Def. Берілген логикалық функция үшін оның дуалы деп аталады: ).

Ескертпелер.

Логикалық функция берілсін.

Пікір. Функцияларда f мен, i=1,…,m кейбір айнымалылар жалған болуы мүмкін.

= = = =

Салдары.Егер логикалық функция F формуласымен B 0 =(x&y,x˅y,-,0,1) негізінде берілсе, қос функцияны алу үшін ауыстыруды орындау жеткілікті:

БИЛЕТ 26

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

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

Кез келген логикалық f=f(x 1 ,…,x n) және V 1≤k≤n үшін f(x1,…,xn)= көрінісі жарамды, мұнда x 1 =x, x 0 = ̚ x.

Z=(α1,…,αn) ерікті жиынын алайық және оны формуланың сол және оң жақ бөліктеріне қоямыз:

L.Ch.=f(α1,…,αn)

P.Ch.= =

{ 1 0 ==0; 0 1 =0; 1 1 =1; 0 0 ==1; }

Оң жағы сол жағына сәйкес келді.

Салдары 1.Айнымалылардағы логикалық функцияны кеңейту формуласы:

k=1 болсын. Соңғы айнымалыдағы кеңейтуді алайық.

Салдары 2.Функцияның тамаша дизъюнктивті қалыпты формулаға (SDNF) ыдырауы.

В әділ = .

=1.

Теоремадағы k=n жағдайын алайық, яғни. барлық айнымалылардағы кеңейту.

Салдары 3.Кез келген функцияның классикалық негізде бейнеленуі туралы.

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

B 0= (x&y,x˅y,)

Пікір.Кез келген логикалық функция үшін SDNF түріндегі ұсыну бар және бұл ұсыну бірегей болып табылады.

БИЛЕТ 27

Perfect Disjunctive Normal Forms (PDNF) [өнімдердің қосындысы ˅&].

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

келесі қадамдарды қамтиды:

f (x 1 , x 2 ,..., xn) функциясы 1-ге тең x 1 , x 2 ,..., xn айнымалы мәндерінің әрбір жиыны үшін барлық айнымалылардың конъюнктуралары жазылады. шығу;

терістеулер осы жиында 0-ге тең айнымалылардың үстіне қойылады;

· мұндай жалғаулардың барлығы дизъюнкция белгілері арқылы байланысады.

Осылайша алынған формула логикалық функцияның тамаша дизъюнктивті қалыпты түрі (PDNF) деп аталады.

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

Сонымен, f (x 1 , x 2 ,..., xn) функциясының SDNF элементар конъюнкциялардың дизъюнкциясы болып табылады: D = K 1 ˅ K 2 ˅ ... ˅ K m , мұндағы барлық конъюнктуралардың саны бірдей. факторлардың саны логикалық айнымалылар санына тең, ал конъюнкциялар саны f (x 1, x 2) функциясы орындалатын x 1 , x 2 ,..., xn айнымалылар мәндерінің жиындарының санына тең. ,..., xn) 1-ге тең. Бұл шарттарға сай келмейтін D = K 1 ˅ K 2 ˅ ... ˅ K m түріндегі логикалық функцияның кез келген басқа жазбалары деп аталады.

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

БИЛЕТ 28

Perfect Conjunctive Normal Forms (CKNF)[сомалардың өнімі &˅].

Мәлімдеме. Кез келген логикалық функция үшін f=f(x1,…,xn),f ≠ 1 әділ өкілдік

Бізде: f* ≠ 0. Енді f* үшін SDNF құрастырайық.

Теңдеудің екі жағының қосарлығын алайық.

Ауыстыруларды орындау:

= .

Пікір. Әрбір логикалық функция үшін ≠ 1 SKNF түріндегі өкілдік бар және бұл ұсыну жалғыз.

БИЛЕТ 29

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

Логика алгебрасында функцияны формула түрінде көрсетудің 3 кононикалық формасы әдетте ажыратылады:

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

Мономиаль – 0,1, түріндегі формула.

Жегалкин полиномы:

P=M 1 ⊕M 2 ⊕…⊕M k , M i – моном.

Барлық мономалдар жұптық түрде ерекшеленеді.

Теорема.Кез келген логикалық функцияны Жегалкин көпмүшесі ретінде көрсетуге болады және бұл көрініс бірегей.

I. Функцияның Жегалкин көпмүшесі ретінде берілгендігін дәлелдейміз.

2 жағдайды қарастырыңыз

1. f ≠ 0, содан кейін

Біз ˅-ді ⊕-пен алмастыра аламыз, өйткені SDNF≠1-де екі термин жоқ.

Сондықтан j () бар

Түрлендірулер жасайық

Біз жақшаларды ашамыз, AA \u003d 0 ережесіне сәйкес ұқсастарын береміз.

Нәтижесінде әрбір функция үшін Жегалкин көпмүшелігін аламыз.

II. Біз бірегейлікті дәлелдейміз.

Дирихле принципін қолданайық.

Жегалкин көпмүшелерінің санын есептейік.

. Яғни, 2 n нөл емес.

Бос мономиал=1.

Көпмүшені құраймыз:

Мономов = N=2 n

Көпмүшеліктер = 2 N =

Егер ештеңе қосылмаған болса, онда 0.

БИЛЕТ 30

Бульдік функциялар жүйесінің функционалдық толықтығы туралы түсінік. Жүйенің толықтығы (ЖӘНЕ, НЕМЕСЕ, ЕМЕС).

Анықтама.Логикалық алгебраның кез келген функциясын А формуласымен өрнектеуге болатын болса, А логикалық алгебраның функцияларының жиынтығы толық жүйе (Р2-де) деп аталады. Теорема. A = (v, &, ─) жүйесі аяқталды.

Дәлелдеу.Егер f логикалық алгебра функциясы бірдей нөлге тең болмаса, f тек дизъюнкцияны, конъюнкцияны және терістеуді қамтитын тамаша дизъюнктивтік қалыпты форма ретінде өрнектеледі. Егер f≡ 0 болса, онда f = x*(─x). Теорема дәлелденді.

БИЛЕТ 31

Жабық және жабық сабақтар.

1°. Жабық сынып туралы түсінік.

Анықтама 1. A ⊆ P2 болсын. Сонда А-ның тұйықталуы - бұл А-ның үстіндегі формулалармен өрнектелетін логика алгебраның барлық функцияларының жиыны.

Белгіленуі: [A].

Келесі қасиеттер орын алады:

2) A ⊇ B ⇒ [A] ⊇ [B], оның үстіне импликацияның сол жағында қатаң кірістіру болса, оң жағындағы қатаң кірістіру мүлдем орындалмайды - тек A ⊃ B ⇒ [ A] ⊇ [B] шын;

Анықтама 2. А логикалық алгебраның функциялар жүйесі толық деп аталады, егер [A] = P2.

Анықтама 3. A ⊆ P2 болсын. Сонда А жүйесін тұйық класс деп атайды, егер А тұйықталуының өзі А-мен сәйкес келсе: [A] = A.

2°. Жабық сабақтардың мысалдары.

Т класы 0 = (f (x 1 , …, x n) | f (0, …, 0) = 0).

T 0 класына, мысалы, 0, x, xy, x ∨ y, x ⊕ y функциялары кіреді.

T 0 класына 1, x , x → y, x | функциялары кірмейді y, x ↓ y, x ~ y.

T 1 класы = (f (x 1 , …, x n) | f (1, 1, …, 1) = 1).

T 1 класы 1, x, xy, x ∨ y, x → y, x ~ y функцияларын қамтиды.

T 1 класына 0, x , x ⊕ y, x | функциялары кірмейді y, x ↓ y.

Сызықтық функциялардың L класы.

Анықтама 4. Логикалық алгебраның f (x 1 , …, x n) функциясы сызықтық деп аталады, егер

f (x 1 , …,x n) = a 0 ⊕ a 1 x 1 ⊕ … ⊕ a n x n , мұндағы a i ∈ (0, 1).

Басқаша айтқанда, сызықтық функцияның көпмүшесінде конъюнктурасы бар мүшелер болмайды.

L класында 0, 1, x = x⊕1, x ~ y, x ⊕ y функциялары бар.

xy, x ∨ y, x → y, x |функциялары y, x ↓ y.

Өзіндік қосарланған функциялардың S класы.

Анықтама 2. f (x 1 ,…, x n) логикалық алгебра функциясы f (x 1 ,…, x n) = f* (x 1 ,…,x n) болса, өзіндік қосарлы деп аталады.

Басқаша айтқанда, S = (f | f = f*).

Анықтама 2. Логикалық алгебраның f (x 1 ,…,xn) функциясы монотонды деп аталады, егер кез келген екі салыстырылатын ~α және ~β жиындары үшін импликация ~α≤ ~ β ⇒f(~α) ≤ f ( ~ β)

Барлық монотонды функциялардың М класы.

M класы 0 , 1 , x , xy , x ∨ y, m (x, y, z) = xy ∨ yz ∨ zx функцияларын қамтиды.

x , x |функциялары y , x ↓ y , x ⊕ y , x ~ y , x → y

БИЛЕТ 32

Сабақтан кейінгі.

Пост критерийлері- логикалық функциялар теориясындағы орталық теоремалардың бірі, логикалық функциялардың белгілі бір жиынының кез келген логикалық функцияны көрсету үшін жеткілікті экспрессивтілікке ие болуы үшін қажетті және жеткілікті шартты белгілейді. Оны алғаш рет американдық математик Эмиль Пост тұжырымдаған.

Логикалық функция - түрдегі функция, мұндағы және аритет. Әртүрлі логикалық функциялардың жалпы саны шексіз, ал әр түрлі аритеттік функциялардың саны тең. Дегенмен, суперпозиция операторы арқылы көптеген функцияларды басқаларымен көрсетуге болатыны анық. Мысалы, дизъюнкция мен терістеуден де Морган заңдарын пайдалана отырып, конъюнкция алуға болатыны бұрыннан белгілі. Сонымен қатар, кез келген логикалық функция (бірдей нөлден басқа) DNF ретінде, яғни конъюнкция, дизъюнкция және терістеу тұрғысынан ұсынылуы мүмкін. Табиғи сұрақ туындайды: берілген функциялар жиыны кез келген логикалық функцияны көрсету үшін жеткілікті болатынын қалай анықтауға болады? Мұндай жиынтықтар деп аталады функционалдық толық. Пост теоремасы бұл сұраққа жауап береді. Теореманың шарттары қажетті және жеткілікті болғандықтан, ол да аталады критерий.

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

БИЛЕТ 33

толықтық критерийі.

12-теорема (Пост теоремасы). A = (f1, f2, …) логикалық алгебраның функциялар жүйесі, егер ол келесі сыныптардың ешқайсысында толығымен қамтылмаған болса ғана, P2-де толық болады: T0, T1, S, L, M.

Дәлелдеу. Қажет.А толық жүйе болсын, N T 0 , T 1 , S, L, M кластарының кез келгені болсын және A ⊆ N болсын. Сонда [A] ⊆ [N] = N ≠ P2 және [A] ≠ P2. Пайда болған қайшылық қажеттілікті негіздеуді аяқтайды.

Адекваттылық. A ⊄ T 0 , A ⊄ T 1 , A ⊄ M, A ⊄ L, A ⊄ S болсын. Сонда A құрамында f 0 ∉ T 0 , f 1 ∉ T 1 , f m ∉ M,

f l ∉ L, f s ∉ S. [A] ⊇ = P2 екенін көрсету жеткілікті. Дәлелдеуді үш бөлікке бөлейік: терістеуді, тұрақтыларды және жалғауларды алу.

a) ─x алу. f 0 (x 1 , …, x n) ∉ T0 функциясын қарастырып, φ 0 (x) =f 0 (x, x, …, x) функциясын енгізіңіз. f 0 функциясы нөлді сақтамайтындықтан, φ 0 (0) = f (0, 0, ..., 0) = 1. Екі жағдай мүмкін: не ϕ 0 (x) = ─x, не φ0 (x) ) ≡ 1. f 1 (x 1 , …, xn) ∉ T 1 функциясын қарастырып, сол сияқты φ 1 (x) = f 1 (x, x, …, x) функциясын енгізіңіз. f 1 функциясы сәйкестікті сақтамайтындықтан, φ 1 (1) = f (1, 1, ..., 1) = 0. Екі жағдай да мүмкін: не ϕ 1 (x) = ─x , немесе φ1 (x) ≡ 0 Кем дегенде бір жағдайда қажетті теріске шығару алынса, тармақ аяқталды. Егер екі жағдайда да тұрақтылар алынса,

онда монотонды емес функция леммасы бойынша f m ∉ M функциясына тұрақтылар мен бірдей функцияларды ауыстыру арқылы біз терістеуді аламыз.

Бас тарту қабылданды.

б) 0 және 1 тұрақтыларын алу. Бізде fs ∉ S бар. Өзіндік қосарлы емес функция леммасы бойынша, fs функциясының барлық айнымалыларының орнына терістеуді (а нүктесінде алынған) және сәйкестендіру функциясын ауыстырып, біз тұрақтыларды алыңыз: ∋ . Алынған тұрақтылар.

в) x · y конъюнктурасын алу. Бізде fl ∉ L функциясы бар. Сызықтық емес функция леммасы бойынша fl функциясына тұрақтылар мен терістеулерді (дәлелдеудің алдыңғы қадамдарында алынған) ауыстыру арқылы a конъюнкциясын немесе терістеуін алуға болады. жалғаулық. Алайда, бірінші кезеңде терістеу әлдеқашан алынған, сондықтан конъюнкцияны алуға әрқашан болады:

∋ . конъюнктура алынды.

Нәтижесінде ⊇ [ ─x,xy] = P 2 болады. Соңғы теңдік 4-теореманың 2-тармағынан шығады. 2-лемманың күшімен жеткіліктілік дәлелденді.

БИЛЕТ 34

Функционалдық элементтердің схемалары бойынша логикалық функцияларды жүзеге асыру.

*оқулық*

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

Функционалдық элементтерді біріктіріп, біз аламыз функционалдық диаграмма.Оны кез келген логикалық функцияны жүзеге асыру үшін пайдалануға болады.

Функционалдық элементтер тізбегінің күрделілігі - бұл схемадағы функционалды элементтердің саны.

Дизьюнктор, инвектор.

SFE - функционалдық элементтердің схемалары.

F=(f 1 , f 2 , …, f m)

L(S) – күрделілік – схемадағы функционалдық элементтердің саны.

L(S) = minL(S) - схеманы құруға болатын элементтердің ең аз саны.

L A (f) = L(S A (f)) - тізбектің күрделілігі.

L A (n) = maxL A (f), f ϵ . Макс барлық айнымалылар үшін алынады.

А үшін Шеннон функциясы.

SDNF енгізіңіз л (el) шарттары.

f = k 1 ˅k 2 ˅…˅k л

Алынған S схемасын белгілеңіз, онда

L(S) = L(Dn)+L(V л)

L(Dn) = 2*2n + n - 4

л≤ 2н

L(V л)=л- 1≤ 2 n – 1

L(S) ≤ (2*2 n + n - 4) + (2 n - 1) = 3*2 n + n - 5.

БИЛЕТ 35

Функционалдық элементтерден тізбектер класында дешифраторды іске асыру (элементтерді таңдау схемасы).

*оқулық*

n ретті Qn дешифраторы – n кірісі x 1 , x 2 , …, x n және 2 n шығысы z0, z 1 ,… болатын функционалдық элементтер тізбегі, егер |x1x2…xn| = i, онда zi = 1 және i ≠ j үшін zj = 0.

Егер i = (i 1 , i 2 , …, i n) 2 болса, z i (x 1 ,…,x n) = болатынын ескеріңіз.

Лемма.Ең көбі n2 n+1 элементтері бар Qn дешифраторы бар.

Дәлелдеу.Әрбір z i жүзеге асыру үшін дәл n–1 конъюнктураны және n артық емес теріске шығаруды, яғни жалпы саны 2n-ден аз функционалдық элементтерді алу жеткілікті. Дәл 2 n түрлі конъюнктура бар және дешифратордың күрделілігі n 2n+1 аспайды.

Тривиальды әдістер элементар қосылыстардың автономды орындалуына негізделген.

БИЛЕТ 36

Функционалды элементтерден тізбектерді синтездеудің әмбебап әдістері.

Теорема.Функционалдық элементтерден тізбектерді синтездеу әдісі бар, кез келген логикалық функция f(x1,…,xn) үшін оның іске асырушы S тізбегі құрылады, осылайша

L(S) ≤ 3*2 n + n – 5 , демек:

Салдары. L(n) ≤ 3*2 n + n - 5

Пікір.

БИЛЕТ 37

Функционалдық элементтерден тізбектер класында екілік қосқышты іске асыру.

*оқулық*

Анықтама. Қосқыш С n n реті 2n кірісі бар тізбек деп аталады x 1 , x 2 , …, x n, y 1 , y 2 , …, y nжәне n + 1 шығыс z 0 , z 1 , z 2 , …, z nосылайша | z| = |С n (x,ж)| = |x|+|ж|.

Теорема. Базисте (˅, &, ̚ ) элементтер саны 9n – 5 болатын n ретті тізбек қосқышы бар. Дәлелдеу. Қажетті тізбек қосқышты құрастырайық. Ол үшін төрт элементі бар бір жартылай қосушы ұяшықты және әрқайсысында тоғыз элементтен тұратын n–1 қосушы ұяшықтарды алыңыз. Осы бөліктерден қосынды құрастырайық.

Екілік жүйеде жазылған екі сан болсын.

Күрделілігі: L(Bi)=9.

Теорема. L()=9n-5 болатындай n-разрядты екілік қосқышты синтездеу әдісі бар.

БИЛЕТ 38

Мәлімдемелердің логикасы.

Ұсыныс логикасы - белгілі бір формулалар жиынтығы, т.б. арнайы құрастырылған жасанды тілде жазылған күрделі айтылымдар. Пропозициялық логика тіліне мыналар кіреді:

1. айнымалылардың шектеусіз жиыны: A, B, C, ..., A1, B1, C1, ... операторларды білдіретін;

2. логикалық жалғаулықтардың арнайы таңбалары: & - «және», v - «немесе», V - «не, не», ? - «егер, онда», ? - "егер және тек егер", ~ - "бұл дұрыс емес"

3. қарапайым тілде тыныс белгілерінің қызметін атқаратын жақшалар. Жақшаларды азырақ қолдану үшін алдымен терістеу амалы орындалады, одан кейін конъюнкция мен дизъюнкция келеді, содан кейін ғана импликация мен баламалы болады.

Табиғи тілдегі айнымалылар мен жалғаулардан жасалған болжамдық логикалық формулалар сөйлемдерге сәйкес келеді. Мысалы, егер А - «күндізгі уақыт», В - «Қазір жарық», С - «Қазір суық» мәлімдемесі болса, онда формула:

А? B v C немесе барлық жақшалармен: (A? (B v C)) ,

«Егер күндізгі жарық болса, онда ол жарық немесе суық» деген тұжырымды білдіреді. Формула:

B & C? A немесе ((B & C) ? A),

«Егер қазір күн ашық және суық болса, онда күндізгі жарық» деген тұжырымды білдіреді. Формула:

~ In? ~ A немесе ((~ B) ? (~ A)) ,

«Егер қазір жарық екені рас болмаса, күн екені рас емес» деген тұжырымды білдіреді. Айнымалылардың орнына басқа нақты (шын немесе жалған) мәлімдемелерді ауыстыра отырып, біз көрсетілген формулалардың қарапайым тілге басқа аудармаларын аламыз.

Мағыналы сөйлемге сәйкес келмейтін формула қате құрастырылған.

Бұл, атап айтқанда, формулалар:

(A?), (& B), (A v BC), (~ &), т.б.

Ұсыныс логикасының әрбір формуласы ақиқат кестесіне сәйкес келеді, бұл формуладағы нақты мәлімдемелердің қандай алмастыруларында ол шын күрделі мәлімдемені береді, ал қай жерде ол жалған. Мысалы, формула (~ B? ~ A) егер В орнына жалған мәлімдемені, ал А орнына - ақиқат болса ғана жалған мәлімдеме береді.

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

Басқа сөздермен айтқанда, ішкі құрылымыТавтология оған енгізілген айнымалыларды қандай нақты мәлімдемелерді ауыстырсақ та, оның әрқашан шынайы мәлімдемеге айналуына кепілдік береді.