Тұжырымдар алгебрасы диплом жұмысы
МАЗМҰНЫ
КІРІСПЕ 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
Жұмыс түрі: Дипломдық жұмыс
Жұмыс көлемі: 43 бет
Пәні: Соңғы қосылған дипломдық жұмыстар
-----------------------------------------------------------------------------------
ДИПЛОМДЫҚ ЖҰМЫСТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ
МАЗМҰНЫ
КІРІСПЕ 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 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең
1.9 Негізгі тепе-теңдіктер 10
1.10 Формулаларды тепе-тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.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 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс
Тақырып бойынша тесттер 24
Глава 3. предикаттар логикасы 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе-теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары
Тесты по теме 32
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТестТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның
Логика өз алдына ғылым болып грек философы Аристотельдің
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны
Логикада математиканы қолдану логикалық теорияларды жаңа формада кқруге
XIX ғ. аяғында математика үшін актуальді мәнге ие
Математикалық ойлаудың ерекшеліктері математикалық абстракция және олардың байланыстарының
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі математикалық
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін айтты
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының қорында
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”,
Егер L – “дұрыс” жиын болса, онда L
Егер L – “дұрыс емес” жиын болса, онда
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын теориясын
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943)
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа математикалық
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны математикалық
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1.1. Тұжырым ұғымы
Бүкіл математикадағы сияқты, біздің курстағы әр бөлімде де
Тұжырым деп ақиқатығы немесе жалғандығы туралы айтуға болатын
Мысал 1. «2*2=4» (екі көбейту екі тең төрт).
Мысал 2. «Егер натурал сан 6ға бөлінсе, онда
Мысал 3. Тауық қүс емес.
Мысал 4. 3≥5.
1 және 2 тұжырымдар – ақиқат, ал 3,
Граматикалық байланыстар көмегімен («және», «немесе», «егер..., онда...», «сонда
Әрі қарай бізді тұжырымдардың мағыналы жағы қызықтырмастан, олар
Қарапайым тұжырымдары латын алфавиттің a,b,c,…,x,y,z,… әріптерімен, ақиқат мәнді
Егер а ақиқат болса, онда а=1, ал егер
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу
а тұжырымының терістеуі жаңа тұжырым болып табылады, бұл
a терістеу тұжырымы (¬a) деп
Бұл түрдегі кестені ақиқаттық кестесі деп атайды.
Мәселен, «2 кіші 5тен» тұжырымы үшін терістеу болып
а тұжырым болсын. да тұжырым
1.3 Конъюнкция
a және b тұжырымдарының конъюнкциясы деп, егер екі
a және b тұжырымдарының конъюнкциясы мына символмен белгіленеді
a b a(b
1 1 1
1 0 0
0 1 0
0 0 0
Мысалы: «6 2-ге бөлінеді», «6 3-ке
Конъюнкция операциясы анықтамасында көрсетілгендей «және» сөзі логика алгебрасында
1. 4 Дизъюнкция
a және b тұжырымдарының дизъюнкциясы деп,егер екі
a, b тұжырымдардың дизъюнкциясы мына символмен белгіленеді:
a және b екі тұжырымның барлық мүмкін логикалық
1. 5 Эквиваленция
a және b екі тұжырымдарының эквиваленциясы
a және b тұжырымдарының эквиваленциясы мына символмен белгіленеді:
a B a~b
1 1 1
1 0 0
0 1 0
0 0 1
Мысалы: «S төбесі және PQ негізімен берілген SPQ
Эквиваленттілік математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың белгілі
1.6 Импликация
a және b екі тұжырымның импликациясы деп, егер
a, b тұжырым импликациясы былай белгіленеді a( b
a және b екі тұжырымның барлық мүмкін логикалық
a b a( b
1 1 1
1 0 0
0 1 1
0 0 1
Мысалы, “егер 12 6-ға бөлінсе, онда ол
Импликация математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың белгілі
Логикалық амалдармен алғаш танысқанда импликациядан басқаның барлығы мейлінше
Сонда шығатыны:
Q(x )= А(x )( В(x )
(1) формулаға х=8, 2, 3 мәндерін қоя отырып
Қарапайым тілде «Егер А, онда В» түрдегі сөйлемде
1.7 Тұжырымдар алгебрасының формулалары
Тұжырымдарға қолданылатын логикалық амалдары көмегімен берілген тұжырымдардан күрделі
және .
Қарапайым тұжырымдардан терістеу, конъюнкция, дизъюнкция, импликация және эквиваленция
Тұжырымдар алгебрасының формулаларын латын алфавиттің бас әріптерімен белгілейміз:
Жазуды жинақтау үшін формулалардағы амалдарды ретімен орындау келісілген.
Демек, жоғарыда келтірілген және
және
немесе
Логика алгебрасында формуланың логикалық мәні оған кіретін қарапайым
Логикалық амалдар сияқты, формуланың барлық мүмкін болған мәндері
Мысалы, (x(y(х((у формуласы үшін ақиқаттық кестесінің көрінісі
х у (x (у (x(y х((у (x(y(х((у
1
1
0
0 1
0
1
0 0
0
1
1 0
1
0
1 1
0
1
1 0
1
0
0 0
1
0
0
Егер формуланың құрамына n қарапайым тұжырым енетін болса,
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең
Егер логика алгебрасының А және В формулалары олардың
А (В ( А және В формулалары пара-пар.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде
Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар:
1.9 Негізгі тепе-теңдіктер
Теорема 1 Келесе тепе-теңдіктер орындалады:
а( b((a(b;
a~b ( (а( b)( b( a) ( ((a(b)(
Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен дәлелдеуге болады.
Келтірілген тепе-тең көрінетіндей, ( және ~ амалдары (,
Теорема 2 Айтылымдар алгебрасының булдік амалдары үшін келесі
0. – екі еселі терістеу
– коммутативтік заңдары
– ассоциативтік заңдары
– дистрибутивтік заңдары
–идемпотенттік заңдары
– де Морган заңдары
– 0 мен 1 заңдары
– жұту заңдары
– үшіншісі өшірілген заңы
– қайшылық заңы
Бұлардың кез-келгенін ақиқаттық кесте көмегімен дәлелдеуге болады.
1.10 Формулаларды тепе-тең түрлендіру
Тепе-теңдіктерді пайдаланып, формуланы немесе оның бөлігін оған пара-пар
Тепе-тең түрлендірулер тепе-теңдіктерді дәлелдеу, формуланы берілген түрге келтіру,
Егер А формуланың құрамына оған пара-пар В формулаға
1.11 Логика алгебрасының функциялары
Жоғарыда айтылғандай, логика алгебрасы формуласының мәні бұл формулаға
Мысалы, формуласы үш айнымалының f(x,y,z)
Анықтама Функцией алгебры логики n переменных (или функций
Ясно, что тождественно истинные и тождественно ложные формулы
n айнымалы функциялардың санын анықтаймыз. Логика алгебрасының әрбір
Мысалы, бір айнымалы әртүрлі функциялардың саны төрт, ал
Бір айнымалы барлық функциялардың ақиқаттық кестесін қарастырамыз. Ол
x f1(x) f2(x) f3(x) f4(x)
1 1 1 0 0
0 1 0 1 0
Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар
Барлық мүмкін болған екі айнымалы функциялардың ақиқаттық кестесі
x Y f1 f2 f3 f4 f5 f6
1 1 1 1 1 1 0 1
1 0 1 1 1 0 1 1
0 1 1 1 0 1 1 0
0 0 1 0 1 1 1 0
Түсінікті, бұл функциялардың аналитикалық өрнектері келесі түрде жазылуы
, ,
,
,
, , ,
функциясы Пирс функциясы деп аталады және былай белгіленеді:
1.12 Нормал және жетілдірілген формалар
А(а1, а2, …, аn) n тұжырымның формуласын қарастырайық.
Анықтама 1. n тұжырымның қарапайым конъюнкциясы (қарапайым
Мысал 1. xyz, (xy – қарапайым конъюнкция;
(x(y(z, y(z, x((z –қарапайым дизъюнкция.
Анықтама 2. Егер А формуладағы қарапайым дизъюнкциялар бір-бірімен
Анықтама 3. Егер А формуладағы қарапайым конъюнкциялар бір-бірімен
Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер
Анықтама 4 Егер дизъюнктивті нормал формадағы қарапайым конъюнкцияның
Анықтама 5 Егер конъюнктивті нормал формадағы қарапайым дизъюнкцияның
Мысал 2. А(x,y,z)= xyz((xy – дизъюнктивті нормал форма;
B(x,y,z)= ((x(y(z)( y(z)( x((z) – конъюнктивті нормал форма;
C(x,y,z)= xyz((xyz – жетілдірілген дизъюнктивті нормал форма;
D(x,y,z)= ((x(y(z)( x(y(z)( x(y((z) – жетілдірілген конъюнктивті нормал
Теорем 1 Тұжырымдар алгебрасының кез келген формуласының оған
Теорема 2 Тұжырымдар алгебрасының кез келген тепе-тең жалған
Теорема 3 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат
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
Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген
Бірінші жолдағы мәндерде 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 Логикалық байланыстардың толық жүйелері
(1, (2, …, (n логикалық амалдардың символдары болсын.
Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар
Лемма 9.1 Логикалық байланыстардың келесі жиындары:
, толық жүйе құрайды.
Лемма 9.2 , Тақырып бойынша тесттер
1. Келесі импликациялардың қайсысы жалған?
1) егер 2(2=4, онда 2>3;
2) егер 2(2=4, онда 23) егер 2(2=5, онда 24) егер 2(2=5, онда 2>3;
2. Келесі сөйлемдердің қайсысы тұжырым болмайды?
1) «Информатика» кафедрасының студенті.
2) Париж – Испания астанасы.
3) 3 саны А жиынына тиісті.
3. Айнымалылардың қайсылары бір бірінің терістеулері болады:
1) 2>3, 2(3;
2) 69;
3) f функциясы жұп, f функциясы тақ;
4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы
4. 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 )
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-ші бөлімі бойынша формулалар болады.
Формула түсінігі мен бірге ішформула немесе формула бөлігі
1. Қарапайым формуланың ішформуласы оның өзі болады.
2. Егер формула көрінісінде болса,
3. Егер формула (А*В) (мұнда * –
Формуладағы логикалық амалдарының саны формуланың рангі деп аталады.
2.2. Дәлелденетін формула ұғымы
Тұжырымдар есептелімінің құруда келесі кезең дәлелденетін (шығарылатын) формулалардың
Дәлелденетін формула анықтамасы формулалар анықтамасы сияқты. Алдымен бастапқы
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі
Тұжырымдар есептелімінің аксиомалар жүйесі төрт топқа бөлінетін 11
Аксималардың бірінші тобы (құрамыларыны тек импликация енеді).
: .
: .
Аксималардың екінші тобы ( импликацияға конъюнкция қосылды):
:
: .
: .
Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды):
:
:
: .
Аксималардың төртінші тобы (импликацияға терістеу қосылды):
:
:
:
2.4 Шығару ережелері
1. Алмастыру ережесі (АЕ).
Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін)
А формуладағы х айнымалыны В формулаға алмастыру
немесе .
Егер А – шығарылатын (дәлелденетін) болса, онда
├А____ .
├
Бұл жазылу былай оқылады: “Егер А формуласы шығарылатын
2 Қорытындылау ережесі (ҚЕ).
Егер А және А→В формулалары тұжырымдар есептелімінде шығарылатын
├А;├А→В
├В
Бұл ереженің дұрыстығы айқын: егер импликация мен
2.5 Дәлелденетін формуланың анықтамасы
а) Әрбір аксиома дәлелденетін формула болады.
б) Кез келген В формуласынан х айнымалының
в) А және дәлелденетін формулаларға
г) Тұжырымдар есептелімінің ешқандай басқа формуласы дәледенетін болып
Дәлелденетін формулаларды шығару процесін формулалардың дәлелдеуі (шығаруы) деп
2.6 Туынды шығару ережелері
Күрделі алмастыру ережесі (КАЕ)
Туынды шығару ережелері, қарастырылған шығару ережелері сияқты, жаңа
А – дәлелденетін формула, – айнымалылар,
КАЕ схематикалық түрде былай жазылады:
├А______
├
Күрделі қорытындылау ережесі
Қорытындылау ережесін де жалпылау мүмкін. Жалпылау нәтижесінде алынған
түрдегі формулаларға қолданылады да былай анықталады:
егер және
Күрделі қорытындылау ережесі былай жазылады:
├А1, ├А2, …,├Аn, ├A1→(A2→(A3→(...(An→L) …))) .
├ L
Силлогизм ережесі
Егер А→В және В→С формулалары дәлелденетін болса, онда
├А→В,├В→С .
├А→С
Контрапозиция ережесі
Егер А→В формуласы дәлелденетін болса, онда
├ А →В .
├
Бұл ереженің мысалында тұжырымдар есептелімінде мұндай тұжырымдардың дәлелдеу
├(А→В)→├( )
дәлелденетін формуланы аламыз.
Ал шарт бойынша
├А→В
– дәлелденетін формула.
Онда (2) және (1) формулаларынан қорытындылау ережесі бойынша
Екі еселі терістеу ережесі
а) Егер формуласы дәлелденетін болса,
б) Егер формуласы дәлелденетін
Схематикалық жазылулары: ├
├
2.7 Формулаларды гипотезалардан қорытып шығару
Формулалардың Н={А1,А2,…,Аn} ақырлы жиынын қарастырамыз.
Н жиынынан шығарылатын формула анықтамасы.
1) Ai(H формуласы Н-тан шығарылатын формула деп аталады.
2) Әрбір дәлелденетін формула Н-тан шығарылатын болады.
3) Егер С және С→В формулалар Н-тан шығарылатын
Егер кейбір В формуласы формулалардың Н жиынынан шығарылатын
Н жиыны бос немесе тек дәлелденетін формулалардан тұратын
Егер де Н жиынында кем дегенде бір дәлелденбейтін
Мысал.
Формулалардың Н={А, В} жиынынан формуласы
A(H және B(H болғандықтан, дәлелденетін формуланың анықтамасы бойынша
Н├А,
Н├В.
және аксиомаларды алып,
Нәтижесінде Н-тан шығарылатын дәлелденетін формулаларды аламыз, яғни
Н├(А→А)→((А→В)→(А )),
Н├В→(А→В),
А→А формуласы дәлелденетін, онда Н├А→А.
(5) және (3) формулалардан қорытындылау ережесі бойынша
алынады.
(2) және (4) формулалардан қорытындылау ережесі бойынша:
Н├А→В .
(7) және (6) формулалардан қорытындылау ережесі бойынша:
Соңында (1) және (8) формулалардан
Н├
алынады.
Формуланың шығарылатынын дәлелдеуде тек қана қорытындылау ережесін емес,
Анықтама. Формулалардың Н ақырлы жиынынан шығаруы деп әрбір
1) ол Н жиынының бір формуласы болады,
2) ол дәлелденетін формула болады,
3) ол В1,В2,…,Вк тізбегінің алдынғы кез келген
Алдынғы мысалда көрсеткеніміздей, формулалардың Н={А,В} жиынынан шығаруы формулалардың
А, В, (А→А)→((А→В)→(А )), (А→В), А→А, (А→В)→(А
Егер күрделі қорытындылау ережесін пайдалансақ, онда шығаруды былай
А, В, (А→А)→((А→В)→(А )), В→(А→В), А→А, А→В,
Шығарылатын формула анықтамасынан және формулалар жиынынан шығару анықтамасынан
1) Н жиынынан шығарудың әрбір бастапқы кесіндісі –
2) Егер Н тан шығарудың екі көршілес мүшелерінің
3) Н жиынынан шығарудың әрбір мүшесі Н тан
4) Егер болса, онда Н
5) В формуласы Н жиынынан шығарылатын болуы үшін
2.8 Шығарылу ережелері
Бұл ережелер шығарудың қасиеттерінен алмастыру және қорытындылау ережелерін
Н және W – тұжырымдар есептелімі формулаларының екі
Н, W арқылы олардың бірігуін белгілейміз, яғни
Мысалы, W жиыны тек бір С формуласынан
Негізгі шығарылу ережелерін көрсетейік.
1. H ├ 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
5A. Жалпыланған дедукция теоремасы:
├C1→(C2→(C3→…(Ck→A)…))
6. Конъюнкцияны енгізу ережесі: H├A,H├B
H├
7. Дизъюнкцияны енгізу ережесі:
H, ├C
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс
Тұжырымдар есептелімінің формулаларын тұжырымдар алгебрасының формулалары ретінде қарастыруға
операцияларын тұжырымдар алгебрасында сияқты анықтаймыз. Тұжырымдар есептелімінің
Тұжырымдар есептелімі формуласының мәні түсінігін енгіземіз. А –
Келесі үш теорема орынды.
Теорема 1. Әрбір тұжырымдар есептелімінде дәлелденетін формула тұжырымдар
Теорема 2. (шығарылу туралы). А – тұжырымдар есептелімінің
, где
Онда:
Егер Ra1,a2,..,an(A)=1 болса, онда H├A .
Егер Ra1,a2,..,an(A)=0 болса, онда H├ , мұнда
Теорема 3. Тұжырымдар алгебрасының әрбір тепе-тең ақиқат
Тақырып бойынша тесттер
1. формуланың рангін табыңыз
7
6
5
4
2. формуланың рангін табыңыз
8
6
7
5
3. Дұрыс құрылған формуланы көрсетіңіз:
4. Келтірілген өрнектердің қайсысы формула болады?
Барлық жауаптар дұрыс
5. формула үшін
6. формула үшін
Глава 3. предикаттар логикасы
3.1 Предикат ұғымы
Анықтама 1. x1, x2, …, xn – пәндік
Мысалдарды қарастырар алдын n-орынды предикаттарға квазианықтама берейік:
Анықтама. «n айнымалыға тәуелді және келесі қасиетке
Мысал 1. D(x1, x2) = «x1 натурал саны
Мысал 2. Q(x) = «х2Мысал 3. R(x, y, z)= «x2+ y2
Мысал 4. S(x, y) = «sin2ху>-3; x, y
Р(x1, x2, …, xn) - ( аймағында анықталған
IP={( x1, x2, …, xn )( ( |
LP={( x1, x2, …, xn)( ( | Р(x1,
Анықтама 2. Р – (-да анықталған предикат болсын.
Егер IP ( ( және LP ( (
R3 кеңістікте 3 мысалдағы
z
1 сурет
у
х
3.2 Предикаттарға логикалық амалдарды қолдану
Анықтама 3. Р – (-да анықталған предикат болсын.
P және Q – (-да анықталған предикаттар болсын.
P және Q предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, эквиваленциясы)
( )
( )
( )
Анықтама 4. Егер аймағына тиісті
Теорема 1. аймағында анықталған n
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
Мұнда 1 – -дағы тепе-тең ақиқат
Бұл теореманың дұрыстығы айқын. Өйткені предикаттарға қолданылатын амалдар
3.3 Кванторлық амалдар
Предикаттарды тұжырымдарға түрлендіретін амалдарды қарастырайық. М жиынында анықталған
Жоғарыда айтылғанды n – орынды предикаттарға жалпылау мүмкін:
Квантификация амалдарын қарастырамыз. Бұл амалдардар да предикаттарды тұжырымдарға
Жалпылау кванторы
Р(х) – ( жиынында анықталған предикат болсын. Бұл
символын жалпылау кванторы деп атайды. Р(х) предикатқа х
Бар болу кванторы
P(x) – ( жиынында анықталған предикат болсын.
Кванторлық амалдарды көп орынды предикаттарға да қолдануға болады.
3.4 Предикаттар логикасының формуласының ұғымы
Предикаттар логикасында келесі символдарды пайдаланамыз:
p, q, r, … символдары – 1–
x, y, z, … – кейбір М жиынына
x0, y0, z0 – пәндік тұрақтылар, яғни пәндік
P(·), Q(·), F(·), … - бір орынды предикаттық
Q(·,·,…,·), R(·,·, …,·) – n-орынды предикаттық айнымалыла;р
P0(·), Q0(·,·, …,·) – тұрақты предикаттардың символдары.
Логикалық амалдардың символдары:
Кванторлық амалдардың символдары:
Көмекші символдар: жақшалар, үтірлер.
Предикаттар логикасы формуласының анықтамасы
Кез келген тұжырым (қарапайым) формула болады.
Егер F(·,·, …,·) – n-орынды предикатты айнымалы немесе
Егер А және В – формулалар (бұл формулаларға
Егер А – формула болса, онда
Егер А(х) – формула (бұл формулаға х пәндік
1 – 5 бөлімдерде айтылған сөздерден басқа сөздер
Мысалы, егер Р(х) және Q(x,y) – бір орынды
Мысалы, сөзі формула емес. Мұнда
Предикаттар логикасы формуласы анықтамасынан тұжырымдар алгебрасының әрбір формуласы
Предикаттар логикасының формуласының мәні
Формуланың логикалық мәні жайлы бұл формулаға кіретін предикаттардың
Осы үш түрлі айнымалылардың анық мәндерінде предикаттар логикасының
Мысал ретінде келесі формуланы қарастырамыз:
,
Бұл формулада екі орынды Р(x, y) предикаты M(M
В формулу (1) формулаға кіретін P(x,y) айнымалы предикаттың
P(x,y) предикаттың мәнін бекітеміз: P0(x,y)= «x
Анықтама 1. Егер предикаттар логикасының А және В
Анықтама 2. Егер предикаттар логикасының А және В
А(х) және В(х) – айнымалы предикаттар, ал С
1.
2.
3.
4.
5.
6. .
7.
8.
9.
10.
11.
12.
13.
14.
15.
3.6 Пренекстік нормал форма
Анықтама. Егер предикаттар логикасының формуласы терістеу, конъюнкция, дизъюнкция
Тұжырымдар алгебрасының және предикаттар логикасының тепе-теңдіктерін пайдаланып, предикаттар
Мысал 1.
формуланы нормал формаға келтірейік.
Тепе-тең түрлендірулерді пайдаланып, келесіні аламыз:
.
Предикаттар логикасы формулаларының арасында пренекстік (префикстік) нормал форма
,
мұнда символы –
Теорема. Предикаттар логикасының кез келген формуласын пренекстік нормал
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары
Предикаттар логикасының тілі математикалық тұжырымдар мен анықтамаларды жазу
, мұнда .
Мысал 2. Нүктедегі үзіліссіз функцияның анықтамасы.
Егер , мұндағы ,
Тесты по теме
1. Р(х) = «х2-4=0, х(R» және Q(х)= «3х-2(16,
IP = (2; -2(; IQ = (-(; 6)
IP = (2(; IQ = (-(; 6)
IP = (2(; IQ = (1; 2; 3;
2. Р(х)= «х2-4=0, х(N» және Q(х)= «3х-2(16, х(N»
IP = (2(; IQ = (1; 2; 3;
IP = (2(; IQ = (1; 2; 3;
IP = (2(; IQ = (-(; 6)
IP = (2(; IQ = (6(
3. Пара-пар предикаттарды көрсетіңіз (пәндік айнымалылар R жиынына
х2 ( 0 және 2|x| =
және
және
және
4. Келесі өрнектердің қайсысы предикаттар логикасының формуласы болады?
5. формуладағы айнымалылардың түрін анықтаңыз:
х, z байланған, у бос
х, z бос, у байланған
х, у байланған, z бос
y, z байланған, x бос
6. Предикаттардың қайсылары бір бірінің терістеулері болады?
«k бүтін саны тақ», «k бүтін саны
«f функциясы жұп», «f функциясы тақ»
«a(b», «a(b»
«n натурал саны – жай», «n натурал саны
7. Р(х,у) = «х натурал саны у натурал
8. және
9. Р(х) = «х – жұп саны, х(N»
IР& Q = (6; 12; …; 6n; …(
IР& Q = (2; 3; 4; 6; …;
IР& Q = (1; 3; 5; …; 2n-1;
10. предикаттың ақиқаттық жиынын табыңыз.
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ
4.1 Алгоритм түсінігі және оның қасиеттері
Алгоритм түсінігі негізігі математика түсінігінің қатарына жатады.
Сандармен жұмыс жасалатын арифметикалық әрекеттердің ережесі.
Ең үлкен ортақ бөлгішті табу ережесі.(Евклид алгоритмі).
Квадраттық түбірден құтылу ережесі.
Квадраттық түбірдің шешімін табатын ереже.
Әрбір келтірілген мысалдардың біртекті шешім кластарымен немесе массалық
Айтылғандарға қарап алгоритм түсінігінің келесі анықтамасын беруімізге болады.
Алгоритм дегеніміз бір образды және берілген массалық проблеманың
Алгоритм түсінігінің нақты қасиеттерін қарастырайық.
1. Жалпылық – бұл алгоритмнің жеке тапсырмаға емес,
2. Дискреттік – четкая разбивка на отдельные этапы
3. Анықталғандық – такая организация этапов выполнения, при
4. Конечность – Алгоритм қолданысындағы нақты тапсырмалардың шешімін
«Алгоритм дегеніміз не?», «Алгоритмнің шешілген және шешілмеген проблемалары
4.2. Тьюринг машиналары
Егер кейбір жалпы мәселені шешу үшін алгоритм белгілі
Тъюринг машинасы деп аталатын айтылған машиналардың варианттарының бірін
Тьюринг машинасының үш алфавиті бар:
1. Бос символмен берілген сыртқы алфавит – А((((.
2. Ішкі алфавит немесе жағдайлар алфавиті Q
3. Қозғалыстар алфавиті S = (-1, 0, +1(.
Машинаның құрылымына кіреді:
а) шексіз таспа (ұяшықтарға бөлінген). Әрбір ұяшыққа тек
б) оқып-жазушы құрылғы. Оқып-жазушы құрылғының шолу жасау,
г) машинаның бір конфигурациясынан басқасына өтулерін анықтайтын машинаның
Егер шолу жасалған ұяшық пен машинаның жағдайы белгілі
Машинаның программасы бұл әрбір (а, qi )
4.3 Машинаның жұмыс істеу ережелері
Машина дискретті түрде жұмыс істейді (қадам қадам
Машинаның жұмыстары машинаның қадамы q0 ға жеткенше жалғаса
4.4 Машина мысалдары
Мысал 1. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| |q1+1 (q3-1 |q3-1
+ |q1+1
( ( q2-1
(q0+1
Мысал 2. Келесі Тьюринг машинасы унарлық санақ жүйесінде
q1 q2 q3
| (q1+1 |q2-1 |q3+1
(
|q3+1
( ( q2-1 (q0+1 |q2-1
Тақырып бойынша тесттер
1. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( ( q0( ( (
( ( ( q0( (
( ( q0( ((
( ( ( q0( (
( ( ( ( ( q0(
2. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
(( q0( ( (
( ( ( q0( (
( ( q0( ((
( ( ( q0( (
( ( ( ( ( q0(
3. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( ( ( ( q0(
( ( ( q0( (
( ( q0( ((
( ( ( q0( (
((( q0( ( (
4. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( ( q0( (
( ( ( q0( (
( ( q0( ((
( ( ( ( ( q0(
((( q0( ( (
5. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( q0( ((
( ( ( q0( (
( ( ( q0( (
( ( ( ( ( q0(
((( q0( ( (
6. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( ( q0( (
( ( ( q0( (
( ( ( ( ( q0(
((( q0( ( (
( ( q0( ((
КУРС БОЙЫНША ТестТЕР
1. Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
2. Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
3. формуланың рангін табыңыз:
7
6
5
4
4. – ( аймағында анықталған предикат
IP= (
IP= (
LP= (
5. – ( аймағында анықталған предикат
LP= (
IP= (
LP= (
6. Ықшамдаңыз:
7. Ықшамдаңыз:
y
х
8. Келтірілген ЖДНФ бойынша формуланың
9. Келтірілген ЖКНФ бойынша формуланың
10. Формуланың ақиқаттық кестесi бойынша оның ЖДНФ табыңыз:
x y F
0
0
1
1 0
1
0
1 0
0
0
1
11. Формуланың ақиқаттық кестесi бойынша оның ЖКНФ табыңыз:
x y F
0
0
1
1 0
1
0
1 0
1
1
0
12. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( q0( ( (
( ( ( q0( (
( ( q0( ((
( ( ( q0( (
( ( ( ( ( q0(
13. Берiлген Т Тьюринг машинасы және K1
T:
q1 q2 q3
( (q2+1 (q3+1 (q1+1
( (q00 (q0-1 (q1-1
( ( q0( ((
( ( ( q0( (
( ( ( q0( (
( ( ( ( ( q0(
((( q0( ( (
14. формуланың жетілдірілген конъюнктивті нормал
15. 0-ді Пирс функциясы арқылы өрнектеңіз:
16. Пирс функциясы арқылы өрнектеңіз:
17. Шеффер функциясы арқылы өрнектеңіз:
18. Шеффер функциясы арқылы өрнектеңіз:
19. x = 1, y = 1, z
F = 1, G =1
F = 0, G = 0
F = 0, G = 1
F = 1, G = 0
20. x = 1, y = 1, z
.F = 1, G = 0
F = 0, G = 1
F = 1, G = 1
F = 0, G = 0
ӘДЕБИЕТТЕР
Ершов Ю.Л., Палютин Е.А., «Математическая логика». М., Наука,
Жетпісов Қ., Түсіпов Ж.А., «Математикалық логика», Тараз, 2000.
Лавров И.А., Максимова Л.Л., «Задачи по теории
Лихтарников Л.М., Сукачева Т.Г., «Математическая логика». СПб.: «Лань»,
Мальцев А.И., «Алгоритмы и рекурсивные функции». М.: Наука,
Мендельсон Э., «Введение в математическую логику», М., 1976.
2
а ¬a
1 0
0 1
а b а(b
1 1 1
1 0 1
0 1 1
0 0 0
