Алгебралық тұжырымдау туралы түсінік

_{1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру}

 

Есеп. А(x,y,z) формуласының ақиқаттық кестесі берілсін.

 

х	у	z	А(x,y,z)
1	1	1	1
1	1	0	0
1	0	1	0
0	1	1	1
1	0	0	1
0	1	0	0
0	0	1	0
0	0	0	0

 

 

 

 

 

 

 

 

 

 

 

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

Бірінші жолдағы мәндерде  xyz ақиқат,

Төртінші жолдағы мәндерде Øxyz ақиқат,

Бесінші жолдағы мәндерде xØyØz ақиқат.

Енді, осы қарапайым конъюнкциялардан жетілдірілген нормал дизъюнктивті форма құрайық:

хyz Ú Øxyz Ú xØyØz.

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

А(x,y,z)= хyz Ú Øxyz Ú xØyØz.

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

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

Мәселен, жоғарыда қарастырылған  формуланың ЖКНФ келесі түрде болады:

А(x,y,z)= (ØхÚØyÚz) (ØxÚyÚØz)(xÚØyÚz) (xÚyÚØz) (xÚyÚz).

_{1.14 Логикалық байланыстардың толық жүйелері}

 

D₁, D₂, …, D_n логикалық амалдардың символдары болсын. Егер тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар D₁, D₂, …, D_n  амалдарының көмегімен құрылған формула бар болса, онда <D₁, D₂, …, D_n> жүйе толық деп аталады.

Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және КНФ болғандықтан, <Ø, Ù, Ú > – толық жүйе екендігі түсінікті.

Лемма 9.1 Логикалық байланыстардың келесі жиындары:

<Ø, Ù, Ú, ® >, <Ø, Ù >, <Ø, Ú >, <Ø, ®>

толық жүйе құрайды.

Лемма 9.2 <Ù, Ú, ® >, <Ø > жиындары логикалық амалдардың толық жүйесін құрмайды.

Тақырып бойынша  тесттер

 

1. Келесі импликациялардың қайсысы  жалған?

1) егер 2*2=4, онда 2>3;

2) егер 2*2=4, онда 2<3;

3) егер 2*2=5, онда 2<3;

4) егер 2*2=5, онда 2>3;

 

2. Келесі сөйлемдердің қайсысы тұжырым болмайды?

1) «Информатика» кафедрасының студенті.

2) Париж – Испания астанасы.

3) 3 саны А жиынына тиісті.

 

3. Айнымалылардың қайсылары бір бірінің терістеулері болады:

1) 2>3, 2£3;

2) 6<9, 6>9;

3) f функциясы жұп, f функциясы тақ;

4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі.

 

4. A®B тұжырымы ақиқат болсын. (ØAÙB ) ® ( ØAÚB ) тұжырымы қандай логикалық мәнге ие болады?

1) ақиқат

2) жалған

 

5. Ø (ØPÚQ ) ® ((PÚQ ) ®P) формуланы ықшамдаңыз:

1) 1

2) 0

3) Р

4) Q

 

_{6. Келесі өрнектердің қайсысы формула болады?:}

_{1) ((PÙ( ØQ®R )) Ú ((ØP~ R ) ØQ ))}

_{2) ((PÚQ) R) ®ØS}

 

_{7. КНФ-ті табыңыз: Ø(xÚz )Ù(x®y)}

_{1) Øx(yÚØz)}

_{2) (xÚy)(yÚz)}

_{3) yÚz}

 

_{8. 0 мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті бірмүшені құрыңыз}:

1) xÚy

2) ØxÚy

3) xÚØy

4) Øx ÚØy

 

_{9. формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз:}

1)   Ø(ØxÙyÙØz )

2)  xÙy

 

10. ДНФті табыңыз: (x~y) ÙØ ( z®T )

1) (xÙyÙzÙØT) Ú (ØxÙØyÙzÙØT);

2) x ÙyÚz

 

2 тарау. тұжырымдар есептелімі

2.1  Тұжырымдар есептелімі формуласының ұғымы

 

Тұжырымдар есептелімі бұл интерпретациясы тұжырымдар алгебрасы болатын аксиоматикалық логикалық жүйе.

Әрбір есептелімнің сипаттамасына бұл есептелімі символдарының, формулаларының сипаттамасы, дәлелденетін формулалардың анықтамасы енеді.

Тұжырымдар  есептелімінің алфавиті үш түрлі символдардан тұрады:

1. Бұл символдарды айнымалы тұжырымдар деп атаймыз.

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

3. Жақшалар деп аталатын символдар: (,   ).

Тұжырымдар есептелімінде  басқа символдар болмайды.

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

Тұжырымдар  есептелімі формуласының анықтамасы

1. Кез келген айнымалы формула б олады.

2. Егер А және В – формулалар болса, онда сөздер де формулалар.

3. Ешқандай басқа символдардың қатары формула болмайды.

Айнымалы тұжырымдарды қарапайым формулалар деп атаймыз.

Тұжырымдар есептелімі формуласына мысал келтірейік.

 айнымалы тұжырымдар анықтаманың 1-ші бөлімі бойынша формулалар болады. Бірақ, онда сөздер де анықтаманың 2-ші бөлімі бойынша формулалар бола алады. Сол себепке байланысты сөздер де формула бола алады.

Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі енгізіледі.

1. Қарапайым формуланың ішформуласы оның өзі болады.

2. Егер формула көрінісінде болса, онда оның ішформулалары формуланың өзі, А формуласы және А формуланың барлық ішформулалары болады.

3. Егер формула (А*В) (мұнда * – үш символдардың бірі деп түсінеміз) көрінісінде болса, онда оның ішформулалары формуланың өзі, А, В формулалары және А мен В формулалардың барлық ішформулалары болады.

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

2.2. Дәлелденетін формула ұғымы

 

Тұжырымдар есептелімінің  құруда келесі кезең дәлелденетін (шығарылатын) формулалардың класын бөліктеу болады.

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

          

_{2.3 Тұжырымдар есептелімінің аксиомалар жүйесі}

 

Тұжырымдар есептелімінің  аксиомалар жүйесі төрт топқа бөлінетін 11 аксиомадан тұрады.

Аксималардың бірінші  тобы (құрамыларыны тек импликация енеді).

: .     

: .

Аксималардың екінші тобы ( импликацияға конъюнкция қосылды):

:    

: .  

: .

Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды):

:    

:          

: .

Аксималардың төртінші тобы (импликацияға терістеу қосылды):

:

:                

:

_{2.4 Шығару ережелері}

 

1. Алмастыру ережесі (АЕ).

Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін) формула, х – айнымалы, В – тұжырымдар есептелімінің кез келген формуласы болса, онда А формуладағы х айнымалыны В формулаға алмастыру нәтижесінде алынған формула да шығарылатын (дәлелденетін) болады.

А формуладағы х айнымалыны В формулаға алмастыру амалы алмастыру деп аталады да келесі түрде жазылады:

 немесе .

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

├А____  .

├

Бұл жазылу былай оқылады: “Егер А формуласы шығарылатын (дәлелденетін) болса, онда формуласы да шығарылатын (дәлелденетін) болады.

2 Қорытындылау ережесі (ҚЕ).

Егер А және А→В формулалары тұжырымдар есептелімінде шығарылатын (дәлелденетін) болса, онда В формуласы да шығарылатын (дәлелденетін) болады. Бұл ереженің схематикалық жазылуы мынадай болады:

├А;├А→В                            (Modus ponens)

                                      ├В

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

_{2.5  Дәлелденетін формуланың анықтамасы}

 

а) Әрбір аксиома дәлелденетін формула болады.

б) Кез келген В формуласынан х айнымалының орнына алмастыруды қолдану нәтижесінде алынған формула – дәлелденетін формула.

в) А және дәлелденетін формулаларға   қорытындылау ережесін қолдану нәтижесінде алынған В формуласы – дәлелденетін формула болады.

г) Тұжырымдар есептелімінің ешқандай басқа формуласы дәледенетін болып саналмайды.

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

_{2.6 Туынды  шығару ережелері}

 

 

Күрделі алмастыру  ережесі (КАЕ)

 

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

А – дәлелденетін формула, – айнымалылар, ал – тұжырымдар есептелімінің кез келген формулалары болсын. Онда А формулада айнымалыларын формулаларға алмастыру нәтижесі дәлелденетін формула болады.

КАЕ схематикалық түрде  былай жазылады:

├А______

├

Күрделі қорытындылау ережесі

 

Қорытындылау ережесін де жалпылау мүмкін. Жалпылау нәтижесінде алынған туынды ереже

түрдегі формулаларға қолданылады  да былай анықталады:

егер      және   формулалар дәлелденетін болса, онда L формуласы да дәлелденетін формула.  

Күрделі қорытындылау ережесі былай жазылады:

├А₁, ├А₂, …,├А_n, ├A₁→(A₂→(A₃→(...(A_n→L) …))) .

├ L

 

Силлогизм ережесі

 

Егер А→В және В→С формулалары дәлелденетін болса, онда А→С формуласы да дәлелденеді, яғни

├А→В,├В→С .

├А→С

 

Контрапозиция ережесі

 

Егер А→В формуласы дәлелденетін болса, онда формула да дәлелденеді, яғни

├ А →В .

├

Бұл ереженің мысалында  тұжырымдар есептелімінде мұндай тұжырымдардың дәлелдеу жолын көрсетеміз. алмастыруын орындап,

                ├(А→В)→├(

)                  (1)

дәлелденетін формуланы  аламыз.

Ал шарт бойынша 

                            ├А→В                                                             (2)

– дәлелденетін формула.     

Онда (2) және (1) формулаларынан қорытындылау ережесі бойынша ├ .

 

Екі еселі терістеу ережесі

 

а) Егер формуласы дәлелденетін болса, онда формуласы да дәлелденетін.

б) Егер формуласы дәлелденетін болса, онда формуласы да дәлелденетін.

Схематикалық жазылулары:      ├ А →     және      ├ →В

                                                      ├                     ├      .

 

2.7 Формулаларды гипотезалардан қорытып шығару