Классикалық тұжырымдар есептер
МАЗМҰНЫ
КІРІСПЕ. 2
1 ТАРАУ. ТҰЖЫРЫМДАР АЛГЕБРАСЫ.. 5
1.1. Тұжырым ұғымы.. 5
1.2. Тұжырымдарға қолданылатын логикалық амалдар. Терістеу. 5
1.3 Конъюнкция. 6
4 Дизъюнкция. 6
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
1
0
0
0
1
1
0
1
0
1
1
0
1
1
0
1
0
0
0
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 мен 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 f3 f4 f5 f6 f7 f8 F9 f10 f11 f12 f13 f14 f15 f16
1 1 1 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0
1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0
0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 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
Формуланың ақиқаттық кестесі бойынша оның өзін анықтайық. Берілген формула қарпайым тұжырымдардың 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 Логикалық байланыстардың толық жүйелері
D1, D2, …, Dn логикалық амалдардың символдары болсын. Егер тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар D1, D2, …, Dn амалдарының көмегімен құрылған формула бар болса, онда <D1, D2, …, Dn> жүйе толық деп аталады.
Тұжырымдар алгебрасының кез келген формуласы үшін оған пара-пар ДНФ және КНФ болғандықтан, <Ø, Ù, Ú > – толық жүйе екендігі түсінікті.
Лемма 9.1 Логикалық байланыстардың келесі жиындары:
<Ø, Ù, Ú, ® >, <Ø, Ù >, <Ø, Ú >, <Ø, ®>
толық жүйе құрайды.
Лемма 9.2 <Ù, Ú, ® >, <Ø > жиындары логикалық амалдардың толық жүйесін құрмайды.
Тақырып бойынша тесттер
Келесі импликациялардың қайсысы жалған?
1) егер 2*2=4, онда 2>3;
2) егер 2*2=4, онда 2<3;
3) егер 2*2=5, онда 2<3;
4) егер 2*2=5, онда 2>3;
Келесі сөйлемдердің қайсысы тұжырым болмайды?
1) «Информатика» кафедрасының студенті.
2) Париж – Испания астанасы.
3) 3 саны А жиынына тиісті.
Айнымалылардың қайсылары бір бірінің терістеулері болады:
1) 2>3, 2£3;
2) 6<9, 6>9;
3) f функциясы жұп, f функциясы тақ;
4) ABC үшбұрышы тікбұрышты, ABC үшбұрышы – тең бүйірлі.
A®B тұжырымы ақиқат болсын. (ØAÙB ) ® ( ØAÚB ) тұжырымы қандай логикалық мәнге ие болады?
1) ақиқат
2) жалған
Ø (ØPÚQ ) ® ((PÚQ ) ®P) формуланы ықшамдаңыз:
1) 1
2) 0
3) Р
4) Q
Келесі өрнектердің қайсысы формула болады?:
1) ((PÙ( ØQ®R )) Ú ((ØP~ R ) ØQ ))
2) ((PÚQ) R) ®ØS
КНФ-ті табыңыз: Ø(xÚz )Ù(x®y)
1) Øx(yÚØz)
2) (xÚy)(yÚz)
3) yÚz
0мәнді айнымалылардың тек (0,0) мәндер тобында қабылдайтын дизъюнктивті бірмүшені құрыңыз:
1) xÚy
2) ØxÚy
3) xÚØy
4) Øx ÚØy
формулаға пара-пар тек және амалдары көмегімен құрылған формуланы табыңыз:
1) Ø(ØxÙyÙØz )
2) xÙy
ДНФті табыңыз: (x~y) ÙØ ( z®T )
1) (xÙyÙzÙØT) Ú (ØxÙØyÙzÙØT);
2) x ÙyÚz
2 тарау. тұжырымдар есептелімі
2.1 Тұжырымдар есептелімі формуласының ұғымы
Тұжырымдар есептелімі бұл интерпретациясы тұжырымдар алгебрасы болатын аксиоматикалық логикалық жүйе.
Әрбір есептелімнің сипаттамасына бұл есептелімі символдарының, формулаларының сипаттамасы, дәлелденетін формулалардың анықтамасы енеді.
Тұжырымдар есептелімінің алфавиті үш түрлі символдардан тұрады:
Бұл символдарды айнымалы тұжырымдар деп атаймыз.
Бұл символдар логикалық байланыс деген жалпы атауға ие. Келтірілген символдардың біріншісі дизъюнкция (немесе логикалық қосу) белгісі, екіншісі – конъюнкция (немесе логикалық көбейту) белгісі, үшіншісі – импликация және төртіншісі – терістеу белгісі.
Жақшалар деп аталатын символдар: (, ).
Тұжырымдар есептелімінде басқа символдар болмайды.
Тұжырымдар есептелімінің формуласы тұжырымдар есептелімі алфавитінің символдарының тізбегі болады. Формула белгісі үшін латын алфавитінің үлкен әріптерін қолданамыз. Олар өздері есептелімнің символдары болмай, формулалардың тек шартты белгілері болады.
Тұжырымдар есептелімі формуласының анықтамасы
Кез келген айнымалы формула б олады.
Егер А және В – формулалар болса, онда сөздер де формулалар.
Ешқандай басқа символдардың қатары формула болмайды.
Айнымалы тұжырымдарды қарапайым формулалар деп атаймыз.
Тұжырымдар есептелімі формуласына мысал келтірейік.
айнымалы тұжырымдар анықтаманың 1-ші бөлімі бойынша формулалар болады. Бірақ, онда сөздер де анықтаманың 2-ші бөлімі бойынша формулалар бола алады. Сол себепке байланысты сөздер де формула бола алады.
Формула түсінігі мен бірге ішформула немесе формула бөлігі түсінігі енгізіледі.
Қарапайым формуланың ішформуласы оның өзі болады.
Егер формула көрінісінде болса, онда оның ішформулалары формуланың өзі, А формуласы және А формуланың барлық ішформулалары болады.
Егер формула (А*В) (мұнда * – үш символдардың бірі деп түсінеміз) көрінісінде болса, онда оның ішформулалары формуланың өзі, А, В формулалары және А мен В формулалардың барлық ішформулалары болады.
Формуладағы логикалық амалдарының саны формуланың рангі деп аталады.
2.2. Дәлелденетін формула ұғымы
Тұжырымдар есептелімінің құруда келесі кезең дәлелденетін (шығарылатын) формулалардың класын бөліктеу болады.
Дәлелденетін формула анықтамасы формулалар анықтамасы сияқты. Алдымен бастапқы дәлелденетін шығарылатын формулалар (аксиомалар) анықталады, ал содан кейін бар дәлелденетін формулалардан жаңа дәлелденетін формулаларды алуға мүмкіндік беретін шығару ережелері анықталады. Бастапқы дәлелденетін формулалардан шығару ережелерін қолдану көмегімен жаңа дәлелденетін формуланы алу процесі берілген формуланы аксиомалардан шығаруы (дәлелдеуі) деп аталады.
2.3 Тұжырымдар есептелімінің аксиомалар жүйесі
Тұжырымдар есептелімінің аксиомалар жүйесі төрт топқа бөлінетін 11 аксиомадан тұрады.
Аксималардың бірінші тобы (құрамыларыны тек импликация енеді).
: .
:.
Аксималардың екінші тобы ( импликацияға конъюнкция қосылды):
:
: .
: .
Аксималардың үшінші тобы ( импликацияға дизъюнкция қосылды):
:
:
: .
Аксималардың төртінші тобы (импликацияға терістеу қосылды):
:
:
:
2.4 Шығару ережелері
Алмастыру ережесі (АЕ).
Егер А формуласы тұжырымдар есептелімінде шығарылатын (дәлелденетін) формула, х – айнымалы, В – тұжырымдар есептелімінің кез келген формуласы болса, онда А формуладағы х айнымалыны В формулаға алмастыру нәтижесінде алынған формула да шығарылатын (дәлелденетін) болады.
А формуладағы х айнымалыны В формулаға алмастыру амалы алмастыру деп аталады да келесі түрде жазылады:
немесе .
Егер А – шығарылатын (дәлелденетін) болса, онда ├А деп жазамыз. АЕ схематикалық түрде төмендегідей жазуға болады:
├А____ .
├
Бұл жазылу былай оқылады: “Егер А формуласы шығарылатын (дәлелденетін) болса, онда формуласы да шығарылатын (дәлелденетін) болады.
2 Қорытындылау ережесі (ҚЕ).
Егер А және А→В формулалары тұжырымдар есептелімінде шығарылатын (дәлелденетін) болса, онда В формуласы да шығарылатын (дәлелденетін) болады. Бұл ереженің схематикалық жазылуы мынадай болады:
├А;├А→В (Modus ponens)
├В
Бұл ереженің дұрыстығы айқын: егер импликация мен шарт ақиқат болса, онда импликациядағы қорытынды тек ақиқат болуы мүмкін.
2.5 Дәлелденетін формуланың анықтамасы
а) Әрбір аксиома дәлелденетін формула болады.
б) Кез келген В формуласынан х айнымалының орнына алмастыруды қолдану нәтижесінде алынған формула – дәлелденетін формула.
в) А және дәлелденетін формулаларға қорытындылау ережесін қолдану нәтижесінде алынған В формуласы – дәлелденетін формула болады.
г) Тұжырымдар есептелімінің ешқандай басқа формуласы дәледенетін болып саналмайды.
Дәлелденетін формулаларды шығару процесін формулалардың дәлелдеуі (шығаруы) деп атаймыз. Бұл бір дәлелденетін формуладан әр қадамда аксиомаларды, алмастыру және қорытындылау ережелерін қолдану көмегімен басқа дәлелденетін формулаға өту процесі (белгілі мағынада логика алгебрасындағы тепе-тең түрлендірулердің аналогі), сондықтан қарапайым формуланың шығаруы да көпқадамды, күрделі болуы мүмкін.
2.6 Туынды шығару ережелері
Күрделі алмастыру ережесі (КАЕ)
Туынды шығару ережелері, қарастырылған шығару ережелері сияқты, жаңа дәлелденетін формулаларды алуға мүмкіндік береді. Бұл ережелер алмастыру және қорытындылау ережелері көмегімен алынған, сондықтан, олар туынды ережелер деп аталады.
А – дәлелденетін формула, – айнымалылар, ал – тұжырымдар есептелімінің кез келген формулалары болсын. Онда А формулада айнымалыларын формулаларға алмастыру нәтижесі дәлелденетін формула болады.
КАЕ схематикалық түрде былай жазылады:
├А______
├
Күрделі қорытындылау ережесі
Қорытындылау ережесін де жалпылау мүмкін. Жалпылау нәтижесінде алынған туынды ереже
түрдегі формулаларға қолданылады да былай анықталады:
егер және формулалар дәлелденетін болса, онда L формуласы да дәлелденетін формула.
Күрделі қорытындылау ережесі былай жазылады:
├А1, ├А2, …,├Аn, ├A1→(A2→(A3→(…(An→L) …))) .
├ L
Силлогизм ережесі
Егер А→В және В→С формулалары дәлелденетін болса, онда А→С формуласы да дәлелденеді, яғни
├А→В,├В→С .
├А→С
Контрапозиция ережесі
Егер А→В формуласы дәлелденетін болса, онда формула да дәлелденеді, яғни
├ А →В .
├
Бұл ереженің мысалында тұжырымдар есептелімінде мұндай тұжырымдардың дәлелдеу жолын көрсетеміз. алмастыруын орындап,
├(А→В)→├() (1)
дәлелденетін формуланы аламыз.
Ал шарт бойынша
├А→В (2)
– дәлелденетін формула.
Онда (2) және (1) формулаларынан қорытындылау ережесі бойынша ├.
Екі еселі терістеу ережесі
а) Егер формуласы дәлелденетін болса, онда формуласы да дәлелденетін.
б) Егер формуласы дәлелденетін болса, онда формуласы да дәлелденетін.
Схематикалық жазылулары: ├ А → және ├ →В
├ ├ .
2.7 Формулаларды гипотезалардан қорытып шығару
Формулалардың Н={А1,А2,…,Аn} ақырлы жиынын қарастырамыз.
Н жиынынан шығарылатын формула анықтамасы.
1) AiÎH формуласы Н-тан шығарылатын формула деп аталады.
2) Әрбір дәлелденетін формула Н-тан шығарылатын болады.
3) Егер С және С→В формулалар Н-тан шығарылатын болса, онда В формуласы да Н-тан шығарылатын болады.
Егер кейбір В формуласы формулалардың Н жиынынан шығарылатын болса, онда бұл былай жазылады: Н├В.
Н жиыны бос немесе тек дәлелденетін формулалардан тұратын жағдайда Н жиынынан шығарылатын формулалардың класы дәлелденетін формулалардың класымен сәйкес келеді.
Егер де Н жиынында кем дегенде бір дәлелденбейтін формула болса, онда Н-тан шығарылатын формулардың класы дәлелденетін формулалар класынан кең болады.
Мысал.
Формулалардың Н={А, В} жиынынан формуласы шығатынын дәлелдеу керек.
AÎH және BÎH болғандықтан, дәлелденетін формуланың анықтамасы бойынша
Н├А, (1)
Н├В. (2)
және аксиомаларды алып, және алмастыруларды орындаймыз.
Нәтижесінде Н-тан шығарылатын дәлелденетін формулаларды аламыз, яғни
Н├(А→А)→((А→В)→(А)), (3)
Н├В→(А→В), (4)
А→А формуласы дәлелденетін, онда Н├А→А. (5)
(5) және (3) формулалардан қорытындылау ережесі бойынша Н├(А→В)→(А)) (6)
алынады.
(2) және (4) формулалардан қорытындылау ережесі бойынша:
Н├А→В . (7)
(7) және (6) формулалардан қорытындылау ережесі бойынша: Н├А . (8)
Соңында (1) және (8) формулалардан
Н├ (9)
алынады.
Формуланың шығарылатынын дәлелдеуде тек қана қорытындылау ережесін емес, күрделі қорытындылау ережесін пайдалануға мүмкін екендігі түсінікті. Онда бұл ережені пайдаланып, (9) тұжырымды (5), (7), (1) және (3) тұжырымдардан алуға болады.
Анықтама. Формулалардың Н ақырлы жиынынан шығаруы деп әрбір мүшесі келесі шарттарды қанағаттандыратын формулалардың В1,В2,…,Вк тізбегін айтамыз:
1) ол Н жиынының бір формуласы болады,
2) ол дәлелденетін формула болады,
3) ол В1,В2,…,Вк тізбегінің алдынғы кез келген екі мүшесінен қорытындылау ережесі бойынша шығады.
Алдынғы мысалда көрсеткеніміздей, формулалардың Н={А,В} жиынынан шығаруы формулалардың келесі ақырлы тізбегі болады:
А, В, (А→А)→((А→В)→(А)), (А→В), А→А, (А→В)→(А)), А→В, А, . (1,2,3,7,5,6,8 формулалар).
Егер күрделі қорытындылау ережесін пайдалансақ, онда шығаруды былай жазуға болады:
А, В, (А→А)→((А→В)→(А)), В→(А→В), А→А, А→В, . (5, 7, 1, 3 формулалар).
Шығарылатын формула анықтамасынан және формулалар жиынынан шығару анықтамасынан шығарудың келесі қасиеттері келіп шығады:
1) Н жиынынан шығарудың әрбір бастапқы кесіндісі – Н-тан шығару болады.
2) Егер Н тан шығарудың екі көршілес мүшелерінің арасында (басында немесе соңында) кейбір Н тан шығаруді қойсақ, онда формулалардың алынған жаңа тізбегі Н тан шығару болады.
3) Н жиынынан шығарудың әрбір мүшесі Н тан шығарылатын формула болады. Н тан кез келген шығару оның соңғы формуласының шығаруы болады.
4) Егер болса, онда Н тан кез келген шығару W дан шығару болады.
5) В формуласы Н жиынынан шығарылатын болуы үшін бұл формуланың Н тан шығаруы бар болуы қажетті және жеткілікті.
2.8 Шығарылу ережелері
Бұл ережелер шығарудың қасиеттерінен алмастыру және қорытындылау ережелерін қолдану арқылы тікелей келіп шығады.
Н және W – тұжырымдар есептелімі формулаларының екі тобы болсын.
Н, W арқылы олардың бірігуін белгілейміз, яғни Н,W=.
Мысалы, W жиыны тек бір С формуласынан тұратын жағдайда біріктіруді Н, С түрінде жазамыз.
Негізгі шығарылу ережелерін көрсетейік.
H ├ A Бұл ереже формулалар жиынынан шығарудың анықтамасынан H,W├A келіп шығады: “Егер А формуласы Н тан шығарылатын болса, онда ол тан да шығарылады. ”.
H,C ├ A,H├C
H├A .
H,C ├ A, W├C
H,W├A .
H ├ C→A
H,C├A .
Дедукция теоремасы: H, C├ A .
H├C→A
5A. Жалпыланған дедукция теоремасы: {C1, C1, …, Ck}├ A
├C1→(C2→(C3→…(Ck→A)…))
Конъюнкцияны енгізу ережесі: H├A,H├B .
H├
Дизъюнкцияны енгізу ережесі: H,A├C;Н,B├C .
H,├C
2.9 Тұжырымдар алгебрасы мен тұжырымдар есептелімі арасындағы байланыс
Тұжырымдар есептелімінің формулаларын тұжырымдар алгебрасының формулалары ретінде қарастыруға болады. Ол үшін тұжырымдар есептелімінің айнымалыларын тұжырымдар алгебрасының айнымалысындай, яғни екі ақиқат және жалған мән қабылдайтын, қарастырамыз.
операцияларын тұжырымдар алгебрасында сияқты анықтаймыз. Тұжырымдар есептелімінің формулалары тұжырымдар алгебрасының ережелері бойынша есептелетін 1 немесе 0 мәндерінің біреуін ғана қабылдайды.
Тұжырымдар есептелімі формуласының мәні түсінігін енгіземіз. А – тұжырымдар есептелімінің формуласы, х1,х2,…,хn – өзара әртүрлі А формуласына енетін айнымалылар болсын. а1, а2,…,аn арқылы бұл айнымалыларының мәндер тобын белгілейміз. (а1, а2,…,аn) векторы 2n мән қабылдайтыны айқын.
Келесі үш теорема орынды.
Теорема 1. Әрбір тұжырымдар есептелімінде дәлелденетін формула тұжырымдар алгебрасында тепе-тең ақиқат болады.
Теорема 2. (шығарылу туралы). А – тұжырымдар есептелімінің қандай да бір формуласы болсын; х1,х2,…,хn – А формулаға енетін айнымалылардың тобы; а1, а2, …, аn – бұл айнымалылар мәндерінің кез келген бекітілген тобы. Н арқылы формулалардың ақырлы жиынынын белгілейміз:
, где
Онда:
Егер Ra1,a2,..,an(A)=1 болса, онда H├A .
Егер Ra1,a2,..,an(A)=0 болса, онда H├, мұнда Ra1,a2,..,an(A) – А формуланың а1, а2,…,аn топтағы мәні.
Теорема 3. Тұжырымдар алгебрасының әрбір тепе-тең ақиқат формуласы тұжырымдар есептелімінде дәлелденетін формула болады.
Тақырып бойынша тесттер
формуланың рангін табыңыз
7
6
5
4
формуланың рангін табыңыз
8
6
7
5
Дұрыс құрылған формуланы көрсетіңіз:
Келтірілген өрнектердің қайсысы формула болады?
Барлық жауаптар дұрыс
формула үшін алмастыру нәтижесін жазыңыз
формула үшін алмастыру нәтижесін жазыңыз
Глава 3. предикаттар логикасы
3.1 Предикат ұғымы
Анықтама 1. x1, x2, …, xn – пәндік айнымалылардың символдары болсын. Пәндік айнымалылардың (x1, x2, …, xn) топтары пәндік аймақ деп аталатын W жиыныны тиісті болсын. W пәндік аймағында анықталған n-орынды предикат деп, W-ның тұжырымдар жиынына бейнелеуін айтады.
Мысалдарды қарастырар алдын n-орынды предикаттарға квазианықтама берейік:
Анықтама. «n айнымалыға тәуелді және келесі қасиетке ие болған баяндамалы байланысты сөйлемі: айнымалылардың орнына анық мәндер қойылғанда ақиқат немесе жалған болсын».
Мысал 1. D(x1, x2) = «x1 натурал саны x2 натурал санына бөлінеді (қалдықсыз)» — NN жиынында анықталған екі орынды предикат. Түсінікті, D(4, 2)=1, D(3, 5)=0.
Мысал 2. Q(x) = «х2<-1, xR» — R нақты сандар жиынында анықталған бір орынды предикат. Q(-1)=0, Q()=0. Q(x) – тепе-тең жалған екендігі түсінікті, яғни Q(x) 0.
Мысал 3. R(x, y, z)= «x2+ y2z; x, y, zR» — R3 жиынында анықталған үш орынды предикат. R(1, 1, -2)=0, R(1, 1, 2)=1.
Мысал 4. S(x, y) = «sin2ху>-3; x, yR» — екі орынды тепе-тең ақиқат предикат.
Р(x1, x2, …, xn) — W аймағында анықталған n-орынды предикат болсын. Онымен келесі түрде анықталған екі жиынды байланыстырамыз:
IP={( x1, x2, …, xn )Î W | Р(x1, x2, …, xn)=1} – Р предикаттың ақиқаттық жиыны,
LP={( x1, x2, …, xn)Î W | Р(x1, x2, …, xn)=0} – Р предикаттың жалғандық жиыны.
Анықтама 2. Р – W-да анықталған предикат болсын. Егер IP=W (LP=Æ) болса, онда Р тепе-тең ақиқат, егер LP=W (IP=Æ) болса, онда Р тепе-тең жалған предикат деп аталады.
Егер IP ¹ W және LP ¹ Æ болса, онда Р орындалатын предикат деп айтамыз.
R3 кеңістікте 3 мысалдағы R(x, y, z) предикаттың IP және LP жиындарын көрсетейік (1 сурет).
z IP
1 сурет
у
х
3.2 Предикаттарға логикалық амалдарды қолдану
Анықтама 3. Р – W-да анықталған предикат болсын. Р предикаттың терістеуі дегеніміз белгіленетін және W-да келесі түрде анықталған предикат:
P және Q – W-да анықталған предикаттар болсын.
P және Q предикаттардың дизъюнкциясы (конъюнкциясы, импликациясы, эквиваленциясы) дегеніміз былай белгіленетін , ( (,, PQ), , ) және -да келесі түрде анықталатын предикат:
()
()
()
Анықтама 4. Егер аймағына тиісті кез келген ( x1, x2, …, xn ) пәндік айнымалылардың топтары үшін Р( x1, x2, …, xn ) Q( x1, x2, …, xn ) болса, онда P және Q предикаттар аймағында анықталған пара-пар предикаттар деп аталады (PQ).
Теорема 1. аймағында анықталған n – орынды предикаттардың жиыны предикаттардың бульдік алгебрасық құрайды, яғни олар үшін бульдік алгебраның келесі 19 негізгі тепе-теңдіктер орынды:
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
Мұнда 1 – -дағы тепе-тең ақиқат предикаттың, ал 0 – тепе-тең жалған предикаттың белгілері.
Бұл теореманың дұрыстығы айқын. Өйткені предикаттарға қолданылатын амалдар тұжырымдарға қолданылатын амалдар көмегімен енгізілген, ал тұжырымдар бульдік алгебраны құрайды.
3.3 Кванторлық амалдар
Предикаттарды тұжырымдарға түрлендіретін амалдарды қарастырайық. М жиынында анықталған Р(х) предикат берілсін. Егер “а” – М жиынының қандай да бір элементі болса, онда Р(х) предикатта х орнына а ны қою берілген предикатты Р(а) тұжырымға айналдырады. Мұндай предикатты бірлік деп атайды. Мысалы, Р(x): “х – жұп сан” – предикат, ал Р(6) – ақиқат тұжырым, Р(3) – жалған тұжырым.
Жоғарыда айтылғанды n – орынды предикаттарға жалпылау мүмкін: егер барлық хi, i=, пәндік айнымалылардың орнына олардың мәндері қойылса, онда тұжырым алынады.
Квантификация амалдарын қарастырамыз. Бұл амалдардар да предикаттарды тұжырымдарға айналдырады.
Жалпылау кванторы
Р(х) – W жиынында анықталған предикат болсын. Бұл предикатқа предикат тепе-тең ақиқат болғанда ғана ақиқат болатын тұжырымын сәйкестікке қоямыз. тұжырымы былай оқылады: “Кез келген х үшін Р(х) ақиқат ”. тұжырымы Р(х) предикатқа х айнымалы бойынша жалпылау кванторын ілу көмегімен алынған деп айтады.
символын жалпылау кванторы деп атайды. Р(х) предикатқа х айнымалы бос болып, ал тұжырымға – х жалпылау кванторымен байланған болып енеді деп айтады.
Бар болу кванторы
P(x) – W жиынында анықталған предикат болсын. Бұл предикатқа предикат тепе-тең жалған болғанда ғана жалған болатын тұжырымын сәйкестікке қоямыз. тұжырымы былай оқылады:“ P(x) ақиқат болатын х табылады”. символын бар болу (табылу) кванторы деп аиаймыз. тұжырымы Р(х) предикатқа х айнымалы бойынша бар болу кванторын ілу көмегімен алынған деп айтады. х айнымалы бұл квантормен байланған болады.
Кванторлық амалдарды көп орынды предикаттарға да қолдануға болады. Мысалы, W жиынында екі орынды P(x,y) предикаты берілсін. Предикаттың айнымалыларына кванторларды іліп, мынадай тұжырымдарды алуға болады:
3.4 Предикаттар логикасының формуласының ұғымы
Предикаттар логикасында келесі символдарды пайдаланамыз:
p, q, r, … символдары – 1– ақиқат немесе 0 – жалған екі мәнді қабылдайтын айнымалы тұжырымдар;
x, y, z, … – кейбір М жиынына тиісті мәндерді қабылдайтын пәндік айнымалылар;
x0, y0, z0 – пәндік тұрақтылар, яғни пәндік айнымалылардың мәндері.
P(·), Q(·), F(·), … — бір орынды предикаттық айнымалылар;
Q(·,·,…,·), R(·,·, …,·) – n-орынды предикаттық айнымалыла;р
P0(·), Q0(·,·, …,·) – тұрақты предикаттардың символдары.
Логикалық амалдардың символдары:
Кванторлық амалдардың символдары:
Көмекші символдар: жақшалар, үтірлер.
Предикаттар логикасы формуласының анықтамасы
Кез келген тұжырым (қарапайым) формула болады.
Егер F(·,·, …,·) – n-орынды предикатты айнымалы немесе тұрақты предикат, ал x1, x2,…, xn – пәндік айнымалылар немесе пәндік тұрақтылар болса, онда F(x1, x2,…, xn) – формула. Мұндай формула қарапайым деп аталады, бұл формулада пәндік айнымалылар бос, кванторлармен байланбаған болады.
Егер А және В – формулалар (бұл формулаларға айнымалылар бір түрде кіреді – бос немесе байланған), онда сөздер – формулалар.
Егер А – формула болса, онда да – формула, А формуладан формулаға өтуде пәндік айнымалылардың ену түрі өзгермейді.
Егер А(х) – формула (бұл формулаға х пәндік айнымалы бос болып енеді), онда және сөздер де формулалар.
1 – 5 бөлімдерде айтылған сөздерден басқа сөздер формула болмайды.
Мысалы, егер Р(х) және Q(x,y) – бір орынды және екі орынды предикаттар, ал q, r – айнымалы тұжырымдар болса, онда келесі сөздер (өрнектер) формулалар болады: .
Мысалы, сөзі формула емес. Мұнда үшінші бөлімнің шарты бұзылған: формулаға х айнымалы байланған болып, ал Р(х) формулаға бос болып енеді.
Предикаттар логикасы формуласы анықтамасынан тұжырымдар алгебрасының әрбір формуласы предикаттар логикасының формуласы болатыны түсінікті.
Предикаттар логикасының формуласының мәні
Формуланың логикалық мәні жайлы бұл формулаға кіретін предикаттардың М анықталу аймағы берілгенде ғана айтуға болады. Формуланың логикалық мәні үш түрлі айнымалылардың мәндеріне тәуелді: 1) формулаға енетін айнымалы тұжырымдардың мәндеріне, 2) М жиынына тиісті бос пәндік айнымалылардың мәндеріне, 3) предикатты айнымалылардың мәндеріне.
Осы үш түрлі айнымалылардың анық мәндерінде предикаттар логикасының формуласы ақиқат немесе жалған мән қабылдайтын тұжырым болады.
Мысал ретінде келесі формуланы қарастырамыз:
, (1)
Бұл формулада екі орынды Р(x, y) предикаты M´M жиынында анықталған, мұнда M={0,1,2,…,n,…}, яғни M´M=N´N.
В формулу (1) формулаға кіретін P(x,y) айнымалы предикаттың үш x,y,z пәндік айнымалыларынан екеуі – у және z кванторлармен байланған, ал үшіншісі х – бос.
P(x,y) предикаттың мәнін бекітеміз: P0(x,y)= «x<y», ал х бос айнымалының мәні болсын. Онда у-тің x0=5 мәнінен кіші мәндерінде P0(x0,y) предикаты “жалған” мәнін, ал импликация барлық үшін “ақиқат” мәнін қабылдайды, яғни тұжырымы ақиқат.
3.5 Предикаттар логикасының формулаларының тепе-теңдігі
Анықтама 1. Егер предикаттар логикасының А және В формулалары М аймаққа тиісті айнымалыларының барлық мәндерінде бірдей логикалық мән қабылдаса, онда бұл формулалар М аймақта тепе-тең деп айтады.
Анықтама 2. Егер предикаттар логикасының А және В формулалары кез келген аймақта тепе-тең болса, онда бұл формулалар тепе-тең деп аталады. Түсінікті, егер тұжырымдар алгебрасының тепе-теңдіктеріне айнымалы тұжырымдардың орындарына предикаттар логикасының формулалары қойылса, олар дұрыс болады. Бірақ, олардан басқа, предикаттар логикасының өзінің тепе-теңдіктері орынды болады. Олардың негізгілерін қарастырайық.
А(х) және В(х) – айнымалы предикаттар, ал С – айнымалы тұжырым болсын (немесе х ке тәуелді емес формула). Онда келесі тепе-теңдіктер орынды:
.
3.6 Пренекстік нормал форма
Анықтама. Егер предикаттар логикасының формуласы терістеу, конъюнкция, дизъюнкция және кванторлық операциялар көмегімен құрылған болса және терістеу амалы тек қарапайым формулаларға қатысты болса, онда бұл формула нормал формаға ие деп айтады.
Тұжырымдар алгебрасының және предикаттар логикасының тепе-теңдіктерін пайдаланып, предикаттар логикасының кез келген формуласын нормал формаға келтіру мүмкін.
Мысал 1.
формуланы нормал формаға келтірейік.
Тепе-тең түрлендірулерді пайдаланып, келесіні аламыз:
.
Предикаттар логикасы формулаларының арасында пренекстік (префикстік) нормал форма деп аталатын формулаларды бөліктейді. Бұл формада кванторлық амалдар жоқ болады немесе олар логика алгебрасы барлық амалдарынан кейін қолданылады, яғни предикаттар логикасы формуласының ПНФ келесі түрде болады:
,
мұнда символы – немесе , ал А формуласында кванторлар жоқ.
Теорема. Предикаттар логикасының кез келген формуласын пренекстік нормал формаға келтіру мүмкін.
3.7 Математикалық тұжырымдар мен анықтамаларды предикаттар логикасының формулалары түрінде жазу
Предикаттар логикасының тілі математикалық тұжырымдар мен анықтамаларды жазу үшін ыңғайлы. Ол ұғымдар арасындағы логикалық байланыстарды өрнектеу, анықтамаларды, теоремаларды, дәлелдеулерді жазу мүмкіндігін береді. Мұндай жазылулардың бірнеше мысалдарын келтірейік. Мысал 1. Е облыста анықталған ƒ(х) функцияның x0 нүктедегі шегінің анықтамасы.: . үш орынды предикатты қолданып жазамыз:
, мұнда .
Мысал 2. Нүктедегі үзіліссіз функцияның анықтамасы.
Егер , мұндағы , онда Е жиыныдағы анықталған функциясы нүктеде үзіліссіз деп аталады.
Тесты по теме
Р(х) = «х2-4=0, хÎR» және Q(х)= «3х-2<16, хÎR» предикаттар берілген. Бұл предикаттардың ақиқаттық жиындарын табыңыз.
IP = {2; -2}; IQ = (-¥; 6)
IP = {2}; IQ = (-¥; 6)
IP = {2}; IQ = {1; 2; 3; 4; 5; 6}
Р(х)= «х2-4=0, хÎN» және Q(х)= «3х-2<16, хÎN» предикаттар берілген. Бұл предикаттардың ақиқаттық жиындарын табыңыз.
IP = {2}; IQ = {1; 2; 3; 4; 5}
IP = {2}; IQ = {1; 2; 3; 4; 5; 6}
IP = {2}; IQ = (-¥; 6)
IP = {2}; IQ = {6}
Пара-пар предикаттарды көрсетіңіз (пәндік айнымалылар R жиынына тиісті):
х2 < 0 және 2|x| = Cosx
және
және
және
Келесі өрнектердің қайсысы предикаттар логикасының формуласы болады?
формуладағы айнымалылардың түрін анықтаңыз:
х, z байланған, у бос
х, z бос, у байланған
х, у байланған, z бос
y, z байланған, x бос
Предикаттардың қайсылары бір бірінің терістеулері болады?
«k бүтін саны тақ», «k бүтін саны жүп»
«f функциясы жұп», «f функциясы тақ»
«a<b», «a>b»
«n натурал саны – жай», «n натурал саны – құрама»
Р(х,у) = «х натурал саны у натурал санына бөлінеді (қалдықсыз)». Келесі сөйлемдердің қайсысы ақиқат?
және – кез келген предикаттар болсын. Келесі формулалардың қайсысы формулаға пара-пар болады?
Р(х) = «х – жұп саны, хÎN» және Q(х)= « х 3 санына еселі, хÎN» болсын. Р(х)& Q(х) предикаттың ақиқаттық жиынын табыңыз.
IР& Q = {6; 12; …; 6n; …}
IР& Q = {2; 3; 4; 6; …; 2n; 3n; …}
IР& Q = {1; 3; 5; …; 2n-1; …}
предикаттың ақиқаттық жиынын табыңыз.
VI тарау. АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ ЭлементтерІ
4.1 Алгоритм түсінігі және оның қасиеттері
Алгоритм түсінігі негізігі математика түсінігінің қатарына жатады. Бұл үлкен даму қатарынан өткен. Мұнда математика дамымай тұрып та таза механикалық қасиеттердің белгілі ережелерге сүйеніп, бүкіл кластың тапсырмалары есептелетін әртүрлі есептеуіш процестері қалыптаса бастады. Алгоритм мысалдары болып мыналар табылады:
Сандармен жұмыс жасалатын арифметикалық әрекеттердің ережесі.
Ең үлкен ортақ бөлгішті табу ережесі.(Евклид алгоритмі).
Квадраттық түбірден құтылу ережесі.
Квадраттық түбірдің шешімін табатын ереже.
Әрбір келтірілген мысалдардың біртекті шешім кластарымен немесе массалық проблемаларымен жұмыс істеуге тура келеді. Кластың мұндай шешімдері бір-бірімен параметрге кіретін мәндермен ажыратылады. Осылайша, квадраттық теңдеудің шешімін табуда мынадай үш параметр қатысады және с; бұларды ауыстыра отырып бір кластың әртүрлі шешімдерін таба аламыз.
Айтылғандарға қарап алгоритм түсінігінің келесі анықтамасын беруімізге болады.
Алгоритм дегеніміз бір образды және берілген массалық проблеманың кез-келген тапсырмасының дәлме-дәл шешімі. Мұндай анықтаманы қатаң деп қарауға болмайды. Шынында да, мұнда дәл мағынасы берілмеген сөздер де кездеседі. Жекелей бұл «әдіс» сөзіне қатысты. Алгоритмнің мұндай қатаң емес анықтамасы интуитивтік деп аталады.
Алгоритм түсінігінің нақты қасиеттерін қарастырайық.
Жалпылық – бұл алгоритмнің жеке тапсырмаға емес, бүкіл класс тапсырмаларына қолданылады.
Дискреттік – четкая разбивка на отдельные этапы (шаги).
Анықталғандық – такая организация этапов выполнения, при которой для перехода от одного этапа к другому не приходится прибегать к датчикам случайных чисел, гаданию на кофейной гуще, подбрасыванию монеты и т.п.
Конечность – Алгоритм қолданысындағы нақты тапсырмалардың шешімін алу үшін алгоритм қадамдарында орындалады.
«Алгоритм дегеніміз не?», «Алгоритмнің шешілген және шешілмеген проблемалары дегеніміз не?» сұрақтары ЭВМ-мен байланысқан ХХ ғасырда және анализдің жаратылыс мүмкіндігінің актуальдылығы болып табылады. Алгоритм теориясы америкалық, ағылшындық және совет математиктерінің бірігуінен (параллельдік) туылған. Алгоритм түсінігінің мағынасын ашу үшін көптеген философиялық ойлар керек болды. Барлық кезде адам жұмыс істегенде «баспен» ойлай ма? Егер біздің бастың жұмысының жартысы машинаға өтілген болса, онда машина ойлайды деп ойлаймыз ба? Мұндай философиялық проблемалардың шешімін ХХ ғ., бірегей ұлы математиктері кибернетик Н. Винер, американдық математик Э. Пост және ағылшын математигі А. Тьюринг тапқан.
4.2. Тьюринг машиналары
Егер кейбір жалпы мәселені шешу үшін алгоритм белгілі болса, онда оны жүзеге асыру үшін тек алгоритмдің нұсқауларын қатаң орындау қажет. Осы алгоритмды атқаратын адамдың функцияларын машинаға беру ой пайда болады. Мұндай машинаның идеясын ХХ ғасырдың 30-ші жылдарында америкалық математигі Э. Пост және ағылшын математигі А. Тьюринг ұсынған.
Тъюринг машинасы деп аталатын айтылған машиналардың варианттарының бірін қарастырайық.
Тьюринг машинасының үш алфавиті бар:
Бос символмен берілген сыртқы алфавит – АÈ{L}.
Ішкі алфавит немесе жағдайлар алфавиті Q = {q0, q1, …, qn}. q0 жағдайы қорытынды жағдай, q1 – бастапқы жағдай, q2, q3, …, qn – жұмыс жағдайлар деп аталады.
Қозғалыстар алфавиті S = {-1, 0, +1}.
Машинаның құрылымына кіреді:
а) шексіз таспа (ұяшықтарға бөлінген). Әрбір ұяшыққа тек бір ғана әріп жазылуы мүмкін.
б) оқып-жазушы құрылғы. Оқып-жазушы құрылғының шолу жасау, ұяшыққа жазылған әріпті оқу, ұяшыққа әріпті жазу, жылжу мүмкіндіктері бар. в) басқару құрылғысы – машинаның программасы көмегімен машина жұмысын басқарады.
г) машинаның бір конфигурациясынан басқасына өтулерін анықтайтын машинаның программасы.
Егер шолу жасалған ұяшық пен машинаның жағдайы белгілі болса, онда машинаның конфигурациясы белгілі деп айтады.
Машинаның программасы бұл әрбір (а, qi ) – әріп-жағдай қосағына (b, qi , s) – әріп-жағдай-қозғалыс үштікті сәйкестікке қоятын бейнелеу. Әдетде Тьюринг машинасының программасы кесте түрінде беріледі.
4.3 Машинаның жұмыс істеу ережелері
Машина дискретті түрде жұмыс істейді (қадам қадам бойынша). Әр қадамда бір конфигурациядан басқасына өту орындалады. Жұмыс бастаудан алдын машина бастапқы конфигурацияда болады: оқып-жазушы құрылғы сөздің бірінші әріпіне шолу жасайды, ал машина q1 бастапқы жағдайында болады. Оқып-жазушы құрылғы шолу жасалған ұяшықтағы әріпті оқиды. Басқару құрылғысы машинаның программасынан оқылған әріп пен машинаның жағдайына сәйкес клетканы табады. Бұл клеткада (а, q, s) үштік болсын. Онда шолу жасалған ұяшыққа а әріпі жазылады, машина q жағдайға өткізіледі, егер s=-1 болса, онда оқып-жазушы құрылғы бір ұяшыққа сол жаққа жылжыйды, егер s=+1 болса, онда оқып-жазушы құрылғы бір ұяшыққа оң жаққа жылжыйды, егер s=0 болса – қозғалмайды. Осымен машинаның бірінші қадамдағы жұмысы аяқталады.
Машинаның жұмыстары машинаның қадамы q0 ға жеткенше жалғаса береді. Бұл жағдайда басқару құрылғысы машинаны тоқтатады. Пайда болған конфигурация қорытынды, ал алынған сөз – машинаны берілген сөзге қолдану нәтижесі деп аталады.
4.4 Машина мысалдары
Мысал 1. Келесі Тьюринг машинасы унарлық санақ жүйесінде жазылған натурал сандарды қосады.
q1 q2 q3
| |q1+1 Lq3-1 |q3-1
+ |q1+1
L L q2-1
Lq0+1
Мысал 2. Келесі Тьюринг машинасы унарлық санақ жүйесінде жазылған натурал сандарды екі есе көбейтеді.
q1 q2 q3
| aq1+1 |q2-1 |q3+1
a
|q3+1
L L q2-1 Lq0+1 |q2-1
Тақырып бойынша тесттер
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= | ( q1) | L |
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
| L ( q0) | |
L | ( q0) |
L ( q0) LL
| L ( q0) |
| L L L ( q0)
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= |( q1) L |
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
|( q0) | |
L | ( q0) |
L ( q0) LL
| L ( q0) |
| L L L ( q0)
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= |( q1) | | L
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
| L L L ( q0)
L | ( q0) |
L ( q0) LL
| L ( q0) |
|L( q0) | |
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= | ( q1) | L
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
| L ( q0) |
L | ( q0) |
L ( q0) LL
| L L L ( q0)
|L( q0) | |
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1=L( q1) L L
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
L ( q0) LL
L | ( q0) |
| L ( q0) |
| L L L ( q0)
|L( q0) | |
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1=L | ( q1) L
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
L | ( q0) |
| L ( q0) |
| L L L ( q0)
|L( q0) | |
L ( q0) LL
КУРС БОЙЫНША ТестТЕР
Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
Пара-пар формулаларды көрсетіңіз:
,
,
,
,
,
формуланың рангін табыңыз:
7
6
5
4
– W аймағында анықталған предикат болсын. Қандай шарт орындалса, Р тепе тең ақиқат предикат деп аталады?
IP= W
IP= Æ
LP= W
– W аймағында анықталған предикат болсын. Қандай шарт орындалса, Р тепе тең жалған предикат деп аталады?
LP= W
IP= W
LP= Æ
Ықшамдаңыз:
Ықшамдаңыз:
y
х
Келтірілген ЖДНФ бойынша формуланың ЖКНФін табыңыз:
Келтірілген ЖКНФ бойынша формуланың ЖДНФін табыңыз:
Формуланың ақиқаттық кестесi бойынша оның ЖДНФ табыңыз:
x y F
0
0
1
1
0
1
0
1
0
0
0
1
Формуланың ақиқаттық кестесi бойынша оның ЖКНФ табыңыз:
x y F
0
0
1
1
0
1
0
1
0
1
1
0
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1= | ( q1) | L |
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
L ( q0) | |
L | ( q0) |
L ( q0) LL
| L ( q0) |
| L L L ( q0)
Берiлген Т Тьюринг машинасы және K1 бастапқы конфигурация бойынша қорытынды конфигурацияны табыңыз.
T: K1=L( q1) L L
q1 q2 q3
| |q2+1 Lq3+1 Lq1+1
L Lq00 |q0-1 |q1-1
L ( q0) LL
L | ( q0) |
| L ( q0) |
| L L L ( q0)
|L( q0) | |
формуланың жетілдірілген конъюнктивті нормал формасын табыңыз:
0-ді Пирс функциясы арқылы өрнектеңіз:
Пирс функциясы арқылы өрнектеңіз:
Шеффер функциясы арқылы өрнектеңіз:
Шеффер функциясы арқылы өрнектеңіз:
x = 1, y = 1, z = 0 аргументтердің берілген мәндерінде және функциялардың мәндерін есептеңіз.
F = 1, G =1
F = 0, G = 0
F = 0, G = 1
F = 1, G = 0
x = 1, y = 1, z = 1 аргументтердің берілген мәндерінде және функциялардың мәндерін есептеңіз.
.F = 1, G = 0
F = 0, G = 1
F = 1, G = 1
F = 0, G = 0
ӘДЕБИЕТТЕР
Ершов Ю.Л., Палютин Е.А., «Математическая логика». М., Наука, 1979.
Жетпісов Қ., Түсіпов Ж.А., «Математикалық логика», Тараз, 2000.
Лавров И.А., Максимова Л.Л., «Задачи по теории множеств, математической статистике и теории алгоритмов». М., Наука, 1975.
Лихтарников Л.М., Сукачева Т.Г., «Математическая логика». СПб.: «Лань», 1998.
Мальцев А.И., «Алгоритмы и рекурсивные функции». М.: Наука, 1986.
Мендельсон Э., «Введение в математическую логику», М., 1976.
