Математикалық логика және дискретті математика
Алғы сөз ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..3
І ТАРАУ. ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
§1.1. Жиындар және оларда анықталған қатынастар ... ... ... ... ... 6
§1.2. Жиындардағы амалдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7
§1.3. Теоретикалық.жиындық амалдардың қасиетттері ... ... ... ...8
§1.4. Эйлер.Венн диаграммалары ... ... ... ... ... ... ... ... ... ... ... ... ...9
§1.5. Жиындардың декарттық көбейтіндісі ... ... ... ... ... ... ... ... ... 11
§1.6. Сәйкестіктер және олардың берілу тәсілдері ... ... ... ... ... ...14
§1.7. Сәйкестіктерде анықталған амалдар ... ... ... ... ... ... ... ... ... ..16
§ 1.8 Бейнелеулер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..17
ІІ ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
§2.1. Тұжырым ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..22
§2.2. Күрделі тұжырымдар. Логикалық
амалдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..23
§2.3. Эквиваленттіктер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .26
§2.4.Тұжырымдардың Буль алгебрасы ... ... ... ... ... ... ... ... ... ... ...28
§2.5. Буль функциясынық толық жүйесі ... ... ... ... ... ... ... ... ... ... 28
§2.6. Жетілдірілген формалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..32
§2.7. Дизъюнктивті нормаль формаларды минимизациялау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..35
§2.8. ДНФ.ны минимизациялау этаптары (кезеңдері) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..36
§2.9. Квант әдісі бойынша ДНФ . минимизациялау ... ... ... ... .38
§2.10 Логикалық амалдардың толық
жүйесі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .40
§2.11. Тұжырымдар (алгебрасының) логикасының
формулаларын қолдану ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .42
ІІІ ТАРАУ. ТҰЖЫРЫМДАР САНАҒЫ. АКСИОМАЛАР ӘДІСІ.
§3.1. Тұжырымдар санағы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...50
§3.2. Тұжырымдар санағының дәлелденетін
формулаларының мысалдары ... ... ... ... ... ... ... ... ... ... ... ... ... ..52
§3.3. Гипотезалардың көмегімен дәлелденетін
формулалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .53
§3.4. Туынды қортындылау ережелері ... ... ... ... ... ... ... ... ... ... ..56
§3.5. Тұжырымдар алгебрасы мен тұжырымдар санағының формулаларының арасындағы байланыс ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .59
ІV ТАРАУ. ПРЕДИКАТТАР САНАҒЫ
§4.1. Кванторлар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..62
§4.2. Берілген сигнатураның предикаттар санағының
тілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .63
§4.3. Гипотезаның көмегімен дәлелдеу ... ... ... ... ... ... ... ... ... ... 65
§4.4. Дәлелденетін формулалардың мысалдары ... ... ... ... ... ... .67
V ТАРАУ. АЛГЕБРАЛЫҚ ЖҮЙЕЛЕР
§5.1. Берілген сигнатураның алгебралық жүйелері ... ... ... ... ... 71
§5.2. Морфизмдер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...73
§5.3. Предикаттар санағы тілінің формулаларының
модельдегі мәндері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .75
§5.4. Гедель теоремасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..78
§5.5. Предикаттар санағының негізгі теоремалары ... ... ... ... ... 82
§5.6. Предикаттар санағының сөйлемдер жиыны жайлы ... ... ...86
§5.7. A.моделінің диаграммасы ... ... ... ... ... ... ... ... ... ... ... ... ... .87
§5.8. Элементар ішкі модельдер және олардың кеңеюі ... ... ... ..90
§5.9. Алгебралық жүйелердің элементар тізбегі ... ... ... ... ... ... ..92
VІ ТАРАУ. ГРАФТАР ТЕОРИЯСЫНЫҢ НЕГІЗДЕРІ
§6.1. Негізгі анықтамалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...94
6.1.1. Жалпы ұғымдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .94
6.1.2. Бағдарланған және бағдарланбаған графтар ... ... ... ... ... ..95
6.1.3. Графтардың тізбелері, циклдері, жолдары
және контурлары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .96
6.1.4. Ақырлы және шексіз графтар ... ... ... ... ... ... ... ... ... ... ... ..97
6.1.5. Бөліктік графтар, ішкі графтар, бөліктік
ішкі графтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .98
6.1.6. Графтағы байламдылық ... ... ... ... ... ... ... ... ... ... ... ... ... ... 99
6.1.7. Изоморфизм. Жазық графтар ... ... ... ... ... ... ... ... ... ... ... ...101
§6.2. Жиындардағы қатынастар және графтар ... ... ... ... ... ... ... .102
§6.3. Сыбайластық матрицалары және графтың инциденттері ... .104
§6.4. Графтарда анықталған амалдар ... ... ... ... ... ... ... ... ... ... ... 106
§6.5. Графтың дәрежелері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...112
6.5.1. Бағдарланбаған графтардың дәрежелері ... ... ... ... ... ... ... .112
6.5.2. Бағдарланған графтардың дәрежелері ... ... ... ... ... ... ... ... 113
§6.6. Графтардағы ара.қашықтықтардың
сипаттамалары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .114
§6.7. Графтардағы жолдарды және ең қысқа
жолдарды анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...115
6.7.1. Графтағы жолдарды анықтау алгоритмі ... ... ... ... ... ... ... .115
6.7.2. Графтағы ең қысқа жолды анықтау алгоритмі ... ... ... ... ...116
§6.8. Графты орап өту ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .120
6.8.1. Эйлерлік тізбелер, циклдер, жолдар және контурлар ... ... 120
6.8.2. Гамильтондық тізбелер, циклдар, жолдар, контурлар ... ...123
6.8.3. Графтың сипаттамалары ... ... ... ... ... ... ... ... ... ... ... ... ... .124
VІІ ТАРАУ. КОДТАУ ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
§7.1. Алфавиттік кодтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..130
§7.2. Кодтаудың мысалдары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..131
§7.3. Тиімді кодтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..135
§7.4.Қателерді анықтайтын және түзететін кодтар ... ... ... ... ... ..138
§7.5. Хемминг коды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .140
VІІІ.тарау. ЛОГИКАЛЫҚ ЖЕЛІЛЕР ЖӘНЕ АВТОМАТТАР
§8.1. Буль функциялары үшін функционалды
элементтердің сызбасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...144
§8.2. Логикалық желілер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .149
§8.3. Ақырлы автоматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..153
§8.4. Автоматтағы периодты тізбектер ... ... ... ... ... ... ... ... ... ... .158
Әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..161
І ТАРАУ. ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
§1.1. Жиындар және оларда анықталған қатынастар ... ... ... ... ... 6
§1.2. Жиындардағы амалдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7
§1.3. Теоретикалық.жиындық амалдардың қасиетттері ... ... ... ...8
§1.4. Эйлер.Венн диаграммалары ... ... ... ... ... ... ... ... ... ... ... ... ...9
§1.5. Жиындардың декарттық көбейтіндісі ... ... ... ... ... ... ... ... ... 11
§1.6. Сәйкестіктер және олардың берілу тәсілдері ... ... ... ... ... ...14
§1.7. Сәйкестіктерде анықталған амалдар ... ... ... ... ... ... ... ... ... ..16
§ 1.8 Бейнелеулер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..17
ІІ ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
§2.1. Тұжырым ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..22
§2.2. Күрделі тұжырымдар. Логикалық
амалдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..23
§2.3. Эквиваленттіктер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .26
§2.4.Тұжырымдардың Буль алгебрасы ... ... ... ... ... ... ... ... ... ... ...28
§2.5. Буль функциясынық толық жүйесі ... ... ... ... ... ... ... ... ... ... 28
§2.6. Жетілдірілген формалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..32
§2.7. Дизъюнктивті нормаль формаларды минимизациялау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..35
§2.8. ДНФ.ны минимизациялау этаптары (кезеңдері) ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..36
§2.9. Квант әдісі бойынша ДНФ . минимизациялау ... ... ... ... .38
§2.10 Логикалық амалдардың толық
жүйесі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .40
§2.11. Тұжырымдар (алгебрасының) логикасының
формулаларын қолдану ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .42
ІІІ ТАРАУ. ТҰЖЫРЫМДАР САНАҒЫ. АКСИОМАЛАР ӘДІСІ.
§3.1. Тұжырымдар санағы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...50
§3.2. Тұжырымдар санағының дәлелденетін
формулаларының мысалдары ... ... ... ... ... ... ... ... ... ... ... ... ... ..52
§3.3. Гипотезалардың көмегімен дәлелденетін
формулалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .53
§3.4. Туынды қортындылау ережелері ... ... ... ... ... ... ... ... ... ... ..56
§3.5. Тұжырымдар алгебрасы мен тұжырымдар санағының формулаларының арасындағы байланыс ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .59
ІV ТАРАУ. ПРЕДИКАТТАР САНАҒЫ
§4.1. Кванторлар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..62
§4.2. Берілген сигнатураның предикаттар санағының
тілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .63
§4.3. Гипотезаның көмегімен дәлелдеу ... ... ... ... ... ... ... ... ... ... 65
§4.4. Дәлелденетін формулалардың мысалдары ... ... ... ... ... ... .67
V ТАРАУ. АЛГЕБРАЛЫҚ ЖҮЙЕЛЕР
§5.1. Берілген сигнатураның алгебралық жүйелері ... ... ... ... ... 71
§5.2. Морфизмдер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...73
§5.3. Предикаттар санағы тілінің формулаларының
модельдегі мәндері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .75
§5.4. Гедель теоремасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..78
§5.5. Предикаттар санағының негізгі теоремалары ... ... ... ... ... 82
§5.6. Предикаттар санағының сөйлемдер жиыны жайлы ... ... ...86
§5.7. A.моделінің диаграммасы ... ... ... ... ... ... ... ... ... ... ... ... ... .87
§5.8. Элементар ішкі модельдер және олардың кеңеюі ... ... ... ..90
§5.9. Алгебралық жүйелердің элементар тізбегі ... ... ... ... ... ... ..92
VІ ТАРАУ. ГРАФТАР ТЕОРИЯСЫНЫҢ НЕГІЗДЕРІ
§6.1. Негізгі анықтамалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...94
6.1.1. Жалпы ұғымдар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .94
6.1.2. Бағдарланған және бағдарланбаған графтар ... ... ... ... ... ..95
6.1.3. Графтардың тізбелері, циклдері, жолдары
және контурлары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .96
6.1.4. Ақырлы және шексіз графтар ... ... ... ... ... ... ... ... ... ... ... ..97
6.1.5. Бөліктік графтар, ішкі графтар, бөліктік
ішкі графтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .98
6.1.6. Графтағы байламдылық ... ... ... ... ... ... ... ... ... ... ... ... ... ... 99
6.1.7. Изоморфизм. Жазық графтар ... ... ... ... ... ... ... ... ... ... ... ...101
§6.2. Жиындардағы қатынастар және графтар ... ... ... ... ... ... ... .102
§6.3. Сыбайластық матрицалары және графтың инциденттері ... .104
§6.4. Графтарда анықталған амалдар ... ... ... ... ... ... ... ... ... ... ... 106
§6.5. Графтың дәрежелері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...112
6.5.1. Бағдарланбаған графтардың дәрежелері ... ... ... ... ... ... ... .112
6.5.2. Бағдарланған графтардың дәрежелері ... ... ... ... ... ... ... ... 113
§6.6. Графтардағы ара.қашықтықтардың
сипаттамалары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .114
§6.7. Графтардағы жолдарды және ең қысқа
жолдарды анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...115
6.7.1. Графтағы жолдарды анықтау алгоритмі ... ... ... ... ... ... ... .115
6.7.2. Графтағы ең қысқа жолды анықтау алгоритмі ... ... ... ... ...116
§6.8. Графты орап өту ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .120
6.8.1. Эйлерлік тізбелер, циклдер, жолдар және контурлар ... ... 120
6.8.2. Гамильтондық тізбелер, циклдар, жолдар, контурлар ... ...123
6.8.3. Графтың сипаттамалары ... ... ... ... ... ... ... ... ... ... ... ... ... .124
VІІ ТАРАУ. КОДТАУ ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
§7.1. Алфавиттік кодтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..130
§7.2. Кодтаудың мысалдары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..131
§7.3. Тиімді кодтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..135
§7.4.Қателерді анықтайтын және түзететін кодтар ... ... ... ... ... ..138
§7.5. Хемминг коды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .140
VІІІ.тарау. ЛОГИКАЛЫҚ ЖЕЛІЛЕР ЖӘНЕ АВТОМАТТАР
§8.1. Буль функциялары үшін функционалды
элементтердің сызбасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...144
§8.2. Логикалық желілер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .149
§8.3. Ақырлы автоматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..153
§8.4. Автоматтағы периодты тізбектер ... ... ... ... ... ... ... ... ... ... .158
Әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..161
Математикалық логика және дискретті математика оқулығы екі бөлімнен тұрады.
Оқулықтың бірінші бөлімі – математикалық логика. Ол автордың Х. Дулати атындағы Тараз мемлекеттік университетінің ақпараттық жүйелер кафедрасының доценті Ж. А. Түсіповпен бірлесіп жазған 2000 жылы жарық көрген «Математикалық логика» оқу-құралының негізінде жазылған.
Онда қарастырылған мәселелер: жиындар теориясына кіріспе, тұжырымдар алгебрасы, тұжырымдар санағы, предикаттар санағы, алгебралық жүйелер және модельдер теориясына кіріспе.
Модельдер теориясына кіріспе тарауында теоретикалы-модельдік алгебра мен предикаттар санағы тілінің арасындағы байланыстар туралы алғашқы мағлұматтар берілген.
Атап айтқанда, элементар ішкі модель, элементар эквивалентті және изоморфты модельдер, модельдің диаграммалары, алгебралық жүйелердің элементар тізбегі қарастырылған.
Алгебралық жүйелер тарауында предикаттар санағының негізгі теоремалары толығымен дәлелденген.
Оқулықтың екінші бөлімі үш тараудан тұрады.
Графтар теориясының негіздері деп аталатын алтыншы тарауда графтар мен оның бөліктері, элементтері (тізбек, жол, цикл және контур) бөлікті графтар, ішкі графтар, графтарда анықталған амалдар мен қатынастар, графтардың сыбайластық және инциденттік матрицалары, графтың дәрежесі, эйлерлік және гамильтонды графтар, графтағы ең қысқа жолды табу алгоритмі сияқты сұрақтар қарастырылған. Кодтау теориясының элементтері тарауында әріптік және сандық кодтаулар, тиімді кодтау, қателерді ажырататын және түзететін кодтар, Хеминг коды туралы айтылған.
Әріптік кодтардың мысалы ретінде Морзе коды келтірілген.
Логикалық желілер және автоматтар атты сегізінші тарауда Буль функциялары арқылы анықталған функционалдық сызбалар, логикалық желілер, автоматтардағы периодты тізбектер туралы мағлұматтар берілген.
Әрбір тараудың соңында мысалдар келтіріліп, есептер мен жаттығулар берілген.
Көптеген есептердің шығару тәсілдері көрсетілген.
Оқулықта байқалған кемшіліктер болса және басқа да тілектеріңізді Е. А. Бөкетов атындағы Қарағанды мемлекеттік университетінің математика факультетінің Т. Ғ. Мұстафин атындағы алгебра, математикалық логика және геометрия кафедрасына жолдауларыңызды сұраймын.
Оқулықтың бірінші бөлімі – математикалық логика. Ол автордың Х. Дулати атындағы Тараз мемлекеттік университетінің ақпараттық жүйелер кафедрасының доценті Ж. А. Түсіповпен бірлесіп жазған 2000 жылы жарық көрген «Математикалық логика» оқу-құралының негізінде жазылған.
Онда қарастырылған мәселелер: жиындар теориясына кіріспе, тұжырымдар алгебрасы, тұжырымдар санағы, предикаттар санағы, алгебралық жүйелер және модельдер теориясына кіріспе.
Модельдер теориясына кіріспе тарауында теоретикалы-модельдік алгебра мен предикаттар санағы тілінің арасындағы байланыстар туралы алғашқы мағлұматтар берілген.
Атап айтқанда, элементар ішкі модель, элементар эквивалентті және изоморфты модельдер, модельдің диаграммалары, алгебралық жүйелердің элементар тізбегі қарастырылған.
Алгебралық жүйелер тарауында предикаттар санағының негізгі теоремалары толығымен дәлелденген.
Оқулықтың екінші бөлімі үш тараудан тұрады.
Графтар теориясының негіздері деп аталатын алтыншы тарауда графтар мен оның бөліктері, элементтері (тізбек, жол, цикл және контур) бөлікті графтар, ішкі графтар, графтарда анықталған амалдар мен қатынастар, графтардың сыбайластық және инциденттік матрицалары, графтың дәрежесі, эйлерлік және гамильтонды графтар, графтағы ең қысқа жолды табу алгоритмі сияқты сұрақтар қарастырылған. Кодтау теориясының элементтері тарауында әріптік және сандық кодтаулар, тиімді кодтау, қателерді ажырататын және түзететін кодтар, Хеминг коды туралы айтылған.
Әріптік кодтардың мысалы ретінде Морзе коды келтірілген.
Логикалық желілер және автоматтар атты сегізінші тарауда Буль функциялары арқылы анықталған функционалдық сызбалар, логикалық желілер, автоматтардағы периодты тізбектер туралы мағлұматтар берілген.
Әрбір тараудың соңында мысалдар келтіріліп, есептер мен жаттығулар берілген.
Көптеген есептердің шығару тәсілдері көрсетілген.
Оқулықта байқалған кемшіліктер болса және басқа да тілектеріңізді Е. А. Бөкетов атындағы Қарағанды мемлекеттік университетінің математика факультетінің Т. Ғ. Мұстафин атындағы алгебра, математикалық логика және геометрия кафедрасына жолдауларыңызды сұраймын.
1. Белоусова А.И. Лекции по дискретной математике. МГТУ
им.Баумана, -М., 1994.
2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной
математике. -М.: Наука, 1977.
3. Горбатов В.А. Основы дискретной математики. -М.: Высшая школа, 1986г.
4. Ершов Ю.Л., Палютин Е.А. Математическая логика.
– М.:Наука, 1987.
5. Горбатов В.А. Фундаментальные основы дискретной математики. –М.:Физматлит, 2000.
6. Жетпісов Қ., Түсіпов Ж.А. Математикалық логика: Оқу
құралы.-Тараз ТаразМУ, 2000.
7. Жетпісов Қ., БашееваА.О. Дискретті математика негіздері; Оқу-әдістемелік құрал. – Қарағанды; ҚарМУ баспасы, 2007.
8. Жетпісов Қ., Қойкелова Д.К. Бул функцияларының толық жүйесі; Әдістемелік нұсқау және өзіндік жұмыстарды орындау тапсырмалары. – Қарағанды; ҚарМУ баспасы, 2007.
9. Кейслер Г.., Чен Ч.Ч.. Теория моделей. -М.: Мир, 1977.
10. Клини С.К. Математическая логика. -М.: Мир, 1973.И.А.
11. Кузин Л.Т. Основы кибернетики.: -В 2т. Т.2.
12. Куратовский К.., Мостовский А.. Теория множеств. -М.: Мир, 1970.
13. Кристофидес Н. Теория графов. Алгоритмический подход. –М.:Мир, 1978.
14. Лавров И.А.. Логика и алгоритмы. –Новосибирск:. НГУ, 1970.
15. Лавров., Л.Л., Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. -М.: Наука, 1975.
16. Мальцев А.И. Алгоритмы и рекурсивные функции.
-М.: Наука, 1986.
17. Мальцев А.И. Алгебраические системы. -М.: Наука, 1970.
18. Мендельсон Э. Введение в математическую логику. -М.: Наука, 1971.
19. Мустафин Т.Г. Стабильные теории. –Караганда: КарГУ, 1981.
20. Мустафин Т.Г. Число моделей теории. –Караганда: КарГУ, 1983.
21. Нефедров В.Н., Осипова В.А. Курс дискретной математики:
учебное пособие для студентов специальности «Прикладная математика», -МАИ, 1992.
22. Новиков К.С.. Элементы математической логики. -М.: Наука,
1973.
23. Нұрсұлтанов К. Математикалық логиканың бастамалары. –
Алматы.: Республикалық баспа кабинеті, 1994.
24. Оре О. Теория графов. -М.: Наука, 1968.
25. Сакс Дж.Е. Теория насышенных моделей. -М.: Мир, 1976.
26. Сачков В.Н. Введение в комбинаторные методы дискретной математики. -М.: Наука, 1982.
27. Сикорский Р. Булевы алгебры. -М.: Мир, 1969.
28. Столл Р. Множества, логика, аксиоматические теории. -М.:
Просвещение, 1968.
29. Судоплатов С.В., Овчинникова Е.В. Дискреттная математика: Учебник. –2-е изд., переработ. –М.:ИНФРА-М; Новосибирск: Изд-во НГТУ, 2005
30. Фролов А.Б., Болотов А.А., Коляда К.В. Учебное пособие по
куосу «Дискретная математика». Модели и методы. -Мос. энергетический инсттут, 1989.
31. Шевелев Ю.П. Высшая школа математика 5. Дискретная
математика. ч.1: Теория множеств. Булевая алгебра: Учебное пособие - Томск: Том. гос. университет систем управления и радиоэлектроники, 1998.
32. Яблонский С.В. Введение в дискртную математику. -М.: Наука, 1986.
им.Баумана, -М., 1994.
2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной
математике. -М.: Наука, 1977.
3. Горбатов В.А. Основы дискретной математики. -М.: Высшая школа, 1986г.
4. Ершов Ю.Л., Палютин Е.А. Математическая логика.
– М.:Наука, 1987.
5. Горбатов В.А. Фундаментальные основы дискретной математики. –М.:Физматлит, 2000.
6. Жетпісов Қ., Түсіпов Ж.А. Математикалық логика: Оқу
құралы.-Тараз ТаразМУ, 2000.
7. Жетпісов Қ., БашееваА.О. Дискретті математика негіздері; Оқу-әдістемелік құрал. – Қарағанды; ҚарМУ баспасы, 2007.
8. Жетпісов Қ., Қойкелова Д.К. Бул функцияларының толық жүйесі; Әдістемелік нұсқау және өзіндік жұмыстарды орындау тапсырмалары. – Қарағанды; ҚарМУ баспасы, 2007.
9. Кейслер Г.., Чен Ч.Ч.. Теория моделей. -М.: Мир, 1977.
10. Клини С.К. Математическая логика. -М.: Мир, 1973.И.А.
11. Кузин Л.Т. Основы кибернетики.: -В 2т. Т.2.
12. Куратовский К.., Мостовский А.. Теория множеств. -М.: Мир, 1970.
13. Кристофидес Н. Теория графов. Алгоритмический подход. –М.:Мир, 1978.
14. Лавров И.А.. Логика и алгоритмы. –Новосибирск:. НГУ, 1970.
15. Лавров., Л.Л., Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. -М.: Наука, 1975.
16. Мальцев А.И. Алгоритмы и рекурсивные функции.
-М.: Наука, 1986.
17. Мальцев А.И. Алгебраические системы. -М.: Наука, 1970.
18. Мендельсон Э. Введение в математическую логику. -М.: Наука, 1971.
19. Мустафин Т.Г. Стабильные теории. –Караганда: КарГУ, 1981.
20. Мустафин Т.Г. Число моделей теории. –Караганда: КарГУ, 1983.
21. Нефедров В.Н., Осипова В.А. Курс дискретной математики:
учебное пособие для студентов специальности «Прикладная математика», -МАИ, 1992.
22. Новиков К.С.. Элементы математической логики. -М.: Наука,
1973.
23. Нұрсұлтанов К. Математикалық логиканың бастамалары. –
Алматы.: Республикалық баспа кабинеті, 1994.
24. Оре О. Теория графов. -М.: Наука, 1968.
25. Сакс Дж.Е. Теория насышенных моделей. -М.: Мир, 1976.
26. Сачков В.Н. Введение в комбинаторные методы дискретной математики. -М.: Наука, 1982.
27. Сикорский Р. Булевы алгебры. -М.: Мир, 1969.
28. Столл Р. Множества, логика, аксиоматические теории. -М.:
Просвещение, 1968.
29. Судоплатов С.В., Овчинникова Е.В. Дискреттная математика: Учебник. –2-е изд., переработ. –М.:ИНФРА-М; Новосибирск: Изд-во НГТУ, 2005
30. Фролов А.Б., Болотов А.А., Коляда К.В. Учебное пособие по
куосу «Дискретная математика». Модели и методы. -Мос. энергетический инсттут, 1989.
31. Шевелев Ю.П. Высшая школа математика 5. Дискретная
математика. ч.1: Теория множеств. Булевая алгебра: Учебное пособие - Томск: Том. гос. университет систем управления и радиоэлектроники, 1998.
32. Яблонский С.В. Введение в дискртную математику. -М.: Наука, 1986.
Қазақстан Республикасының білім және ғылым министрлігі
Қ. Жетпісов
МАТЕМАТИКАЛЫҚ ЛОГИКА ЖӘНЕ
ДИСКРЕТТІ МАТЕМАТИКА
Қазақстан Республикасы Білім және ғылым
министрілігі оқулық ретінде бекіткен
Алматы, 2011
ӘОЖ 510 (075.8)
ББЖ 22.12 я73
Ж 56
Пікір жазғандар:
Е. С. Смаилов - Қолданбалы математика институты Республикалық мемлекеттік қазыналық кәсіпорынның директоры ф.-м. ғ.д., профессор;
У. У. Өмірбаев - Л. Н. Гумилев атындағы Евразия ұлттық университе-тінің алгебра және геометрия кафедрасының меңгерушісі ф.-м.ғ.д., профессор;
Қ. Оспанов - Л. Н. Гумилев атындағы Евразия ұлттық университетінің есептеу және қолданбалы математика кафедрасының профессоры, ф.-м.ғ.д..
Жетпісов Қ.
Ж 56 Математикалық логика және дискретті математика:оқулық жоғары оқу орындарының студенттеріне арналған. - Алматы: ЖШС РПБК Дәуір, 2011.- 264 бет.
ISBN 978-601-217-186-0
Оқулық математикалық логика, дискретті математика атты екі бөлімнен тұрады.
Математикалық логика бөлімінде жиындар теориясының элементтері, тұжырымдар алгебрасы мен тұжырымдар санағы, предикаттар санағы мен алгебралық жүйелер туралы айтылады. Бұл бөлімде математикалық логиканың негізгі теоремалары дәлелденген. Атап айтқанда, Левенгейм-Сколем теоремасы, Гедель теоремасы, Мальцевтің локальдық теоремасы т.т.
Дискретті математика бөлімінде графтар теориясының негіздері, кодтау теориясының элементтері, логикалық желілер мен ақырлы автоматтар туралы баяндалады.
Оқулық университеттердің математика, информатика, ақпараттық жүйелер мамандықтары бойынша білім алушы студенттерге арналған.
ISBN 978-601-217-186-0
Ж
(C) Жетпісов Қ., 2011 ж.
(C) ҚР Жоғары оқу орындарының
қауымдастығы, 2011 ж.
Алғы сөз
Математикалық логика және дискретті математика оқулығы екі бөлімнен тұрады.
Оқулықтың бірінші бөлімі - математикалық логика. Ол автордың Х. Дулати атындағы Тараз мемлекеттік университетінің ақпараттық жүйелер кафедрасының доценті Ж. А. Түсіповпен бірлесіп жазған 2000 жылы жарық көрген Математикалық логика оқу-құралының негізінде жазылған.
Онда қарастырылған мәселелер: жиындар теориясына кіріспе, тұжырымдар алгебрасы, тұжырымдар санағы, предикаттар санағы, алгебралық жүйелер және модельдер теориясына кіріспе.
Модельдер теориясына кіріспе тарауында теоретикалы-модельдік алгебра мен предикаттар санағы тілінің арасындағы байланыстар туралы алғашқы мағлұматтар берілген.
Атап айтқанда, элементар ішкі модель, элементар эквивалентті және изоморфты модельдер, модельдің диаграммалары, алгебралық жүйелердің элементар тізбегі қарастырылған.
Алгебралық жүйелер тарауында предикаттар санағының негізгі теоремалары толығымен дәлелденген.
Оқулықтың екінші бөлімі үш тараудан тұрады.
Графтар теориясының негіздері деп аталатын алтыншы тарауда графтар мен оның бөліктері, элементтері (тізбек, жол, цикл және контур) бөлікті графтар, ішкі графтар, графтарда анықталған амалдар мен қатынастар, графтардың сыбайластық және инциденттік матрицалары, графтың дәрежесі, эйлерлік және гамильтонды графтар, графтағы ең қысқа жолды табу алгоритмі сияқты сұрақтар қарастырылған. Кодтау теориясының элементтері тарауында әріптік және сандық кодтаулар, тиімді кодтау, қателерді ажырататын және түзететін кодтар, Хеминг коды туралы айтылған.
Әріптік кодтардың мысалы ретінде Морзе коды келтірілген.
Логикалық желілер және автоматтар атты сегізінші тарауда Буль функциялары арқылы анықталған функционалдық сызбалар, логикалық желілер, автоматтардағы периодты тізбектер туралы мағлұматтар берілген.
Әрбір тараудың соңында мысалдар келтіріліп, есептер мен жаттығулар берілген.
Көптеген есептердің шығару тәсілдері көрсетілген.
Оқулықта байқалған кемшіліктер болса және басқа да тілектеріңізді Е. А. Бөкетов атындағы Қарағанды мемлекеттік университетінің математика факультетінің Т. Ғ. Мұстафин атындағы алгебра, математикалық логика және геометрия кафедрасына жолдауларыңызды сұраймын.
МАТЕМАТИКАЛЫҚ
ЛОГИКА
I. ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТЕРІ
II. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
IІI. аксиомалық Әдіс. санақ.
ІV. ПРЕДИКАТТАР САНАҒЫ
V. АЛГЕБРАЛЫҚ ЖҮЙЕЛЕР
I ТАРАУ
ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
Жиындар теориясының негізі XIX ғасырда Кантор еңбектерінде құрылған. Оған негізгі себеп математикалық талдауды құру және негіздеу проблемасы болды. Әріректе, осы математикалық талдау берген алғашқы серпін мен оның негізгі концепицяларының дамуы және оларды талдау мен қатаң түрде ұғынудың қалыптасуы қазіргі заманғы аксиомалық жиындар теориясына негіз болды.
Математиканың дамуына тигізген жиындар теориясының үлкен ықпалы қазіргі заманда барлығымыз мойындаған факт. Сондықтан, жоғарғы оқу орындарында математиканы оқытуда жиындар теориясының идеялары мен әдістерінің маңызды роль атқаратындығы толығымен заңдылық. Жиындар теориясының интуитивті негіздерін жүйелі оқып-зерттеу кез келген қазіргі заманғы математикалық пәндерді табысты оқып-зерттеудің айрылмас құраушысы болып табылады.
Бұл тараудың негізгі оқып-зерттеу объектісі теоретикалы-жиындық амалдар мен қатынастар және сонымен қатар олармен байланысты қарапайым құрылымдар болып табылады.
Материалды баяндау жиын ұғымы туралы көріністі интуитивті ұғыну негізінде іске асырылады.
Алғашқы ұғым ретінде жиын ұғымымен қатар элементінің жиынына тиісті болу қатынасы ұғымы пайдаланылады (). Жиын өзінің элементтерімен толығымен анықталады деген қағиданы ұстанып жиынды берудің (жиынның берілуінің) айқын әдісімен қатар шыршықтау принципіне негізделген әдісті пайдаланамыз.
Жиынды әртүрлі әдістермен анықтай отырып, біз алдын-ала оның ең болмағанда бір элементінің болатындығы туралы айта алмаймыз. Осы себепті, бос жиын ұғымын енгізу қажеттілігі туындайды. Алдағы уақытта, элементтің жиынға тиісті болу термині ұғымында қамтылу қатынасы мен жиындардың теңдігі енгізіледі. Ал бұлар содан соң жиындардың теңдігін дәлелдеудің негізгі әдісі ретінде қамтылу әдісін негіздеуге және қолдануға көмектеседі.
Бұл ұғымдарды енгізу процесінде ; ; қатынастарының арасындағы айрықша ерекшеліктерге ерекше көңіл аударылады.
Теоретикалы-жиындық амалдар ; ; \ - бірігу, қиылысу, айырма жаңа жиындарды құрудың әдістері ретінде пайдаланылады және әріректе, ешқандай проблемасыз аксиомалық жиындар теориясын оқып-зерттеуге көшуге көмегін тигізеді. Бұл сонымен қатар, берілген жиынның ішкі жиындарының жиынын алу және реттелген пар жиындарды алу амалдарына да қатысты. Теоретикалы-жиындық амалдардың қасиеттері қос-қостан топталады. Бұл және бірігу және қиылысу амалдарының қосалқылық сипатын көрсетеді және ол жиындар алгебрасында және басқа да математикалық жүйелерде қосалқылық заңын ұғынудың пропедитивті негіздерін қалайды.
Универсал жиынның кейбір ішкі жиындарының арасында орын алуы мүмкін қарапайым қатынастар мен тәуелділіктерді графиктік кескіндеу үшін Эйлер-Венн диаграммасы қолданылады.
Универсал жиынның кейбір ішкі жиындарынан құрылған күрделі өрнек үшін оларға ; ; \ амалдарын бірнеше қайтара (бірақ ақырлы рет) қолдану арқылы Эйлер-Венн диаграммасы қарапайым қатынастар мен тәуелділіктерге сәйкес келуші диаграммаларды топтастырудың көмегімен құрылады және ол күрделі өрнек құрайды.
Мұндай диаграмаларды құру процесінде интуитивті деңгейде жиындар теориясының формулалары мен ішкі формулалары ұғымдары енгізіледі. Бұл алдағы уақытта, формальді тіл мен логикалық санақтың дедуктивті құралдарын анықтаудың базалық процедуралық негізгі ретінде индуктивті әдісті қолданудың ерекшеліктерін түсінуде басты роль атқарады.
Екі жиынның декарттық көбейтіндісін енгізудегі жұмыста бастапқы нүкте ретінде жазықтықтағы тік бұрышты декарттық координаталар жүйесі концепциясы алынады.
Жиындардың берілуінің алдыңғы (ертеректе) келтірілген әдісіне қосымша ретінде екі ақырлы жиынның декарттық көбейтіндісін сипаттаудың кестелік әдісі мен график арқылы оның көрнекі берілу әдісі беріледі. Осыдан кейін, мысал арқылы кесіндідегі үзіліссіз функциясының графигі мен және жиындарының декарттық көбейтіндісі -ның графигінің арасындағы айырмашылықтары мен ұқсастықтары көрсетіледі, мұндағы және сандары кесіндісіндегі осы функцияның, сәйкесінше, ең үлкен және ең кіші мәндері.
Бірнеше жиындардың декарттық көбейтіндісін табу үшін анықтаудың индуктивті әдісі қолданылады.
Оқытудың мазмұндық негіздеу концепциясының қарарларын іске асыра отырып, бұл тарауда, жаңа декарттық көбейтінді амалын енгізуге байланысты, негізгі амалдардың қасиеттерін анықтаумен қатар оның негізгі ; ; \ амалдарымен үйлесімді қасиеттерін анықтау сұрақтары туындайды.
Сонымен, ертеректе енгізілген ұғымдардың мазмұндық өрісінің тармақталу процесінде оларды жаңа мазмұндармен толықтыру мүмкіндіктері қолданылады.
Мұндай тәсілдің өміршеңдігін атай отырып, жұмыста әдістемелік сипаттағы келесі қарарлар тұжырымдалады (универсал қолдануға ие):
а) Жаңадан еңгізілген ұғымдардың басқа да, ертеректе анықталған ұғымдармен байланысын және ерекшеліктері мен қасиеттерін анықтау. Бұл жаңа ұғымдарға нақты ажыратушы белгілер береді және олар белгілі бір контексте пайда болған жағдайда оларды тануға, ажыратуға көмектеседі.
б) Жаңа ұғымдармен тікелей жұмыс (олардың ең қарапайым түрінде) математикалық пәндерді оқып-зерттеудің фрагменттік шеңберінде, бұл ұғымдардың әртүрлі байытылу мен трансформациялар ерекшеліктерін қолдануда өзіндік (қалыптасу) үйрену дайындығы және бұл ұғымдардың қазіргі заманғы математика мен оның қосымшаларындағы әртүрлі облыстары болып табылады. Жиындардың декарттық көбейтіндісінен сәйкестіктерге, олардың берілу тәсілдері мен оларға қолданылатын амалдарға көшу табиғи түрде орындалады. Ақырлы сәйкестіктер, декарттық көбейтіндінің ішкі жиыны ретінде бағдарланған графтар мен қималар арқылы да берілуі мүмкін.
Сонымен, ұғымдарды байыту өзінен кейін тікелей оларды мазмұндық ұғынумен, сезінумен қатар жүретін байыту мүмкіндігі. Сондықтан оны сипаттық суреттерде, сызбаларда, графиктерде және басқа да геометриялық сипаттағы баламаларда іске асырған дұрыс. Бұл үшін, сәйкестіктердің берілу тәсілдеріне байланысты материалдар үлкен мүмкіндік береді.
Сәйкестік ұғымы белгілі теоретикалық-жиындық амалдар мен декарттық көбейтінді амалынан басқа тағы екі амал енгізуге мүмкіндік береді: кері сәйкестік алу амалы мен сәйкестіктерді көбейту (композиция) амалы. Бұл амалдар ұғымын тармақтауға кезекті қадам жасауға жол ашады.
1.7 параграфында жоғарыда келтірілген әдістемелік сипаттағы а), б) қарарларын іске асыру аясында жаңа амалдардың қасиеттері анықталады. Тарауды жиындар теориясының ең бір маңызды ұғымы - бейнелеу ұғымын аяқтайды. Мұнда алдымен тікелей осы ұғымның анықтамасы беріледі, (мектептік функционалдық көріністі іске асырушы), ал сонан соң кері бейнелеуді алу амалы мен бейнелеулердің көбейтіндісі тілінде оның сипаттамасы беріледі. Сонан соң осы екі анықтамалардың теңқуаттылығы дәлелденеді. Әдістемелік деңгейде осыған ұқсас дәлелдеулерден алынатын тәжірибе формальды аксиомалық теориялар әдісін меңгеруде қажетті кезең болып табылады. Себебі, олар мазмұндық қорытынды шарттарын құрумен байланысты болады. Мұнда ұғым бір қатынастар жүйесінде (осы ұғымды беруші шарттардан), бірақ олар басқа қатынастар жүйесінің тілінде тұжырымдалған.
1.8 параграфында атомдық бейнелеулердің ерекше рөлі атап өтіледі.
Олар: сюръекция, биекция, инъекция және олардың көмегімен сәйкес композициялардың көмегімен алынатын, атомдардан құрылған молекула сияқты, кез келген бейнелеу.
Алгебралық амал ұғымы алгебралық жүйе ұғымының негізгі құраушысы ретінде өзінің маңыздылығын жан жақты ұғынуды талап етеді. Бұл тарауда амал ұғымының тура интуитивті мағыналық көрінісінен аксиомалар жүйесі түрінде абстракциялы берілу жолының кезеңдерін қадағалайтын боламыз.
Басты назарды бинарлық және унарлық (екі орынды және бір орынды) амалдарға аударамыз.
Себебі, олар жоғарғы оқу орындарында оқып, зерттелетін классикалық алгебралық жүйелердің негізгі амалдарының санына енеді.
Бұл тараудың материалдарын баяндау сандық жиындарда анықталған мектептегі әріптік алгебра мен онда анықталған арифметикалық (рационал) амалдарға алғашқы саяхаттан басталады. Осыдан кейін абстракциялық жиында берілген алгебралық амалдар концепциясына байланысты анықтамалар мен ұғымдар жүйесін оқып-зерттеуге көшеміз.
Жұмыс барысында бұл процесті іске асыру алдымен рационал сандарға негізделген, ал содан кейін нақты сандарға негізделген бірнеше ғасырлық (көпғасырлық) практиканың екендігін бірнеше қайтара атап өтіп отырамыз.
Екі орынды амалдардың аксиомалық берілуінің қасиеттерін мектептен белгілі, формальды әріптік теңдіктердің арифметикалық амалдарының заңдылықтары ретінде өрнектелуінен шыққандығын айта кетуге болады. Бинарлық алгебралық амал ұғымын анықтауға жетелеуші көптеген анықтамалардың мағыналық кері бейнесінің баламалары болып кәдімгі қосу, көбейту, алу, бөліктік амал бөлу және олардың қарапайым қасиеттері болып табылады. Алгебралық жүйелер класын абстрактілі сипаттауға (қатысты) байланысты қойылатын мақсаттың бірі ретінде қарастырылып отырған класта анықталған жүйенің негізгі амалдары мен қатынастарының қасиеттерін беруші тиімді аксиомалар жиынтығын таңдау болып табылады. Бұл жағдайда, бұл амалдар мен қатынастардың басқа қасиеттері сол сияқты жүйенің құрылымдық қасиеттері толығымен осы таңдап алынған аксиоматика негізінде анықталады, яғни олардыңсалдарлары ретінде алынады.
§1.1. Жиындар және оларда анықталған қатынастар
Жиын ұғымы математикада жиынтықтар, кластар, құрылымдар мен элементтердің (заттардың) көпбейнелері туралы интуитивті көріністерді кеңейтудің нәтижесінде қалыптасты және нәтижесінде жеке өздігінен бар объект ретінде белгілі болды. Жиындар теориясының негізін қалаушы Г. Кантор (1845-1918 ж.) жиын ұғымын біздің санамызға, интуициямызға тұтас бір объект ретінде анықталатын және бір-бірінен ажыратылатын кез келген жиынтық түрінде енгізді.
Осы тұжырымдауға сәйкес жиындар деп жоғарыда айтылған сипаттамалардың біреуін қанағаттандыратын осындай объектілер құрылымдарын айтуға болады. Бұл қасиетке қойылатын бір ғана талап - ол біздің интуитивті танымымызға (ұғынуымызға) қол жеткізу.
XIX-ғасырдың аяғына дейін жиынның интуитівті концепциясы ешқандай келіспеушілік тудырған жоқ. Осы концепцияның негізінде интуитивті жиындар теориясы құрылды. Бірақ, одан кейініректегі жиындар теориясының даму кезеңінде, жиын ұғымының осындай кең баяндалуы әртүрлі қарама-қайшылықтарды туғызды (жиындар теориясының еш зиянсыз парадокстары).
Қазіргі уақытта жиындар теориясы аксиомалық негізге орайластырылған (тұрақтандырылған) және осының нәтижесінде белгілі парадокстық (қарама-қайшылықтық) қасиеттерге ие жиындар толық жойылған. Себебі, қасиеттерді таңдауды шектейтін аксиомалар жүйесі арқылы жиынды қалыптастыру негізін құру мүмкін болды. Осыған қарамастан біз, әріректе, жиын ұғымы туралы интуитивті көрініске жүгінетін боламыз, себебі, аксиомалық жиындар теориясын мағыналық ұғыну, (интуитивті теория деңгейінде алынған), әруақытта терең ұғынылған жеткілікті ұғымдар мен нәтижелер бар деп ұйғарылады. Сонымен жиын деп белгілі бір ортақ қасиеттері бойынша топтастырылған объектілер жиынтығын (құрылымын) түсінетін боламыз.
Жиын - латын алфавитіндегі үлкен әріптермен, ал оның элементтері осы алфавиттің кіші әріптерімен белгіленетін болады. Бірақ, а-ның А жиынының элементі болатынын таңбалық түрде аА деп жазамыз.
Керісінше жағдайда, жазуын қолданамыз. әріптерімен әдетте, жиындардың нақты элементтері белгіленеді. Мысалға өрнегі жиының ішкі жиындарының жиыны.
жиының барлық ішкі жиындарының жиынын арқылы белгілейміз және жиының Булианы деп атаймыз, яғни
Булиан ұғымына байланысты байқайтынымыз - , бірақ .
§1.2. Жиындардағы амалдар
Барлық жиындар жиынтығында келесі төмендегі анықтамалдарға сәйкес келетін теоретикалық-жиындық 1) - қиылысу; 2) - бірігу; 3) \ - айырма амалдары енгізіледі.
1. және жиындарының қиылысуы деп бір уақытта осы және жиындарында жататын элементтерден құрылған жиынды айтамыз, яғни, және .
Нақтылы жиындарға амалын қолдану мысалдарын келтірейік:
а) ;
б) .
2. және жиындарының бірігуі деп осы жиындардың ең болмағанда біреуіне тиісті болатын элементтерден тұратын жиынды айтамыз, яғни,
немесе .
Мысалға:
а) .
б) Айталық,
және
болсын.
1-суретте жиынына тиісті координаталар жазықтығына тиісті нүктелер жиыны кескінделген.
Сурет 1
3. және жиындарының айырмасы деп -ға тиісті емес жиының элементтерінен тұратын жиынды айтамыз, яғни,
және .
Сонымен, және жиындарының айырмасы деп жиынындағы жиынының толығуын айтамыз.
Мысалдар:
а) егер өрнегі жазықтықтағы төртбұрыштың ромб болу қасиетін, ал - тіктөртбұрыш болу қасиетін білдірсе, онда өрнегі барлық шаршы болмайтын ромбтар жиыны;
в)
.
§1.3. Теоретикалық-жиындық амалдардың қасиеттері
жиындарына , , \ амалдарын бірнеше қайта қолданудың нәтижесінде қайтадан басқадан жаңа жиындарды аламыз.
Бұл жиындардың алу процесі - қадамдық сипаттағы индуктивтік процесс. Бұл процестегі әрбір қадам, екіншісінен бастап алғанда алдыңғы қадамға кез келген жиынға осы амалдардың кез келгенін бір рет қана қолдану арқылы алынады.Атап айтқанда:
0-қадам: Бұл қадамда жиындары алынады, яғни негізгі (берілген, бастапқы) жиындар 0-дік қадамның жиындары деп жарияланады.
Әрі қарай қадамындағы () барлық жиындар құрылған деп есептеледі және - осы қадамның кез келген жиындары.
- қадам: онда қадамның жиындары деп қадамының барлық жиындары және
түріндегі жиындар жарияланады.
Осыдан кейін келесі қадамға көшу орындалады.
Мысалы, жиындары бірінші қадамда алынса, ал
жиындары 2-ші нөмірлі қадамда алынады.
Алгебралық өрнектердегі сияқты жазуды жақшалардың көмегімен теоретикалық-жиындық амалдарды қолдануда да бір мәнді реттеуге болады. Бұл процесті орындау барысында бастапқы жиындардан әртүрлі сипаттағы амалдардың көмегімен алынған, бірақ осыған қарамастан өзара тең болатын жиындарда кездесуі мүмкін. Бұл теоретикалық-жиындық амалдардың сандарда анықталған арифметикалық амалдарға ұқсас белгілі бір анықталған қасиеттерінің бар болуына байланысты болады келеді.
Шын мәнісінде келесі теңбе-теңдіктер орынды:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
9) ;
10) ;
11) ;
12) ;
13) ;
14) ;
15) .
Бұл теңбе-теңдіктердің барлығы кез-келген жиындары үшін орынды, яғни жиындар теориясының теңбе-теңдіктері (заңдары).
1)-15) теңбе-теңдіктерді қамтылу әдісін қолданып, оңай дәлелдеуге болады. Осы әдістің 9-теңбе-теңдікті дәлелдеуге қалай қолданылатындығын көрсеттік
Дәлелдеу үшін екі қамтылуды көрсету қажет:
а) ;
б) .
а) Айталық, жане
және және
және ;
б) Айталық және және және және .
1)-15) тізіммен теоретикалық-жиындық амалдардың негізгі қасиеттерін көрсететін теңбе-теңдіктер келтірілген. Әрине, бұл тізімге енбеген басқа да теңбе-теңдіктер бар.
§1.4. Эйлер-Венн диаграммалары
және жиындарына теоретикалық-жиындық амалдарды қолдану нәтижесін көрнекі түрде кескіндеуді Эйлер-Венн диаграммасы арқылы беруге болады.
Ол үшін және жиындары жазықтықта геометриялық фигура түрінде кескінделеді. Көпшілік жағдайда бұл мақсат үшін эллипс немесе шеңбер таңдалып алынады.
Жиындардың элементтері ретінде осы фигуралардың ішінде немесе шекараларында жататын жазықтықтың нүктелері алынады. Онда, егер А және В жиындары 2а - суретіндегідей кескінделсе, онда үшін кескіндер 2б,в,г - суреттеріндегідей кескінделеді.
а) б)
в) г)
Cурет 2.
Көрнекі болу үшін диаграмманың сәйкес бөлігі штрихталып (боялып) көрсетілген.
Келесі жиындар үшін Эйлер-Венн диаграммаларын құрайық:
a) ;
б) .
a) Диаграммаларды тізбектей құруды жүргізейік. (сурет 3а,б,в - қара)
Сурет 3.
б) Ақырғы нәтижені көрсетейік (4-суретке қара).
Эйлер-Венн диаграммалар әдісі жиындардың теңбе-теңдігінде көрнекі түрде негіздеуге мүмкіндік береді. Ол үшін бірінші диаграммада теңбе-теңдіктің сол жақ бөлігіне сәйкес келетін жазықтықтың бөлігін штрихтың көмегімен бөліп аламыз. Осылай теңбе-теңдіктің оң жақ бөлігін анықтаймыз. Осыдан кейін штрихталған облыстарды салыстырамыз. Облыстардың сәйкес келуі беттесуі бізге берілген жиындардың шын мәніндегі теңдігі туралы қорытынды шығаруға мүмкіндік береді.
Сурет 4.
Мысалға, Эйлер-Венн диаграммасын пайдаланып,
теңбе-теңдігін негіздейік.
Бұл жиынның сол жақ бөлігіне сәйкес келетін диаграмма 5а-суретінде кескінделген. Сол жағына сәйкес келетін диаграмма 5б-суретінде кескінделген.
Сурет 5.
Бұл суреттердегі екі рет штрихталған жазықтықтың бөліктері бір-біріне тең. Шын мәнісінде бұл облыстар дәлелдеуді қажет ететін (дәлелденетін) теңбе-теңдіктің сол және оң жақ бөліктеріне сәйкес келеді.
§1.5. Жиындардың декарттық көбейтіндісі
Жазықтықта тікбұрышты декарттық координат жүйесін енгізу осы жазықтықтағы әрбір нүктесімен және нақты сандарымен жұбын байланыстыруға мүмкіндік береді, және сандары нүктесінің координаталары деп, және бұл жағдайда - бірінші координатасы (абцисса) деп, ал - екінші координатасы (ордината) деп саналады. Нүктенің координаталары болатын жұбы екі элементті жиынынан мүлдем басқа (мағыналық түрде ажыратылады), себебі, жиындардың теңбе-теңдігі қатынасының анықтамасы бойынша: .
Ал, болғанда және жұптары әртүрлі нүктелерді анықтайды. жұбының теоретикалық-жиындық мағынасы , ал жұбының теоретикалық-жиындық мағынасы , сондықтан , яғни және жұптары тең емес.
Сонымен, координаттық жұбы - бұл екі элементті жиын және оның элементтеріне қатысты қайсысы бірінші, қайсысы екінші деп есептеу туралы келісім қабылданған.
Бұл мағынадан алғанда координаталық жұп - реттелген екі элементті жиын немесе реттелген жұп.
Жалпы жағдайда және элементтері әр түрлі және жиындарынан алынуы мүмкін.
Бірақ бұрынғы анықтамадағы сияқты жұбын реттелген деп санаймыз. Яғни, егер болса, онда .
элементі жұбының бірінші координатасы деп, ал элементі оның екінші координатасы деп аталады. Жалпы алғанда жұптардың теңдігі туралы да айтуға болады.
Кез келген реттелген және жұптары үшін келесі теңдік орынды:
.
Реттелген жұптар ұғымы негізінде және жиындарының декарттық көбейтіндісі ұғымы енгізіледі. Айталық, және кез келген бос емес жиындар болсын. және жиындарының декарттық көбейтіндісі деп түріндегі барлық реттелген жұптардың жиынын айтамыз, мұндағы және .
Сонымен, .
Мысал. Егер және болса, онда
.
Лемма 1.5.1. Егер және жиындары сәйкесінше элементті және элементті ақырлы жиындар болса, онда ақырлы элементті жиын болады.
Ақырлы жиындардың декарттық көбейтіндісін кесте арқылы берген өте ыңғайлы.
Айталық, және болсын.
және жиындарының декарттық көбейтіндісінің элементтері элементтерін кестеге келесі түрде орналастырған өте ыңғайлы (1 кестені қара).
1- кесте
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Бұл кестенің жолдары жиынының элементтерімен нөмірленсе, ал бағаналары жиынының элементтерімен нөмірленеді. Яғни, жұбы жол нөмірі , ал бағана нөмірі болатын тор көзде орналасады.
Егер және сандық жиындар болса, онда жиынын декарттық жазықтық нүктелер жиынымен сәйкес қоюға болады. Мұндағы .
Бұл ішкі жиын декарттық көбейтіндісінің графигі деп аталады.
Мысалға, 6а,б-суреттерінде декраттық көбейтіндісінің графигі кескінделген, мұндағы,
a) ;
б) ]}.
Сурет 6.
Бұдан байқайтынымыз 6б - суретіндегі жағдайда декарттық көбейтіндінің графигі тік төртбұрышының барлық нүктелер жиыны болса, ал функциясының графигі осы тік төртбұрыштың ішінде жататын синусоиданы анықтайтын нүктелер жиыны.
Бірнеше (үш және одан да көп) жиындардаң декарттық көбейтіндісін анықтау индуктивті әдістің анықтамасы туралы алғашқы түсінікті талап етеді.
Индуктивті анықтама - бұл n натурал параметрге тәуелді ұғымын анықтау.
Айталық, саны өрнегінің мағынасы болатын параметрінің ең кіші мәні болсын. Анықталатын ұғымның ерекшелігіне байланысты саны 0,1,2,.., т.т. сандар болуы мүмкін, яғни, жалпы жағдайда .
Индуктивті анықтама келесі сызба бойынша іске асады:
a) - ұғым, яғни ұғым n параметрінің ең кіші мәні үшін тікелей анықталады.
б) Әрі қарай кез келген натурал саны үшін ұғымы анықталған жорамалдың негізінде барлық үшін ұғымын анықтауға мүмкіндік беретін ереже қалыптасады.
Әдетте, a) пунктін индуктивті анықтаманың базисі немесе индукция базисі деп, ал б) пунктін индуктивті қадам (инуктивті жорамал негізінде құрылған) деп атайды.
Көпшілік жағдайда индуктивтік қадамды екі ішкі қадамға бөледі: б.1) индуктивтік жорамал, б.2) индуктивті қадам. Қарастырылып отырған жағдайда ұғымы n жиындарының декарттық көбейтіндісі өрнегін анықтау болып табылады.
ретінде 2 санын аламыз, себебі көбейту екі орынды амал болғандықтан тек осы жағдайда ғана көбейтінді туралы индукцияның мағынасы сақталады.
a) Индукция базисі (n=2) және жиындарының декарттық көбейтіндісінің анықтамасы 1 анықтамаға сәйкес келеді, яғни,
.
б1) Индуктивтік жорамал (n=k).
Айталық кез келген бос емес жиындарының декарттық көбейтіндісі анықталған деп санайық.
б2) Индкутивтік қадам (n=k+1),
деп алайық.
Жеке жағдайда бұл анықтамадан шығатыны:
.
жиындарының элементтері реттелген үштіктер (немесе ұзындығы 3 болатын кортеж) деп аталады және ішкі жақшаларды алып тастап түрінде жазылады. Осыған ұқсас жиынының элементі реттелген n-діктер (немесе ұзындығы n кортеж) деп аталады және арқылы белгіленеді.
Анықтама бойынша жиындардың декарттық көбейтіндісі қайтадан жиын болғандықтан жиындардың декарттық көбейтіндісінің ішкі жиындары, олардың бірігулері, қиылысулары және т.т. туралы да айтуға болады. Декарттық көбейтінді амалының қасиеттерімен қатар, оның (бірігу),
(қиылысу), \ (айырма) амалдарымен үйлесімдік қасиеттері де пайда болады.
Біріншіден, қасиеттер мен басқа да жаңа енгізілген ұғымдармен байланыс жаңа ұғымдардың нақтылы өзіндік белгілеріне ие болады. Ал бұл әріректе олар әртүрлі мәтіндерде кездескен жағдайда ажырата білуге көмектеседі.
Екіншіден, математикалық пәндердің фрагменттерін оқып- үйрену аясында жаңа ұғымдармен тікелей жұмыс істеу қазіргі заманғы математика мен олардың қосымшаларында бұл ұғымдарды жаттықтыруға (қалыптастыруға) дайындайды және олардың қалай өзгеретіндігін аңғартады.
амалының анықтамасына қайта оралсақ, байқайтынымыз, реттелген жұптар мен екі жиынның декарттық көбейтіндісінің анықтамасына сәйкес, амалы коммутативті емес, бірақ ассоциативті.
және амалдарының бірқатар үйлесімді қасиеттерін келтіре кетейік: Кез келген жиындары үшін
а) ;
б) ;
в) ;
г) ;
д) ;
e) ;
ж) ;
Бұл қасиеттердің (теңбе-теңдіктердің) әрқайсысын қамтылу әдісімен дәлелдеуге болады.
Мысал ретінде в) - пунктінің дәлелдеуін келтірейік.
Айталық
.
Сонымен, .
Кері қамтылуды осыған ұқсас әдіспен алуға болады.
декарттық көбейтіндісі жиынының декарттық n дәрежесі деп аталады және A(n=2,...) арқылы белгіленеді. Егер М ақырлы жиын болса, онда арқылы осы М жиынының элементтерінің санын белгілейтін боламыз.
Лемма 1.5.2. Егер М ақырлы жиын және , болса, онда .
§1.6. Сәйкестіктер және олардың берілу тәсілдері
Әртүрлі жиынтықтардың элементтерінің арасындағы сәйкестік ұғымы туралы интуитивті түсінік әрбір адамға тән және оны келесі түрде тұжырымдауға болады: егер және кез келген бос емес жиындар болса, онда жиынының жиынына сәйкестігі деп декарттық көбейтіндісінің ішкі жиынын айтады.
Сәйкестіктер, әріректе, латын алфавитінің үлкен әріптерімен белгіленетін болады. Яғни, . Анықтамаға сәйкес -ның -ға сәкестігі - бұл кейбір реттелген жұптар жиыны, мұндағы Егер болса, онда жиынының элементі жиынының элементіне сәйкес келеді деп атайды. жазуының орнына жазуын қолданады. Әрбір сәйкестікпен оның анықталу және мәндер облыстары байланысты.
Егер жиынының жиынына сәйкестігі болса, онда
осы сәйкестігінің анықталу облысы деп аталады, ал
жиыны осы сәйкестіктің мәндер облысы деп аталады.
Сонымен, осы сәйкестігіне тиісті жиындардың бірінші координаталар жиыны болса, онда оның екінші координаталар жиынын құрайды.
Айталық, мысалға, және болса,
.
Сәйкестіктің анықтамасының кейбір ерекшеліктерін келесі жаттығу көрсетеді: егер сәйкестік болса, онда болатынын көрсетіңдер. жиынының жиынына болатын жиындарын және сәйкестігін табыңдар.
жиынының жиынына сәйкестіктерін берілу тәсілдеріне тоқтала келе байқайтынымыз, сәйкестікті берудің әмбебап әдісі - бұл жиынының тек таңдалып алынған реттелген парларының координаталары осы сәйкестікте болатындығын көрсететін нақты қасиетті (белгіні) көрсету. Әрине бұл жағдайда, предикативтік емес сипаттағы қасиеттерден аулақ болу керек.
Сонымен қатар, тексеру оңай және нәтижелі жүргізілетін қасиеттерді пайдаланған абзал.
Айталық, мысалға, болсын. жиынының жиынына сәйкестігін келесі түрде анықтайық: үшін , егер - нольден өзгеше жұп сан және - дауысты дыбыс (әріп) немесе егер - тақ сан және - дауыссыз дыбыс (әріп).
Әрине бұл көрсетілген қасиеттер сәйкестігіне тиісті жиынының барлық парларын жазып шығуға мүмкіндік береді.
Ақырлы жиындардың арасындағы сәйкестіктерді көрнекі түрде көрсетуге болады. Осылардың бірнешеуін сипаттайық.
Ақырлы және жиындарының арасындағы сәйкестіктерді оларға тиісті барлық жұптар арқылы жазып шығуға болатындықтан онда оны көрнекілік үшін 1-кесте түрінде беруге болады (§1.5. қараңыз). Айталық, мысалға, болсын.
Онда, жиынының жиынына сәйкестігін 2-кесте түрінде беруге болады.
.
2 - кесте
Әрине, егер сәйкестік жиынының өзіндік ішкі жиыны болса, онда оның кестесінде бос тор көздер (клеткалар) болады.
Ақырлы жиындардың арасындағы сәйкестікті бағдарланған графтың көмегімен де беруге болады.
Бағдарланған граф деп (бейресми түрде) жазықтықтың ақырлы нүктелер жиыны (графтың төбелері) мен олардың кейбір төбелер жұптарын өзара қосатын (бағыты көрсетілген) бағытталған доғаларды (графтың бағытталған қабырғалары) айтады. Бұл жағдайда, егер жиынының жиынына сәйкестігі қарастырылатын болса, онда графтың төбесі ретінде жиынының элементтерін жиынының элементтеріне сәйкес қоюшы жазықтықтың нүктелері алынады.
Белгілі бір доғалар жиынтығын бағыт арқылы бере отырып жиынының кейбір нүктелеріне жиынының сәйкес келуші нүктелерін графтың бағдарланған қабырғалары түрінде анықтаймыз. Бұл жағдайда нақты сәйкестігінің (жиынының жиынына) анықталу облысы осы жиынының бағдарланған қабырғалары шығатын нүктелер жиыны, ал мәндер жиыны - осы қабырғалар енетін жиынының нүктелер жиыны (бағдарланған граф 7 - суретте келтірілген).
Сурет 7.
Сәйкестіктердің арнайы түрлерін қарастырған жағдайда (мысалы, эквиваленттік қатынасын қарастырған жағдайда) сәйкестікті қима түрінде беру өте ыңғайлы. Егер жиынының жиынына сәйкестігі және болса, онда жиынын сәйкестігінің элементі бойынша қимасы деп аталады.
Ақырлы жиынының жиынына сәйкестігін әрбір элементі үшін қималарын толық жазып шығу арқылы беруге болады.
Айталық, мысалға, арифметикалық амалдар үшін таңбалар жиыны болсын.
және үшін сәйкестігінің келесі қималарды беретіндігін түсіну қиын емес
.
Жоғарыда және жиындарының декарттық көбейтіндісін график түрінде беруге болатындығы туралы айтылған болатын. жиынының жиынына сәйкестігі жиынының ішкі жиыны түрінде берілетін болғандықтан, онда декарттық көбейтінің бұл берілу әдісі сәйкестіктің берілу тәсілі ретінде қабылданады.
§1.7. Сәйкестіктерде анықталған амалдар
жиынының жиынына сәйкестігі жиын болып табылады, сондықтан сәйкестіктердің теңдігі мен қамтылуы туралы, бір сәйкестіктің екінші сәйкестікпен қиылысуы, бірігуі және толықтауышы туралы да айтуға болады. Сәйкестіктер жиынтығында сонымен қатар кері сәйкестікті анықтау және оларды көбейту (композиция) амалдары анықталған.
1. Айталық, кейбір сәйкестік болсын.
ережесімен анықталған сәйкестігі сәкестігімен қайтымды сәйкестік деп аталады.
Әрине, егер болса, онда .
Сонымен, сәйкестігіне кері сәйкестікті алу үшін ондағы парлардың координатасының орындарын ауыстыру қажет.
Мысалы, егер сәйкестігі бағдарланған граф түрінде берілсе, онда сәйкестігін анықтау үшін барлық бағыттарды қарама - қарсыға ауыстыру керек.
2. Айталық -ның -ға сәйкестігі және -ның -ғасәйкестіктері берілсін.
Онда жиынының жиынына сәйкестігі келесі ережемен анықталады:
және ол және сәйкестіктерінің көбейтіндісі (немесе композициясы) деп аталады.
Анықтама 1.7.1. және болатын және сәйкестіктері үшін болсын.
Онда және ØØ.
Жоғарыда енгізілген кез келген сәйкестіктері үшін келесі теңдіктерді қанағаттандыратың бірнеше қасиеттерді атап өтейік:
а)
б)
в)
г)
д)
Мысал үшін қамтылу әдісін қолданып б) пунктінің дәлелдеуін, яғни
қамтылуларын дәлелдейік.
Айталық жиынының жиынына сәйкестігі , ал жиынының жиынына сәйкестігі болсын.
Онда:
Екінші қамтылу осыған ұқсас дәлелденеді.
Егер сәйкестіктің анықтамасында деп алсақ, онда -ның -ға (өз-өзіне) сәйкестігін аламыз.
Мұндай сәйкестіктің қарапайым мысалы А жиынының диагоналі деп аталатын
сәйкестігі.
Бұл терминологияны келесі түрде түсіндіруге болады.
Егер жиыны ақырлы және сәйкестігі кесте түрде берілсе, онда жұптары осы кестенің бас диагоналін құрайтын торкөздерден тұрады, ал басқа тор көздер бос болады.
Егер жиынының жиынына сәйкестігі болса, онда
болатынын тексеру қиын емес.
Көбейту (композиция) және кері сәйкестікті алу амалдарының теоретикалық-жиындық және амалдарымен байланысуының негізгі қасиеттері келесі мысалдарда келтірілген.
Егер кез келген сәйкестіктер болса, онда:
а)
б)
в)
г)
д)
е)
§ 1.8. Бейнелеулер
Жиындардың арасындағы сәйкестіктердің маңызды түрлерінің бірі болып бейнелеулер табылады.
жиынының жиынына сәйкестігі жиынының жиынына бейнелеуі (немесе -дан -ға функция ) деп аталады, егер келесі шарттар орындалса:
1.
2. .
Егер сәйкестігі бейнелеу болса, онда жазуымен қатар жазуында қолданамыз. Бұл жағдайда элементі элементінің кері бейнесі, ал элементі элементінің осы бейнелеуіндегі бейнесі деп аталады. (8 - суретке қара)
х
у
А
В
Dom Ф=А
Im Ф=А
Ф
Ф
у = Ф(х)
Сурет 8.
жазуы, әріректе, жиынының жиынына бейнелеуі дегенді білдіреді.
Келесі тұжырым қима терминіндегі бейнелеудің қарапайым сипаттамасын береді.
Бейнелеудің анықтамасындағы 1 - шарт , ал (екінші) 2 - шарт сәйкестігінің кез келген элементі бойынша қимасында ең көп дегенде бір элемент болады деген шарттармен пара - пар.
Бейнелеу ұғымын кері сәйкестік алу және сәйкестіктердің көбейтіндісі амалдары тілінде сипаттау практикалық қолдану тұрғысынан алғанда қызығушылық туғызады.
сәйкестігі бейнелеу болады, сонда тек қана сонда, егер келесі шарттар орындалса:
а) ;
б) .
Бір ғана ұғымның екі анықтамасының тең мәнділігін (тең ағыналылығын) дәлелдеу көптеген жағдайларда маңызды.
Ұғымды әртүрлі терминдерде беру оның мағынасын терең түсінуге көмектессе, екіншіден оларды анықтаушы қатынастардың арасындағы байланысты анықтай түседі. Мұндай қорытындыларды ала білу тәжірибесі формаль аксиоматикалық теориялар әдісін меңгерудін қажетті кезеңі болып табылады.
Базистік (1, 2 шарттар) және жоғарыда келтірілген (а, б шарттары) бейнелеу ұғымының келтірілген екі анықтамаларының теңмәнділігін дәлелдейік.
) Айталық, -ның -ға бейнелеуі болсын.
а) және б) шарттарының орындалатындығын көрсетейік.
а) болсын делік. Бейнелеудің анықтамасының 1-шарты бойынша элементі үшін элементі табылып болады. Онда, , яғни .
б) болсын делік. Онда -ның -ға сәйкестігі болғандықтан, онда -ның -ға сәйкестігі болады, яғни, және болатындай элементі табылады. Сондықтан, , себебі, үшін бейнелеудің анықтамасының 2 - шарты орындалады.
) Айталық, енді сәйкестігі үшін екінші анықтаманың а) және б) шарттары орындалған болсын.
Бейнелеу ұғымының қима тіліндегі сипаттамасына сәйкес ол үшін келесі тұжырымды дәлелдеу керек:
және кез келген элементі үшін - қимасы бір элементті.
Шын мәнісінде болғандықтан, онда теңдікті дәлелдеу үшін тексеру жеткілікті.
Айталық болсын. Онда, а) шартты сәйкестікте , яғни элементі табылып және , ал бұл дегенді білдіреді. Әрбір қимасының бірэлементті болатынын кері жору әдісімен дәлелдейік. Айталық, кейбір элементі үшін қимасында ең болмағанда екі және элементтері жатқан болсын.
Онда және , яғни және . Бұдан алатынымыз, бейнелеулердің көбейтіндісі амалының анықтамасына сәйкес, , яғни .
мен қатысты алынған қарама - қайшылық дәлелдеуді толық аяқтайды.
Алынған сипаттамалардың практикалық қолданыстарын келесі жаттығудан көруге болады.
Лемма 1.8.1. Егер және бейнелеулер болса, онда бейнелеу болады.
сәйкестігінің бейнелеу болатынын көрсету үшін бейнелеудің операция тілі сипаттамасында а) және б) шарттарының орындалатындығын тексеру жеткілікті.
Яғни, а) ;
б) болатынын тексеру керек.
Әдетте бұл шарттарды студенттер өздіктерінен тексере алады. Бейнелеулердің кейбіреулері математикадағы маңыздылығына байланысты арнайы аттарға ие болған.
жиынының жиынына бейнелеуі :
а) сюръективті деп аталады, егер болса;
б) инъективті деп аталады, егер
болса;
в) биективті деп аталады, егер ол бір уақытта сюръективті және инъективті болса.
Енгізілген ұғымдардың қазақ тіліндегі мағыналарын келесі түрде түсіндіруге болады:
а) сюръективті бейнелеу барлық жиынына бейнелеу дегенді білдіреді;
б) инъективті бейнелеу жиынының кейбір ішкі жиынына бейнелеуді білдіреді және бұл жағдайда жиынының әрбір элементінің тек бір ғана кері бейнесі болады.
в) биективті бейнелеу бір уақытта сюръективті және инъективті бейнелеу болғандықтан ол жиынының жиынына өзара бірмәнді бейнеленуі дегенді білдіреді.
Осы сюръективті, инъективті және биективті бейнелеулердің ерекшеліктерін сипаттаушы сурет төменде келтірілген (сурет 9, а,б,с - қара).
А
В
а)
А
В
В1
б)
А
В
в)
Сурет 9.
II ТАРАУ
ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1. Математикалық логика термині. Логика сөзінің негізі грек тілі. Лого сөзін грек тілінен әртүрлі мағынада аударуға болады: сөз, ұғым, ой, таным.
Жалпы философиялық термин сапасында бұл сөзді әлемдегі жалпы заңдылықтарды белгілеу үшін қолданады.
Математикалық логика - бұл дұрыс математикалық ой-пайымдаулар, математикалық (ойлау) талдауларды нақты ғылымдарда қолдану туралы ғылым.
Математикалық логикада ойлау заңдылықтары талданады және оқып зерттеледі. Математикада дұрыс ой-пайымдаулар маңызды рөл атқарады. Сондықтан, дұрыс ой-пайымдауларды математикалық логика деп атағанға ешқандай таң қалуға болмайды.
Математикалық логика терминінің орнына кейде формальдық логика, символдық (таңбалық) логика терминдері де қолданылады.
Элементар математикалық логика тек ғана ақиқат немесе тек ғана жалған болатын оқиғаларды зерттейді.
Қазіргі уақытта оқиғаны нақты сипаттау үшін математиканың тілі, оқиғаны түрлендірудің нақты сипаттамасының тілі қолданылады. Бұл тілді есептеу машиналарының түсінетіндігін айта кету керек.
Оқиға мен нақты түрлендіруді математикалық сипаттаудың зерттеу негізі (базасы) математикалық логика мен субрекурсивті алгоритмдер теориясы болып табылады.
2. Математикалық логиканың қалыптасуы. Ой-пайымдаулар ережелерін алғашқы рет бір жүйеге келтірген Аристотель деп айтуға болады.
Бұл ережелер силлогизмдер деп аталған.
Математикалық логиканың келесі бір даму жолының кезеңін математик және философ Лейбництің идеяларына жатқызуға болады.
Қазіргі математикалық логиканың дамуының басталуына ХІХ ғасырдың ортасындағы Джордж Бульдің Математикалық талдау және Ойлау Заңдары еңбектерін жатқызуға болады. Дж.Буль тұжырымдар санағы мен логикалық амалдарды [және, немесе, емес] енгізді. Кейініректе Фреге жалпылау және бар болу кванторларын енгізуді ұсынды.
Жеткілікті шамада ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Қ. Жетпісов
МАТЕМАТИКАЛЫҚ ЛОГИКА ЖӘНЕ
ДИСКРЕТТІ МАТЕМАТИКА
Қазақстан Республикасы Білім және ғылым
министрілігі оқулық ретінде бекіткен
Алматы, 2011
ӘОЖ 510 (075.8)
ББЖ 22.12 я73
Ж 56
Пікір жазғандар:
Е. С. Смаилов - Қолданбалы математика институты Республикалық мемлекеттік қазыналық кәсіпорынның директоры ф.-м. ғ.д., профессор;
У. У. Өмірбаев - Л. Н. Гумилев атындағы Евразия ұлттық университе-тінің алгебра және геометрия кафедрасының меңгерушісі ф.-м.ғ.д., профессор;
Қ. Оспанов - Л. Н. Гумилев атындағы Евразия ұлттық университетінің есептеу және қолданбалы математика кафедрасының профессоры, ф.-м.ғ.д..
Жетпісов Қ.
Ж 56 Математикалық логика және дискретті математика:оқулық жоғары оқу орындарының студенттеріне арналған. - Алматы: ЖШС РПБК Дәуір, 2011.- 264 бет.
ISBN 978-601-217-186-0
Оқулық математикалық логика, дискретті математика атты екі бөлімнен тұрады.
Математикалық логика бөлімінде жиындар теориясының элементтері, тұжырымдар алгебрасы мен тұжырымдар санағы, предикаттар санағы мен алгебралық жүйелер туралы айтылады. Бұл бөлімде математикалық логиканың негізгі теоремалары дәлелденген. Атап айтқанда, Левенгейм-Сколем теоремасы, Гедель теоремасы, Мальцевтің локальдық теоремасы т.т.
Дискретті математика бөлімінде графтар теориясының негіздері, кодтау теориясының элементтері, логикалық желілер мен ақырлы автоматтар туралы баяндалады.
Оқулық университеттердің математика, информатика, ақпараттық жүйелер мамандықтары бойынша білім алушы студенттерге арналған.
ISBN 978-601-217-186-0
Ж
(C) Жетпісов Қ., 2011 ж.
(C) ҚР Жоғары оқу орындарының
қауымдастығы, 2011 ж.
Алғы сөз
Математикалық логика және дискретті математика оқулығы екі бөлімнен тұрады.
Оқулықтың бірінші бөлімі - математикалық логика. Ол автордың Х. Дулати атындағы Тараз мемлекеттік университетінің ақпараттық жүйелер кафедрасының доценті Ж. А. Түсіповпен бірлесіп жазған 2000 жылы жарық көрген Математикалық логика оқу-құралының негізінде жазылған.
Онда қарастырылған мәселелер: жиындар теориясына кіріспе, тұжырымдар алгебрасы, тұжырымдар санағы, предикаттар санағы, алгебралық жүйелер және модельдер теориясына кіріспе.
Модельдер теориясына кіріспе тарауында теоретикалы-модельдік алгебра мен предикаттар санағы тілінің арасындағы байланыстар туралы алғашқы мағлұматтар берілген.
Атап айтқанда, элементар ішкі модель, элементар эквивалентті және изоморфты модельдер, модельдің диаграммалары, алгебралық жүйелердің элементар тізбегі қарастырылған.
Алгебралық жүйелер тарауында предикаттар санағының негізгі теоремалары толығымен дәлелденген.
Оқулықтың екінші бөлімі үш тараудан тұрады.
Графтар теориясының негіздері деп аталатын алтыншы тарауда графтар мен оның бөліктері, элементтері (тізбек, жол, цикл және контур) бөлікті графтар, ішкі графтар, графтарда анықталған амалдар мен қатынастар, графтардың сыбайластық және инциденттік матрицалары, графтың дәрежесі, эйлерлік және гамильтонды графтар, графтағы ең қысқа жолды табу алгоритмі сияқты сұрақтар қарастырылған. Кодтау теориясының элементтері тарауында әріптік және сандық кодтаулар, тиімді кодтау, қателерді ажырататын және түзететін кодтар, Хеминг коды туралы айтылған.
Әріптік кодтардың мысалы ретінде Морзе коды келтірілген.
Логикалық желілер және автоматтар атты сегізінші тарауда Буль функциялары арқылы анықталған функционалдық сызбалар, логикалық желілер, автоматтардағы периодты тізбектер туралы мағлұматтар берілген.
Әрбір тараудың соңында мысалдар келтіріліп, есептер мен жаттығулар берілген.
Көптеген есептердің шығару тәсілдері көрсетілген.
Оқулықта байқалған кемшіліктер болса және басқа да тілектеріңізді Е. А. Бөкетов атындағы Қарағанды мемлекеттік университетінің математика факультетінің Т. Ғ. Мұстафин атындағы алгебра, математикалық логика және геометрия кафедрасына жолдауларыңызды сұраймын.
МАТЕМАТИКАЛЫҚ
ЛОГИКА
I. ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТЕРІ
II. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
IІI. аксиомалық Әдіс. санақ.
ІV. ПРЕДИКАТТАР САНАҒЫ
V. АЛГЕБРАЛЫҚ ЖҮЙЕЛЕР
I ТАРАУ
ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
Жиындар теориясының негізі XIX ғасырда Кантор еңбектерінде құрылған. Оған негізгі себеп математикалық талдауды құру және негіздеу проблемасы болды. Әріректе, осы математикалық талдау берген алғашқы серпін мен оның негізгі концепицяларының дамуы және оларды талдау мен қатаң түрде ұғынудың қалыптасуы қазіргі заманғы аксиомалық жиындар теориясына негіз болды.
Математиканың дамуына тигізген жиындар теориясының үлкен ықпалы қазіргі заманда барлығымыз мойындаған факт. Сондықтан, жоғарғы оқу орындарында математиканы оқытуда жиындар теориясының идеялары мен әдістерінің маңызды роль атқаратындығы толығымен заңдылық. Жиындар теориясының интуитивті негіздерін жүйелі оқып-зерттеу кез келген қазіргі заманғы математикалық пәндерді табысты оқып-зерттеудің айрылмас құраушысы болып табылады.
Бұл тараудың негізгі оқып-зерттеу объектісі теоретикалы-жиындық амалдар мен қатынастар және сонымен қатар олармен байланысты қарапайым құрылымдар болып табылады.
Материалды баяндау жиын ұғымы туралы көріністі интуитивті ұғыну негізінде іске асырылады.
Алғашқы ұғым ретінде жиын ұғымымен қатар элементінің жиынына тиісті болу қатынасы ұғымы пайдаланылады (). Жиын өзінің элементтерімен толығымен анықталады деген қағиданы ұстанып жиынды берудің (жиынның берілуінің) айқын әдісімен қатар шыршықтау принципіне негізделген әдісті пайдаланамыз.
Жиынды әртүрлі әдістермен анықтай отырып, біз алдын-ала оның ең болмағанда бір элементінің болатындығы туралы айта алмаймыз. Осы себепті, бос жиын ұғымын енгізу қажеттілігі туындайды. Алдағы уақытта, элементтің жиынға тиісті болу термині ұғымында қамтылу қатынасы мен жиындардың теңдігі енгізіледі. Ал бұлар содан соң жиындардың теңдігін дәлелдеудің негізгі әдісі ретінде қамтылу әдісін негіздеуге және қолдануға көмектеседі.
Бұл ұғымдарды енгізу процесінде ; ; қатынастарының арасындағы айрықша ерекшеліктерге ерекше көңіл аударылады.
Теоретикалы-жиындық амалдар ; ; \ - бірігу, қиылысу, айырма жаңа жиындарды құрудың әдістері ретінде пайдаланылады және әріректе, ешқандай проблемасыз аксиомалық жиындар теориясын оқып-зерттеуге көшуге көмегін тигізеді. Бұл сонымен қатар, берілген жиынның ішкі жиындарының жиынын алу және реттелген пар жиындарды алу амалдарына да қатысты. Теоретикалы-жиындық амалдардың қасиеттері қос-қостан топталады. Бұл және бірігу және қиылысу амалдарының қосалқылық сипатын көрсетеді және ол жиындар алгебрасында және басқа да математикалық жүйелерде қосалқылық заңын ұғынудың пропедитивті негіздерін қалайды.
Универсал жиынның кейбір ішкі жиындарының арасында орын алуы мүмкін қарапайым қатынастар мен тәуелділіктерді графиктік кескіндеу үшін Эйлер-Венн диаграммасы қолданылады.
Универсал жиынның кейбір ішкі жиындарынан құрылған күрделі өрнек үшін оларға ; ; \ амалдарын бірнеше қайтара (бірақ ақырлы рет) қолдану арқылы Эйлер-Венн диаграммасы қарапайым қатынастар мен тәуелділіктерге сәйкес келуші диаграммаларды топтастырудың көмегімен құрылады және ол күрделі өрнек құрайды.
Мұндай диаграмаларды құру процесінде интуитивті деңгейде жиындар теориясының формулалары мен ішкі формулалары ұғымдары енгізіледі. Бұл алдағы уақытта, формальді тіл мен логикалық санақтың дедуктивті құралдарын анықтаудың базалық процедуралық негізгі ретінде индуктивті әдісті қолданудың ерекшеліктерін түсінуде басты роль атқарады.
Екі жиынның декарттық көбейтіндісін енгізудегі жұмыста бастапқы нүкте ретінде жазықтықтағы тік бұрышты декарттық координаталар жүйесі концепциясы алынады.
Жиындардың берілуінің алдыңғы (ертеректе) келтірілген әдісіне қосымша ретінде екі ақырлы жиынның декарттық көбейтіндісін сипаттаудың кестелік әдісі мен график арқылы оның көрнекі берілу әдісі беріледі. Осыдан кейін, мысал арқылы кесіндідегі үзіліссіз функциясының графигі мен және жиындарының декарттық көбейтіндісі -ның графигінің арасындағы айырмашылықтары мен ұқсастықтары көрсетіледі, мұндағы және сандары кесіндісіндегі осы функцияның, сәйкесінше, ең үлкен және ең кіші мәндері.
Бірнеше жиындардың декарттық көбейтіндісін табу үшін анықтаудың индуктивті әдісі қолданылады.
Оқытудың мазмұндық негіздеу концепциясының қарарларын іске асыра отырып, бұл тарауда, жаңа декарттық көбейтінді амалын енгізуге байланысты, негізгі амалдардың қасиеттерін анықтаумен қатар оның негізгі ; ; \ амалдарымен үйлесімді қасиеттерін анықтау сұрақтары туындайды.
Сонымен, ертеректе енгізілген ұғымдардың мазмұндық өрісінің тармақталу процесінде оларды жаңа мазмұндармен толықтыру мүмкіндіктері қолданылады.
Мұндай тәсілдің өміршеңдігін атай отырып, жұмыста әдістемелік сипаттағы келесі қарарлар тұжырымдалады (универсал қолдануға ие):
а) Жаңадан еңгізілген ұғымдардың басқа да, ертеректе анықталған ұғымдармен байланысын және ерекшеліктері мен қасиеттерін анықтау. Бұл жаңа ұғымдарға нақты ажыратушы белгілер береді және олар белгілі бір контексте пайда болған жағдайда оларды тануға, ажыратуға көмектеседі.
б) Жаңа ұғымдармен тікелей жұмыс (олардың ең қарапайым түрінде) математикалық пәндерді оқып-зерттеудің фрагменттік шеңберінде, бұл ұғымдардың әртүрлі байытылу мен трансформациялар ерекшеліктерін қолдануда өзіндік (қалыптасу) үйрену дайындығы және бұл ұғымдардың қазіргі заманғы математика мен оның қосымшаларындағы әртүрлі облыстары болып табылады. Жиындардың декарттық көбейтіндісінен сәйкестіктерге, олардың берілу тәсілдері мен оларға қолданылатын амалдарға көшу табиғи түрде орындалады. Ақырлы сәйкестіктер, декарттық көбейтіндінің ішкі жиыны ретінде бағдарланған графтар мен қималар арқылы да берілуі мүмкін.
Сонымен, ұғымдарды байыту өзінен кейін тікелей оларды мазмұндық ұғынумен, сезінумен қатар жүретін байыту мүмкіндігі. Сондықтан оны сипаттық суреттерде, сызбаларда, графиктерде және басқа да геометриялық сипаттағы баламаларда іске асырған дұрыс. Бұл үшін, сәйкестіктердің берілу тәсілдеріне байланысты материалдар үлкен мүмкіндік береді.
Сәйкестік ұғымы белгілі теоретикалық-жиындық амалдар мен декарттық көбейтінді амалынан басқа тағы екі амал енгізуге мүмкіндік береді: кері сәйкестік алу амалы мен сәйкестіктерді көбейту (композиция) амалы. Бұл амалдар ұғымын тармақтауға кезекті қадам жасауға жол ашады.
1.7 параграфында жоғарыда келтірілген әдістемелік сипаттағы а), б) қарарларын іске асыру аясында жаңа амалдардың қасиеттері анықталады. Тарауды жиындар теориясының ең бір маңызды ұғымы - бейнелеу ұғымын аяқтайды. Мұнда алдымен тікелей осы ұғымның анықтамасы беріледі, (мектептік функционалдық көріністі іске асырушы), ал сонан соң кері бейнелеуді алу амалы мен бейнелеулердің көбейтіндісі тілінде оның сипаттамасы беріледі. Сонан соң осы екі анықтамалардың теңқуаттылығы дәлелденеді. Әдістемелік деңгейде осыған ұқсас дәлелдеулерден алынатын тәжірибе формальды аксиомалық теориялар әдісін меңгеруде қажетті кезең болып табылады. Себебі, олар мазмұндық қорытынды шарттарын құрумен байланысты болады. Мұнда ұғым бір қатынастар жүйесінде (осы ұғымды беруші шарттардан), бірақ олар басқа қатынастар жүйесінің тілінде тұжырымдалған.
1.8 параграфында атомдық бейнелеулердің ерекше рөлі атап өтіледі.
Олар: сюръекция, биекция, инъекция және олардың көмегімен сәйкес композициялардың көмегімен алынатын, атомдардан құрылған молекула сияқты, кез келген бейнелеу.
Алгебралық амал ұғымы алгебралық жүйе ұғымының негізгі құраушысы ретінде өзінің маңыздылығын жан жақты ұғынуды талап етеді. Бұл тарауда амал ұғымының тура интуитивті мағыналық көрінісінен аксиомалар жүйесі түрінде абстракциялы берілу жолының кезеңдерін қадағалайтын боламыз.
Басты назарды бинарлық және унарлық (екі орынды және бір орынды) амалдарға аударамыз.
Себебі, олар жоғарғы оқу орындарында оқып, зерттелетін классикалық алгебралық жүйелердің негізгі амалдарының санына енеді.
Бұл тараудың материалдарын баяндау сандық жиындарда анықталған мектептегі әріптік алгебра мен онда анықталған арифметикалық (рационал) амалдарға алғашқы саяхаттан басталады. Осыдан кейін абстракциялық жиында берілген алгебралық амалдар концепциясына байланысты анықтамалар мен ұғымдар жүйесін оқып-зерттеуге көшеміз.
Жұмыс барысында бұл процесті іске асыру алдымен рационал сандарға негізделген, ал содан кейін нақты сандарға негізделген бірнеше ғасырлық (көпғасырлық) практиканың екендігін бірнеше қайтара атап өтіп отырамыз.
Екі орынды амалдардың аксиомалық берілуінің қасиеттерін мектептен белгілі, формальды әріптік теңдіктердің арифметикалық амалдарының заңдылықтары ретінде өрнектелуінен шыққандығын айта кетуге болады. Бинарлық алгебралық амал ұғымын анықтауға жетелеуші көптеген анықтамалардың мағыналық кері бейнесінің баламалары болып кәдімгі қосу, көбейту, алу, бөліктік амал бөлу және олардың қарапайым қасиеттері болып табылады. Алгебралық жүйелер класын абстрактілі сипаттауға (қатысты) байланысты қойылатын мақсаттың бірі ретінде қарастырылып отырған класта анықталған жүйенің негізгі амалдары мен қатынастарының қасиеттерін беруші тиімді аксиомалар жиынтығын таңдау болып табылады. Бұл жағдайда, бұл амалдар мен қатынастардың басқа қасиеттері сол сияқты жүйенің құрылымдық қасиеттері толығымен осы таңдап алынған аксиоматика негізінде анықталады, яғни олардыңсалдарлары ретінде алынады.
§1.1. Жиындар және оларда анықталған қатынастар
Жиын ұғымы математикада жиынтықтар, кластар, құрылымдар мен элементтердің (заттардың) көпбейнелері туралы интуитивті көріністерді кеңейтудің нәтижесінде қалыптасты және нәтижесінде жеке өздігінен бар объект ретінде белгілі болды. Жиындар теориясының негізін қалаушы Г. Кантор (1845-1918 ж.) жиын ұғымын біздің санамызға, интуициямызға тұтас бір объект ретінде анықталатын және бір-бірінен ажыратылатын кез келген жиынтық түрінде енгізді.
Осы тұжырымдауға сәйкес жиындар деп жоғарыда айтылған сипаттамалардың біреуін қанағаттандыратын осындай объектілер құрылымдарын айтуға болады. Бұл қасиетке қойылатын бір ғана талап - ол біздің интуитивті танымымызға (ұғынуымызға) қол жеткізу.
XIX-ғасырдың аяғына дейін жиынның интуитівті концепциясы ешқандай келіспеушілік тудырған жоқ. Осы концепцияның негізінде интуитивті жиындар теориясы құрылды. Бірақ, одан кейініректегі жиындар теориясының даму кезеңінде, жиын ұғымының осындай кең баяндалуы әртүрлі қарама-қайшылықтарды туғызды (жиындар теориясының еш зиянсыз парадокстары).
Қазіргі уақытта жиындар теориясы аксиомалық негізге орайластырылған (тұрақтандырылған) және осының нәтижесінде белгілі парадокстық (қарама-қайшылықтық) қасиеттерге ие жиындар толық жойылған. Себебі, қасиеттерді таңдауды шектейтін аксиомалар жүйесі арқылы жиынды қалыптастыру негізін құру мүмкін болды. Осыған қарамастан біз, әріректе, жиын ұғымы туралы интуитивті көрініске жүгінетін боламыз, себебі, аксиомалық жиындар теориясын мағыналық ұғыну, (интуитивті теория деңгейінде алынған), әруақытта терең ұғынылған жеткілікті ұғымдар мен нәтижелер бар деп ұйғарылады. Сонымен жиын деп белгілі бір ортақ қасиеттері бойынша топтастырылған объектілер жиынтығын (құрылымын) түсінетін боламыз.
Жиын - латын алфавитіндегі үлкен әріптермен, ал оның элементтері осы алфавиттің кіші әріптерімен белгіленетін болады. Бірақ, а-ның А жиынының элементі болатынын таңбалық түрде аА деп жазамыз.
Керісінше жағдайда, жазуын қолданамыз. әріптерімен әдетте, жиындардың нақты элементтері белгіленеді. Мысалға өрнегі жиының ішкі жиындарының жиыны.
жиының барлық ішкі жиындарының жиынын арқылы белгілейміз және жиының Булианы деп атаймыз, яғни
Булиан ұғымына байланысты байқайтынымыз - , бірақ .
§1.2. Жиындардағы амалдар
Барлық жиындар жиынтығында келесі төмендегі анықтамалдарға сәйкес келетін теоретикалық-жиындық 1) - қиылысу; 2) - бірігу; 3) \ - айырма амалдары енгізіледі.
1. және жиындарының қиылысуы деп бір уақытта осы және жиындарында жататын элементтерден құрылған жиынды айтамыз, яғни, және .
Нақтылы жиындарға амалын қолдану мысалдарын келтірейік:
а) ;
б) .
2. және жиындарының бірігуі деп осы жиындардың ең болмағанда біреуіне тиісті болатын элементтерден тұратын жиынды айтамыз, яғни,
немесе .
Мысалға:
а) .
б) Айталық,
және
болсын.
1-суретте жиынына тиісті координаталар жазықтығына тиісті нүктелер жиыны кескінделген.
Сурет 1
3. және жиындарының айырмасы деп -ға тиісті емес жиының элементтерінен тұратын жиынды айтамыз, яғни,
және .
Сонымен, және жиындарының айырмасы деп жиынындағы жиынының толығуын айтамыз.
Мысалдар:
а) егер өрнегі жазықтықтағы төртбұрыштың ромб болу қасиетін, ал - тіктөртбұрыш болу қасиетін білдірсе, онда өрнегі барлық шаршы болмайтын ромбтар жиыны;
в)
.
§1.3. Теоретикалық-жиындық амалдардың қасиеттері
жиындарына , , \ амалдарын бірнеше қайта қолданудың нәтижесінде қайтадан басқадан жаңа жиындарды аламыз.
Бұл жиындардың алу процесі - қадамдық сипаттағы индуктивтік процесс. Бұл процестегі әрбір қадам, екіншісінен бастап алғанда алдыңғы қадамға кез келген жиынға осы амалдардың кез келгенін бір рет қана қолдану арқылы алынады.Атап айтқанда:
0-қадам: Бұл қадамда жиындары алынады, яғни негізгі (берілген, бастапқы) жиындар 0-дік қадамның жиындары деп жарияланады.
Әрі қарай қадамындағы () барлық жиындар құрылған деп есептеледі және - осы қадамның кез келген жиындары.
- қадам: онда қадамның жиындары деп қадамының барлық жиындары және
түріндегі жиындар жарияланады.
Осыдан кейін келесі қадамға көшу орындалады.
Мысалы, жиындары бірінші қадамда алынса, ал
жиындары 2-ші нөмірлі қадамда алынады.
Алгебралық өрнектердегі сияқты жазуды жақшалардың көмегімен теоретикалық-жиындық амалдарды қолдануда да бір мәнді реттеуге болады. Бұл процесті орындау барысында бастапқы жиындардан әртүрлі сипаттағы амалдардың көмегімен алынған, бірақ осыған қарамастан өзара тең болатын жиындарда кездесуі мүмкін. Бұл теоретикалық-жиындық амалдардың сандарда анықталған арифметикалық амалдарға ұқсас белгілі бір анықталған қасиеттерінің бар болуына байланысты болады келеді.
Шын мәнісінде келесі теңбе-теңдіктер орынды:
1) ;
2) ;
3) ;
4) ;
5) ;
6) ;
7) ;
8) ;
9) ;
10) ;
11) ;
12) ;
13) ;
14) ;
15) .
Бұл теңбе-теңдіктердің барлығы кез-келген жиындары үшін орынды, яғни жиындар теориясының теңбе-теңдіктері (заңдары).
1)-15) теңбе-теңдіктерді қамтылу әдісін қолданып, оңай дәлелдеуге болады. Осы әдістің 9-теңбе-теңдікті дәлелдеуге қалай қолданылатындығын көрсеттік
Дәлелдеу үшін екі қамтылуды көрсету қажет:
а) ;
б) .
а) Айталық, жане
және және
және ;
б) Айталық және және және және .
1)-15) тізіммен теоретикалық-жиындық амалдардың негізгі қасиеттерін көрсететін теңбе-теңдіктер келтірілген. Әрине, бұл тізімге енбеген басқа да теңбе-теңдіктер бар.
§1.4. Эйлер-Венн диаграммалары
және жиындарына теоретикалық-жиындық амалдарды қолдану нәтижесін көрнекі түрде кескіндеуді Эйлер-Венн диаграммасы арқылы беруге болады.
Ол үшін және жиындары жазықтықта геометриялық фигура түрінде кескінделеді. Көпшілік жағдайда бұл мақсат үшін эллипс немесе шеңбер таңдалып алынады.
Жиындардың элементтері ретінде осы фигуралардың ішінде немесе шекараларында жататын жазықтықтың нүктелері алынады. Онда, егер А және В жиындары 2а - суретіндегідей кескінделсе, онда үшін кескіндер 2б,в,г - суреттеріндегідей кескінделеді.
а) б)
в) г)
Cурет 2.
Көрнекі болу үшін диаграмманың сәйкес бөлігі штрихталып (боялып) көрсетілген.
Келесі жиындар үшін Эйлер-Венн диаграммаларын құрайық:
a) ;
б) .
a) Диаграммаларды тізбектей құруды жүргізейік. (сурет 3а,б,в - қара)
Сурет 3.
б) Ақырғы нәтижені көрсетейік (4-суретке қара).
Эйлер-Венн диаграммалар әдісі жиындардың теңбе-теңдігінде көрнекі түрде негіздеуге мүмкіндік береді. Ол үшін бірінші диаграммада теңбе-теңдіктің сол жақ бөлігіне сәйкес келетін жазықтықтың бөлігін штрихтың көмегімен бөліп аламыз. Осылай теңбе-теңдіктің оң жақ бөлігін анықтаймыз. Осыдан кейін штрихталған облыстарды салыстырамыз. Облыстардың сәйкес келуі беттесуі бізге берілген жиындардың шын мәніндегі теңдігі туралы қорытынды шығаруға мүмкіндік береді.
Сурет 4.
Мысалға, Эйлер-Венн диаграммасын пайдаланып,
теңбе-теңдігін негіздейік.
Бұл жиынның сол жақ бөлігіне сәйкес келетін диаграмма 5а-суретінде кескінделген. Сол жағына сәйкес келетін диаграмма 5б-суретінде кескінделген.
Сурет 5.
Бұл суреттердегі екі рет штрихталған жазықтықтың бөліктері бір-біріне тең. Шын мәнісінде бұл облыстар дәлелдеуді қажет ететін (дәлелденетін) теңбе-теңдіктің сол және оң жақ бөліктеріне сәйкес келеді.
§1.5. Жиындардың декарттық көбейтіндісі
Жазықтықта тікбұрышты декарттық координат жүйесін енгізу осы жазықтықтағы әрбір нүктесімен және нақты сандарымен жұбын байланыстыруға мүмкіндік береді, және сандары нүктесінің координаталары деп, және бұл жағдайда - бірінші координатасы (абцисса) деп, ал - екінші координатасы (ордината) деп саналады. Нүктенің координаталары болатын жұбы екі элементті жиынынан мүлдем басқа (мағыналық түрде ажыратылады), себебі, жиындардың теңбе-теңдігі қатынасының анықтамасы бойынша: .
Ал, болғанда және жұптары әртүрлі нүктелерді анықтайды. жұбының теоретикалық-жиындық мағынасы , ал жұбының теоретикалық-жиындық мағынасы , сондықтан , яғни және жұптары тең емес.
Сонымен, координаттық жұбы - бұл екі элементті жиын және оның элементтеріне қатысты қайсысы бірінші, қайсысы екінші деп есептеу туралы келісім қабылданған.
Бұл мағынадан алғанда координаталық жұп - реттелген екі элементті жиын немесе реттелген жұп.
Жалпы жағдайда және элементтері әр түрлі және жиындарынан алынуы мүмкін.
Бірақ бұрынғы анықтамадағы сияқты жұбын реттелген деп санаймыз. Яғни, егер болса, онда .
элементі жұбының бірінші координатасы деп, ал элементі оның екінші координатасы деп аталады. Жалпы алғанда жұптардың теңдігі туралы да айтуға болады.
Кез келген реттелген және жұптары үшін келесі теңдік орынды:
.
Реттелген жұптар ұғымы негізінде және жиындарының декарттық көбейтіндісі ұғымы енгізіледі. Айталық, және кез келген бос емес жиындар болсын. және жиындарының декарттық көбейтіндісі деп түріндегі барлық реттелген жұптардың жиынын айтамыз, мұндағы және .
Сонымен, .
Мысал. Егер және болса, онда
.
Лемма 1.5.1. Егер және жиындары сәйкесінше элементті және элементті ақырлы жиындар болса, онда ақырлы элементті жиын болады.
Ақырлы жиындардың декарттық көбейтіндісін кесте арқылы берген өте ыңғайлы.
Айталық, және болсын.
және жиындарының декарттық көбейтіндісінің элементтері элементтерін кестеге келесі түрде орналастырған өте ыңғайлы (1 кестені қара).
1- кесте
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Бұл кестенің жолдары жиынының элементтерімен нөмірленсе, ал бағаналары жиынының элементтерімен нөмірленеді. Яғни, жұбы жол нөмірі , ал бағана нөмірі болатын тор көзде орналасады.
Егер және сандық жиындар болса, онда жиынын декарттық жазықтық нүктелер жиынымен сәйкес қоюға болады. Мұндағы .
Бұл ішкі жиын декарттық көбейтіндісінің графигі деп аталады.
Мысалға, 6а,б-суреттерінде декраттық көбейтіндісінің графигі кескінделген, мұндағы,
a) ;
б) ]}.
Сурет 6.
Бұдан байқайтынымыз 6б - суретіндегі жағдайда декарттық көбейтіндінің графигі тік төртбұрышының барлық нүктелер жиыны болса, ал функциясының графигі осы тік төртбұрыштың ішінде жататын синусоиданы анықтайтын нүктелер жиыны.
Бірнеше (үш және одан да көп) жиындардаң декарттық көбейтіндісін анықтау индуктивті әдістің анықтамасы туралы алғашқы түсінікті талап етеді.
Индуктивті анықтама - бұл n натурал параметрге тәуелді ұғымын анықтау.
Айталық, саны өрнегінің мағынасы болатын параметрінің ең кіші мәні болсын. Анықталатын ұғымның ерекшелігіне байланысты саны 0,1,2,.., т.т. сандар болуы мүмкін, яғни, жалпы жағдайда .
Индуктивті анықтама келесі сызба бойынша іске асады:
a) - ұғым, яғни ұғым n параметрінің ең кіші мәні үшін тікелей анықталады.
б) Әрі қарай кез келген натурал саны үшін ұғымы анықталған жорамалдың негізінде барлық үшін ұғымын анықтауға мүмкіндік беретін ереже қалыптасады.
Әдетте, a) пунктін индуктивті анықтаманың базисі немесе индукция базисі деп, ал б) пунктін индуктивті қадам (инуктивті жорамал негізінде құрылған) деп атайды.
Көпшілік жағдайда индуктивтік қадамды екі ішкі қадамға бөледі: б.1) индуктивтік жорамал, б.2) индуктивті қадам. Қарастырылып отырған жағдайда ұғымы n жиындарының декарттық көбейтіндісі өрнегін анықтау болып табылады.
ретінде 2 санын аламыз, себебі көбейту екі орынды амал болғандықтан тек осы жағдайда ғана көбейтінді туралы индукцияның мағынасы сақталады.
a) Индукция базисі (n=2) және жиындарының декарттық көбейтіндісінің анықтамасы 1 анықтамаға сәйкес келеді, яғни,
.
б1) Индуктивтік жорамал (n=k).
Айталық кез келген бос емес жиындарының декарттық көбейтіндісі анықталған деп санайық.
б2) Индкутивтік қадам (n=k+1),
деп алайық.
Жеке жағдайда бұл анықтамадан шығатыны:
.
жиындарының элементтері реттелген үштіктер (немесе ұзындығы 3 болатын кортеж) деп аталады және ішкі жақшаларды алып тастап түрінде жазылады. Осыған ұқсас жиынының элементі реттелген n-діктер (немесе ұзындығы n кортеж) деп аталады және арқылы белгіленеді.
Анықтама бойынша жиындардың декарттық көбейтіндісі қайтадан жиын болғандықтан жиындардың декарттық көбейтіндісінің ішкі жиындары, олардың бірігулері, қиылысулары және т.т. туралы да айтуға болады. Декарттық көбейтінді амалының қасиеттерімен қатар, оның (бірігу),
(қиылысу), \ (айырма) амалдарымен үйлесімдік қасиеттері де пайда болады.
Біріншіден, қасиеттер мен басқа да жаңа енгізілген ұғымдармен байланыс жаңа ұғымдардың нақтылы өзіндік белгілеріне ие болады. Ал бұл әріректе олар әртүрлі мәтіндерде кездескен жағдайда ажырата білуге көмектеседі.
Екіншіден, математикалық пәндердің фрагменттерін оқып- үйрену аясында жаңа ұғымдармен тікелей жұмыс істеу қазіргі заманғы математика мен олардың қосымшаларында бұл ұғымдарды жаттықтыруға (қалыптастыруға) дайындайды және олардың қалай өзгеретіндігін аңғартады.
амалының анықтамасына қайта оралсақ, байқайтынымыз, реттелген жұптар мен екі жиынның декарттық көбейтіндісінің анықтамасына сәйкес, амалы коммутативті емес, бірақ ассоциативті.
және амалдарының бірқатар үйлесімді қасиеттерін келтіре кетейік: Кез келген жиындары үшін
а) ;
б) ;
в) ;
г) ;
д) ;
e) ;
ж) ;
Бұл қасиеттердің (теңбе-теңдіктердің) әрқайсысын қамтылу әдісімен дәлелдеуге болады.
Мысал ретінде в) - пунктінің дәлелдеуін келтірейік.
Айталық
.
Сонымен, .
Кері қамтылуды осыған ұқсас әдіспен алуға болады.
декарттық көбейтіндісі жиынының декарттық n дәрежесі деп аталады және A(n=2,...) арқылы белгіленеді. Егер М ақырлы жиын болса, онда арқылы осы М жиынының элементтерінің санын белгілейтін боламыз.
Лемма 1.5.2. Егер М ақырлы жиын және , болса, онда .
§1.6. Сәйкестіктер және олардың берілу тәсілдері
Әртүрлі жиынтықтардың элементтерінің арасындағы сәйкестік ұғымы туралы интуитивті түсінік әрбір адамға тән және оны келесі түрде тұжырымдауға болады: егер және кез келген бос емес жиындар болса, онда жиынының жиынына сәйкестігі деп декарттық көбейтіндісінің ішкі жиынын айтады.
Сәйкестіктер, әріректе, латын алфавитінің үлкен әріптерімен белгіленетін болады. Яғни, . Анықтамаға сәйкес -ның -ға сәкестігі - бұл кейбір реттелген жұптар жиыны, мұндағы Егер болса, онда жиынының элементі жиынының элементіне сәйкес келеді деп атайды. жазуының орнына жазуын қолданады. Әрбір сәйкестікпен оның анықталу және мәндер облыстары байланысты.
Егер жиынының жиынына сәйкестігі болса, онда
осы сәйкестігінің анықталу облысы деп аталады, ал
жиыны осы сәйкестіктің мәндер облысы деп аталады.
Сонымен, осы сәйкестігіне тиісті жиындардың бірінші координаталар жиыны болса, онда оның екінші координаталар жиынын құрайды.
Айталық, мысалға, және болса,
.
Сәйкестіктің анықтамасының кейбір ерекшеліктерін келесі жаттығу көрсетеді: егер сәйкестік болса, онда болатынын көрсетіңдер. жиынының жиынына болатын жиындарын және сәйкестігін табыңдар.
жиынының жиынына сәйкестіктерін берілу тәсілдеріне тоқтала келе байқайтынымыз, сәйкестікті берудің әмбебап әдісі - бұл жиынының тек таңдалып алынған реттелген парларының координаталары осы сәйкестікте болатындығын көрсететін нақты қасиетті (белгіні) көрсету. Әрине бұл жағдайда, предикативтік емес сипаттағы қасиеттерден аулақ болу керек.
Сонымен қатар, тексеру оңай және нәтижелі жүргізілетін қасиеттерді пайдаланған абзал.
Айталық, мысалға, болсын. жиынының жиынына сәйкестігін келесі түрде анықтайық: үшін , егер - нольден өзгеше жұп сан және - дауысты дыбыс (әріп) немесе егер - тақ сан және - дауыссыз дыбыс (әріп).
Әрине бұл көрсетілген қасиеттер сәйкестігіне тиісті жиынының барлық парларын жазып шығуға мүмкіндік береді.
Ақырлы жиындардың арасындағы сәйкестіктерді көрнекі түрде көрсетуге болады. Осылардың бірнешеуін сипаттайық.
Ақырлы және жиындарының арасындағы сәйкестіктерді оларға тиісті барлық жұптар арқылы жазып шығуға болатындықтан онда оны көрнекілік үшін 1-кесте түрінде беруге болады (§1.5. қараңыз). Айталық, мысалға, болсын.
Онда, жиынының жиынына сәйкестігін 2-кесте түрінде беруге болады.
.
2 - кесте
Әрине, егер сәйкестік жиынының өзіндік ішкі жиыны болса, онда оның кестесінде бос тор көздер (клеткалар) болады.
Ақырлы жиындардың арасындағы сәйкестікті бағдарланған графтың көмегімен де беруге болады.
Бағдарланған граф деп (бейресми түрде) жазықтықтың ақырлы нүктелер жиыны (графтың төбелері) мен олардың кейбір төбелер жұптарын өзара қосатын (бағыты көрсетілген) бағытталған доғаларды (графтың бағытталған қабырғалары) айтады. Бұл жағдайда, егер жиынының жиынына сәйкестігі қарастырылатын болса, онда графтың төбесі ретінде жиынының элементтерін жиынының элементтеріне сәйкес қоюшы жазықтықтың нүктелері алынады.
Белгілі бір доғалар жиынтығын бағыт арқылы бере отырып жиынының кейбір нүктелеріне жиынының сәйкес келуші нүктелерін графтың бағдарланған қабырғалары түрінде анықтаймыз. Бұл жағдайда нақты сәйкестігінің (жиынының жиынына) анықталу облысы осы жиынының бағдарланған қабырғалары шығатын нүктелер жиыны, ал мәндер жиыны - осы қабырғалар енетін жиынының нүктелер жиыны (бағдарланған граф 7 - суретте келтірілген).
Сурет 7.
Сәйкестіктердің арнайы түрлерін қарастырған жағдайда (мысалы, эквиваленттік қатынасын қарастырған жағдайда) сәйкестікті қима түрінде беру өте ыңғайлы. Егер жиынының жиынына сәйкестігі және болса, онда жиынын сәйкестігінің элементі бойынша қимасы деп аталады.
Ақырлы жиынының жиынына сәйкестігін әрбір элементі үшін қималарын толық жазып шығу арқылы беруге болады.
Айталық, мысалға, арифметикалық амалдар үшін таңбалар жиыны болсын.
және үшін сәйкестігінің келесі қималарды беретіндігін түсіну қиын емес
.
Жоғарыда және жиындарының декарттық көбейтіндісін график түрінде беруге болатындығы туралы айтылған болатын. жиынының жиынына сәйкестігі жиынының ішкі жиыны түрінде берілетін болғандықтан, онда декарттық көбейтінің бұл берілу әдісі сәйкестіктің берілу тәсілі ретінде қабылданады.
§1.7. Сәйкестіктерде анықталған амалдар
жиынының жиынына сәйкестігі жиын болып табылады, сондықтан сәйкестіктердің теңдігі мен қамтылуы туралы, бір сәйкестіктің екінші сәйкестікпен қиылысуы, бірігуі және толықтауышы туралы да айтуға болады. Сәйкестіктер жиынтығында сонымен қатар кері сәйкестікті анықтау және оларды көбейту (композиция) амалдары анықталған.
1. Айталық, кейбір сәйкестік болсын.
ережесімен анықталған сәйкестігі сәкестігімен қайтымды сәйкестік деп аталады.
Әрине, егер болса, онда .
Сонымен, сәйкестігіне кері сәйкестікті алу үшін ондағы парлардың координатасының орындарын ауыстыру қажет.
Мысалы, егер сәйкестігі бағдарланған граф түрінде берілсе, онда сәйкестігін анықтау үшін барлық бағыттарды қарама - қарсыға ауыстыру керек.
2. Айталық -ның -ға сәйкестігі және -ның -ғасәйкестіктері берілсін.
Онда жиынының жиынына сәйкестігі келесі ережемен анықталады:
және ол және сәйкестіктерінің көбейтіндісі (немесе композициясы) деп аталады.
Анықтама 1.7.1. және болатын және сәйкестіктері үшін болсын.
Онда және ØØ.
Жоғарыда енгізілген кез келген сәйкестіктері үшін келесі теңдіктерді қанағаттандыратың бірнеше қасиеттерді атап өтейік:
а)
б)
в)
г)
д)
Мысал үшін қамтылу әдісін қолданып б) пунктінің дәлелдеуін, яғни
қамтылуларын дәлелдейік.
Айталық жиынының жиынына сәйкестігі , ал жиынының жиынына сәйкестігі болсын.
Онда:
Екінші қамтылу осыған ұқсас дәлелденеді.
Егер сәйкестіктің анықтамасында деп алсақ, онда -ның -ға (өз-өзіне) сәйкестігін аламыз.
Мұндай сәйкестіктің қарапайым мысалы А жиынының диагоналі деп аталатын
сәйкестігі.
Бұл терминологияны келесі түрде түсіндіруге болады.
Егер жиыны ақырлы және сәйкестігі кесте түрде берілсе, онда жұптары осы кестенің бас диагоналін құрайтын торкөздерден тұрады, ал басқа тор көздер бос болады.
Егер жиынының жиынына сәйкестігі болса, онда
болатынын тексеру қиын емес.
Көбейту (композиция) және кері сәйкестікті алу амалдарының теоретикалық-жиындық және амалдарымен байланысуының негізгі қасиеттері келесі мысалдарда келтірілген.
Егер кез келген сәйкестіктер болса, онда:
а)
б)
в)
г)
д)
е)
§ 1.8. Бейнелеулер
Жиындардың арасындағы сәйкестіктердің маңызды түрлерінің бірі болып бейнелеулер табылады.
жиынының жиынына сәйкестігі жиынының жиынына бейнелеуі (немесе -дан -ға функция ) деп аталады, егер келесі шарттар орындалса:
1.
2. .
Егер сәйкестігі бейнелеу болса, онда жазуымен қатар жазуында қолданамыз. Бұл жағдайда элементі элементінің кері бейнесі, ал элементі элементінің осы бейнелеуіндегі бейнесі деп аталады. (8 - суретке қара)
х
у
А
В
Dom Ф=А
Im Ф=А
Ф
Ф
у = Ф(х)
Сурет 8.
жазуы, әріректе, жиынының жиынына бейнелеуі дегенді білдіреді.
Келесі тұжырым қима терминіндегі бейнелеудің қарапайым сипаттамасын береді.
Бейнелеудің анықтамасындағы 1 - шарт , ал (екінші) 2 - шарт сәйкестігінің кез келген элементі бойынша қимасында ең көп дегенде бір элемент болады деген шарттармен пара - пар.
Бейнелеу ұғымын кері сәйкестік алу және сәйкестіктердің көбейтіндісі амалдары тілінде сипаттау практикалық қолдану тұрғысынан алғанда қызығушылық туғызады.
сәйкестігі бейнелеу болады, сонда тек қана сонда, егер келесі шарттар орындалса:
а) ;
б) .
Бір ғана ұғымның екі анықтамасының тең мәнділігін (тең ағыналылығын) дәлелдеу көптеген жағдайларда маңызды.
Ұғымды әртүрлі терминдерде беру оның мағынасын терең түсінуге көмектессе, екіншіден оларды анықтаушы қатынастардың арасындағы байланысты анықтай түседі. Мұндай қорытындыларды ала білу тәжірибесі формаль аксиоматикалық теориялар әдісін меңгерудін қажетті кезеңі болып табылады.
Базистік (1, 2 шарттар) және жоғарыда келтірілген (а, б шарттары) бейнелеу ұғымының келтірілген екі анықтамаларының теңмәнділігін дәлелдейік.
) Айталық, -ның -ға бейнелеуі болсын.
а) және б) шарттарының орындалатындығын көрсетейік.
а) болсын делік. Бейнелеудің анықтамасының 1-шарты бойынша элементі үшін элементі табылып болады. Онда, , яғни .
б) болсын делік. Онда -ның -ға сәйкестігі болғандықтан, онда -ның -ға сәйкестігі болады, яғни, және болатындай элементі табылады. Сондықтан, , себебі, үшін бейнелеудің анықтамасының 2 - шарты орындалады.
) Айталық, енді сәйкестігі үшін екінші анықтаманың а) және б) шарттары орындалған болсын.
Бейнелеу ұғымының қима тіліндегі сипаттамасына сәйкес ол үшін келесі тұжырымды дәлелдеу керек:
және кез келген элементі үшін - қимасы бір элементті.
Шын мәнісінде болғандықтан, онда теңдікті дәлелдеу үшін тексеру жеткілікті.
Айталық болсын. Онда, а) шартты сәйкестікте , яғни элементі табылып және , ал бұл дегенді білдіреді. Әрбір қимасының бірэлементті болатынын кері жору әдісімен дәлелдейік. Айталық, кейбір элементі үшін қимасында ең болмағанда екі және элементтері жатқан болсын.
Онда және , яғни және . Бұдан алатынымыз, бейнелеулердің көбейтіндісі амалының анықтамасына сәйкес, , яғни .
мен қатысты алынған қарама - қайшылық дәлелдеуді толық аяқтайды.
Алынған сипаттамалардың практикалық қолданыстарын келесі жаттығудан көруге болады.
Лемма 1.8.1. Егер және бейнелеулер болса, онда бейнелеу болады.
сәйкестігінің бейнелеу болатынын көрсету үшін бейнелеудің операция тілі сипаттамасында а) және б) шарттарының орындалатындығын тексеру жеткілікті.
Яғни, а) ;
б) болатынын тексеру керек.
Әдетте бұл шарттарды студенттер өздіктерінен тексере алады. Бейнелеулердің кейбіреулері математикадағы маңыздылығына байланысты арнайы аттарға ие болған.
жиынының жиынына бейнелеуі :
а) сюръективті деп аталады, егер болса;
б) инъективті деп аталады, егер
болса;
в) биективті деп аталады, егер ол бір уақытта сюръективті және инъективті болса.
Енгізілген ұғымдардың қазақ тіліндегі мағыналарын келесі түрде түсіндіруге болады:
а) сюръективті бейнелеу барлық жиынына бейнелеу дегенді білдіреді;
б) инъективті бейнелеу жиынының кейбір ішкі жиынына бейнелеуді білдіреді және бұл жағдайда жиынының әрбір элементінің тек бір ғана кері бейнесі болады.
в) биективті бейнелеу бір уақытта сюръективті және инъективті бейнелеу болғандықтан ол жиынының жиынына өзара бірмәнді бейнеленуі дегенді білдіреді.
Осы сюръективті, инъективті және биективті бейнелеулердің ерекшеліктерін сипаттаушы сурет төменде келтірілген (сурет 9, а,б,с - қара).
А
В
а)
А
В
В1
б)
А
В
в)
Сурет 9.
II ТАРАУ
ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1. Математикалық логика термині. Логика сөзінің негізі грек тілі. Лого сөзін грек тілінен әртүрлі мағынада аударуға болады: сөз, ұғым, ой, таным.
Жалпы философиялық термин сапасында бұл сөзді әлемдегі жалпы заңдылықтарды белгілеу үшін қолданады.
Математикалық логика - бұл дұрыс математикалық ой-пайымдаулар, математикалық (ойлау) талдауларды нақты ғылымдарда қолдану туралы ғылым.
Математикалық логикада ойлау заңдылықтары талданады және оқып зерттеледі. Математикада дұрыс ой-пайымдаулар маңызды рөл атқарады. Сондықтан, дұрыс ой-пайымдауларды математикалық логика деп атағанға ешқандай таң қалуға болмайды.
Математикалық логика терминінің орнына кейде формальдық логика, символдық (таңбалық) логика терминдері де қолданылады.
Элементар математикалық логика тек ғана ақиқат немесе тек ғана жалған болатын оқиғаларды зерттейді.
Қазіргі уақытта оқиғаны нақты сипаттау үшін математиканың тілі, оқиғаны түрлендірудің нақты сипаттамасының тілі қолданылады. Бұл тілді есептеу машиналарының түсінетіндігін айта кету керек.
Оқиға мен нақты түрлендіруді математикалық сипаттаудың зерттеу негізі (базасы) математикалық логика мен субрекурсивті алгоритмдер теориясы болып табылады.
2. Математикалық логиканың қалыптасуы. Ой-пайымдаулар ережелерін алғашқы рет бір жүйеге келтірген Аристотель деп айтуға болады.
Бұл ережелер силлогизмдер деп аталған.
Математикалық логиканың келесі бір даму жолының кезеңін математик және философ Лейбництің идеяларына жатқызуға болады.
Қазіргі математикалық логиканың дамуының басталуына ХІХ ғасырдың ортасындағы Джордж Бульдің Математикалық талдау және Ойлау Заңдары еңбектерін жатқызуға болады. Дж.Буль тұжырымдар санағы мен логикалық амалдарды [және, немесе, емес] енгізді. Кейініректе Фреге жалпылау және бар болу кванторларын енгізуді ұсынды.
Жеткілікті шамада ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz