Дипломдық жұмыс «Пропозициялық логика»


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



бет6/28
Дата11.05.2022
өлшемі2,21 Mb.
#34056
түріДиплом
1   2   3   4   5   6   7   8   9   ...   28
Байланысты:
bestreferat-314444 (2)

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


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

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



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

мұндағы және әр түрлі элементар жалғаулар.

DNF мысалдары:



DNF азайту алгоритмін жоғарыда көрсетілген эквиваленттердің көмегімен сипаттауға болады:

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

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

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

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

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



Элементар дизъюнкциялардың мысалдары:

Кез келген элементар дизъюнкция конъюнктивтік қалыпты форма (CNF) деп аталады және келесідей көрінеді:

мұндағы және әртүрлі элементар дизъюнкциялар.

CNF мысалдары:



CNF-ге келтіру алгоритмін DNF үшін алгоритмде қолданылған қатынастар мен заңдарды пайдалана отырып сипаттауға болады.

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-ӘДІС – Кесте

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




x

ж

z



0

0

0

0

0

0

бір

бір

0

бір

0

0

0

бір

бір

0

бір

0

0

бір

бір

0

бір

бір

бір

бір

0

бір

бір

бір

бір

бір

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

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

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

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

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

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

SDNF:


SKNF-ке қысқарту:

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

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

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

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

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



біз екінші жолды тастаймыз және т.б.

SKNF:


Ескертулер:

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

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


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   28




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет