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

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

Элементар жалғауларға мысалдар

DNF мысалдары:

1. Қос терістеу заңын және Де Морган заңдарын қолданып, барлық терістеулер айнымалыларға «төмендейді»;

2. Жақшалар бөлу заңы бойынша ашылады;

3. Жұтылу, қарама-қайшылық және алынып тасталған орта заңдарының көмегімен қажетсіз жалғаулар мен ауыспалы қайталаулар жойылады;

4. Логикалық тұрақтыларды қамтитын қатынастардың көмегімен қалған тұрақтылар жойылады.

Элементар дизъюнкция - әр айнымалы ең көп бір рет болатын айнымалылар немесе олардың терістеу дизъюнкциясы.

CNF мысалдары:

1. Қос терістеу заңын және Де Морган заңдарын қолданып, барлық терістеулер айнымалыларға «төмендейді»;

2. Жақшалар бөлу заңы бойынша ашылады;

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

4. Логикалық тұрақтыларды қамтитын қатынастардың көмегімен қалған тұрақтылар жойылады.

тамаша дизъюнктивті қалыпты түрі DNF деп аталады, онда: 1) барлық терминдер фактор ретінде барлық айнымалыларды қамтиды - теріске шығарусыз немесе терістеумен, бірақ бірге емес. 2) терминдер мен факторлардың қайталануы болмайды.

Болжамдық алгебра формуласының (SKNF) тамаша конъюнктивтік қалыпты түрі CNF деп аталады, онда: 1) әрбір фактор терістеусіз немесе терістеусіз, бірақ бірге емес, әрбір айнымалының қосындысын қамтиды; 2) факторлар мен терминдердің қайталануы болмайды.

Ескерту: «Термин» және «фактор» сөздерін бір-бірінің орнына қою арқылы бір анықтаманың екіншісінен шығатынына назар аударайық.

Мысалдар
— Екі айнымалының кейбір формуласының SDNF

- Үш айнымалының SKNF функциялары
SDNF (SKNF) үшін тек кейбір толық конъюнкциялар (дизъюнкциялар) рұқсат етіледі: құрамында - қайталаусыз - осы функцияның барлық айнымалылары - терістеулері бар немесе жоқ.

Кемелді қалыпты формаларға келтірудің екі әдісін сипаттайық.

1-ӘДІС – АНАЛИТИКАЛЫҚ

SDNF-ге азайту алгоритмі:

1. Эквивалентті түрлендірулер көмегімен DNF-ге әкелу;

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

3. Ашық жақшалар – бірінші үлестіру заңы бойынша;

4. Терминдердің қайталануын жою.

Мысалы:

SKNF-ге келтіру алгоритмі:

1. CNF формуласы;

2. Нөлдер қосылады, әрбір жетіспейтін айнымалының терістеуімен жалғаулары ретінде көрсетіледі;

3. Екінші дистрибутивтік заңның көмегімен бұл факторлар бірінші дәрежелі, яғни өнімі жоқ қосындыларға келтіріледі;

4. Факторлардың қайталануын жою.
Мысалы:

2-ӘДІС – Кесте

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

SDNF-ге азайту алгоритмі:

1. Ақиқат кестесін құрастырамыз;

2. Формула 1 мәнін алатын кестенің жолдарын ғана қарастырамыз;

3. Әрбір осындай жол барлық аргументтердің конъюнкциясына сәйкес келеді (қайталаусыз). 0 мәнін қабылдайтын аргумент оны терістеумен, 1 мәні терістеусіз енгізеді;

4. Барлық шыққан жалғаулықтардың дизъюнкциясын жасаймыз.

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

SDNF:

1. Ақиқат кестесін құрастырамыз;

2. Функция 0 мәнін алатын кестенің жолын ғана қарастырамыз;

3. Әрбір осындай жол барлық айнымалылардың дизъюнкциясына сәйкес келеді (қайталаусыз). 0 мәнін қабылдайтын аргумент терістеусіз, 1 мәні терістеумен қабылданады;

4. Салынған дизъюнкциялардан одағай құрыңыз.

Біздің мысалда кестенің бірінші жолы дизъюнкцияға сәйкес келеді

SKNF:

1. 
   Егер біз SDNF және SKNF деген екі тамаша пішіннен аз әріптерді қамтитынға артықшылық беруге келісетін болсақ, онда SDNF ақиқат кестесі функциясының мәндерінің бағанында біреуден аз болса, қолайлы болады; SKNF - егер осы бағанда нөлден аз болса.
   
2. 
   Кәдімгі мектеп алгебрасында функцияның кестелік анықтамасынан аналитикалық анықтамаға өтудің жалпы әдісі жоқ екенін білеміз. Ұсыныстар алгебрасында, көріп отырғанымыздай, мұндай әдіс бар /5,7/.