Тұжырымдар алгебрасының формулалары
МАЗМҰНЫ
КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең
1.9 Негізгі тепе-теңдіктер 10
1.10 Формулаларды тепе-тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 тарау. тұжырымдар есептелімі 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс
Тақырып бойынша тесттер 24
Глава 3. предикаттар логикасы 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе-теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары
Тесты по теме 32
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТестТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның
Логика өз алдына ғылым болып грек философы Аристотельдің
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны
Логикада математиканы қолдану логикалық теорияларды жаңа формада кқруге
XIX ғ. аяғында математика үшін актуальді мәнге ие
Математикалық ойлаудың ерекшеліктері математикалық абстракция және олардың байланыстарының
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі математикалық
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін айтты
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының қорында
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”,
Егер L – “дұрыс” жиын болса, онда L
Егер L – “дұрыс емес” жиын болса, онда
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын теориясын
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943)
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа математикалық
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны математикалық
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1.1. Тұжырым ұғымы
Бүкіл математикадағы сияқты, біздің курстағы әр бөлімде де
Тұжырым деп ақиқатығы немесе жалғандығы туралы айтуға болатын
Мысал 1. «2*2=4» (екі көбейту екі тең төрт).
Мысал 2. «Егер натурал сан 6ға бөлінсе, онда
Мысал 3. Тауық қүс емес.
Мысал 4. 3≥5.
1 және 2 тұжырымдар – ақиқат, ал 3,
Граматикалық байланыстар көмегімен («және», «немесе», «егер..., онда...», «сонда
Әрі қарай бізді тұжырымдардың мағыналы жағы қызықтырмастан, олар
Қарапайым тұжырымдары латын алфавиттің a,b,c,…,x,y,z,… әріптерімен, ақиқат мәнді
Егер а ақиқат болса, онда а=1, ал егер
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу
а тұжырымының терістеуі жаңа тұжырым болып табылады, бұл
a терістеу тұжырымы (¬a) деп
Бұл түрдегі кестені ақиқаттық кестесі деп атайды.
Мәселен, «2 кіші 5тен» тұжырымы үшін терістеу болып
а тұжырым болсын. да тұжырым
1.3 Конъюнкция
a және b тұжырымдарының конъюнкциясы деп, егер екі
a және b тұжырымдарының конъюнкциясы мына символмен белгіленеді
a b a(b
1 1 1
1 0 0
0 1 0
0 0 0
Мысалы: «6 2-ге бөлінеді», «6 3-ке
Конъюнкция операциясы анықтамасында көрсетілгендей «және» сөзі логика алгебрасында
1. 4 Дизъюнкция
a және b тұжырымдарының дизъюнкциясы деп,егер екі
a, b тұжырымдардың дизъюнкциясы мына символмен белгіленеді:
a және b екі тұжырымның барлық мүмкін логикалық
1. 5 Эквиваленция
a және b екі тұжырымдарының эквиваленциясы
a және b тұжырымдарының эквиваленциясы мына символмен белгіленеді:
a B a~b
1 1 1
1 0 0
0 1 0
0 0 1
Мысалы: «S төбесі және PQ негізімен берілген SPQ
Эквиваленттілік математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың белгілі
1.6 Импликация
a және b екі тұжырымның импликациясы деп, егер
a, b тұжырым импликациясы былай белгіленеді a( b
a және b екі тұжырымның барлық мүмкін логикалық
a b a( b
1 1 1
1 0 0
0 1 1
0 0 1
Мысалы, “егер 12 6-ға бөлінсе, онда ол
Импликация математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың белгілі
Логикалық амалдармен алғаш танысқанда импликациядан басқаның барлығы мейлінше
Сонда шығатыны:
Q(x )= А(x )( В(x )
(1) формулаға х=8, 2, 3 мәндерін қоя отырып
Қарапайым тілде «Егер А, онда В» түрдегі сөйлемде
1.7 Тұжырымдар алгебрасының формулалары
Тұжырымдарға қолданылатын логикалық амалдары көмегімен берілген тұжырымдардан күрделі
және .
Қарапайым тұжырымдардан терістеу, конъюнкция, дизъюнкция, импликация және эквиваленция
Тұжырымдар алгебрасының формулаларын латын алфавиттің бас әріптерімен белгілейміз:
Жазуды жинақтау үшін формулалардағы амалдарды ретімен орындау келісілген.
Демек, жоғарыда келтірілген және
және
немесе
Логика алгебрасында формуланың логикалық мәні оған кіретін қарапайым
Логикалық амалдар сияқты, формуланың барлық мүмкін болған мәндері
Мысалы, (x(y(х((у формуласы үшін ақиқаттық кестесінің көрінісі
х у (x (у (x(y х((у (x(y(х((у
1
1
0
0 1
0
1
0 0
0
1
1 0
1
0
1 1
0
1
1 0
1
0
0 0
1
0
0
Егер формуланың құрамына n қарапайым тұжырым енетін болса,
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең
Егер логика алгебрасының А және В формулалары олардың
А (В ( А және В формулалары пара-пар.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде
Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар:
1.9 Негізгі тепе-теңдіктер
Теорема 1 Келесе тепе-теңдіктер орындалады:
а( b((a(b;
a~b ( (а( b)( b( a) ( ((a(b)(
Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен дәлелдеуге болады.
Келтірілген тепе-тең көрінетіндей, ( және ~ амалдары (,
Теорема 2 Айтылымдар алгебрасының булдік амалдары үшін келесі
0. – екі еселі терістеу
– коммутативтік заңдары
– ассоциативтік заңдары
– дистрибутивтік заңдары
–идемпотенттік заңдары
– де Морган заңдары
– 0 мен 1 заңдары
– жұту заңдары
– үшіншісі өшірілген заңы
– қайшылық заңы
Бұлардың кез-келгенін ақиқаттық кесте көмегімен дәлелдеуге болады.
1.10 Формулаларды тепе-тең түрлендіру
Тепе-теңдіктерді пайдаланып, формуланы немесе оның бөлігін оған пара-пар
Тепе-тең түрлендірулер тепе-теңдіктерді дәлелдеу, формуланы берілген түрге келтіру,
Егер А формуланың құрамына оған пара-пар В формулаға
1.11 Логика алгебрасының функциялары
Жоғарыда айтылғандай, логика алгебрасы формуласының мәні бұл формулаға
Мысалы, формуласы үш айнымалының f(x,y,z)
Анықтама Функцией алгебры логики n переменных (или функций
Ясно, что тождественно истинные и тождественно ложные формулы
n айнымалы функциялардың санын анықтаймыз. Логика алгебрасының әрбір
Мысалы, бір айнымалы әртүрлі функциялардың саны төрт, ал
Бір айнымалы барлық функциялардың ақиқаттық кестесін қарастырамыз. Ол
x f1(x) f2(x) f3(x) f4(x)
1 1 1 0 0
0 1 0 1 0
Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар
Барлық мүмкін болған екі айнымалы функциялардың ақиқаттық кестесі
x Y f1 f2 f3 f4 f5 f6
1 1 1 1 1 1 0 1
1 0 1 1 1 0 1 1
0 1 1 1 0 1 1 0
0 0 1 0 1 1 1 0
Түсінікті, бұл функциялардың аналитикалық өрнектері келесі түрде жазылуы
, ,
,
,
, , ,
функциясы Пирс функциясы деп аталады және былай белгіленеді:
1.12 Нормал және жетілдірілген формалар
А(а1, а2, …, аn) n тұжырымның формуласын қарастырайық.
Анықтама 1. n тұжырымның қарапайым конъюнкциясы (қарапайым
Мысал 1. xyz, (xy – қарапайым конъюнкция;
(x(y(z, y(z, x((z –қарапайым дизъюнкция.
Анықтама 2. Егер А формуладағы қарапайым дизъюнкциялар бір-бірімен
Анықтама 3. Егер А формуладағы қарапайым конъюнкциялар бір-бірімен
Тұжырымдар алгебрасының кез келген формуласы үшін тепе-тең түрлендірулер
Анықтама 4 Егер дизъюнктивті нормал формадағы қарапайым конъюнкцияның
Анықтама 5 Егер конъюнктивті нормал формадағы қарапайым дизъюнкцияның
Мысал 2. А(x,y,z)= xyz((xy – дизъюнктивті нормал форма;
B(x,y,z)= ((x(y(z)( y(z)( x((z) – конъюнктивті нормал форма;
C(x,y,z)= xyz((xyz – жетілдірілген дизъюнктивті нормал форма;
D(x,y,z)= ((x(y(z)( x(y(z)( x(y((z) – жетілдірілген конъюнктивті нормал
Теорем 1 Тұжырымдар алгебрасының кез келген формуласының оған
Теорема 2 Тұжырымдар алгебрасының кез келген тепе-тең жалған
Теорема 3 Тұжырымдар алгебрасының кез келген тепе-тең ақиқат
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру
Есеп. А(x,y,z) формуласының ақиқаттық кестесі берілсін.
х у z А(x,y,z)
1 1 1 1
1 1 0 0
1 0 1 0
0 1 1 1
1 0 0 1
0 1 0 0
0 0 1 0
0 0 0 0
Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген
Бірінші жолдағы мәндерде xyz ақиқат,
Төртінші жолдағы мәндерде (xyz ақиқат,
Бесінші жолдағы мәндерде x(y(z ақиқат.
Енді, осы қарапайым конъюнкциялардан жетілдірілген нормал дизъюнктивті форма
хyz ( (xyz ( x(y(z.
Бұл формуланың ақиқаттық кестесінің А(x,y,z) формуласының ақиқаттық
А(x,y,z)= хyz ( (xyz ( x(y(z.
Демек, тепе-тең жалған емес формуланы жетілдірілген нормал дизъюнктивті
Тепе-тең ақиқат емес формуланы жетілдірілген нормал конъюнктивті формаға
Мәселен, жоғарыда қарастырылған формуланың ЖКНФ келесі түрде болады:
А(x,y,z)= ((х((y(z) ((x(y((z)(x((y(z) (x(y((z) (x(y(z).
1.14 Логикалық байланыстардың толық жүйелері
(1, (2, …, (n логикалық амалдардың символдары болсын.
Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар
Лемма 9.1 Логикалық байланыстардың келесі жиындары:
,
Тұжырымдар алгебрасы
Тұжырымдар алгебрасы. Тұжырымдар есептелімі
Санау жүйелері. Буль алгебрасы
Математикалық логика және дискретті математика
Html тілінде математикалық логика пәнінен электрондық оқулық құру
Логика алгебрасы
Жиындар теориясының негізгі ұғымдары
Жазық эллипстік сандар алгебрасының құрылымы
Дискретті математиканың негізі
МАТРИЦАЛАР АЛГЕБРАСЫНЫҢ АМАЛДАРЫ