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

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

МАЗМҰНЫ

 

 

КІРІСПЕ

 

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

Логика өз алдына ғылым болып грек философы Аристотельдің  (384-322 ж.ж б.э.д) еңбегінде нақтыланған. Ол өзіне дейінгі мәліметтерді жүйеледі және осы жүйе кейін формальды немесе Аристотель логикасы деп аталды.

Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді. Математиканың дамуы Аристотель логикасының жетіспеушіліктерін көрсетті және оның әрі қарай дамуын талап етті.

Математикалық негізде  логиканы құру идеясын тарихта алғашқы  болып неміс математигі Г.Лейбниц (1646-1716) XVI ғ. аяғында айтты. Ол логиканың  негізгі ұғымдарын арнайы шарттармен байланысқан символдармен белгіленуі тиіс дейді. Бұл кез-келген ойларды есепке ауыстыруға мүмкіндік береді.

Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы

Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны құрды және бұл айтылымдар алгебрасын дүниеге әкелді. Логикаға симвлодық белгілеуді ендіру, бұл ғылымға маңызды болды. Дәл осы символдарды логикаға ендіру жаңа математикалық логика ғылымының негізін қалады.   

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

XIX ғ. аяғында математика үшін  актуальді мәнге ие болатын  сұрақтар туындады, яғни оның негізгі ұғымдары мен идеялары бойынша. Бұл мәселенің логикалық негізі болды және бұл математикалық логиканың әрі қарай дамуына алып келді. Бұл қатынаста неміс математигі Г.Фреге (1848-1925) және Итальян математигі Д. Пеано (1858-1932) еңбектерінде көрсетілген.

Математикалық ойлаудың ерекшеліктері  математикалық абстракция және олардың  байланыстарының түрлілігінің ерекшеліктерімен түсіндіріледі.

Осыған орай осы заманғы математикалық  логиканы математиканың бөлімі ретінде  қарастырады.

Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі математикалық теорияларды құруда аксиоматикалық әдістердің кең таралуы болып табылады.

Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе ұғымы және олардың арасындағы қатынас  тандалады. Осы ұғымдар мен қатынастар негізгі деп аталады. Әрі қарай дәлелдеусіз теория қарастыратын негізгі орын аксиома қолданылады. Барлық алдағы теорияның мазмұны аксиомадан логикалық түрде шығарады. Математикалық теорияда аксиоматикалық құруды алғашқы болып геометрияны құруды Эвклид қолданды .

Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі ұғымдарға (нүкте, түзу, жазықтық) анықтама бергісі  келді. Теорияны дәлелдеуде еш жерде  жинақталмаған орын қолданылды. 

 Теорияны аксиоматикалық құру  тәсілі XIX ғ. дейін жалғыз болды. Осы әдісті өзгертуде   Н. И. Лобачевский (1792-1856) еңбектерінің маңызы зор болды. 

Лобачевский алғашқы  болып Евклидтің 5 постулатының дәлелденбейтінін айтты және осы айтуын жаңа геометрияны құруда нақтылады. Кейін неміс математигі Ф.Клейн (1849-1925) Лобачевский геометриясын дәлелдеді. Осылайша математика тарихында олардың еңбектері алғашқы болып аксиоматикалық теорияның ділелденбейтін мәселесі көрсетілді.  

Қарсылықты емес аксиоматикалық теория осы теорияның аксиома  жүйесіне қойылатын негізгі талаптардың бірі болып табылады.

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

Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының  қорында құрылады.

Бірақтан,  XIX ғ. аяғында жиын теориясында  кемшіліктер пайда болды (жиын теориясының  парадоксы). Осыған мысал ретінде  Б. Рассела парадоксы болып табылады.

 Барлық ойланды жиынды екі  класқа бөлеміз. Жиынды “дұрыс”,  деп айтамыз егер ол өзінің  элементі ретінде өзі болмаса  және      “дұрыс емес”  кері жағдайда . Мысалы, барлық кітаптар  жиыны дұрыс жиын, ал ойдағы  заттар жиыны дұрыс емес жиын . L –барлық дұрыс жиындар жиыны болсын. Онда  L қай жиын класына жатады?

Егер L – “дұрыс” жиын болса, онда L Î L, яғни  дұрыс жиын класында, бірақ ол өз элементі ретінде өзі кіреді, сондықтан ол “дұрыс емес”.

Егер L – “дұрыс емес”  жиын болса, онда L Ï L, яғни дұрыс жиындар құрамында жоқ, бірақ L өз элементі ретінде өзі кірмейді, сондықтан ол  “дұрыс”. Осылайша дұрыс жиын ұғымында қарама-қайшылық туындайды.

Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын теориясын құру қажеттілігіне алып келді. Кейінгі өзгерістерге байланысты бұл теория осы заманғы жиын теориясы құрылды.

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

Осылайша, математикалық  теорияның қарсылықты еместігін  дәлелдеу басқа математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу теориясы деп атады.

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

Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз. 

 

1 ТАРАУ. ТҰЖЫРЫМДАР  АЛГЕБРАСЫ

1.1. Тұжырым  ұғымы

 

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

Тұжырым деп ақиқатығы немесе жалғандығы туралы айтуға болатын байланысты баяндамалы сөйлемді айтамыз.

Мысал 1. «2*2=4» (екі көбейту екі тең төрт).

Мысал 2. «Егер натурал сан 6ға бөлінсе, онда ол 3ке бөлінеді».

Мысал 3. Тауық қүс емес.

Мысал 4. 3≥5.

1 және 2 тұжырымдар – ақиқат, ал 3, 4 –жалған. Бір ғана тұжырым болатын айтылымды жай немесе қарапайым деп атайды. Қарапайым тұжырымға мысал болып 1 тұжырымды айтуға болады.

Граматикалық байланыстар көмегімен («және», «немесе», «егер..., онда...», «сонда тек сонда ғана») құрылған тұжырымдарды күрделі деп атайды. Осылайша 2 тұжырым мынадай қарапайым тұжырымдардан тұрады: «натурал сан 6 бөлінеді», «натурал сан 3 бөлінеді». 4 тұжырым «немесе» сөзімен қосылған «3 үлкен 5» және «3 тең 5» тұжырымдар.

Әрі қарай бізді тұжырымдардың мағыналы жағы қызықтырмастан, олар қандай ақиқаттық («ақиқат» немесе «жалған») мәнге ие болатындығы қызықтырады. Тұжырымдар алгебрасында бірдей ақиқаттық мәні бар барлық тұжырымдар алмасымды, яғни бізде ақиқат тұжырым  және жалған тұжырым секілді екі тұжырым класы бар.

Қарапайым тұжырымдары  латын алфавиттің a,b,c,…,x,y,z,… әріптерімен, ақиқат мәнді А әріппен немесе 1 цифрмен, жалған мәнді Ж әріппен немесе 0 цифрмен белгілейміз.

Егер а ақиқат болса, онда а=1, ал егер жалған болса,  а=0 деп жазамыз.

 1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу

 

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

 a терістеу тұжырымы (¬a) деп бегіленеді және «а емес» немесе «дұрыс емес а» деп оқылады. ¬a тұжырымының логикалық мәнін кесте арқылы көрсетуге болады:

 


 

 

 

 

Бұл түрдегі кестені ақиқаттық кестесі деп атайды.

Мәселен, «2 кіші 5тен» тұжырымы үшін терістеу болып «2 кіші емес 5тен» тұжырымы болады.

а тұжырым болсын. да тұжырым болғандықтан, тұжырымына терістеу құруға болады, яғни тұжырымы а тұжырымына екілік терістеу болады. және а тұжырымдарының логикалық мәні бірдей.

1.3 Конъюнкция

 

a және b тұжырымдарының конъюнкциясы деп, егер екі тұжырым да ақиқат болғанда ақиқат және егер кем дегенде біреуі жалған болғанда жалған болатын жаңа тұжырымды айтамыз.

a және b тұжырымдарының конъюнкциясы мына символмен белгіленеді aÙb (a ּb, a b,  a&b) және былай оқылады «a және b». a , b тұжырымдары конъюнкция мүшелері деп аталады. a және b екі тұжырымның барлық мүмкін логикалық мәндерінің конъюнкциясы келесі ақиқат кестеде көрсетілген:

                                                    

a

b

aÙb

1

1

1

1

0

0

0

1

0

0

0

0


 

Мысалы: «6  2-ге бөлінеді», «6  3-ке бөлінеді» тұжырымы үшін оның конъюнкциясы «6  2-ге бөлінеді және 6  3-ке бөлінеді» тұжырымы болады, бұл ақиқат.

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

1. 4 Дизъюнкция

 

a және b тұжырымдарының дизъюнкциясы деп,егер екі тұжырымның бірі ақиқат болса, ақиқат және егер екеуі де жалған болса, жалған болатын жаңа тұжырымды айтамыз.

 a, b тұжырымдардың дизъюнкциясы мына символмен белгіленеді:  aÚb және былай оқылады «a немесе b». a, b тұжырымдары дизъюнкция мүшелері деп аталады.

    a және b екі тұжырымның барлық мүмкін логикалық мәндерінің дизъюнкциясы келесі ақиқат кестеде көрсетілген:


 

 

 

 

 

 

1. 5 Эквиваленция

 

a және b екі тұжырымдарының   эквиваленциясы деп егер тұжырымдар бірдей ақиқат немесе жалған болса, ақиқат, ал қалған жағдайларда жалған болатын жаңа тұжырымды айтамыз.

a және b тұжырымдарының эквиваленциясы мына символмен белгіленеді: a~b (a«b) және былай оқылады: “a үшін қажетті және жеткілікті b ” немесе “ a сонда және тек сонда ғана, қашан b”. a, b тұжырымдары эквиваленция мүшелері деп аталады.  a және b екі тұжырымның барлық мүмкін логикалық мәндерінің эквиваленциясы келесі ақиқат кестеде көрсетілген:

a

B

a~b

1

1

1

1

0

0

0

1

0

0

0

1




 

 

 

 

 

 

Мысалы: «S төбесі және PQ негізімен берілген SPQ  үшбұрышы тең бүйірлі болады, сонда және тек сонда ғана, қашан P= Q» эквиваленциясы ақиқат. “ S төбесі және PQ негізімен берілген SPQ  үшбұрышы тең бүйірлі” және “ S төбесі және PQ негізімен берілген SPQ  үшбұрышында P= Q ” тұжырымдары бір мезгілде ақиқат немесе жалған.

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

1.6 Импликация

 

 a және b екі тұжырымның импликациясы деп, егер a ақиқат, ал b – жалған болса жалған және қалған жағдайда ақиқат болатын жаңа тұжырымды айтамыз.

 a, b тұжырым импликациясы былай белгіленеді a® b (a É b  aÞ b) және былай оқылады “егер a, онда b ” немесе «a дан b шығады».  а тұжырымын шарт немесе сілтеме тұжырым, ал b тұжырымын – салдары немесе қорытынды деп атайды.

  a және b екі тұжырымның барлық мүмкін логикалық мәндерінің импликациясы келесі ақиқаттық кестеде көрсетілген:

 

a

b

a® b

1

1

1

1

0

0

0

1

1

0

0

1

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