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

Автор работы: Пользователь скрыл имя, 06 Марта 2013 в 16:50, курсовая работа

Описание

Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943) және оның мектебінде дамытылды. Олар математикалық теорияны құруды синтаксистік теория негізіне сүйене отырып құрды.
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу теориясы деп атады.
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны математикалық логика негізін құру мәселесі туындайды. Әртүрлі тәсілмен аксиома жүйесі және басқа формуланы шығару шартын таңдауда әртүрлі синтаксистік логикалық теорияны аламыз. Олардың әрқайсысын логика есептелімі деп атаймыз.

Содержание

КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған формулалары 9
1.9 Негізгі тепе-теңдіктер 10
1.10 Формулаларды тепе-тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру 13
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 ТАРАУ. ТҰЖЫРЫМДАР ЕСЕПТЕЛІМІ 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс 23
Тақырып бойынша тесттер 24
ГЛАВА 3. ПРЕДИКАТТАР ЛОГИКАСЫ 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе-теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары түрінде жазу 31
Тесты по теме 32
VI ТАРАУ. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТЕСТТЕР 39
ӘДЕБИЕТТЕР 43

Работа состоит из  1 файл

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

— 1.18 Мб (Скачать документ)

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 Логикалық байланыстардың толық жүйелері

 

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

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

Лемма 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 формуласы да дәлелденетін формула.  

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

├А1, ├А2, …,├Аn, ├A1→(A2→(A3→(...(An→L) …))) .

├ L

 

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

 

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

├А→В,├В→С .

├А→С

 

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

 

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

├ А →В .

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

                ├(А→В)→├(

)                  (1)

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

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

                            ├А→В                                                             (2)

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

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

 

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

 

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

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

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

                                                      ├                     ├      .

 

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

Информация о работе Алгебралық тұжырымдау туралы түсінік