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

Автор работы: Пользователь скрыл имя, 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 Мб (Скачать документ)

 

Формулалардың Н={А12,…,Аn} ақырлы жиынын қарастырамыз.

Н жиынынан шығарылатын формула анықтамасы.

1) AiÎH формуласы Н-тан шығарылатын формула деп аталады.

2) Әрбір дәлелденетін формула Н-тан шығарылатын болады.

3) Егер С және С→В формулалар Н-тан шығарылатын болса, онда В формуласы да Н-тан шығарылатын болады.

Егер кейбір В формуласы формулалардың Н жиынынан шығарылатын болса, онда бұл былай жазылады: Н├В.

Н жиыны бос немесе тек дәлелденетін формулалардан тұратын жағдайда Н жиынынан шығарылатын формулалардың класы дәлелденетін формулалардың класымен сәйкес келеді.

Егер де Н жиынында кем дегенде бір дәлелденбейтін формула болса, онда Н-тан шығарылатын формулардың класы дәлелденетін формулалар класынан кең болады.

Мысал.

Формулалардың Н={А, В} жиынынан формуласы шығатынын дәлелдеу керек.

AÎH және BÎH болғандықтан, дәлелденетін формуланың анықтамасы бойынша

 Н├А,                                   (1) 

 Н├В.               (2)

және аксиомаларды алып, және алмастыруларды орындаймыз.

Нәтижесінде Н-тан шығарылатын дәлелденетін формулаларды аламыз, яғни

Н├(А→А)→((А→В)→(А )),                   (3)

Н├В→(А→В),             (4)

А→А формуласы дәлелденетін, онда Н├А→А.                (5)

(5) және (3) формулалардан қорытындылау ережесі бойынша                                                          Н├(А→В)→(А ))            (6)

алынады.

(2) және (4) формулалардан қорытындылау ережесі бойынша: 

           Н├А→В .              (7)

(7) және (6) формулалардан қорытындылау ережесі бойынша:               Н├А .                               (8)

Соңында (1) және (8) формулалардан

                 Н├             (9)

алынады.

Формуланың шығарылатынын  дәлелдеуде тек қана қорытындылау ережесін емес, күрделі қорытындылау ережесін пайдалануға мүмкін екендігі түсінікті. Онда бұл ережені пайдаланып, (9) тұжырымды (5), (7), (1) және (3) тұжырымдардан алуға болады.

Анықтама. Формулалардың Н ақырлы жиынынан шығаруы деп әрбір мүшесі келесі шарттарды қанағаттандыратын формулалардың В12,…,Вк тізбегін айтамыз:

1) ол Н жиынының бір формуласы болады,

2) ол дәлелденетін формула болады,

3) ол В12,…,Вк тізбегінің алдынғы кез келген екі мүшесінен қорытындылау ережесі бойынша шығады.

Алдынғы мысалда көрсеткеніміздей, формулалардың Н={А,В} жиынынан шығаруы формулалардың келесі ақырлы тізбегі болады:

А, В, (А→А)→((А→В)→(А )), (А→В), А→А, (А→В)→(А )), А→В, А , . (1,2,3,7,5,6,8 формулалар).

Егер күрделі қорытындылау ережесін пайдалансақ, онда шығаруды былай жазуға болады:

 А, В, (А→А)→((А→В)→(А )), В→(А→В), А→А, А→В, . (5, 7, 1, 3 формулалар).

Шығарылатын формула  анықтамасынан және формулалар жиынынан шығару анықтамасынан шығарудың келесі қасиеттері келіп шығады:

1) Н жиынынан шығарудың әрбір бастапқы кесіндісі – Н-тан шығару болады.

2) Егер Н тан шығарудың екі көршілес мүшелерінің арасында (басында немесе соңында) кейбір Н тан шығаруді қойсақ, онда формулалардың алынған жаңа тізбегі Н тан шығару болады.

3) Н жиынынан шығарудың әрбір мүшесі Н тан шығарылатын формула болады. Н тан кез келген шығару оның соңғы формуласының шығаруы болады.

4) Егер болса, онда Н тан кез келген шығару W дан шығару болады.

5) В формуласы Н жиынынан шығарылатын болуы үшін бұл формуланың Н тан шығаруы бар болуы қажетті және жеткілікті.

2.8  Шығарылу ережелері

 

Бұл ережелер шығарудың  қасиеттерінен алмастыру және қорытындылау ережелерін қолдану арқылы тікелей  келіп шығады.

Н және W – тұжырымдар есептелімі формулаларының екі тобы болсын.

Н, W арқылы олардың бірігуін белгілейміз, яғни Н,W= .

Мысалы, W жиыны тек бір С формуласынан тұратын жағдайда біріктіруді Н, С түрінде жазамыз.

Негізгі шығарылу ережелерін көрсетейік.

 

1. H ├ A              Бұл ереже формулалар жиынынан шығарудың анықтамасынан                                                   H,W├A           келіп шығады: “Егер А формуласы Н тан шығарылатын болса, онда ол тан да шығарылады. ”.

 

    2. H,C ├ A,H├C 

                H├A          .

 

    3. H,C ├ A, W├C 

               H,W├A       .

 

    4. H ├ C→A 

              H,C├A    .

 

    5. Дедукция теоремасы:                 H, C├ A  .

                                                               H├C→A

  5A. Жалпыланған дедукция теоремасы:            {C1, C1, …, Ck}├ A 

                                                                           ├C1→(C2→(C3→…(Ck→A)…))

  

  6. Конъюнкцияны енгізу ережесі:  H├A,H├B   .

                                                                 H├

 

  7. Дизъюнкцияны енгізу ережесі:                  H,A├C;Н,B├C   .

                                                                                  H, ├C

 

2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс

 

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

 операцияларын тұжырымдар алгебрасында сияқты анықтаймыз. Тұжырымдар есептелімінің формулалары тұжырымдар алгебрасының ережелері бойынша есептелетін 1 немесе 0 мәндерінің біреуін ғана қабылдайды.

Тұжырымдар есептелімі формуласының мәні түсінігін енгіземіз. А – тұжырымдар есептелімінің формуласы, х12,…,хn – өзара әртүрлі А формуласына енетін айнымалылар болсын. а1, а2,…,аn арқылы бұл айнымалыларының мәндер тобын белгілейміз. (а1, а2,…,аn) векторы 2n мән қабылдайтыны айқын.

Келесі үш теорема  орынды.

Теорема 1. Әрбір тұжырымдар есептелімінде дәлелденетін формула тұжырымдар алгебрасында тепе-тең ақиқат болады.

Теорема 2. (шығарылу туралы). А – тұжырымдар есептелімінің қандай да бір формуласы болсын; х12,…,хn  – А формулаға енетін айнымалылардың тобы; а1, а2, …, аn – бұл айнымалылар мәндерінің кез келген бекітілген тобы. Н арқылы формулалардың ақырлы жиынынын белгілейміз:

, где 

Онда:

  1. Егер Ra1,a2,..,an(A)=1 болса, онда H├A .
  2. Егер Ra1,a2,..,an(A)=0 болса, онда H├ , мұнда Ra1,a2,..,an(A) – А формуланың а1, а2,…,аn топтағы мәні.

 

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

 

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

 

1. формуланың рангін табыңыз

7

6

5

4

 

2. формуланың рангін табыңыз

 8

6

7

5

 

3. Дұрыс құрылған формуланы көрсетіңіз:

 

 

 

4. Келтірілген өрнектердің қайсысы формула болады?

Барлық жауаптар дұрыс

 

5. формула үшін алмастыру нәтижесін жазыңыз

 

6. формула үшін алмастыру нәтижесін жазыңыз

 

Глава 3. предикаттар логикасы

3.1 Предикат ұғымы

 

Анықтама 1. x1, x2, …, xn – пәндік айнымалылардың символдары болсын. Пәндік айнымалылардың (x1, x2, …, xn) топтары пәндік аймақ деп аталатын W жиыныны тиісті болсын. W пәндік аймағында анықталған n-орынды предикат деп,  W-ның тұжырымдар жиынына бейнелеуін айтады.

Мысалдарды қарастырар алдын n-орынды предикаттарға квазианықтама  берейік:

Анықтама. «n  айнымалыға тәуелді және келесі қасиетке ие болған баяндамалы байланысты сөйлемі: айнымалылардың орнына анық мәндер қойылғанда ақиқат немесе жалған болсын».

Мысал 1. D(x1, x2) = «x1 натурал саны x2 натурал санына бөлінеді (қалдықсыз)» - N N жиынында анықталған екі орынды предикат. Түсінікті, D(4, 2)=1, D(3, 5)=0.

Мысал 2. Q(x) = «х2<-1, x R» - R нақты сандар жиынында анықталған бір орынды предикат. Q(-1)=0, Q( )=0. Q(x) – тепе-тең жалған екендігі түсінікті, яғни Q(x) 0.

Мысал 3. R(x, y, z)= «x2+ y2 z; x, y, z R» - R3 жиынында анықталған үш орынды предикат. R(1, 1, -2)=0, R(1, 1, 2)=1.

Мысал 4. S(x, y) = «sin2ху>-3; x, y R» - екі орынды тепе-тең ақиқат предикат.

Р(x1, x2, …, xn) - W аймағында анықталған n-орынды предикат болсын. Онымен келесі түрде анықталған екі жиынды байланыстырамыз:

IP={( x1, x2, …, xn )Î W | Р(x1, x2, …, xn)=1} Р предикаттың ақиқаттық жиыны,

LP={( x1, x2, …, xn)Î W | Р(x1, x2, …, xn)=0}Р предикаттың жалғандық жиыны.

Анықтама  2. РW-да анықталған предикат болсын. Егер IP=W (LP=Æ) болса, онда Р тепе-тең ақиқат, егер LP=W (IP=Æ) болса, онда Р тепе-тең жалған предикат деп аталады.

Егер  IP ¹ W және LP ¹ Æ болса, онда Р орындалатын предикат деп айтамыз.

R3 кеңістікте 3 мысалдағы      R(x, y, z) предикаттың  IP  және LP жиындарын көрсетейік (1 сурет).                                                         


                                                                 z                        IP


 

 

 

1 сурет

                             

                                                                                        у

                                             х                                                                   

3.2 Предикаттарға логикалық амалдарды қолдану

 

Анықтама 3. РW-да анықталған предикат болсын. Р предикаттың терістеуі дегеніміз белгіленетін және W-да келесі түрде анықталған предикат:

P және Q – W-да анықталған предикаттар болсын.

P және Q предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, эквиваленциясы) дегеніміз былай белгіленетін , ( ( , , PQ), , ) және -да келесі түрде анықталатын предикат:

( )

( )

( )

 

Анықтама 4. Егер аймағына тиісті кез келген ( x1, x2, …, xn ) пәндік айнымалылардың топтары үшін Р( x1, x2, …, xn ) Q( x1, x2, …, xn ) болса, онда P және Q предикаттар аймағында анықталған пара-пар предикаттар деп аталады (P Q).

 

Теорема 1. аймағында анықталған n – орынды предикаттардың жиыны предикаттардың бульдік алгебрасық құрайды, яғни олар үшін бульдік алгебраның келесі 19 негізгі тепе-теңдіктер орынды:

 

0.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.


Мұнда 1 – -дағы тепе-тең ақиқат предикаттың, ал 0 – тепе-тең жалған предикаттың белгілері.

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

3.3 Кванторлық амалдар

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