Тұжырымдар алгебрасы
МАЗМҰНЫ
КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара.пар, тепе.тең ақиқат және тепе.тең жалған формулалары 9
1.9 Негізгі тепе.теңдіктер 10
1.10 Формулаларды тепе.тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру 13
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 ТАРАУ. ТҰЖЫРЫМДАР ЕСЕПТЕЛІМІ 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс 23
Тақырып бойынша тесттер 24
ГЛАВА 3. ПРЕДИКАТТАР ЛОГИКАСЫ 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе.теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары түрінде жазу 31
Тесты по теме 32
VI ТАРАУ. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТЕСТТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара.пар, тепе.тең ақиқат және тепе.тең жалған формулалары 9
1.9 Негізгі тепе.теңдіктер 10
1.10 Формулаларды тепе.тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру 13
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 ТАРАУ. ТҰЖЫРЫМДАР ЕСЕПТЕЛІМІ 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс 23
Тақырып бойынша тесттер 24
ГЛАВА 3. ПРЕДИКАТТАР ЛОГИКАСЫ 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе.теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары түрінде жазу 31
Тесты по теме 32
VI ТАРАУ. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТЕСТТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның ойлау қабілеті заңының жолдарын қолданып, дәлелденетін ғылым болып табылады. Адамның ойлау қабілетінің заңын оқу логика пәні болып табылады.
Логика өз алдына ғылым болып грек философы Аристотельдің (384-322 ж.ж б.э.д) еңбегінде нақтыланған. Ол өзіне дейінгі мәліметтерді жүйеледі және осы жүйе кейін формальды немесе Аристотель логикасы деп аталды.
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді. Математиканың дамуы Аристотель логикасының жетіспеушіліктерін көрсетті және оның әрі қарай дамуын талап етті.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып неміс математигі Г.Лейбниц (1646-1716) XVI ғ. аяғында айтты. Ол логиканың негізгі ұғымдарын арнайы шарттармен байланысқан символдармен белгіленуі тиіс дейді. Бұл кез-келген ойларды есепке ауыстыруға мүмкіндік береді.
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны құрды және бұл айтылымдар алгебрасын дүниеге әкелді. Логикаға симвлодық белгілеуді ендіру, бұл ғылымға маңызды болды. Дәл осы символдарды логикаға ендіру жаңа математикалық логика ғылымының негізін қалады.
Логикада математиканы қолдану логикалық теорияларды жаңа формада кқруге мүмкіндік берді және есептеуіш аппараттарды адамның ойлау қабілеті жетпейтін есептерді шешуде қолдану логиканың зерттеу облысын кеңейтті.
XIX ғ. аяғында математика үшін актуальді мәнге ие болатын сұрақтар туындады, яғни оның негізгі ұғымдары мен идеялары бойынша. Бұл мәселенің логикалық негізі болды және бұл математикалық логиканың әрі қарай дамуына алып келді. Бұл қатынаста неміс математигі Г.Фреге (1848-1925) және Итальян математигі Д. Пеано (1858-1932) еңбектерінде көрсетілген.
Математикалық ойлаудың ерекшеліктері математикалық абстракция және олардың байланыстарының түрлілігінің ерекшеліктерімен түсіндіріледі.
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі ретінде қарастырады.
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі математикалық теорияларды құруда аксиоматикалық әдістердің кең таралуы болып табылады.
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе ұғымы және олардың арасындағы қатынас тандалады. Осы ұғымдар мен қатынастар негізгі деп аталады. Әрі қарай дәлелдеусіз теория қарастыратын негізгі орын аксиома қолданылады. Барлық алдағы теорияның мазмұны аксиомадан логикалық түрде шығарады. Математикалық теорияда аксиоматикалық құруды алғашқы болып геометрияны құруды Эвклид қолданды .
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі ұғымдарға (нүкте, түзу, жазықтық) анықтама бергісі келді. Теорияны дәлелдеуде еш жерде жинақталмаған орын қолданылды.
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз болды. Осы әдісті өзгертуде Н. И. Лобачевский (1792-1856) еңбектерінің маңызы зор болды.
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін айтты және осы айтуын жаңа геометрияны құруда нақтылады. Кейін неміс математигі Ф.Клейн (1849-1925) Лобачевский геометриясын дәлелдеді. Осылайша математика тарихында олардың еңбектері алғашқы болып аксиоматикалық теорияның ділелденбейтін мәселесі көрсетілді.
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне қойылатын негізгі талаптардың бірі болып табылады.
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар. Осының бірі интерпретация болып табылады. Мұнда негізгі ұғым мен қатынас ретінде кейбір жиынның элементтері және олардың арасындағы қатынас таңдалады, одан кейін тексеріледі.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының қорында құрылады.
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер пайда болды (жиын теориясының парадоксы). Осыған мысал ретінде Б. Рассела парадоксы болып табылады.
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”, деп айтамыз егер ол өзінің элементі ретінде өзі болмаса және “дұрыс емес” кері жағдайда . Мысалы, барлық кітаптар жиыны дұрыс жиын, ал ойдағы заттар жиыны дұрыс емес жиын . L –барлық дұрыс жиындар жиыны болсын. Онда L қай жиын класына жатады?
Егер L – “дұрыс” жиын болса, онда L Î L, яғни дұрыс жиын класында, бірақ ол өз элементі ретінде өзі кіреді, сондықтан ол “дұрыс емес”.
Егер L – “дұрыс емес” жиын болса, онда L Ï L, яғни дұрыс жиындар құрамында жоқ, бірақ L өз элементі ретінде өзі кірмейді, сондықтан ол “дұрыс”. Осылайша дұрыс жиын ұғымында қарама-қайшылық туындайды.
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын теориясын құру қажеттілігіне алып келді. Кейінгі өзгерістерге байланысты бұл теория осы заманғы жиын теориясы құрылды.
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943) және оның мектебінде дамытылды. Олар математикалық теорияны құруды синтаксистік теория негізіне сүйене отырып құрды.
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу теориясы деп атады.
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны математикалық логика негізін құру мәселесі туындайды. Әртүрлі тәсілмен аксиома жүйесі және басқа формуланы шығару шартын таңдауда әртүрлі синтаксистік логикалық теорияны аламыз. Олардың әрқайсысын логика есептелімі деп атаймыз.
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның ойлау қабілеті заңының жолдарын қолданып, дәлелденетін ғылым болып табылады. Адамның ойлау қабілетінің заңын оқу логика пәні болып табылады.
Логика өз алдына ғылым болып грек философы Аристотельдің (384-322 ж.ж б.э.д) еңбегінде нақтыланған. Ол өзіне дейінгі мәліметтерді жүйеледі және осы жүйе кейін формальды немесе Аристотель логикасы деп аталды.
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді. Математиканың дамуы Аристотель логикасының жетіспеушіліктерін көрсетті және оның әрі қарай дамуын талап етті.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып неміс математигі Г.Лейбниц (1646-1716) XVI ғ. аяғында айтты. Ол логиканың негізгі ұғымдарын арнайы шарттармен байланысқан символдармен белгіленуі тиіс дейді. Бұл кез-келген ойларды есепке ауыстыруға мүмкіндік береді.
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны құрды және бұл айтылымдар алгебрасын дүниеге әкелді. Логикаға симвлодық белгілеуді ендіру, бұл ғылымға маңызды болды. Дәл осы символдарды логикаға ендіру жаңа математикалық логика ғылымының негізін қалады.
Логикада математиканы қолдану логикалық теорияларды жаңа формада кқруге мүмкіндік берді және есептеуіш аппараттарды адамның ойлау қабілеті жетпейтін есептерді шешуде қолдану логиканың зерттеу облысын кеңейтті.
XIX ғ. аяғында математика үшін актуальді мәнге ие болатын сұрақтар туындады, яғни оның негізгі ұғымдары мен идеялары бойынша. Бұл мәселенің логикалық негізі болды және бұл математикалық логиканың әрі қарай дамуына алып келді. Бұл қатынаста неміс математигі Г.Фреге (1848-1925) және Итальян математигі Д. Пеано (1858-1932) еңбектерінде көрсетілген.
Математикалық ойлаудың ерекшеліктері математикалық абстракция және олардың байланыстарының түрлілігінің ерекшеліктерімен түсіндіріледі.
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі ретінде қарастырады.
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі математикалық теорияларды құруда аксиоматикалық әдістердің кең таралуы болып табылады.
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе ұғымы және олардың арасындағы қатынас тандалады. Осы ұғымдар мен қатынастар негізгі деп аталады. Әрі қарай дәлелдеусіз теория қарастыратын негізгі орын аксиома қолданылады. Барлық алдағы теорияның мазмұны аксиомадан логикалық түрде шығарады. Математикалық теорияда аксиоматикалық құруды алғашқы болып геометрияны құруды Эвклид қолданды .
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі ұғымдарға (нүкте, түзу, жазықтық) анықтама бергісі келді. Теорияны дәлелдеуде еш жерде жинақталмаған орын қолданылды.
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз болды. Осы әдісті өзгертуде Н. И. Лобачевский (1792-1856) еңбектерінің маңызы зор болды.
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін айтты және осы айтуын жаңа геометрияны құруда нақтылады. Кейін неміс математигі Ф.Клейн (1849-1925) Лобачевский геометриясын дәлелдеді. Осылайша математика тарихында олардың еңбектері алғашқы болып аксиоматикалық теорияның ділелденбейтін мәселесі көрсетілді.
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне қойылатын негізгі талаптардың бірі болып табылады.
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар. Осының бірі интерпретация болып табылады. Мұнда негізгі ұғым мен қатынас ретінде кейбір жиынның элементтері және олардың арасындағы қатынас таңдалады, одан кейін тексеріледі.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының қорында құрылады.
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер пайда болды (жиын теориясының парадоксы). Осыған мысал ретінде Б. Рассела парадоксы болып табылады.
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”, деп айтамыз егер ол өзінің элементі ретінде өзі болмаса және “дұрыс емес” кері жағдайда . Мысалы, барлық кітаптар жиыны дұрыс жиын, ал ойдағы заттар жиыны дұрыс емес жиын . L –барлық дұрыс жиындар жиыны болсын. Онда L қай жиын класына жатады?
Егер L – “дұрыс” жиын болса, онда L Î L, яғни дұрыс жиын класында, бірақ ол өз элементі ретінде өзі кіреді, сондықтан ол “дұрыс емес”.
Егер L – “дұрыс емес” жиын болса, онда L Ï L, яғни дұрыс жиындар құрамында жоқ, бірақ L өз элементі ретінде өзі кірмейді, сондықтан ол “дұрыс”. Осылайша дұрыс жиын ұғымында қарама-қайшылық туындайды.
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын теориясын құру қажеттілігіне алып келді. Кейінгі өзгерістерге байланысты бұл теория осы заманғы жиын теориясы құрылды.
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943) және оның мектебінде дамытылды. Олар математикалық теорияны құруды синтаксистік теория негізіне сүйене отырып құрды.
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу теориясы деп атады.
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны математикалық логика негізін құру мәселесі туындайды. Әртүрлі тәсілмен аксиома жүйесі және басқа формуланы шығару шартын таңдауда әртүрлі синтаксистік логикалық теорияны аламыз. Олардың әрқайсысын логика есептелімі деп атаймыз.
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
ӘДЕБИЕТТЕР
1. Ершов Ю.Л., Палютин Е.А., «Математическая логика». М., Наука, 1979.
2. Жетпісов Қ., Түсіпов Ж.А., «Математикалық логика», Тараз, 2000.
3. Лавров И.А., Максимова Л.Л., «Задачи по теории множеств, математической статистике и теории алгоритмов». М., Наука, 1975.
4. Лихтарников Л.М., Сукачева Т.Г., «Математическая логика». СПб.: «Лань», 1998.
5. Мальцев А.И., «Алгоритмы и рекурсивные функции». М.: Наука, 1986.
6. Мендельсон Э., «Введение в математическую логику», М., 1976.
1. Ершов Ю.Л., Палютин Е.А., «Математическая логика». М., Наука, 1979.
2. Жетпісов Қ., Түсіпов Ж.А., «Математикалық логика», Тараз, 2000.
3. Лавров И.А., Максимова Л.Л., «Задачи по теории множеств, математической статистике и теории алгоритмов». М., Наука, 1975.
4. Лихтарников Л.М., Сукачева Т.Г., «Математическая логика». СПб.: «Лань», 1998.
5. Мальцев А.И., «Алгоритмы и рекурсивные функции». М.: Наука, 1986.
6. Мендельсон Э., «Введение в математическую логику», М., 1976.
Пән: Математика, Геометрия
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 42 бет
Таңдаулыға:
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 42 бет
Таңдаулыға:
МАЗМҰНЫ
КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған
формулалары 9
1.9 Негізгі тепе-теңдіктер 10
1.10 Формулаларды тепе-тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру 13
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 тарау. тұжырымдар есептелімі 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс 23
Тақырып бойынша тесттер 24
Глава 3. предикаттар логикасы 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе-теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының
формулалары түрінде жазу 31
Тесты по теме 32
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТестТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның ойлау
қабілеті заңының жолдарын қолданып, дәлелденетін ғылым болып табылады.
Адамның ойлау қабілетінің заңын оқу логика пәні болып табылады.
Логика өз алдына ғылым болып грек философы Аристотельдің (384-322 ж.ж
б.э.д) еңбегінде нақтыланған. Ол өзіне дейінгі мәліметтерді жүйеледі және
осы жүйе кейін формальды немесе Аристотель логикасы деп аталды.
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді. Математиканың
дамуы Аристотель логикасының жетіспеушіліктерін көрсетті және оның әрі
қарай дамуын талап етті.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып неміс
математигі Г.Лейбниц (1646-1716) XVI ғ. аяғында айтты. Ол логиканың негізгі
ұғымдарын арнайы шарттармен байланысқан символдармен белгіленуі тиіс дейді.
Бұл кез-келген ойларды есепке ауыстыруға мүмкіндік береді.
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны құрды
және бұл айтылымдар алгебрасын дүниеге әкелді. Логикаға симвлодық
белгілеуді ендіру, бұл ғылымға маңызды болды. Дәл осы символдарды логикаға
ендіру жаңа математикалық логика ғылымының негізін қалады.
Логикада математиканы қолдану логикалық теорияларды жаңа формада
кқруге мүмкіндік берді және есептеуіш аппараттарды адамның ойлау қабілеті
жетпейтін есептерді шешуде қолдану логиканың зерттеу облысын кеңейтті.
XIX ғ. аяғында математика үшін актуальді мәнге ие болатын сұрақтар
туындады, яғни оның негізгі ұғымдары мен идеялары бойынша. Бұл мәселенің
логикалық негізі болды және бұл математикалық логиканың әрі қарай дамуына
алып келді. Бұл қатынаста неміс математигі Г.Фреге (1848-1925) және Итальян
математигі Д. Пеано (1858-1932) еңбектерінде көрсетілген.
Математикалық ойлаудың ерекшеліктері математикалық абстракция және
олардың байланыстарының түрлілігінің ерекшеліктерімен түсіндіріледі.
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі
ретінде қарастырады.
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі
математикалық теорияларды құруда аксиоматикалық әдістердің кең таралуы
болып табылады.
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе
ұғымы және олардың арасындағы қатынас тандалады. Осы ұғымдар мен қатынастар
негізгі деп аталады. Әрі қарай дәлелдеусіз теория қарастыратын негізгі орын
аксиома қолданылады. Барлық алдағы теорияның мазмұны аксиомадан логикалық
түрде шығарады. Математикалық теорияда аксиоматикалық құруды алғашқы болып
геометрияны құруды Эвклид қолданды .
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі ұғымдарға
(нүкте, түзу, жазықтық) анықтама бергісі келді. Теорияны дәлелдеуде еш
жерде жинақталмаған орын қолданылды.
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз болды. Осы
әдісті өзгертуде Н. И. Лобачевский (1792-1856) еңбектерінің маңызы зор
болды.
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін
айтты және осы айтуын жаңа геометрияны құруда нақтылады. Кейін неміс
математигі Ф.Клейн (1849-1925) Лобачевский геометриясын дәлелдеді. Осылайша
математика тарихында олардың еңбектері алғашқы болып аксиоматикалық
теорияның ділелденбейтін мәселесі көрсетілді.
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне
қойылатын негізгі талаптардың бірі болып табылады.
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар.
Осының бірі интерпретация болып табылады. Мұнда негізгі ұғым мен қатынас
ретінде кейбір жиынның элементтері және олардың арасындағы қатынас
таңдалады, одан кейін тексеріледі.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының
қорында құрылады.
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер пайда болды (жиын
теориясының парадоксы). Осыған мысал ретінде Б. Рассела парадоксы болып
табылады.
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”, деп айтамыз
егер ол өзінің элементі ретінде өзі болмаса және “дұрыс емес” кері
жағдайда . Мысалы, барлық кітаптар жиыны дұрыс жиын, ал ойдағы заттар жиыны
дұрыс емес жиын . L –барлық дұрыс жиындар жиыны болсын. Онда L қай жиын
класына жатады?
Егер L – “дұрыс” жиын болса, онда L ( L, яғни дұрыс жиын класында,
бірақ ол өз элементі ретінде өзі кіреді, сондықтан ол “дұрыс емес”.
Егер L – “дұрыс емес” жиын болса, онда L ( L, яғни дұрыс жиындар
құрамында жоқ, бірақ L өз элементі ретінде өзі кірмейді, сондықтан ол
“дұрыс”. Осылайша дұрыс жиын ұғымында қарама-қайшылық туындайды.
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын
теориясын құру қажеттілігіне алып келді. Кейінгі өзгерістерге байланысты
бұл теория осы заманғы жиын теориясы құрылды.
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943) және
оның мектебінде дамытылды. Олар математикалық теорияны құруды синтаксистік
теория негізіне сүйене отырып құрды.
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа
математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу
теориясы деп атады.
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны
математикалық логика негізін құру мәселесі туындайды. Әртүрлі тәсілмен
аксиома жүйесі және басқа формуланы шығару шартын таңдауда әртүрлі
синтаксистік логикалық теорияны аламыз. Олардың әрқайсысын логика
есептелімі деп атаймыз.
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1.1. Тұжырым ұғымы
Бүкіл математикадағы сияқты, біздің курстағы әр бөлімде де бастапқы
негізгі ұғымдар бар. Негізгі ұғымдар анықталмайды. Біздің әрқайсысымыздың
олар туралы ішкі түсінігіміз бар деп есептеледі. Бұл ішкі түсініктерде
математикалық білім саласындағы адамзаттың тарихи тәжірибесі жинақталған.
Негізгі ұғымдар анықталмайды, оларға квазианықтамалар, яғни басқа
анықталған ұғымдар мен объектілерге сілтеме жасайтын анықтамалар беріледі.
Бірінші бөлімде мұндай негізгі анықталған ұғым тұжырымдар болып табылады.
Тұжырым деп ақиқатығы немесе жалғандығы туралы айтуға болатын байланысты
баяндамалы сөйлемді айтамыз.
Мысал 1. 2*2=4 (екі көбейту екі тең төрт).
Мысал 2. Егер натурал сан 6ға бөлінсе, онда ол 3ке бөлінеді.
Мысал 3. Тауық қүс емес.
Мысал 4. 3≥5.
1 және 2 тұжырымдар – ақиқат, ал 3, 4 –жалған. Бір ғана тұжырым болатын
айтылымды жай немесе қарапайым деп атайды. Қарапайым тұжырымға мысал болып
1 тұжырымды айтуға болады.
Граматикалық байланыстар көмегімен (және, немесе, егер..., онда...,
сонда тек сонда ғана) құрылған тұжырымдарды күрделі деп атайды. Осылайша
2 тұжырым мынадай қарапайым тұжырымдардан тұрады: натурал сан 6 бөлінеді,
натурал сан 3 бөлінеді. 4 тұжырым немесе сөзімен қосылған 3 үлкен 5
және 3 тең 5 тұжырымдар.
Әрі қарай бізді тұжырымдардың мағыналы жағы қызықтырмастан, олар қандай
ақиқаттық (ақиқат немесе жалған) мәнге ие болатындығы қызықтырады.
Тұжырымдар алгебрасында бірдей ақиқаттық мәні бар барлық тұжырымдар
алмасымды, яғни бізде ақиқат тұжырым және жалған тұжырым секілді екі
тұжырым класы бар.
Қарапайым тұжырымдары латын алфавиттің a,b,c,...,x,y,z,... әріптерімен,
ақиқат мәнді А әріппен немесе 1 цифрмен, жалған мәнді Ж әріппен немесе 0
цифрмен белгілейміз.
Егер а ақиқат болса, онда а=1, ал егер жалған болса, а=0 деп жазамыз.
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу
а тұжырымының терістеуі жаңа тұжырым болып табылады, бұл тұжырым а ақиқат
болғанда жалған, ал а жалған болғанда кезде, ақиқат болады.
a терістеу тұжырымы (¬a) деп бегіленеді және а емес немесе
дұрыс емес а деп оқылады. ¬a тұжырымының логикалық мәнін кесте арқылы
көрсетуге болады:
Бұл түрдегі кестені ақиқаттық кестесі деп атайды.
Мәселен, 2 кіші 5тен тұжырымы үшін терістеу болып 2 кіші емес 5тен
тұжырымы болады.
а тұжырым болсын. да тұжырым болғандықтан, тұжырымына
терістеу құруға болады, яғни тұжырымы а тұжырымына екілік терістеу
болады. және а тұжырымдарының логикалық мәні бірдей.
1.3 Конъюнкция
a және b тұжырымдарының конъюнкциясы деп, егер екі тұжырым да ақиқат
болғанда ақиқат және егер кем дегенде біреуі жалған болғанда жалған болатын
жаңа тұжырымды айтамыз.
a және b тұжырымдарының конъюнкциясы мына символмен белгіленеді a(b (a ּb,
a b, a&b) және былай оқылады a және b. a , b тұжырымдары конъюнкция
мүшелері деп аталады. a және b екі тұжырымның барлық мүмкін логикалық
мәндерінің конъюнкциясы келесі ақиқат кестеде көрсетілген:
a b a(b
1 1 1
1 0 0
0 1 0
0 0 0
Мысалы: 6 2-ге бөлінеді, 6 3-ке бөлінеді тұжырымы үшін оның
конъюнкциясы 6 2-ге бөлінеді және 6 3-ке бөлінеді тұжырымы болады, бұл
ақиқат.
Конъюнкция операциясы анықтамасында көрсетілгендей және сөзі логика
алгебрасында күнделікті сөйлесудегі сияқты мағынада қолданылады. Бірақ
кәдімгі сөйлесуде және сөзімен мағынасы әртүрлі екі тұжырымды біріктіру
қабылданбаған, ал логика алгебрасында кез-келген екі тұжырым конъюнкциясы
қарастырылған.
1. 4 Дизъюнкция
a және b тұжырымдарының дизъюнкциясы деп,егер екі тұжырымның бірі ақиқат
болса, ақиқат және егер екеуі де жалған болса, жалған болатын жаңа
тұжырымды айтамыз.
a, b тұжырымдардың дизъюнкциясы мына символмен белгіленеді: a(b және
былай оқылады a немесе b. a, b тұжырымдары дизъюнкция мүшелері деп
аталады.
a және b екі тұжырымның барлық мүмкін логикалық мәндерінің дизъюнкциясы
келесі ақиқат кестеде көрсетілген:
1. 5 Эквиваленция
a және b екі тұжырымдарының эквиваленциясы деп егер тұжырымдар
бірдей ақиқат немесе жалған болса, ақиқат, ал қалған жағдайларда жалған
болатын жаңа тұжырымды айтамыз.
a және b тұжырымдарының эквиваленциясы мына символмен белгіленеді: a~b
(a(b) және былай оқылады: “a үшін қажетті және жеткілікті b ” немесе “ a
сонда және тек сонда ғана, қашан b”. a, b тұжырымдары эквиваленция
мүшелері деп аталады. a және b екі тұжырымның барлық мүмкін логикалық
мәндерінің эквиваленциясы келесі ақиқат кестеде көрсетілген:
a B a~b
1 1 1
1 0 0
0 1 0
0 0 1
Мысалы: S төбесі және PQ негізімен берілген SPQ үшбұрышы тең бүйірлі
болады, сонда және тек сонда ғана, қашан P=Q эквиваленциясы
ақиқат. “ S төбесі және PQ негізімен берілген SPQ үшбұрышы тең бүйірлі”
және “ S төбесі және PQ негізімен берілген SPQ үшбұрышында P=Q
” тұжырымдары бір мезгілде ақиқат немесе жалған.
Эквиваленттілік математикалық дәлелдеуде үлкен роль атқарады.
Теоремалардың белгілі бөлігі қажетті және жеткілікті формада құрылады, яғни
эквиваленттілік формасында. Бұл жағдайда оның екі элементінің бірі ақиқат
немесе жалған екенін біле отырып және эквиваленттіліктің өзінің ақиқаттығын
дәлелдеп біз эквиваленттіліктің екінші мүшесінің ақиқат немесе жалған
екенін қорытындылаймыз.
1.6 Импликация
a және b екі тұжырымның импликациясы деп, егер a ақиқат, ал b – жалған
болса жалған және қалған жағдайда ақиқат болатын жаңа тұжырымды айтамыз.
a, b тұжырым импликациясы былай белгіленеді a( b (a ( b a( b) және
былай оқылады “егер a, онда b ” немесе a дан b шығады. а тұжырымын шарт
немесе сілтеме тұжырым, ал b тұжырымын – салдары немесе қорытынды деп
атайды.
a және b екі тұжырымның барлық мүмкін логикалық мәндерінің импликациясы
келесі ақиқаттық кестеде көрсетілген:
a b a( b
1 1 1
1 0 0
0 1 1
0 0 1
Мысалы, “егер 12 6-ға бөлінсе, онда ол 3-ке бөлінеді” тұжырымы ақиқат.
Мұнда ақиқат сілтеме және ақиқат қорытынды.
Импликация математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың
белгілі бөлігі қажетті және жеткілікті формада құрылады. Егер бұл жағдайда
a ақиқат болып және a( b импликацияның ақиқаттығы дәлелденген болса, онда
b салдардың ақиқат екенін қорытындылаймыз.
Логикалық амалдармен алғаш танысқанда импликациядан басқаның барлығы
мейлінше табиғи түрде енгізілген секілді. Ал импликация анықтамасын
енгізуді қабылдауға біздің санамыз қарсылық көрсетіп жатқандай болып
көрінеді. Бірақ импликацияның мұндай анықтамасы біздің түйсікті ішкі
логикамызға және математикада өте жиі қолданылатын егер ..., онда ххх
конструкциясына сәйкес келетіндігін көрсететін мысал келтіруге болады.
Арифметикадан бір теореманы еске түсірейік - Q(x)= Егер х натурал саны 4-
ке бөлінсе онда, ол 2-ге бөлінеді. Бұл теореманың әділдігіне біз күмән
келтіреміз, яғни Q(x ) - қа қандай х натурал санын қойсақ та біз ақиқат
айтылым аламыз. Белгілеу енгіземіз: А(х)= х натурал саны 4-ке бөлінеді,
В(х)= х натурал саны 2-ге бөлінеді.
Сонда шығатыны:
Q(x )= А(x )( В(x )
(1)
(1) формулаға х=8, 2, 3 мәндерін қоя отырып келесілерді аламыз: 1( 1,
0(1, 0( 0. (1) формулаға 1( 0 шарты орындалатындай х-тің мәнін қою мүмкін
емес (себебі келтірілген теорема әділ).
Қарапайым тілде Егер А, онда В түрдегі сөйлемде А мен В мазмұны жағынан
байланысты екенін көреміз. Біздің импликация анықтамасында бұл мүлде
міндетті емес. Яғни біз мынадай импликацияны қарастыру құқымыз бар: Егер
бүгін бейсенбі болса, онда 2*2=5, бұл бейсенбіден басқа барлық күні
ақиқат, ал бейсенбіде жалған.
1.7 Тұжырымдар алгебрасының формулалары
Тұжырымдарға қолданылатын логикалық амалдары көмегімен берілген
тұжырымдардан күрделі тұжырымдарды құруға болады. Операциялардың орындалу
реті жақшамен көрсетіледі. Мысалы, x, y, z үш тұжырымдарынан мынадай
тұжырымды құруға болады:
және .
Қарапайым тұжырымдардан терістеу, конъюнкция, дизъюнкция, импликация және
эквиваленция логикалық амалдарды қолдану көмегімен алынған күрделі тұжырым
тұжырымдар алгебрасының формуласы деп аталады.
Тұжырымдар алгебрасының формулаларын латын алфавиттің бас әріптерімен
белгілейміз: A, B, C,...,X, Y, Z,...
Жазуды жинақтау үшін формулалардағы амалдарды ретімен орындау келісілген.
Басқа барлық операциялардан бұрын конъюнкция орындалады, ал дизъюнкция
импликация мен эквиваленттік бұрын орындалады. Бұл амалдардың орындалу
ретін анықтайтын жақшалар қойылмауы мүмкін. Егер кейбір формуладан немесе
ішформуладан терістеу алынса, ол жағдайда да жақша қойылмайды.
Демек, жоғарыда келтірілген және формулаларды былай
жазуға болады:
және
немесе және .
Логика алгебрасында формуланың логикалық мәні оған кіретін қарапайым
тұжырымдардың логикалық мәндерімен толығымен анықталады. Мысалы, x=1, y=1,
z=0 болғанда ((x(y)((z формуланың логикалық мәні ақиқат болады, яғни
((x(y)((z =1.
Логикалық амалдар сияқты, формуланың барлық мүмкін болған мәндері оның
ақиқаттық кестесі көмегімен берілу мүмкін.
Мысалы, (x(y(х((у формуласы үшін ақиқаттық кестесінің көрінісі
төмендегідей:
х у (x (у (x(y х((у (x(y(х((у
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 1 0 0
0 0 1 1 1 0 0
Егер формуланың құрамына n қарапайым тұжырым енетін болса, онда ол нөл
және бірден тұратын 2n мән қабылдайды немесе формуланың ақиқаттық кестесі
2n қатардан тұрады деп айтуға болады.
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған
формулалары
Егер логика алгебрасының А және В формулалары олардың құрамына енетін
қарапайым тұжырымдарының кез келген мәндерінде бірдей мән қабылдаса, онда
бұл формулалар пара-пар деп аталады. Формулалардың пара-парлығын (
белгісімен белгілейміз, яғни
А (В ( А және В формулалары пара-пар.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 1 мәнді
қабылдайтын болса, онда бұл формула тепе-тең ақиқат (немесе тавтология) деп
аталады.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 0 мәнді
қабылдайтын болса, онда бұл формула тепе-тең жалған (немесе қарама-
қайшылық) деп аталады.
Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар:
егер А және В формулалар пара-пар болса, онда А(В формуласы – тавтология,
және керісінше, егер А(В формуласы тавтология болса, онда А және В
формулалары пара-пар болады.
1.9 Негізгі тепе-теңдіктер
Теорема 1 Келесе тепе-теңдіктер орындалады:
а( b((a(b;
a~b ( (а( b)( b( a) ( ((a(b)( a((b) ( (ab) ( ((a(b)
Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен дәлелдеуге
болады.
Келтірілген тепе-тең көрінетіндей, ( және ~ амалдары (, ( арқылы ¬
өрнектеледі. Кейінірек (, ( және ( арқылы айтылымдар алгебрасының кез-
келген амалын өрнектеуге болатыны көрсетіледі. Сол себепті біз басты
назарды осы амалдардың қасиеттерін зерттеуге аударамыз. Оларды айтылымдар
алгебрасының буль амалдары деп атайды.
Теорема 2 Айтылымдар алгебрасының булдік амалдары үшін келесі 19 тепе-
теңдік орындалады:
0. – екі еселі терістеу заңы
– коммутативтік заңдары
– ассоциативтік заңдары
– дистрибутивтік заңдары
–идемпотенттік заңдары
– де Морган заңдары
– 0 мен 1 заңдары
– жұту заңдары
– үшіншісі өшірілген заңы
– қайшылық заңы
Бұлардың кез-келгенін ақиқаттық кесте көмегімен дәлелдеуге болады.
1.10 Формулаларды тепе-тең түрлендіру
Тепе-теңдіктерді пайдаланып, формуланы немесе оның бөлігін оған пара-пар
формулаға ауыстыруға болады. Мұндай түрлендірулер тепе-тең түрлендірлер деп
аталады.
Тепе-тең түрлендірулер тепе-теңдіктерді дәлелдеу, формуланы берілген
түрге келтіру, формуланы ықшамдау үшін қолданылады.
Егер А формуланың құрамына оған пара-пар В формулаға қарағанда аз әріптер
мен логикалық амалдар кіретін болса, онда А формуласы В дан ықшам деп
саналады. Әдетде эквиваленция және импликация амалдары дизъюнкция және
конъюнкция амалдарына ауыстырылады, ал терістеу қарапайым тұжырымдардан
алынады.
1.11 Логика алгебрасының функциялары
Жоғарыда айтылғандай, логика алгебрасы формуласының мәні бұл формулаға
кіретін тұжырымдардың мәндеріне тәуелді. Сондықтан логика алгебрасының
формуласы оған кіретін қарапайым тұжырымдардың функциясы болады.
Мысалы, формуласы үш айнымалының f(x,y,z) функциясы болады. Бұл
функция және оның аргументтері тек нөл немесе бір екі мәннің біреуін
қабылдайды.
Анықтама Функцией алгебры логики n переменных (или функций Буля)
называется функция n переменных, где каждая переменная принимает два
значения: 0 и 1, и при этом функция может принимать только одно из двух
значений: 0 или 1.
Ясно, что тождественно истинные и тождественно ложные формулы алгебры
логики представляют собой постоянные функции, а две равносильные функции
выражают одну и ту же функцию.
n айнымалы функциялардың санын анықтаймыз. Логика алгебрасының әрбір
функциясын (логика алгебрасының формуласы сияқты) 2n қатардан тұратын
ақиқаттық кестесі көмегімен беруге болады, яғни логика алгебрасының әрбір n
айнымалы функциясы 2n әртүрлі мән қабылдайды. Сондықтан, n айнымалы
функциясы ұзындығы 2n болған нөл және бір мәндерінен тұратын кейбір тобымен
толығымен анықталады, ал ұзындығы 2n болған нөл және бірден тұратын
топтарының жалпы саны тең. Демек, логика алгебрасының барлық n
айнымалы функциялардың саны санына тең.
Мысалы, бір айнымалы әртүрлі функциялардың саны төрт, ал екі айнымалы
функциялардың саны он алты. Логика алгебрасының бір және екі айнымалы
функциялардың барлығын жазып шығамыз.
Бір айнымалы барлық функциялардың ақиқаттық кестесін қарастырамыз. Ол
келесі көріністе болады:
x f1(x) f2(x) f3(x) f4(x)
1 1 1 0 0
0 1 0 1 0
Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар болады:
f1(x)=1, f4(x)=0, ал .
Барлық мүмкін болған екі айнымалы функциялардың ақиқаттық кестесі келесі
түрде болады:.
x Y f1 f2
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
Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген
формула қарпайым тұжырымдардың 1, 4, 5 жолдардағы үлестірулерінде ақиқат
мән қабылдайды. Конъюнкцияның ақиқаттық кестесңн пайдаланып, осы жолдардан
қарапайым конъюнкция құрайық.
Бірінші жолдағы мәндерде 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 логикалық амалдардың символдары болсын. Егер тұжырымдар
алгебрасының кез келген формуласы үшін оған пара-пар (1, (2, ..., (n
амалдарының көмегімен құрылған формула бар болса, онда (1, (2, ..., (n жүйе
толық деп аталады.
Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және
КНФ болғандықтан, (, (, ( – толық жүйе екендігі түсінікті.
Лемма 9.1 Логикалық байланыстардың келесі жиындары:
(, (, (, ( , (, ( , (, ( , (, (
толық жүйе құрайды.
Лемма 9.2 (, (, ( , ( жиындары логикалық амалдардың толық жүйесін
құрмайды.
Тақырып бойынша тесттер
1. Келесі импликациялардың қайсысы жалған?
1) егер 2(2=4, онда 23;
2) егер 2(2=4, онда 23;
3) егер 2(2=5, онда 23;
4) егер 2(2=5, онда 23;
2. Келесі сөйлемдердің қайсысы тұжырым болмайды?
1) Информатика кафедрасының студенті.
2) Париж – Испания астанасы.
3) 3 саны А жиынына тиісті.
3. Айнымалылардың қайсылары бір бірінің терістеулері болады:
1) 23, 2(3;
2) 69, 69;
3) f функциясы жұп, f функциясы тақ;
4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі.
4. A(B тұжырымы ақиқат болсын. ((A(B ) ( ( (A(B ) тұжырымы қандай логикалық
мәнге ие болады?
1) ақиқат
2) жалған
5. ( ((P(Q ) ( ((P(Q ) (P) формуланы ықшамдаңыз:
1) 1
2) 0
3) Р
4) Q
6. Келесі өрнектердің қайсысы формула болады?:
1) ((P(( (Q(R )) ( (((P~ R ) (Q ))
2) ((P(Q) R) ((S
7. КНФ-ті табыңыз: ((x(z )((x(y)
1) (x(y((z)
2) (x(y)(y(z)
3) y(z
8. 0 мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті
бірмүшені құрыңыз:
1) x(y
2) (x(y
3) x((y
4) (x ((y
9. формулаға пара-пар тек және амалдары көмегімен
құрылған формуланы табыңыз:
1) (((x(y((z )
2) x(y
10. ДНФті табыңыз: (x~y) (( ( z(T )
1) (x(y(z((T) ( ((x((y(z((T);
2) x (y(z
2 тарау. тұжырымдар есептелімі
2.1 Тұжырымдар есептелімі формуласының ұғымы
Тұжырымдар есептелімі бұл интерпретациясы тұжырымдар алгебрасы болатын
аксиоматикалық логикалық жүйе.
Әрбір есептелімнің сипаттамасына бұл есептелімі символдарының,
формулаларының сипаттамасы, дәлелденетін формулалардың анықтамасы енеді.
Тұжырымдар есептелімінің алфавиті үш түрлі символдардан тұрады:
1. Бұл символдарды айнымалы тұжырымдар деп атаймыз.
2. Бұл символдар логикалық байланыс деген жалпы атауға ие.
Келтірілген символдардың біріншісі дизъюнкция (немесе логикалық қосу)
белгісі, екіншісі – конъюнкция (немесе логикалық көбейту) белгісі, үшіншісі
– импликация және төртіншісі – терістеу белгісі.
3. Жақшалар деп аталатын символдар: (, ).
Тұжырымдар есептелімінде басқа символдар болмайды.
Тұжырымдар есептелімінің формуласы тұжырымдар есептелімі алфавитінің
символдарының тізбегі болады. Формула белгісі үшін латын алфавитінің үлкен
әріптерін қолданамыз. Олар өздері есептелімнің символдары болмай,
формулалардың тек шартты белгілері болады.
Тұжырымдар есептелімі формуласының анықтамасы
1. Кез келген айнымалы формула б олады.
2. Егер А және В – формулалар болса, онда сөздер де формулалар.
3. Ешқандай басқа символдардың қатары формула болмайды.
Айнымалы тұжырымдарды қарапайым формулалар деп атаймыз.
Тұжырымдар есептелімі формуласына мысал келтірейік.
айнымалы тұжырымдар анықтаманың 1-ші бөлімі бойынша формулалар
болады. Бірақ, онда сөздер де анықтаманың 2-ші бөлімі бойынша
формулалар бола алады. Сол себепке байланысты сөздер де формула бола
алады.
Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі
енгізіледі.
1. Қарапайым формуланың ішформуласы оның өзі болады.
2. Егер формула көрінісінде болса, онда оның ішформулалары формуланың
өзі, А формуласы және А формуланың барлық ішформулалары болады.
3. Егер формула (А*В) (мұнда * – үш символдардың бірі деп түсінеміз)
көрінісінде болса, онда оның ішформулалары формуланың өзі, А, В формулалары
және А мен В формулалардың барлық ішформулалары болады.
Формуладағы логикалық амалдарының саны формуланың рангі деп аталады.
2.2. Дәлелденетін формула ұғымы
Тұжырымдар есептелімінің құруда келесі кезең дәлелденетін (шығарылатын)
формулалардың класын бөліктеу болады.
Дәлелденетін формула анықтамасы формулалар анықтамасы сияқты. Алдымен
бастапқы дәлелденетін шығарылатын формулалар (аксиомалар) анықталады, ал
содан кейін бар дәлелденетін формулалардан жаңа дәлелденетін формулаларды
алуға мүмкіндік беретін шығару ережелері анықталады. Бастапқы дәлелденетін
формулалардан шығару ережелерін қолдану көмегімен жаңа дәлелденетін
формуланы алу процесі берілген формуланы аксиомалардан шығаруы (дәлелдеуі)
деп аталады.
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі
Тұжырымдар есептелімінің аксиомалар жүйесі төрт топқа бөлінетін 11
аксиомадан тұрады.
Аксималардың бірінші тобы (құрамыларыны тек импликация енеді).
: .
:.
Аксималардың екінші тобы ( импликацияға конъюнкция қосылды):
:
: .
: .
Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды):
:
:
: .
Аксималардың төртінші тобы (импликацияға терістеу қосылды):
:
:
:
2.4 Шығару ережелері
1. Алмастыру ережесі (АЕ).
Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін)
формула, х – айнымалы, В – тұжырымдар есептелімінің кез келген формуласы
болса, онда А формуладағы х айнымалыны В формулаға алмастыру нәтижесінде
алынған формула да шығарылатын (дәлелденетін) болады.
А формуладағы х айнымалыны В формулаға алмастыру амалы алмастыру деп
аталады да келесі түрде жазылады:
немесе .
Егер А – шығарылатын (дәлелденетін) болса, онда ├А деп жазамыз. АЕ
схематикалық түрде төмендегідей жазуға болады:
├А____ .
├
Бұл жазылу былай оқылады: “Егер А формуласы шығарылатын (дәлелденетін)
болса, онда формуласы да шығарылатын (дәлелденетін) болады.
2 Қорытындылау ережесі (ҚЕ).
Егер А және А→В формулалары тұжырымдар есептелімінде шығарылатын
(дәлелденетін) болса, онда В формуласы да шығарылатын (дәлелденетін)
болады. Бұл ереженің схематикалық жазылуы мынадай болады:
├А;├А→В (Modus ponens)
├В
Бұл ереженің дұрыстығы айқын: егер импликация мен шарт ақиқат болса, онда
импликациядағы қорытынды тек ақиқат болуы мүмкін.
2.5 Дәлелденетін формуланың анықтамасы
а) Әрбір аксиома дәлелденетін формула болады.
б) Кез келген В формуласынан х айнымалының орнына алмастыруды қолдану
нәтижесінде алынған формула – дәлелденетін формула.
в) А және дәлелденетін формулаларға қорытындылау ережесін қолдану
нәтижесінде алынған В формуласы – дәлелденетін формула болады.
г) Тұжырымдар есептелімінің ешқандай басқа формуласы дәледенетін болып
саналмайды.
Дәлелденетін формулаларды шығару процесін формулалардың дәлелдеуі
(шығаруы) деп атаймыз. Бұл бір дәлелденетін формуладан әр қадамда
аксиомаларды, алмастыру және қорытындылау ережелерін қолдану көмегімен
басқа дәлелденетін формулаға өту процесі (белгілі мағынада логика
алгебрасындағы тепе-тең түрлендірулердің аналогі), сондықтан қарапайым
формуланың шығаруы да көпқадамды, күрделі болуы мүмкін.
2.6 Туынды шығару ережелері
Күрделі алмастыру ережесі (КАЕ)
Туынды шығару ережелері, қарастырылған шығару ережелері сияқты, жаңа
дәлелденетін формулаларды алуға мүмкіндік береді. Бұл ережелер алмастыру
және қорытындылау ережелері көмегімен алынған, сондықтан, олар туынды
ережелер деп аталады.
А – дәлелденетін формула, – айнымалылар, ал – тұжырымдар
есептелімінің кез келген формулалары болсын. Онда А формулада
айнымалыларын формулаларға алмастыру нәтижесі дәлелденетін формула
болады.
КАЕ схематикалық түрде былай жазылады:
├А______
├
Күрделі қорытындылау ережесі
Қорытындылау ережесін де жалпылау мүмкін. Жалпылау нәтижесінде алынған
туынды ереже
түрдегі формулаларға қолданылады да былай анықталады:
егер және формулалар дәлелденетін болса, онда L формуласы
да дәлелденетін формула.
Күрделі қорытындылау ережесі былай жазылады:
├А1, ├А2, ...,├Аn, ├A1→(A2→(A3→(...(An→L) ...))) .
├ L
Силлогизм ережесі
Егер А→В және В→С формулалары дәлелденетін болса, онда А→С формуласы да
дәлелденеді, яғни
├А→В,├В→С .
├А→С
Контрапозиция ережесі
Егер А→В формуласы дәлелденетін болса, онда ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
КІРІСПЕ 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ 5
1.1. Тұжырым ұғымы 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу 5
1.3 Конъюнкция 6
1. 4 Дизъюнкция 6
1. 5 Эквиваленция 7
1.6 Импликация 7
1.7 Тұжырымдар алгебрасының формулалары 8
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған
формулалары 9
1.9 Негізгі тепе-теңдіктер 10
1.10 Формулаларды тепе-тең түрлендіру 11
1.11 Логика алгебрасының функциялары 11
1.12 Нормал және жетілдірілген формалар 12
1.13 Формулаларды ақиқаттық мәндер кестесі бойынша қалпына келтіру 13
1.14 Логикалық байланыстардың толық жүйелері 14
Тақырып бойынша тесттер 15
2 тарау. тұжырымдар есептелімі 17
2.1 Тұжырымдар есептелімі формуласының ұғымы 17
2.2. Дәлелденетін формула ұғымы 18
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі 18
2.4 Шығару ережелері 18
2.5 Дәлелденетін формуланың анықтамасы 19
2.6 Туынды шығару ережелері 19
2.7 Формулаларды гипотезалардан қорытып шығару 21
2.8 Шығарылу ережелері 22
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс 23
Тақырып бойынша тесттер 24
Глава 3. предикаттар логикасы 26
3.1 Предикат ұғымы 26
3.2 Предикаттарға логикалық амалдарды қолдану 27
3.3 Кванторлық амалдар 28
3.4 Предикаттар логикасының формуласының ұғымы 29
3.5 Предикаттар логикасының формулаларының тепе-теңдігі 30
3.6 Пренекстік нормал форма 31
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының
формулалары түрінде жазу 31
Тесты по теме 32
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ 34
4.1 Алгоритм түсінігі және оның қасиеттері 34
4.2. Тьюринг машиналары 35
4.3 Машинаның жұмыс істеу ережелері 35
4.4 Машина мысалдары 36
Тақырып бойынша тесттер 36
КУРС БОЙЫНША ТестТЕР 39
ӘДЕБИЕТТЕР 43
КІРІСПЕ
Математика барлық тұжырымдар ақыл қорытындысы арқылы, яғни адамның ойлау
қабілеті заңының жолдарын қолданып, дәлелденетін ғылым болып табылады.
Адамның ойлау қабілетінің заңын оқу логика пәні болып табылады.
Логика өз алдына ғылым болып грек философы Аристотельдің (384-322 ж.ж
б.э.д) еңбегінде нақтыланған. Ол өзіне дейінгі мәліметтерді жүйеледі және
осы жүйе кейін формальды немесе Аристотель логикасы деп аталды.
Формальды логика еш өзгеріссіз 20 ғасырдай өмір сүрді. Математиканың
дамуы Аристотель логикасының жетіспеушіліктерін көрсетті және оның әрі
қарай дамуын талап етті.
Математикалық негізде логиканы құру идеясын тарихта алғашқы болып неміс
математигі Г.Лейбниц (1646-1716) XVI ғ. аяғында айтты. Ол логиканың негізгі
ұғымдарын арнайы шарттармен байланысқан символдармен белгіленуі тиіс дейді.
Бұл кез-келген ойларды есепке ауыстыруға мүмкіндік береді.
Алғашқы болып Лейбництің айтуын жүзеге асырған ағылшын ғалымы
Д. Буль (1815-1864). Ол айтылымдар әріптермен белгіленген алгебраны құрды
және бұл айтылымдар алгебрасын дүниеге әкелді. Логикаға симвлодық
белгілеуді ендіру, бұл ғылымға маңызды болды. Дәл осы символдарды логикаға
ендіру жаңа математикалық логика ғылымының негізін қалады.
Логикада математиканы қолдану логикалық теорияларды жаңа формада
кқруге мүмкіндік берді және есептеуіш аппараттарды адамның ойлау қабілеті
жетпейтін есептерді шешуде қолдану логиканың зерттеу облысын кеңейтті.
XIX ғ. аяғында математика үшін актуальді мәнге ие болатын сұрақтар
туындады, яғни оның негізгі ұғымдары мен идеялары бойынша. Бұл мәселенің
логикалық негізі болды және бұл математикалық логиканың әрі қарай дамуына
алып келді. Бұл қатынаста неміс математигі Г.Фреге (1848-1925) және Итальян
математигі Д. Пеано (1858-1932) еңбектерінде көрсетілген.
Математикалық ойлаудың ерекшеліктері математикалық абстракция және
олардың байланыстарының түрлілігінің ерекшеліктерімен түсіндіріледі.
Осыған орай осы заманғы математикалық логиканы математиканың бөлімі
ретінде қарастырады.
Математикалық логиканың дамуының негізгі себептерінің бірі әртүрлі
математикалық теорияларды құруда аксиоматикалық әдістердің кең таралуы
болып табылады.
Математикалық теорияны аксиоматикық құруда алдын-ала кейбір белгісіз жүйе
ұғымы және олардың арасындағы қатынас тандалады. Осы ұғымдар мен қатынастар
негізгі деп аталады. Әрі қарай дәлелдеусіз теория қарастыратын негізгі орын
аксиома қолданылады. Барлық алдағы теорияның мазмұны аксиомадан логикалық
түрде шығарады. Математикалық теорияда аксиоматикалық құруды алғашқы болып
геометрияны құруды Эвклид қолданды .
Бұл теория алғашқыда әлсіз түсіндірілді. Эвклид мұнда негізгі ұғымдарға
(нүкте, түзу, жазықтық) анықтама бергісі келді. Теорияны дәлелдеуде еш
жерде жинақталмаған орын қолданылды.
Теорияны аксиоматикалық құру тәсілі XIX ғ. дейін жалғыз болды. Осы
әдісті өзгертуде Н. И. Лобачевский (1792-1856) еңбектерінің маңызы зор
болды.
Лобачевский алғашқы болып Евклидтің 5 постулатының дәлелденбейтінін
айтты және осы айтуын жаңа геометрияны құруда нақтылады. Кейін неміс
математигі Ф.Клейн (1849-1925) Лобачевский геометриясын дәлелдеді. Осылайша
математика тарихында олардың еңбектері алғашқы болып аксиоматикалық
теорияның ділелденбейтін мәселесі көрсетілді.
Қарсылықты емес аксиоматикалық теория осы теорияның аксиома жүйесіне
қойылатын негізгі талаптардың бірі болып табылады.
Қарсылықты емес математикалық теорияны дәлелдеудің әртүрлі тәсілі бар.
Осының бірі интерпретация болып табылады. Мұнда негізгі ұғым мен қатынас
ретінде кейбір жиынның элементтері және олардың арасындағы қатынас
таңдалады, одан кейін тексеріледі.
Математикалық теория үшін интерпретацияның көпшілігі жиын теориясының
қорында құрылады.
Бірақтан, XIX ғ. аяғында жиын теориясында кемшіліктер пайда болды (жиын
теориясының парадоксы). Осыған мысал ретінде Б. Рассела парадоксы болып
табылады.
Барлық ойланды жиынды екі класқа бөлеміз. Жиынды “дұрыс”, деп айтамыз
егер ол өзінің элементі ретінде өзі болмаса және “дұрыс емес” кері
жағдайда . Мысалы, барлық кітаптар жиыны дұрыс жиын, ал ойдағы заттар жиыны
дұрыс емес жиын . L –барлық дұрыс жиындар жиыны болсын. Онда L қай жиын
класына жатады?
Егер L – “дұрыс” жиын болса, онда L ( L, яғни дұрыс жиын класында,
бірақ ол өз элементі ретінде өзі кіреді, сондықтан ол “дұрыс емес”.
Егер L – “дұрыс емес” жиын болса, онда L ( L, яғни дұрыс жиындар
құрамында жоқ, бірақ L өз элементі ретінде өзі кірмейді, сондықтан ол
“дұрыс”. Осылайша дұрыс жиын ұғымында қарама-қайшылық туындайды.
Теория жиынында қарама-қарсылықты жою ЦЕРМЕЛО-ны аксиоматикалық жиын
теориясын құру қажеттілігіне алып келді. Кейінгі өзгерістерге байланысты
бұл теория осы заманғы жиын теориясы құрылды.
Математиканы негіздеудің басқа тәсілдері Д. ГИЛБЕРТ (1862-1943) және
оның мектебінде дамытылды. Олар математикалық теорияны құруды синтаксистік
теория негізіне сүйене отырып құрды.
Осылайша, математикалық теорияның қарсылықты еместігін дәлелдеу басқа
математикалық теория пәні болды, оны Гильберт математика немесе дәлелдеу
теориясы деп атады.
Осы тұрғыда синтаксистік, яғни фромальданған аксиоматикалық теорияны
математикалық логика негізін құру мәселесі туындайды. Әртүрлі тәсілмен
аксиома жүйесі және басқа формуланы шығару шартын таңдауда әртүрлі
синтаксистік логикалық теорияны аламыз. Олардың әрқайсысын логика
есептелімі деп атаймыз.
Бұл курста біз классикалық тұжырымдар есептелімімен танысамыз.
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ
1.1. Тұжырым ұғымы
Бүкіл математикадағы сияқты, біздің курстағы әр бөлімде де бастапқы
негізгі ұғымдар бар. Негізгі ұғымдар анықталмайды. Біздің әрқайсысымыздың
олар туралы ішкі түсінігіміз бар деп есептеледі. Бұл ішкі түсініктерде
математикалық білім саласындағы адамзаттың тарихи тәжірибесі жинақталған.
Негізгі ұғымдар анықталмайды, оларға квазианықтамалар, яғни басқа
анықталған ұғымдар мен объектілерге сілтеме жасайтын анықтамалар беріледі.
Бірінші бөлімде мұндай негізгі анықталған ұғым тұжырымдар болып табылады.
Тұжырым деп ақиқатығы немесе жалғандығы туралы айтуға болатын байланысты
баяндамалы сөйлемді айтамыз.
Мысал 1. 2*2=4 (екі көбейту екі тең төрт).
Мысал 2. Егер натурал сан 6ға бөлінсе, онда ол 3ке бөлінеді.
Мысал 3. Тауық қүс емес.
Мысал 4. 3≥5.
1 және 2 тұжырымдар – ақиқат, ал 3, 4 –жалған. Бір ғана тұжырым болатын
айтылымды жай немесе қарапайым деп атайды. Қарапайым тұжырымға мысал болып
1 тұжырымды айтуға болады.
Граматикалық байланыстар көмегімен (және, немесе, егер..., онда...,
сонда тек сонда ғана) құрылған тұжырымдарды күрделі деп атайды. Осылайша
2 тұжырым мынадай қарапайым тұжырымдардан тұрады: натурал сан 6 бөлінеді,
натурал сан 3 бөлінеді. 4 тұжырым немесе сөзімен қосылған 3 үлкен 5
және 3 тең 5 тұжырымдар.
Әрі қарай бізді тұжырымдардың мағыналы жағы қызықтырмастан, олар қандай
ақиқаттық (ақиқат немесе жалған) мәнге ие болатындығы қызықтырады.
Тұжырымдар алгебрасында бірдей ақиқаттық мәні бар барлық тұжырымдар
алмасымды, яғни бізде ақиқат тұжырым және жалған тұжырым секілді екі
тұжырым класы бар.
Қарапайым тұжырымдары латын алфавиттің a,b,c,...,x,y,z,... әріптерімен,
ақиқат мәнді А әріппен немесе 1 цифрмен, жалған мәнді Ж әріппен немесе 0
цифрмен белгілейміз.
Егер а ақиқат болса, онда а=1, ал егер жалған болса, а=0 деп жазамыз.
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу
а тұжырымының терістеуі жаңа тұжырым болып табылады, бұл тұжырым а ақиқат
болғанда жалған, ал а жалған болғанда кезде, ақиқат болады.
a терістеу тұжырымы (¬a) деп бегіленеді және а емес немесе
дұрыс емес а деп оқылады. ¬a тұжырымының логикалық мәнін кесте арқылы
көрсетуге болады:
Бұл түрдегі кестені ақиқаттық кестесі деп атайды.
Мәселен, 2 кіші 5тен тұжырымы үшін терістеу болып 2 кіші емес 5тен
тұжырымы болады.
а тұжырым болсын. да тұжырым болғандықтан, тұжырымына
терістеу құруға болады, яғни тұжырымы а тұжырымына екілік терістеу
болады. және а тұжырымдарының логикалық мәні бірдей.
1.3 Конъюнкция
a және b тұжырымдарының конъюнкциясы деп, егер екі тұжырым да ақиқат
болғанда ақиқат және егер кем дегенде біреуі жалған болғанда жалған болатын
жаңа тұжырымды айтамыз.
a және b тұжырымдарының конъюнкциясы мына символмен белгіленеді a(b (a ּb,
a b, a&b) және былай оқылады a және b. a , b тұжырымдары конъюнкция
мүшелері деп аталады. a және b екі тұжырымның барлық мүмкін логикалық
мәндерінің конъюнкциясы келесі ақиқат кестеде көрсетілген:
a b a(b
1 1 1
1 0 0
0 1 0
0 0 0
Мысалы: 6 2-ге бөлінеді, 6 3-ке бөлінеді тұжырымы үшін оның
конъюнкциясы 6 2-ге бөлінеді және 6 3-ке бөлінеді тұжырымы болады, бұл
ақиқат.
Конъюнкция операциясы анықтамасында көрсетілгендей және сөзі логика
алгебрасында күнделікті сөйлесудегі сияқты мағынада қолданылады. Бірақ
кәдімгі сөйлесуде және сөзімен мағынасы әртүрлі екі тұжырымды біріктіру
қабылданбаған, ал логика алгебрасында кез-келген екі тұжырым конъюнкциясы
қарастырылған.
1. 4 Дизъюнкция
a және b тұжырымдарының дизъюнкциясы деп,егер екі тұжырымның бірі ақиқат
болса, ақиқат және егер екеуі де жалған болса, жалған болатын жаңа
тұжырымды айтамыз.
a, b тұжырымдардың дизъюнкциясы мына символмен белгіленеді: a(b және
былай оқылады a немесе b. a, b тұжырымдары дизъюнкция мүшелері деп
аталады.
a және b екі тұжырымның барлық мүмкін логикалық мәндерінің дизъюнкциясы
келесі ақиқат кестеде көрсетілген:
1. 5 Эквиваленция
a және b екі тұжырымдарының эквиваленциясы деп егер тұжырымдар
бірдей ақиқат немесе жалған болса, ақиқат, ал қалған жағдайларда жалған
болатын жаңа тұжырымды айтамыз.
a және b тұжырымдарының эквиваленциясы мына символмен белгіленеді: a~b
(a(b) және былай оқылады: “a үшін қажетті және жеткілікті b ” немесе “ a
сонда және тек сонда ғана, қашан b”. a, b тұжырымдары эквиваленция
мүшелері деп аталады. a және b екі тұжырымның барлық мүмкін логикалық
мәндерінің эквиваленциясы келесі ақиқат кестеде көрсетілген:
a B a~b
1 1 1
1 0 0
0 1 0
0 0 1
Мысалы: S төбесі және PQ негізімен берілген SPQ үшбұрышы тең бүйірлі
болады, сонда және тек сонда ғана, қашан P=Q эквиваленциясы
ақиқат. “ S төбесі және PQ негізімен берілген SPQ үшбұрышы тең бүйірлі”
және “ S төбесі және PQ негізімен берілген SPQ үшбұрышында P=Q
” тұжырымдары бір мезгілде ақиқат немесе жалған.
Эквиваленттілік математикалық дәлелдеуде үлкен роль атқарады.
Теоремалардың белгілі бөлігі қажетті және жеткілікті формада құрылады, яғни
эквиваленттілік формасында. Бұл жағдайда оның екі элементінің бірі ақиқат
немесе жалған екенін біле отырып және эквиваленттіліктің өзінің ақиқаттығын
дәлелдеп біз эквиваленттіліктің екінші мүшесінің ақиқат немесе жалған
екенін қорытындылаймыз.
1.6 Импликация
a және b екі тұжырымның импликациясы деп, егер a ақиқат, ал b – жалған
болса жалған және қалған жағдайда ақиқат болатын жаңа тұжырымды айтамыз.
a, b тұжырым импликациясы былай белгіленеді a( b (a ( b a( b) және
былай оқылады “егер a, онда b ” немесе a дан b шығады. а тұжырымын шарт
немесе сілтеме тұжырым, ал b тұжырымын – салдары немесе қорытынды деп
атайды.
a және b екі тұжырымның барлық мүмкін логикалық мәндерінің импликациясы
келесі ақиқаттық кестеде көрсетілген:
a b a( b
1 1 1
1 0 0
0 1 1
0 0 1
Мысалы, “егер 12 6-ға бөлінсе, онда ол 3-ке бөлінеді” тұжырымы ақиқат.
Мұнда ақиқат сілтеме және ақиқат қорытынды.
Импликация математикалық дәлелдеуде үлкен роль атқарады. Теоремалардың
белгілі бөлігі қажетті және жеткілікті формада құрылады. Егер бұл жағдайда
a ақиқат болып және a( b импликацияның ақиқаттығы дәлелденген болса, онда
b салдардың ақиқат екенін қорытындылаймыз.
Логикалық амалдармен алғаш танысқанда импликациядан басқаның барлығы
мейлінше табиғи түрде енгізілген секілді. Ал импликация анықтамасын
енгізуді қабылдауға біздің санамыз қарсылық көрсетіп жатқандай болып
көрінеді. Бірақ импликацияның мұндай анықтамасы біздің түйсікті ішкі
логикамызға және математикада өте жиі қолданылатын егер ..., онда ххх
конструкциясына сәйкес келетіндігін көрсететін мысал келтіруге болады.
Арифметикадан бір теореманы еске түсірейік - Q(x)= Егер х натурал саны 4-
ке бөлінсе онда, ол 2-ге бөлінеді. Бұл теореманың әділдігіне біз күмән
келтіреміз, яғни Q(x ) - қа қандай х натурал санын қойсақ та біз ақиқат
айтылым аламыз. Белгілеу енгіземіз: А(х)= х натурал саны 4-ке бөлінеді,
В(х)= х натурал саны 2-ге бөлінеді.
Сонда шығатыны:
Q(x )= А(x )( В(x )
(1)
(1) формулаға х=8, 2, 3 мәндерін қоя отырып келесілерді аламыз: 1( 1,
0(1, 0( 0. (1) формулаға 1( 0 шарты орындалатындай х-тің мәнін қою мүмкін
емес (себебі келтірілген теорема әділ).
Қарапайым тілде Егер А, онда В түрдегі сөйлемде А мен В мазмұны жағынан
байланысты екенін көреміз. Біздің импликация анықтамасында бұл мүлде
міндетті емес. Яғни біз мынадай импликацияны қарастыру құқымыз бар: Егер
бүгін бейсенбі болса, онда 2*2=5, бұл бейсенбіден басқа барлық күні
ақиқат, ал бейсенбіде жалған.
1.7 Тұжырымдар алгебрасының формулалары
Тұжырымдарға қолданылатын логикалық амалдары көмегімен берілген
тұжырымдардан күрделі тұжырымдарды құруға болады. Операциялардың орындалу
реті жақшамен көрсетіледі. Мысалы, x, y, z үш тұжырымдарынан мынадай
тұжырымды құруға болады:
және .
Қарапайым тұжырымдардан терістеу, конъюнкция, дизъюнкция, импликация және
эквиваленция логикалық амалдарды қолдану көмегімен алынған күрделі тұжырым
тұжырымдар алгебрасының формуласы деп аталады.
Тұжырымдар алгебрасының формулаларын латын алфавиттің бас әріптерімен
белгілейміз: A, B, C,...,X, Y, Z,...
Жазуды жинақтау үшін формулалардағы амалдарды ретімен орындау келісілген.
Басқа барлық операциялардан бұрын конъюнкция орындалады, ал дизъюнкция
импликация мен эквиваленттік бұрын орындалады. Бұл амалдардың орындалу
ретін анықтайтын жақшалар қойылмауы мүмкін. Егер кейбір формуладан немесе
ішформуладан терістеу алынса, ол жағдайда да жақша қойылмайды.
Демек, жоғарыда келтірілген және формулаларды былай
жазуға болады:
және
немесе және .
Логика алгебрасында формуланың логикалық мәні оған кіретін қарапайым
тұжырымдардың логикалық мәндерімен толығымен анықталады. Мысалы, x=1, y=1,
z=0 болғанда ((x(y)((z формуланың логикалық мәні ақиқат болады, яғни
((x(y)((z =1.
Логикалық амалдар сияқты, формуланың барлық мүмкін болған мәндері оның
ақиқаттық кестесі көмегімен берілу мүмкін.
Мысалы, (x(y(х((у формуласы үшін ақиқаттық кестесінің көрінісі
төмендегідей:
х у (x (у (x(y х((у (x(y(х((у
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 1 0 0
0 0 1 1 1 0 0
Егер формуланың құрамына n қарапайым тұжырым енетін болса, онда ол нөл
және бірден тұратын 2n мән қабылдайды немесе формуланың ақиқаттық кестесі
2n қатардан тұрады деп айтуға болады.
1.8 Тұжырымдар алгебрасының пара-пар, тепе-тең ақиқат және тепе-тең жалған
формулалары
Егер логика алгебрасының А және В формулалары олардың құрамына енетін
қарапайым тұжырымдарының кез келген мәндерінде бірдей мән қабылдаса, онда
бұл формулалар пара-пар деп аталады. Формулалардың пара-парлығын (
белгісімен белгілейміз, яғни
А (В ( А және В формулалары пара-пар.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 1 мәнді
қабылдайтын болса, онда бұл формула тепе-тең ақиқат (немесе тавтология) деп
аталады.
Егер А формуласы оған кіретін айнымалылардың барлық мәндерінде 0 мәнді
қабылдайтын болса, онда бұл формула тепе-тең жалған (немесе қарама-
қайшылық) деп аталады.
Пара-парлық және эквиваленттік ұғымдары арасында мынадай байланыс бар:
егер А және В формулалар пара-пар болса, онда А(В формуласы – тавтология,
және керісінше, егер А(В формуласы тавтология болса, онда А және В
формулалары пара-пар болады.
1.9 Негізгі тепе-теңдіктер
Теорема 1 Келесе тепе-теңдіктер орындалады:
а( b((a(b;
a~b ( (а( b)( b( a) ( ((a(b)( a((b) ( (ab) ( ((a(b)
Осы тепе-теңдіктердің кез-келгенін ақиқаттық кестесі көмегімен дәлелдеуге
болады.
Келтірілген тепе-тең көрінетіндей, ( және ~ амалдары (, ( арқылы ¬
өрнектеледі. Кейінірек (, ( және ( арқылы айтылымдар алгебрасының кез-
келген амалын өрнектеуге болатыны көрсетіледі. Сол себепті біз басты
назарды осы амалдардың қасиеттерін зерттеуге аударамыз. Оларды айтылымдар
алгебрасының буль амалдары деп атайды.
Теорема 2 Айтылымдар алгебрасының булдік амалдары үшін келесі 19 тепе-
теңдік орындалады:
0. – екі еселі терістеу заңы
– коммутативтік заңдары
– ассоциативтік заңдары
– дистрибутивтік заңдары
–идемпотенттік заңдары
– де Морган заңдары
– 0 мен 1 заңдары
– жұту заңдары
– үшіншісі өшірілген заңы
– қайшылық заңы
Бұлардың кез-келгенін ақиқаттық кесте көмегімен дәлелдеуге болады.
1.10 Формулаларды тепе-тең түрлендіру
Тепе-теңдіктерді пайдаланып, формуланы немесе оның бөлігін оған пара-пар
формулаға ауыстыруға болады. Мұндай түрлендірулер тепе-тең түрлендірлер деп
аталады.
Тепе-тең түрлендірулер тепе-теңдіктерді дәлелдеу, формуланы берілген
түрге келтіру, формуланы ықшамдау үшін қолданылады.
Егер А формуланың құрамына оған пара-пар В формулаға қарағанда аз әріптер
мен логикалық амалдар кіретін болса, онда А формуласы В дан ықшам деп
саналады. Әдетде эквиваленция және импликация амалдары дизъюнкция және
конъюнкция амалдарына ауыстырылады, ал терістеу қарапайым тұжырымдардан
алынады.
1.11 Логика алгебрасының функциялары
Жоғарыда айтылғандай, логика алгебрасы формуласының мәні бұл формулаға
кіретін тұжырымдардың мәндеріне тәуелді. Сондықтан логика алгебрасының
формуласы оған кіретін қарапайым тұжырымдардың функциясы болады.
Мысалы, формуласы үш айнымалының f(x,y,z) функциясы болады. Бұл
функция және оның аргументтері тек нөл немесе бір екі мәннің біреуін
қабылдайды.
Анықтама Функцией алгебры логики n переменных (или функций Буля)
называется функция n переменных, где каждая переменная принимает два
значения: 0 и 1, и при этом функция может принимать только одно из двух
значений: 0 или 1.
Ясно, что тождественно истинные и тождественно ложные формулы алгебры
логики представляют собой постоянные функции, а две равносильные функции
выражают одну и ту же функцию.
n айнымалы функциялардың санын анықтаймыз. Логика алгебрасының әрбір
функциясын (логика алгебрасының формуласы сияқты) 2n қатардан тұратын
ақиқаттық кестесі көмегімен беруге болады, яғни логика алгебрасының әрбір n
айнымалы функциясы 2n әртүрлі мән қабылдайды. Сондықтан, n айнымалы
функциясы ұзындығы 2n болған нөл және бір мәндерінен тұратын кейбір тобымен
толығымен анықталады, ал ұзындығы 2n болған нөл және бірден тұратын
топтарының жалпы саны тең. Демек, логика алгебрасының барлық n
айнымалы функциялардың саны санына тең.
Мысалы, бір айнымалы әртүрлі функциялардың саны төрт, ал екі айнымалы
функциялардың саны он алты. Логика алгебрасының бір және екі айнымалы
функциялардың барлығын жазып шығамыз.
Бір айнымалы барлық функциялардың ақиқаттық кестесін қарастырамыз. Ол
келесі көріністе болады:
x f1(x) f2(x) f3(x) f4(x)
1 1 1 0 0
0 1 0 1 0
Бұл кестеден көрінгендей, бір айнымалы екі функциясы тұрақтылар болады:
f1(x)=1, f4(x)=0, ал .
Барлық мүмкін болған екі айнымалы функциялардың ақиқаттық кестесі келесі
түрде болады:.
x Y f1 f2
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
Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген
формула қарпайым тұжырымдардың 1, 4, 5 жолдардағы үлестірулерінде ақиқат
мән қабылдайды. Конъюнкцияның ақиқаттық кестесңн пайдаланып, осы жолдардан
қарапайым конъюнкция құрайық.
Бірінші жолдағы мәндерде 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 логикалық амалдардың символдары болсын. Егер тұжырымдар
алгебрасының кез келген формуласы үшін оған пара-пар (1, (2, ..., (n
амалдарының көмегімен құрылған формула бар болса, онда (1, (2, ..., (n жүйе
толық деп аталады.
Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және
КНФ болғандықтан, (, (, ( – толық жүйе екендігі түсінікті.
Лемма 9.1 Логикалық байланыстардың келесі жиындары:
(, (, (, ( , (, ( , (, ( , (, (
толық жүйе құрайды.
Лемма 9.2 (, (, ( , ( жиындары логикалық амалдардың толық жүйесін
құрмайды.
Тақырып бойынша тесттер
1. Келесі импликациялардың қайсысы жалған?
1) егер 2(2=4, онда 23;
2) егер 2(2=4, онда 23;
3) егер 2(2=5, онда 23;
4) егер 2(2=5, онда 23;
2. Келесі сөйлемдердің қайсысы тұжырым болмайды?
1) Информатика кафедрасының студенті.
2) Париж – Испания астанасы.
3) 3 саны А жиынына тиісті.
3. Айнымалылардың қайсылары бір бірінің терістеулері болады:
1) 23, 2(3;
2) 69, 69;
3) f функциясы жұп, f функциясы тақ;
4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі.
4. A(B тұжырымы ақиқат болсын. ((A(B ) ( ( (A(B ) тұжырымы қандай логикалық
мәнге ие болады?
1) ақиқат
2) жалған
5. ( ((P(Q ) ( ((P(Q ) (P) формуланы ықшамдаңыз:
1) 1
2) 0
3) Р
4) Q
6. Келесі өрнектердің қайсысы формула болады?:
1) ((P(( (Q(R )) ( (((P~ R ) (Q ))
2) ((P(Q) R) ((S
7. КНФ-ті табыңыз: ((x(z )((x(y)
1) (x(y((z)
2) (x(y)(y(z)
3) y(z
8. 0 мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті
бірмүшені құрыңыз:
1) x(y
2) (x(y
3) x((y
4) (x ((y
9. формулаға пара-пар тек және амалдары көмегімен
құрылған формуланы табыңыз:
1) (((x(y((z )
2) x(y
10. ДНФті табыңыз: (x~y) (( ( z(T )
1) (x(y(z((T) ( ((x((y(z((T);
2) x (y(z
2 тарау. тұжырымдар есептелімі
2.1 Тұжырымдар есептелімі формуласының ұғымы
Тұжырымдар есептелімі бұл интерпретациясы тұжырымдар алгебрасы болатын
аксиоматикалық логикалық жүйе.
Әрбір есептелімнің сипаттамасына бұл есептелімі символдарының,
формулаларының сипаттамасы, дәлелденетін формулалардың анықтамасы енеді.
Тұжырымдар есептелімінің алфавиті үш түрлі символдардан тұрады:
1. Бұл символдарды айнымалы тұжырымдар деп атаймыз.
2. Бұл символдар логикалық байланыс деген жалпы атауға ие.
Келтірілген символдардың біріншісі дизъюнкция (немесе логикалық қосу)
белгісі, екіншісі – конъюнкция (немесе логикалық көбейту) белгісі, үшіншісі
– импликация және төртіншісі – терістеу белгісі.
3. Жақшалар деп аталатын символдар: (, ).
Тұжырымдар есептелімінде басқа символдар болмайды.
Тұжырымдар есептелімінің формуласы тұжырымдар есептелімі алфавитінің
символдарының тізбегі болады. Формула белгісі үшін латын алфавитінің үлкен
әріптерін қолданамыз. Олар өздері есептелімнің символдары болмай,
формулалардың тек шартты белгілері болады.
Тұжырымдар есептелімі формуласының анықтамасы
1. Кез келген айнымалы формула б олады.
2. Егер А және В – формулалар болса, онда сөздер де формулалар.
3. Ешқандай басқа символдардың қатары формула болмайды.
Айнымалы тұжырымдарды қарапайым формулалар деп атаймыз.
Тұжырымдар есептелімі формуласына мысал келтірейік.
айнымалы тұжырымдар анықтаманың 1-ші бөлімі бойынша формулалар
болады. Бірақ, онда сөздер де анықтаманың 2-ші бөлімі бойынша
формулалар бола алады. Сол себепке байланысты сөздер де формула бола
алады.
Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі
енгізіледі.
1. Қарапайым формуланың ішформуласы оның өзі болады.
2. Егер формула көрінісінде болса, онда оның ішформулалары формуланың
өзі, А формуласы және А формуланың барлық ішформулалары болады.
3. Егер формула (А*В) (мұнда * – үш символдардың бірі деп түсінеміз)
көрінісінде болса, онда оның ішформулалары формуланың өзі, А, В формулалары
және А мен В формулалардың барлық ішформулалары болады.
Формуладағы логикалық амалдарының саны формуланың рангі деп аталады.
2.2. Дәлелденетін формула ұғымы
Тұжырымдар есептелімінің құруда келесі кезең дәлелденетін (шығарылатын)
формулалардың класын бөліктеу болады.
Дәлелденетін формула анықтамасы формулалар анықтамасы сияқты. Алдымен
бастапқы дәлелденетін шығарылатын формулалар (аксиомалар) анықталады, ал
содан кейін бар дәлелденетін формулалардан жаңа дәлелденетін формулаларды
алуға мүмкіндік беретін шығару ережелері анықталады. Бастапқы дәлелденетін
формулалардан шығару ережелерін қолдану көмегімен жаңа дәлелденетін
формуланы алу процесі берілген формуланы аксиомалардан шығаруы (дәлелдеуі)
деп аталады.
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі
Тұжырымдар есептелімінің аксиомалар жүйесі төрт топқа бөлінетін 11
аксиомадан тұрады.
Аксималардың бірінші тобы (құрамыларыны тек импликация енеді).
: .
:.
Аксималардың екінші тобы ( импликацияға конъюнкция қосылды):
:
: .
: .
Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды):
:
:
: .
Аксималардың төртінші тобы (импликацияға терістеу қосылды):
:
:
:
2.4 Шығару ережелері
1. Алмастыру ережесі (АЕ).
Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін)
формула, х – айнымалы, В – тұжырымдар есептелімінің кез келген формуласы
болса, онда А формуладағы х айнымалыны В формулаға алмастыру нәтижесінде
алынған формула да шығарылатын (дәлелденетін) болады.
А формуладағы х айнымалыны В формулаға алмастыру амалы алмастыру деп
аталады да келесі түрде жазылады:
немесе .
Егер А – шығарылатын (дәлелденетін) болса, онда ├А деп жазамыз. АЕ
схематикалық түрде төмендегідей жазуға болады:
├А____ .
├
Бұл жазылу былай оқылады: “Егер А формуласы шығарылатын (дәлелденетін)
болса, онда формуласы да шығарылатын (дәлелденетін) болады.
2 Қорытындылау ережесі (ҚЕ).
Егер А және А→В формулалары тұжырымдар есептелімінде шығарылатын
(дәлелденетін) болса, онда В формуласы да шығарылатын (дәлелденетін)
болады. Бұл ереженің схематикалық жазылуы мынадай болады:
├А;├А→В (Modus ponens)
├В
Бұл ереженің дұрыстығы айқын: егер импликация мен шарт ақиқат болса, онда
импликациядағы қорытынды тек ақиқат болуы мүмкін.
2.5 Дәлелденетін формуланың анықтамасы
а) Әрбір аксиома дәлелденетін формула болады.
б) Кез келген В формуласынан х айнымалының орнына алмастыруды қолдану
нәтижесінде алынған формула – дәлелденетін формула.
в) А және дәлелденетін формулаларға қорытындылау ережесін қолдану
нәтижесінде алынған В формуласы – дәлелденетін формула болады.
г) Тұжырымдар есептелімінің ешқандай басқа формуласы дәледенетін болып
саналмайды.
Дәлелденетін формулаларды шығару процесін формулалардың дәлелдеуі
(шығаруы) деп атаймыз. Бұл бір дәлелденетін формуладан әр қадамда
аксиомаларды, алмастыру және қорытындылау ережелерін қолдану көмегімен
басқа дәлелденетін формулаға өту процесі (белгілі мағынада логика
алгебрасындағы тепе-тең түрлендірулердің аналогі), сондықтан қарапайым
формуланың шығаруы да көпқадамды, күрделі болуы мүмкін.
2.6 Туынды шығару ережелері
Күрделі алмастыру ережесі (КАЕ)
Туынды шығару ережелері, қарастырылған шығару ережелері сияқты, жаңа
дәлелденетін формулаларды алуға мүмкіндік береді. Бұл ережелер алмастыру
және қорытындылау ережелері көмегімен алынған, сондықтан, олар туынды
ережелер деп аталады.
А – дәлелденетін формула, – айнымалылар, ал – тұжырымдар
есептелімінің кез келген формулалары болсын. Онда А формулада
айнымалыларын формулаларға алмастыру нәтижесі дәлелденетін формула
болады.
КАЕ схематикалық түрде былай жазылады:
├А______
├
Күрделі қорытындылау ережесі
Қорытындылау ережесін де жалпылау мүмкін. Жалпылау нәтижесінде алынған
туынды ереже
түрдегі формулаларға қолданылады да былай анықталады:
егер және формулалар дәлелденетін болса, онда L формуласы
да дәлелденетін формула.
Күрделі қорытындылау ережесі былай жазылады:
├А1, ├А2, ...,├Аn, ├A1→(A2→(A3→(...(An→L) ...))) .
├ L
Силлогизм ережесі
Егер А→В және В→С формулалары дәлелденетін болса, онда А→С формуласы да
дәлелденеді, яғни
├А→В,├В→С .
├А→С
Контрапозиция ережесі
Егер А→В формуласы дәлелденетін болса, онда ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz