Логикалық функцияның конъюнктивті қалыпты түрі. Бульдік функциялардың арнайы көрсетілімдері. Кейбір функциялар үшін sknf мысалдары

Анықтама 1.Конъюнктивті мономальды (элементар конъюнктив)айнымалылардың қосындысы немесе олардың терістеулері.

Мысалы, элементар жалғаулық болып табылады.

Анықтама 2.Дизъюнктивтік мономиалды (элементар дизъюнкция)айнымалылардан - бұл айнымалылардың дизъюнкциясы немесе олардың теріске шығарулары.

Мысалы, элементар дизъюнкция болып табылады.

Анықтама 3.Берілген алгебра формуласына эквивалентті және элементар конъюнктивтік мономдардың дизъюнкциясы болып табылатын формула деп аталады. дизъюнктивті қалыпты форма(DNF) осы формуланың.

Мысалы,– DNF.

Анықтама 4.Берілген алгебра формуласына эквивалентті және элементар дизъюнктивтік мономдардың қосындысы болып табылатын формула деп аталады. конъюнктивтік қалыпты форма(CNF) осы формуланың.

Мысалы, – KNF.

Әрбір болжамды алгебра формуласы үшін дизъюнктивті және конъюнктивті қалыпты формалардың жиынын табуға болады.

Қалыпты пішіндерді құру алгоритмі

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

Қос негативтерден арылыңыз.

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

2.6. Perfect disjunctive and perfect conjunctive normal forms

Кез келген логикалық функцияның DNF және CNF түріндегі көптеген көріністері болуы мүмкін. Бұл өкілдіктердің арасында ерекше орынды тамаша DNF (SDNF) және тамаша CNF (SCNF) алады.

Анықтама 1. Керемет дизъюнктивті қалыпты форма(SDNF) әрбір конъюнктивті мономаль жиынның әрбір айнымалыны өзі немесе терістеуін бір рет қамтитын DNF болып табылады.

Құрылымдық тұрғыдан, DNF-ге келтірілген әрбір ұсыныс алгебра формуласы үшін SDNF келесідей анықталуы мүмкін:

Анықтама 2. Керемет дизъюнктивті қалыпты формаҰсынылған алгебра формуласының (SDNF) келесі қасиеттері бар DNF деп аталады:

Анықтама 3. Мінсіз конъюнктивтік қалыпты форма(SCNF) әрбір дизъюнктивтік моном жиынтықтағы әрбір айнымалыны бір рет қамтитын және өзі немесе оның терістеуі пайда болатын CNF.

Құрылымдық тұрғыдан, CNF-ге келтірілген әрбір ұсыныс алгебра формуласы үшін SCNF келесідей анықталуы мүмкін.

Анықтама 4. Мінсіз конъюнктивтік қалыпты формаБерілген ұсыныс алгебра формуласының (SCNF) келесі қасиеттерді қанағаттандыратын CNF деп аталады.

Теорема 1.Бірдей жалған емес айнымалылардың әрбір логикалық функциясы SDNF-де және бірегей түрде ұсынылуы мүмкін.

SDNF табу әдістері

1-ші әдіс

2-ші әдіс

формула 1 мәнін алатын жолдарды таңдаңыз;

конъюнкция дизъюнкциясын құрастырамыз, егер айнымалы 1 мәнімен конъюнктураға қосылса, онда бұл айнымалыны жазамыз, егер 0 мәні болса, онда оны теріске шығару. Біз SDNF аламыз.

2-теорема.Бірдей ақиқат емес айнымалылардың әрбір логикалық функциясы SCNF-де және бірегей түрде ұсынылуы мүмкін.

SCNF табу әдістері

1-ші әдіс– эквивалентті түрлендірулерді қолдану:

2-ші әдіс- ақиқат кестелерін қолдану:

формула 0 мәнін алатын жолдарды таңдаңыз;

егер айнымалы дизъюнкцияға 0 мәнімен қосылса, онда бұл айнымалыны жазамыз, ал егер мәні 1 болса, онда оны теріске шығару шартымен дизъюнкциялардың конъюнкциясын құрастырамыз. Біз SKNF аламыз.

1-мысал. CNF функцияларын құру.

Шешім

Айнымалыларды түрлендіру заңдылықтарын пайдаланып «» жалғаулығын жойайық:

= /де Морган заңдары және қосарлы терістеу/ =

/тарату заңдары/ =

2-мысал. DNF формуласын беріңіз.

Шешім

Логикалық амалдарды және көмегімен өрнектеп көрейік:

= / терістеуді айнымалылар ретінде жіктейік және қосарлы теріс мәндерді азайтайық/ =

= /тарату заңы/ .

3-мысал.Формуланы DNF және SDNF түрінде жазыңыз.

Шешім

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

SDNF құру үшін мына формула үшін ақиқат кестесін құрайық:

Біз кестенің формуласы (соңғы баған) 1 мәнін алатын жолдарды белгілейміз. Әрбір осындай жол үшін осы жолдың айнымалылар жиынында ақиқат болатын формуланы жазамыз:

1-жол: ;

3-жол: ;

5-жол: .

Осы үш формуланың дизъюнкциясы 1, 3, 5-жолдардағы айнымалылар жиынында ғана 1 мәнін қабылдайды, сондықтан қалаған тамаша дизъюнктивтік қалыпты пішін (PDNF) болады:

4-мысал.Формуланы SKNF-ке екі жолмен жеткізіңіз:

а) эквивалентті түрлендірулерді қолдану;

б) ақиқат кестесін қолдану.

Шешімі:

Екінші элементар дизъюнкцияны түрлендірейік:

Формула келесідей көрінеді:

б) мына формула үшін ақиқат кестесін құрастыр:

Біз кестенің формуласы (соңғы баған) 0 мәнін алатын жолдарды белгілейміз. Әрбір осындай жол үшін осы жолдың айнымалылар жиынында ақиқат болатын формуланы жазамыз:

2-жол: ;

6-жол: .

Осы екі формуланың конъюнкциясы тек 2 және 6-жолдардағы айнымалылар жиынында 0 мәнін қабылдайды, сондықтан қалаған тамаша конъюнктивтік қалыпты пішін (PCNF) болады:

Өз бетінше шешуге арналған сұрақтар мен тапсырмалар

1. Эквивалентті түрлендірулерді пайдаланып, формулаларды DNF мәніне келтіріңіз:

2. Эквивалентті түрлендірулерді пайдаланып, формулаларды CNF-ге келтіріңіз:

3. Екінші дистрибутивтік заңның көмегімен DNF-ті CNF-ге түрлендіріңіз:

A) ;

4. Берілген DNF-терді SDNF-ге түрлендіріңіз:

5. Берілген CNF-ті SCNF-ге түрлендіріңіз:

6. Берілген логикалық формулалар үшін SDNF және SCNF екі жолмен құрастырыңыз: эквивалентті түрлендірулерді қолдану және ақиқат кестесін пайдалану.

б) ;

Қарапайым дизъюнкция(ағыл. инклюзивті дизъюнкция) немесе дизъюнкция(Ағылшынша дизъюнкт) - бір немесе бірнеше айнымалылардың дизъюнкциясы немесе олардың теріске шығарулары, әрбір айнымалы бір реттен көп емес орын алады.

Қарапайым дизъюнкция

• толық, егер әрбір айнымалы (немесе оның теріске шығаруы) дәл бір рет пайда болса;
• монотонды, егер ол айнымалылардың терістеулерін қамтымаса.

Конъюнктивтік қалыпты форма, CNF(ағыл. конъюнктивтік қалыпты форма, CNF) логикалық функцияның бірнеше жай сөйлемнен тұратын конъюнктура пішіні болатын қалыпты пішін.

KNF мысалы:$f(x,y) = (x \lor y) \land (y \lor \neg ( z ))$

SKNF

Мінсіз конъюнктивті қалыпты форма, SCNF(Ағылшынша тамаша конъюнктивтік қалыпты пішін, PCNF) - бұл шарттарды қанағаттандыратын CNF:

• онда бірдей қарапайым дизъюнкциялар жоқ
• әрбір қарапайым дизъюнкция аяқталды

SKNF мысалы:$f(x,y,z) = (x \lor \neg ( y ) \lor z) \land (x\lor y \lor \neg ( z ))$

Теорема:Сәйкестікке тең емес кез келген $f(\vec ( x ))$ логикалық функциясы үшін оны анықтайтын SCNF бар.

Дәлелдеу:$\neg ( f ) (\vec x)$ функциясының кері мәні $f(\vec x)$ нөлге тең болатын жиындардағы біріне тең болғандықтан, $\neg ( f ) үшін SDNF (\vec x)$ келесідей жазуға болады:

$\neg ( f ) (\vec x) = \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n) ) )) = 0 ) (x_ ( 1 ) ^ ( \ сигма_ ( 1 ) ) \ сына x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ сына ... \ сына x_ ( n ) ^ ( \ сигма_ ( n ) ) )) $, мұнда $ \sigma_ ( i ) $ $ x_ ( i ) $ кезінде теріске шығарудың бар немесе жоқтығын білдіреді.

Өрнектің сол және оң жақтарының инверсиясын табайық:

$ f(\vec x) = \neg (( \bigvee\limits_ ( f(x^ ( \sigma_ ( 1 ) ) , x^ ( \sigma_ ( 2 ) ) , ... ,x^ ( \sigma_ ( n) ) )) = 0 ) (x_ ( 1 ) ^ ( \ сигма_ ( 1 ) ) \ сына x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ сына ... \ сына x_ ( n ) ^ ( \ сигма_ ( n ) ))) ))) $

Оң жағында алынған өрнекке де Морган ережесін екі рет қолданып, мынаны аламыз: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots ,x ^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n )) ) $

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

Ақиқат кестесін пайдаланып SCNF құру алгоритмі

• Ақиқат кестесінде функцияның мәні $0$ тең болатын айнымалылар жиынын белгілейміз.
• Әрбір белгіленген жиын үшін барлық айнымалылардың дизъюнкциясын келесі ереже бойынша жазамыз: егер қандай да бір айнымалының мәні $0$ болса, онда айнымалының өзін дизъюнкцияға қосамыз, әйтпесе оны теріске шығару.
• Барлық алынған дизъюнкцияларды конъюнкция амалдарымен байланыстырамыз.

Медиана үшін SCNF құру мысалы

1). Ақиқат кестесінде функцияның мәні $0$ тең болатын айнымалылар жиынын белгілейміз.

2). Әрбір белгіленген жиын үшін біз барлық айнымалылардың конъюнкциясын келесі ереже бойынша жазамыз: егер қандай да бір айнымалының мәні $0$ болса, онда айнымалының өзін дизъюнкцияға қосамыз, әйтпесе оны теріске шығару.

3). Барлық алынған дизъюнкцияларды конъюнкция амалдарымен байланыстырамыз.

$ \langle x,y,z \rangle = (x \lor y \lor z) \land (\neg ( x ) \lor y \lor z) \land (x \lor \neg ( y ) \lor z) \land (x \lor y \lor \neg ( z ))$

Кейбір функциялар үшін SKNF мысалдары

Пирс көрсеткісі: $ x \downarrow y = (\neg ( x ) \lor (y )) \land (( x ) \lor \neg (y )) \land (\neg ( x ) \lor \neg ( y ) ) $

Эксклюзивті немесе: $ x \oplus y \oplus z = (\neg ( x ) \lor \neg ( y ) \lor z) \land (\neg ( x ) \lor y \lor \neg ( z )) \land (x \lor \neg ( y ) \lor \neg ( z )) \land (x \lor y \lor z)$

Стандартты негіз. Элементар формулалар әріптер болып табылады. Элементар жалғаулық (дизъюнкция). Дизьюнктивтік (конъюнктивтік) қалыпты форма және мінсіз форма. Теорема: 0-ден (1-ден) басқа кез келген логикалық функция SDNF (SCNF) түрінде ұсынылуы мүмкін. Стандартты базаның толықтығы. Толық негіздердің мысалдары: Жегалкин негізі, Шеффер штрихы, Пирс көрсеткі.

Стандартты негіз логикалық алгебраның үш негізгі амалының жиынтығы болып табылады: қосу (біріктіру), көбейту (қиылысу) және терістеу.

Міне, біз қоңырау шаламыз сөзбе-сөз х айнымалысы немесе оның терісі x және xˆ белгілеңіз. Әртүрлі айнымалылармен анықталған бірнеше литералдардың логикалық қиылысуы, яғни. X = xˆ 1 xˆ 2 түрінің өрнегі. . . xˆ l, деп аталады бастауыш буын . Барлық айнымалылар әртүрлі болу талабы келесімен анықталады. Егер конъюнктураға бірнеше бірдей литерал кірсе, онда конъюнктураның ауыспалылығына, ассоциативтілігіне және идпотенттілігіне байланысты балама формулаға өтіп, тек бір литерал қалдыруға болады (мысалы, x 1 x 1 = x 1). Егер конъюнкция айнымалыны және оның терістеуін қамтыса, онда формула 0 тұрақтысына тең, өйткені x x = 0 және кез келген У формуласы үшін бізде Y x x = 0 болады.

Бірнеше элементар қосылыстардың дизъюнкциясы деп аталады дизъюнктивті қалыпты форма , немесе DNF . Мысалы,

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

Егер берілген DNF әрбір элементар конъюнктурасындағы айнымалылар құрамы бірдей болса, онда DNF деп аталады. тамаша . Берілген мысал мінсіз емес DNF болып табылады. Керісінше, формула

x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

мінсіз формасы бар.

Буль алгебрасында қосу және көбейту симметриялы амалдар болғандықтан және сіз әрқашан қосуды көбейту, ал көбейтуді қосу ретінде түсіндіре аласыз, қос ұғым бар - конъюнктивтік қалыпты форма (KNF ), ол элементар дизъюнкциялардың жалғауы болып табылады және мінсіз жалғаулық форма (SKNF ). Симметриялық жартылай сақиналар үшін екілік принципінен DNF-ке қатысты кез келген мәлімдемеге қосуды (дизъюнкцияны) көбейтумен, көбейтуді (конъюнкцияны) қосумен, тұрақты 0-ді тұрақты 1-мен, тұрақтымен ауыстыру арқылы алынатын CNF-ке қатысты қос мәлімдеме жауап береді. 1 тұрақты 0, реттік қатынас қос (кері) ретімен. Сондықтан, әрі қарай біз тек DNF зерттеуге назар аударамыз.

Теорема 1.4.Тұрақты 0 мәнінен басқа кез келген логикалық функция SDNF ретінде ұсынылуы мүмкін.

◀Х σ деп σ = 1 болса х формуласын, σ = 0 болса х формуласын білдіретініне келістік. f(y 1 , . . . . , y n) функциясы (t) векторында 1 мәнін алсын. 1 , . . , t n ) (мұндай вектор деп аталады құраушы бірлік ). Сонда элементар конъюнкция да осы жиында 1 мәнін қабылдайды, бірақ барлық басқа n өлшемді логикалық векторларда жоғалады. Формуланы қарастырыңыз

онда қосындысы (бірлестігі) берілген функция 1 мәнін алатын аргумент мәндерінің барлық жиындарына (t 1, ..., t n) таралады. Мұндай жиындардың жиыны бос емес екенін ескеріңіз, сондықтан сома кем дегенде бір мүшені қамтиды.

Қарастырылып отырған функция 1 болатын айнымалылардың мәндері үшін Φ формуласы 1 болатынын көру оңай. Бұл Ψ формуласы f функциясын көрсететінін білдіреді.

Қорытынды 1.1.Стандартты негіз аяқталды.

◀ Шынында да, егер функция тұрақты 0 болмаса, оны стандартты негіздегі формула болып табылатын SDNF түрінде де көрсетуге болады. 0 тұрақты мәнін, мысалы, f(x 1, x 2, . . , x n) = x 1 x 1 формуласымен көрсетуге болады.

1.2-мысал.Үш айнымалы m(x 1, x 2, x 3) функциясын қарастырайық (1.4-кесте), деп аталатын мажоритарлық функция ̆. Бұл функция оның аргументтерінің жартысынан көбі 1 мәніне ие болса, 1 мәнін бағалайды. Сондықтан оны жиі дауыс беру функциясы деп атайды. Ол үшін SDNF құрастырайық.

Стандартты негіздің толықтығы функциялардың басқа толық жүйелерін таңдауға мүмкіндік береді. F жиынының толықтығын келесі ойлардан анықтауға болады. Үш стандартты автобус функциясының әрқайсысы F формуласымен ұсынылды делік. Сонда 1.3 теоремасы бойынша F сәйкестігі толық болады.

1.3-мысал.Модуль 2 қосу, көбейту және тұрақты 1 амалдарының жиынтығы деп аталады Жегалкин негізі . Қосу модулі 2 және көбейту – Z2 сақинасының негізгі амалдары, олардың көмегімен құрастырылған өрнектер Z2 сақинасының үстіндегі көпмүшеліктер болып табылады. Бұл жағдайда 1 тұрақтысы бос мүшені жазу үшін қажет. xx = x болғандықтан, онда көпмүшедегі барлық көбейткіштер 1-дәрежеге ие. Сондықтан көпмүшені жазғанда, дәреже ұғымынсыз жасауға болады. Жегалкин негізіндегі формулалардың мысалдары:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Кез келген мұндай формула Жегалкин көпмүшелігі деп аталады. Шындығында, Жегалкин көпмүшесі Z2 сақинасының үстіндегі көпмүше болып табылады.

Стандартты базистің қосу және терістеу амалдарын көрсететін Жегалкин базисі бойынша формулаларды құру қиын емес (екі негізді көбейту жиі кездеседі):

x+y=x⊕y⊕xy, x =x⊕1.

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

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

1.4-мысал.Бір функцияның жиынын қарастырайық – Шеффер штрих*. Бұл жинақ келесідей оңай тексерілетін сәйкестіктер бойынша аяқталды:

x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

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

*Шеффер штрихы екілік операция, бірақ ассоциативті емес. Сондықтан, infix пішінін пайдаланған кезде абай болу керек: нәтиже әрекеттердің ретіне байланысты. Бұл жағдайда жақшаның көмегімен амалдардың орындалу ретін анық көрсету ұсынылады, мысалы, (x |y) жазу | z, x | емес у | z, бірақ екі пішін де эквивалентті.

Логикалық функциялардың қалыпты формалары Буль функциясының Ki 2.7 бірлігінің құрамдас бөліктерінің конъюнктивтік мүшелерінің дизъюнкциясы түрінде берілуі осы функцияның DNF-ның дизъюнктивтік қалыпты түрі деп аталады. Теріспен немесе терістеусіз қабылданған барлық логикалық айнымалылардың дәл біреуін қамтиды, онда функцияны ұсынудың бұл түрі осы функцияның SDNF тамаша дисъюнктивтік қалыпты формасы деп аталады. Көріп отырғаныңыздай, SDNF функциясын құру кезінде функция 1 мәнін қабылдайтын барлық минтермдердің дизъюнкциясын жасау керек.

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

Дәріс 1.xx

Логикалық функциялардың қалыпты формалары

Буль функциясының конъюнктивтік мүшелердің дизъюнкциясы түрінде ұсынылуы (бірлік құраушы)Қ и

, (2.7)

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

Егер DNF-дегі барлық конъюнктивтік терминдер болсаминтермдер , яғни терістеумен немесе терістеусіз алынған барлық логикалық айнымалылардың дәл біреуін қамтитын болса, функцияны ұсынудың бұл түрі деп аталады.мінсіз дизъюнктивті қалыпты форма(SDNF ) бұл функция. Ол SDNF деп аталадытамаша , себебі дизъюнкциядағы әрбір мүше барлық айнымалыларды қамтиды;дизъюнктивтік , себебі формуладағы негізгі операция дизъюнкция болып табылады. Тұжырымдама «қалыпты пішін” берілген функцияны жүзеге асыратын формуланы жазудың бір мәнді тәсілін білдіреді.

Жоғарыда айтылғандарды ескере отырып, 2.1 теоремасынан келесі теорема шығады.

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

3-мысал. Функция берілген кестені алайық f (x 1 , x 2 , x 3 ) (10-кесте).

10-кесте

Формула (2.6) негізінде мынаны аламыз:

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

Буль функциясының дизъюнктивтік мүшелердің конъюнкциясы түрінде ұсынылуы (нөлдік құрамдас) D мен

, (2.8)

шақырды конъюнктивтік қалыпты формаБұл функцияның (CNF).

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

Теорема 3. Кез келген логикалық функция(1-ге ұқсас емес) SKNF-ке тапсырылуы мүмкін, және мұндай өкілдік жалғыз болып табылады.

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

Шеннонның Леммасы . Кез келген логикалық функция f (x 1, x 2, …, x m) бастап m айнымалыларды осылай көрсетуге болады:

. (2.9)

Логикалық функцияны көрсетудің екі формасы да (DNF және CNF) мүмкіндіктері бойынша теориялық жағынан бірдей екенін атап өткен жөн: кез келген логикалық формула DNF-де (бірдей нөлден басқа) және CNF-де (бірдейден басқа) ұсынылуы мүмкін. ). Жағдайға байланысты функцияны сол немесе басқа формада көрсету қысқа болуы мүмкін.

Іс жүзінде DNF жиі қолданылады, өйткені бұл пішін адамға көбірек таныс: бала кезінен ол қосындыларды көбейтуден гөрі өнімді қосуға дағдыланған (соңғы жағдайда ол интуитивті түрде жақшаларды ашып, сол арқылы DNF-ге өтуге ұмтылады).

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

SDNF-тен айырмашылығы, логикалық функцияның ақиқат кестесінде SCNF құрастыру кезінде функция 0 мәнін алатын айнымалылар комбинацияларын қарастырып, сәйкес максимумдардың конъюнкциясын құру керек,бірақ айнымалылар кері инверсиямен қабылдануы керек:

Айта кету керек, функцияның SDNF-ден оның SCNF-ге тікелей немесе керісінше көшу мүмкін емес. Мұндай түрлендірулер әрекеті кезінде нәтижелер қалағанға қарама-қарсы функциялар болып табылады. SDNF және SCNF функцияларына арналған өрнектерді тек оның ақиқат кестесінен тікелей алуға болады.

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

2.3-мысалдың нәтижесін пайдалана отырып, біз мынаны аламыз:

Көріп отырғаныңыздай, жалпы инверсия кезінде логикалық функцияның SCNF алдық, ол 2.4 мысалда алынған функцияға кері функция:

өйткені оның құрамында қарастырылып отырған функцияның SCNF өрнекінде жоқ барлық максимумдар бар.

1. Амалдардың (9-кестені қараңыз) сәйкестік (), қосынды модулі 2 (), импликация () қасиеттерін пайдалана отырып, ЖӘНЕ, НЕМЕСЕ, ЕМЕС (логикалық негізде) операцияларына көшеміз.

2. Терістеу қасиеттерін және Де Морган заңдарын (9-кестені қараңыз) пайдалана отырып, біз терістеу операцияларының тұтас өрнектерге емес, жеке айнымалыларға ғана қолданылатынын қамтамасыз етеміз.

3. ЖӘНЕ және НЕМЕСЕ логикалық операцияларының қасиеттерін пайдалана отырып (9-кестені қараңыз) қалыпты пішінді (DNF немесе CNF) аламыз.

4. Қажет болса, мінсіз пішіндерге (SDNF немесе SKNF) өтіңіз. Мысалы, SCNF алу үшін жиі сипатты пайдалану қажет: .

6-мысал. Логикалық функцияны SKNF түріне түрлендіру

Жоғарыда көрсетілген алгоритмнің қадамдарын ретімен орындай отырып, біз аламыз:

Абсорбция қасиетін пайдаланып, мынаны аламыз:

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

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

Өйткені бірдей логикалық функцияны келесідей көрсетуге болады h жеке формулалар, содан кейін қарапайым пішінді табуР Буль функциясын анықтайтын муль, логикалық функцияны жүзеге асыратын логикалық схеманы жеңілдетедітарту. Минималды пішін lО логикалық функцияқандай да бір негізде біз көңілді суперпозициялардың ең аз санын қамтитын біреуін қарастыра аламызКімге жақшаға рұқсат беретін негіз. Дегенмен, тиімді құру қиынл минималды жақшаны алу үшін осындай минимизациялау алгоритмі r біз.

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

Квин әдісі

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

, (2.10)

содан кейін сіңіру

, (2.11)

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

(2.10) теңдеудің сол жағын бірден қарапайым және айқынырақ түрде азайтуға болатынын ескеріңіз:

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

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

Карно картасы әдісі

Карно карталары (кестелер) әдісі логикалық функцияларды минимизациялаудың неғұрлым көрнекі, аз еңбекті қажет ететін және сенімді әдісі болып табылады, бірақ оны қолдану іс жүзінде 3-4 айнымалы, ең көбі 5-6 айнымалы функциялармен шектеледі.

Карно картасы бұл логикалық функциялардың ең аз DNF-терін графикалық визуалды түрде оңай табуға мүмкіндік беретін логикалық функцияның ақиқат кестесін көрсетудің екі өлшемді кестелік түрі. Кестенің әрбір ұяшығы минимизацияланатын функцияның SDNF минтермімен және кестенің кез келген симметрия осьтері қандай да бір айнымалыға қатысты өзара кері аймақтарға сәйкес келетіндей байланысты. Кестедегі ұяшықтардың бұл орналасуы SDNF-нің жабысу шарттарын анықтауды жеңілдетеді (тек бір айнымалының инверсия белгісімен ерекшеленеді): олар кестеде симметриялы орналасқан.

Ақиқат кестелері және екі жолақтың ЖӘНЕ және НЕМЕСЕ функцияларына арналған Карно карталары e Айнымалылар суретте көрсетілген. 8. Карточканың әрбір ұяшығына мән жазыладыА Осы ұяшыққа сәйкес келетін аргумент мәндерінің жиынындағы функцияның мәні N Жолдас

A) ЖӘНЕ б) НЕМЕСЕ

Күріш. 8. Екі айнымалы функцияларға арналған Карно карталарының мысалы

Карно картасында And функциясы үшін бір ғана 1 бар, сондықтан оны ештеңеге жабыстыру мүмкін емес. Минималды функцияның өрнегі тек осы 1-ге сәйкес терминді қамтиды:

f = x y .

НЕМЕСЕ функциясына арналған Карно картасында қазірдің өзінде үш 1 бар және сіз терминге 1 сәйкес келетін екі жабысатын жұп жасай аласыз. xy , екі рет қолданылады. Минималды функцияның өрнегінде бір-біріне жабыстырылған жұптардың шарттарын жазып, оларда осы жұп үшін өзгермейтін барлық айнымалыларды қалдырып, мәнін өзгертетін айнымалыларды алып тастау керек. Көлденең желімдеу үшін біз аламыз x , және тік үшінж , нәтижесінде өрнекті аламыз

f = x + y.

Суретте. 9 үш айнымалының екі функциясының ақиқат кестелерін көрсетеді (А ) және олардың Карно карталары ( b және c). f 2 функциясы біріншіден айырмашылығы, ол айнымалылардың үш жиынында анықталмаған (кестеде бұл сызықшамен көрсетілген).

Минималды DNF функциясын анықтау кезінде келесі ережелер қолданылады. 1 бар барлық ұяшықтар деп аталатын жабық тікбұрышты аймақтарға біріктірілген k-текшелер, мұндағы k = log 2 K, K тікбұрышты аудандағы 1 шама. Бұл жағдайда әрбір аймақ ұяшықтардың саны 2 болатын тіктөртбұрыш болуы керек k, мұндағы k = 0, 1, 2, 3, …. k = үшін 1 тіктөртбұрыш деп аталадыбіреуі текше және оның құрамында 2 1 = 2 бірлік бар; k = үшін 2 тіктөртбұрышта 2 бар 2 = 4 бірлік және деп аталадыекі текше; k = 2 3-тің 3 облысы үшін = 8 бірлік деп аталадыүш текше ; т.б. тіктөртбұрыштарға біріктірілмейтін бірліктерді шақыруға боладынөлдік текшелер , құрамында бір ғана бірлік бар (2 0 = 1). Көріп отырғанымыздай, біркелкік аймақтар шаршы пішінді болуы мүмкін (бірақ міндетті емес), ал егер тақ болсак тек төртбұрыштар.

Күріш. 9. Үш айнымалы функцияларға арналған Карно карталарының мысалы

Бұл аймақтар қабаттасуы мүмкін, яғни бір ұяшықтар әртүрлі аймақтарға енуі мүмкін. Сонда минималды DNF функциясы сәйкес келетін барлық конъюнктивтік мүшелердің дизъюнкциясы ретінде жазылады k - текшелер.

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

Осылайша, карта ұяшықтарын жабық аймақтармен жабу кезінде аумақтар санының минималды болуын және әрбір аймақта мүмкіндігінше көп ұяшықтардың болуын қамтамасыз етуге тырысу керек, өйткені бұл жағдайда минималды DNF-тегі терминдер саны минималды болады және сәйкес конъюнктурадағы аргументтер саны ең аз болады.

Суреттегі Карнау картасына сәйкес функция үшін. 9,б табамыз

өйткені жоғарғы жабық аймақ үшін айнымалылар x 1 және x 2 төменгі үшін инверсиясыз мәндері бар x 1 инверсиямен байланысты жәнех 3 инверсиясыз.

Суреттегі картадағы анықталмаған мәндер. 9,В оны нөлге немесе біреуге ауыстыру арқылы қосымша анықтауға болады. Бұл функция үшін анықталмаған мәндердің екеуін де 1-ге ауыстыру тиімдірек екені анық. Бұл жағдайда 2-текшелердің әртүрлі түрлері болып табылатын екі аймақ пайда болады. Сонда минималды DNF функциясының өрнегі келесідей болады:

Жабық аумақтарды салу кезінде Карно картасын цилиндрге көлденеңінен де, тігінен де бүктеуге рұқсат етіледі.Р қарама-қарсы беттердің бірігуі бар тік осьтерР сіз, яғни Карно симметрия картасының жиектерінде орналасқан бірліктер h бірақ біріктіруге де болады.

Карно карталарын әртүрлі тәсілдермен салуға болады (10-сурет).

а б

Күріш. 10. Карно карталарын бейнелеудің әртүрлі тәсілдері
3 айнымалы функция үшін

Бірақ 2-4 айнымалы функциялар үшін Карно карталарының ең қолайлы нұсқалары суретте көрсетілген. 11 кесте, себебі олар әр ұяшық үшін көрсетіледіА Бізде тікелей немесе кері түрдегі барлық айнымалылар бар.

а б

Күріш. он бір. Carnaugh карталарының ең ыңғайлы кескіні
функциялар үшін 3 ( a) және 4 (b) айнымалылар

5 және 6 айнымалы функциялар үшін суретте көрсетілген әдіс. 10, V .

Күріш. 12. 5 айнымалы функцияға арналған Карно картасының кескіні

Күріш. 13. 6 айнымалы функцияға арналған Карно картасының кескіні

Мысал. CNF формулаларын табыңыз

~ ~

SDNF-тің тамаша дизъюнктивті қалыпты түрін келесі алгоритм арқылы құруға болады:

1. = 1. DNF алгоритмі

2. = 2. DNF алгоритмі

3. = 3. DNF алгоритмі

4. = 4. DNF алгоритмі

5. Бірдей жалған терминдерді, яғни пішін шарттарын алып тастаңыз

6. Қалған шарттарды жетіспейтін айнымалылармен аяқтаңыз

7. 4-тармақты қайталаңыз.

Мысал. SDNF формулаларын табыңыз.

~

SCNF құру үшін келесі схеманы қолдануға болады:

Мысал. SDNF формулаларын табыңыз.

~

Белгілі (2.11, 2.12 теоремалар) SDNF және SCNF формула бойынша біркелкі анықталған, сондықтан оларды формуланың ақиқат кестесін пайдаланып тұрғызуға болады.

Ақиқат кестесіне сәйкес SDNF және SCNF құру схемасы формула үшін төменде келтірілген. ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Жаттығу.

2.2.1 Төменде логикалық өрнектер берілген. Бульдің логикалық заңдарын қолданып, нұсқаңыздың өрнектерін барынша жеңілдетіңіз. Содан кейін оңайлатылған өрнекті түпнұсқамен салыстыру үшін ақиқат кестелерін пайдаланыңыз.

2.2.2. f 1 және f 2 эквиваленттілігі туралы мәселені SDNF-ге келтіру арқылы нақтылаңыз (1-кесте).

2.2.3. Жалпыланған және логикалық принципті пайдаланып f 3 үшін қос функцияны табыңыз (1-кесте). Нәтижелерді салыстырыңыз.

№	f 1	f 2	f 3

2.3. Бақылау сұрақтары.

2.3.1. Мәлімдемені анықтаңыз.

2.3.2. Мәлімдемедегі негізгі операцияларды көрсетіңіз.

2.3.3. Ақиқат кестесі дегеніміз не?

2.3.4. Келесі формулалар үшін ақиқат кестелерін құрыңыз:

~ ~ ~ ;

2.3.5. Амалдарды орындау тәртібі туралы конвенцияларды ескере отырып, формулалардағы «қосымша» жақшаларды және «» белгісін алып тастаңыз:

;

2.3.6. Эквивалентті түрлендірулерді қолданып, формулалардың бірдей ақиқаттығын дәлелдеңдер:

2.3.7. Қосарлы формулаларды табыңыз:

)

2.3.8. мінсіз DNF (SDNF) пішініне келесі формулаларды азайтыңыз:

~

2.3.9. мінсіз CNF (SCNF) пішініне келесі формулаларды азайтыңыз:

~

Зертханалық жұмыс No3

Тақырыбы:«Бульдік функцияларды минимизациялау. Логика»

Мақсат:Логикалық функцияларды минимизациялау әдістерімен жұмыс істеудің практикалық дағдыларын меңгеру.

3.1. Теориялық ақпарат.

Минималды формалар

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

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

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

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

Мысалы, функция идеалды қалыпты дизъюнктивті түрде берілсін:

Терминдерді топтап, жапсыру операциясын қолданып, бізде .

Басқа топтастыру әдісімен біз мыналарды аламыз:

Тұйық пішіндердің екеуі де аз емес. Минималды пішінді алу үшін бастапқы формуладағы бір терминді қайталауды болжау керек (бұл әрқашан жасалуы мүмкін, өйткені ). Бірінші жағдайда мұндай мүше болуы мүмкін. Содан кейін. Терминді қосу арқылы біз мынаны аламыз: . Барлық мүмкін нұсқаларды қарап шыққаннан кейін, сіз соңғы екі пішіннің минималды екеніне көз жеткізе аласыз.

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

Көпөлшемді куб

-өлшемді текшенің әрбір шыңы бірлік құрамдас бөлігімен байланыстырылуы мүмкін. Демек, белгіленген төбелердің ішкі жиыны айнымалылардың логикалық функциясының -өлшемді текшесінде тамаша дизъюнктивті қалыпты пішіндегі салыстыру болып табылады. Суретте. 3.1 3.7-тармақтағы функция үшін осындай салыстыруды көрсетеді.

3.1-сурет Үш өлшемді текшеде SDNF-де ұсынылған функцияны көрсету

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

(-1) дәрежелі минитерминді дәреженің екі минитерминін (бірлікті құраушы) желімдеу нәтижесі ретінде қарастыруға болады, яғни. , Өлшемді текшеде бұл төбелерді жиекпен байланыстыратын координат мәндерінде ғана ерекшеленетін екі төбені ауыстыруға сәйкес келеді (жиек оған түскен төбелерді жабады деп айтылады). Осылайша, (-1)-ші ретті минитермдер -өлшемді текшенің жиектеріне сәйкес келеді. Сол сияқты, (-2)-ші ретті минитерминдердің сәйкестігі - өлшемді текшенің беттерімен белгіленеді, олардың әрқайсысы төрт шыңды (және төрт жиекті) қамтиды.

Өлшемдерімен сипатталатын -өлшемді текше элементтері -текшелер деп аталады. Сонымен, төбелер 0-куб, жиектер 1-куб, беттер 2-куб, т.б. Жоғарыда келтірілген пайымдауды жалпылай отырып, айнымалылар функциясы үшін дизъюнктивті қалыпты формадағы ()-ші дәрежелі минимерді -кубпен берілген деп болжауға болады, ал әрбір -текше оның өлшемімен байланысты барлық төменгі өлшемді текшелерді қамтиды. шыңдары. Мысал ретінде суретте. 3.2 үш айнымалының функциясын көрсетеді. Мұнда минитерминдер 1-кубқа () сәйкес келеді, ал минитерм 2-кубпен () берілген.

Сурет 3.2 Функцияны қамту

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

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

Күріш. 3.3 Функцияларды қамту.

сол – ; оң жақта –

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

Күріш. 3.4 Функция дисплейі төрт өлшемді текшеде

Карно карталары

Логикалық функцияларды графикалық түрде көрсетудің басқа әдісі қолданылады Карно карталары, олар арнайы ұйымдастырылған корреспонденциялық кестелер. Кестенің бағандары мен жолдары екі айнымалыдан аспайтын мәндердің барлық мүмкін жиындарына сәйкес келеді және бұл жиындар әрбір келесі айнымалылардың тек біреуінің мәні бойынша алдыңғысынан ерекшеленетіндей ретпен орналастырылған. . Осының арқасында кестенің көршілес ұяшықтары көлденең және тігінен тек бір айнымалының мәнімен ерекшеленеді. Кестенің шетінде орналасқан ұяшықтар да іргелес болып саналады және бұл қасиетке ие. Суретте. 3.5-суретте екі, үш, төрт айнымалыға арналған Карно карталары көрсетілген.

Күріш. 3.5 Екі, үш және төрт айнымалыларға арналған Карно карталары

Кәдімгі ақиқат кестелеріндегідей, функция 1 мәнін қабылдайтын жиындардың ұяшықтары бірліктермен толтырылады (нөлдер әдетте сәйкес келмейді, олар бос ұяшықтарға сәйкес келеді). Мысалы, суретте. 3.6, Афункциясы үшін Карнау картасын көрсетеді, оның дисплейі төрт өлшемді текшеде суретте берілген. 3.4. Заттарды жеңілдету үшін айнымалыға арналған 1 мәндеріне сәйкес келетін жолдар мен бағандар сол айнымалыны көрсететін жақшамен бөлектеледі.

Күріш. 3.6 Карно картасында төрт айнымалы функцияны көрсету

(а) және оның ең аз қамтылуы (b)

Функцияларды салыстыру арасында n-өлшемді текше және Карно картасы бір-біріне сәйкес келеді. Карно картасында с-текше қатарға, бағанға, шаршыға немесе тіктөртбұрышқа (картаның қарама-қарсы шеттерінің жақындығын ескере отырып) орналастырылған 2 көрші ұяшықтар жиынтығына сәйкес келеді. Сондықтан жоғарыда көрсетілген барлық ережелер (тармақты қараңыз. көпөлшемді куб), Karnaugh карталары үшін жарамды. Сонымен, суретте. 3.6, бминималды дизъюнктивтік формаға сәйкес карта бірліктерінің қамтылуын көрсетеді қарастырылып отырған функция.

Карнау картасынан минитерминдерді оқу қарапайым ережеге бағынады. Жасушалардың түзілуі с-текше, министр бер (n–s)-оларды қамтитын разряд (n–s)сол мәндерді сақтайтын айнымалылар с-cube, мұндағы 1 мәні айнымалылардың өздеріне, ал 0 мәні олардың терістеулеріне сәйкес келеді. Өз мәндерін сақтамайтын айнымалылар с-куб, минимумда жоқ. Оқудың әртүрлі тәсілдері функцияның дисъюнктивтік қалыпты формада әртүрлі бейнеленуіне әкеледі (ең оң жақтағы минималды) (3.7-сурет).

Карно карталарын пайдалану картаға түсірумен салыстырғанда қарапайым конструкцияларды қажет етеді n-өлшемді текше, әсіресе төрт айнымалы жағдайда. Бес айнымалы функцияларды көрсету үшін төрт айнымалыға арналған екі Карно картасы, ал алты айнымалы функция үшін осындай төрт карта пайдаланылады. Айнымалылар санының одан әрі көбеюімен Карно карталары іс жүзінде жарамсыз болып қалады.

Әдебиетте танымал Veitch карталарыОлар айнымалы мәндер жиынының әртүрлі ретімен ғана ерекшеленеді және Карно карталарымен бірдей қасиеттерге ие.

Текшелер кешені

Айнымалылардың үлкен саны бар графикалық әдістердің сәйкессіздігі логикалық функцияларды көрсету үшін әртүрлі аналитикалық әдістермен өтеледі. Осындай өкілдіктердің бірі текшелер кешені, көпөлшемді логикалық кеңістік терминологиясын арнайы әзірленген символизммен үйлестіре пайдалану.

). Бірліктің құрамдас бөліктеріне сәйкес келетін 0-текшелер функция бірлікке тең болатын айнымалы мәндер жиынымен көрсетіледі. Жазбада анық

Күріш. 3.8 Үш айнымалы функцияның текшелер кешені ( А) және оның символдық көрінісі ( б)

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

,

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

Екі логикалық функция үшін ажырату операциясы олардың текше кешендерінің бірігуіне, ал конъюнкция операциясы олардың текше кешендерінің қиылысына сәйкес келеді. Функцияны теріске шығару текшелер кешенінің толықтауышына сәйкес келеді, яғни және функция 0 мәнін алатын барлық шыңдармен анықталады. Осылайша, алгебрасы арасында бір-біріне сәйкестік (изоморфизм) бар. Логикалық функциялар және текшелер кешендерін көрсететін логикалық жиындар.

Функцияны текшелер кешендері түрінде көрсету визуалдылығы азырақ, бірақ оның маңызды артықшылығы – айнымалылар санына шектеулер жойылады және компьютерлерді пайдалану кезінде ақпаратты кодтау жеңілдетіледі.

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

Мәселенің тұжырымы.Логикалық негізде тізбекті минимизациялау минималды қамтуға сәйкес келетін минималды дизъюнктивті пішінді табуға келеді. Қалыпты түрдегі хаттардың жалпы саны қамту құнымен көрсетіледі , мұндағы n айнымалының берілген функциясын жабуды құрайтын текшелер саны. Ең төменгі қамту оның бағасының ең төменгі мәнімен сипатталады.

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

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

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

Берілген анықтамалар суретте көрсетілген. 3.9, мұнда қысқартылған қамту (3.9а-суретті қараңыз, ) және минималды қамту (3.9б-сурет) және (3.9, б-суретті қараңыз) төмендегідей көрсетіледі.