Раздзел логіка прэдыкатаў




старонка4/4
Дата канвертавання01.05.2016
Памер1.92 Mb.
1   2   3   4

Прыклад 4. Дзяўчына па-рознаму зразумее пачуцці і намеры хлопца, калі ён скажа:

(а) “Я кахаю цябе, і я люблю матэматыку.” ці

(б) “Я кахаю цябе, але я люблю матэматыку.”

Аналагічна, хлопец па-рознаму паставіцца да словаў сваёй сяброўкі ў выпадках (а), (б) прыкладу 5:



Прыклад 5. (а) “Я кахаю цябе, але ты бедны.”

(б) “Я кахаю цябе, не зважаючы на тваю беднасць.”



Прыклад 6. (а) Я спішу дамашняе заданне ў Алены, калі пайду на заняткі па алгебры.

(б) Я не пайду на заняткі па алгебры, калі не спішу дамашняе заданне ў Алены.



Прыклад 7. (а) Калі ўзыйдзе сонца, я ўстану.

(б) Калі я не ўстану, сонца не ўзыйдзе.

Сказ (а) ў прыкладах 6 і 7 запісваецца формулай алгебры выказванняў , а сказ (б) – раўназначнай формулай , але ў жывой мове гэтыя сказы нераўназначныя. У прыкладзе 6 (а) мы разумеем наступным чынам: я спішу дамашняе заданне ў Алены на занятках, а (б): калі я не спішу дамашняе заданне, я не пайду на заняткі (бо мне сорамна ісці з невыкананым заданнем, а сам я з нейкай прычыны не магу яго зрабіць) – яшчэ адзін прыклад таго, як мова перадае ідэю часу ці прычыны. Больш дакладна можна запісаць гэтыя сказы моваю логікі прэдыкатаў. Няхай (Я спішу дамашняе заданне ў Алены ў момант ), (Я пайду на заняткі па алгебры ў момант ). Тады сказ (а) запішацца ў выглядзе , а сказ (б) – .

Аналагічныя заўвагі можна зрабіць пра прыклад 7. Тое, што сказы не раўназначныя, не патрабуе каментараў (толькі той, хто лічыць сябе цэнтрам сусвету, можа думаць, што з-за таго, што ён будзе доўга спаць, адменіцца ўзыход сонца; спадзяемся, што сярод чытычоў кнігі гэтакіх няма).



Прыклад 8. “Калі Сяргей прыйдзе ці калі Мікола падтрымае нашую прапанову і Васіль не будзе супраць, тады нашая прапанова будзе прынятая.” Як перакласці гэты сказ на мову алгебры выказванняў – ці ? Перад “і” няма коскі, таму хутчэй другая формула з’яўляецца перакладам нашага сказу, а калі паставіць коску перад “і” – першая. Гэты прыклад паказвае, што пераклад на мову алгебры выказванняў – не механічная праца, перакладчык мусіць добра зразумець думку аўтара (а аўтар, каб яго правільна зразумелі, павінны выражаць свае думкі больш дакладна).

Пры перакладзе на мову логікі прэдыкатаў трэба выбраць прыдатнае мноства і інтэрпрэтацыю (гэтак, як мы рабілі ў §2 і ў прыкладзе 2 §3). Ізноў трэба памятаць, што пераклад – не механічная працэдура, трэба добра зразумець сэнс сказу.

Часам у звычайнай мове слова “некаторыя” мае адценне “некаторыя, але не ўсе”. Напрыклад, сказ “Некаторыя студэнты – гультаі” больш дакладна перакласці на мову логікі прэдыкатаў формулай , чым формулай .

Словы “усе” (кожны”) і “існуе” (“некаторыя”) у жывой мове часам прапускаюць: сказы “Чалавек падняўся на Джамалунгму” і “На лекцыі студэнт думае пра праблемы матэматычнае логікі” трэба перакладаць формулай ; а сказы “Паліном над полем раскладаецца на непрыводныя множнікі”, “Чалавек смяротны” – формулай .

Калі ў формуле, якой мы запісваем сказ, сустракаюцца квантары і аперацыі алгебры выказванняў, трэба дакладна вызначыць абсягі дзеяння квантараў і парадак дастасавання квантараў і аперацыяў алгебры выказванняў. Выказванне “Не кожны матэматык любіць пустыя размовы” запісваецца формулай , а выказванне “Кожны матэматык не любіць пустыя размовы” – формулай . Выказванне “Не існуе квадратовага кораня з 2” перакладаецца на мову логікі прэдыкатаў формулай , а формуле адпавядае выказванне “Існуе лік, які не з’яўляецца квадратовым коранем з 2”. (Заўважым, што пры інтэрпрэтацыі на мностве рацыянальных лікаў, дзе – прэдыкат “ – квадратовы корань з 2”, выказванні, адпаведныя гэтым формулам, раўназначныя (праўдзівыя), а пры аналагічнай інтэрпрэтацыі на мностве рэчаісных лікаў – нераўназначныя).

У прыкладзе 4 §2 мы запісалі выказванне “Кожны студэнт універсітэту – матэматык або выдатнік” формулай (гэтае выказванне раўназначнае выказванню “Кожны студэнт універсітэту, які вучыцца не на матэматычным факультэце – выдатнік”), а формулу прачыталі як “Ва ўніверсітэце толькі адзін факультэт – матэматычны або ўсе студэнты ўніверсітэту – выдатнікі”, якое нераўназначнае першаму (адсюль, у прыватнасці, вынікае, што формулы логікі прэдыкатаў і нераўназначныя). Выказванне “Некаторыя студэнты ўніверсітэту – матэматыкі і выдатнікі” (г.зн., “На матэматычным факультэце ёсць выдатнікі”) мы запісалі формулай , а формуле у той сама інтэрпрэтацыі адпавядае выказванне “Ва універсітэце ёсць студэнт – матэматык і ёсць студэнт – выдатнік”. Гэтыя выказванні нераўназначныя, таму нераўназначныя і формулы і .

Часам слова “усе” ужываецца не як квантар, а для апісання мноства: “Усе каралеўскія коннікі і ўсе каралеўскія ратнікі не могуць Шалтая – Балтая падняць”. Пераклад гэтага сказу формулай будзе няправільным, апошняя формула значыць, што кожны коннік і ратнік не можа адзін падняць Шалтая – Балтая, правільна перакладаць формулай , дзе – мноства ўсіх каралеўскіх коннікаў і ратнікаў.

Аналагічныя цяжкасці ўзнікаюць з злучнікам “і”. Сказ “Сяргей і Міхась не могуць выцягнуць машыну з канавы” трэба перакладаць формулай , дзе – прэдыкат “Каманда можа выцягнуць машыну з канавы”, а “Сяргей і Міхась здадуць экзамен” – формулай , бо яны будуць здаваць экзамен не разам, а кожны за сябе.

Сказ “Студэнтам-матэматыкам і фізікам неабходна добра ведаць матэматычны аналіз” трэба перакладаць не формулай , а формулай

(пакажыце, што гэтыя формулы логікава эквівалентныя).

Прыклад 9. У “Новым запавеце” падаюцца словы Ісуса Хрыста:

(а) “Хто не са Мною, той супраць Мяне” (Эвангелле паводле Мацвея, 12, 30; паводле Лукі, 11, 23),

якія можна запісаць формулай логікі прэдыкатаў

.

Гэтая формула логікава эквівалентная формуле



,

якой адпавядае сказ

(б) “Хто не супраць Мяне, той са Мною”,

але гэта не тое сама, што сказаў Ісус. Сапраўды, словы Ісуса “Хто не са Мною, той супраць Мяне” трэба разумець гэтак (калі аўтары Эвангелляў і шматлікія перакладчыкі правільна данеслі да нас сэнс словаў Хрыста): “Той, хто бачыў і чуў Мяне, але не паверыў Мне і не пайшоў за Мною – той супраць Мяне, а, значыць, і супраць Таго, Хто паслаў Мяне”. А словы “Хто не супраць Мяне, той са Мной” мы ўспрымаем інакш: “Той, хто не выступае супраць Мяне – патэнцыйна Мой вучань, ён можа пайсці за Мною”. Такім чынам, у гэтых двух сказах супрацьлеглае стаўленне да тых, хто не пайшоў за Ісусам, але і не выступае адкрыта супраць Яго – Ісус кажа, што такі чалавек супраць Яго, а сказ (б) сцвярджае, што гэты чалавек за Яго. (Магчыма, для аналізу гэтых сказаў была б карыснай трохзначная логіка, там гэтыя дзве формулы неэквівалентныя).

(Адзначым, што пра сябе Ісус кажа “Хто не са Мною, той супраць Мяне”, але калі Ён вучыць апосталаў, тады кажа “Бо хто не супраць вас, той за вас” (паводле Марка, 9, 40; паводле Лукі, 9, 50) і тым самым паказвае вялікую розніцу паміж Сабою і апосталамі: чалавек, які не пайшоў за Ісусам – супраць Яго, а той, хто не выступае супраць апосталаў – патэнцыйна іхні вучань, калі яму раскрыць вочы на вучэнне Хрыста, ён пойдзе за Ім.)

Практыкаванне 1. Запішыце наступныя выказванні моваю логікі прэдыкатаў (або алгебры выказванняў). Ці раўназначныя ў практыкаваннях (5) і (6), (7) і (8), (9) і (10), (11) і (12) выказванні і формулы, якімі вы іх запісалі?

(1) Паліном над полем камплексных лікаў мае камплексны корань.

(2) Непарыўная на адрэзку функцыя абмежаваная на гэтым адрэзку i дасягае максiмуму.

(3) Можна падманваць усіх нейкі час і можна падманваць некаторых увесь час, але нельга падманваць усіх увесь час.

(5) Султан выгнаў міністра, і народ зажыў багата і шчасліва.

(6) Народ зажыў багата і шчасліва, і султан выгнаў міністра.

(7) Я не прыйду, калі яна не папросіць прабачэння.

(8) Яна папросіць прабачэння, калі я прыйду.

(9) Калі Мікола і Сяргей атрымаюць стыпендыю і Васіль паедзе з намі на машыне, ці Сяргей зможа прадаць тэлевізар, тады мы паедзем адпачываць на Нарач.

(10) Калі Мікола і Сяргей атрымаюць стыпендыю, і Васіль паедзе з намі на машыне ці Сяргей зможа прадаць тэлевізар, тады мы паедзем адпачываць на Нарач.

(11) Я здам зкзамен і паеду ў Карпаты ці буду займацца матэматычнай логікай.

(12) Я здам зкзамен, і паеду ў Карпаты ці буду займацца матэматычнай логікай.

(13) Студэнтам і пенсіянерам уваход у музей бясплатны.

Практыкаванне 2. Запішыце наступныя разважанні моваю логікі прэдыкатаў і высветліце, ці правільныя гэтыя разважанні.

(1) Калі я стаміўся і галодны, я не хачу вучыцца, а хачу дамоў. Цяпер я стаміўся і галодны. Значыць, цяпер я не хачу вучыцца, а хачу дамоў.

(2) Усім вядома, што сабака – сябар чалавека. Адсюль вынікае, што той, для каго сабака – не сябар, – не чалавек.

(3) Функцыя непарыўная на адрэзку, калі яна дыферэнцавальная на гэтым адрэзку. Функцыя дыферэнцавальная на адрэзку . Значыць, функцыя непарыўная на .

(4) Функцыя непарыўная на адрэзку, калі яна дыферэнцавальная на гэтым адрэзку. Функцыя непарыўная на адрэзку . Значыць, функцыя дыферэнцавальная на .

(5) Сістэма вектараў лінейна незалежная, калі толькі трывіяльная лінейная камбінацыя гэтых вектараў роўная нулю. Трывіяльная лінейная камбінацыя вектараў роўная нулю. Значыць, сістэма лінейна незалежная.

(6) Парадак падгрупы канцоўнай групы дзеліць парадак групы. Парадак зменназнакавай групы роўны 12, лік 6 дзеліць 12; значыць, у групе існуе падгрупа парадку 6.

У матэматыцы і ў штодзённым жыцці часам не ўсе аргументы разважання падаюцца ў яўным выглядзе. Напрыклад, у разважанні “Калі я позна лягу спаць, тады я заўтра дрэнна буду разумець лекцыю. Значыць, я павінны рана легчы спаць” прапушчаны сказ “Я хачу добра разумець лекцыю”:



.

Можна нават прапусціць і вынік разважання, і, такім чынам, абмежавацца намёкам. У нашым прыкладзе дастаткова сказаць: “Калі я позна лягу спаць, тады я заўтра дрэнна буду разумець лекцыю”.

Ёсць такія аргументы, якія відавочныя ў дадзеным разважанні таму, што яны добра вядомыя ці мы пра іх ужо казалі; таму іх можна прапусціць і не баяцца, што нас не зразумеюць. Мы можам у доказе прапускаць і асобныя крокі, калі слухачы змогуць іх лёгка аднавіць, сказаўшы пры гэтым: “Можна даказаць, што...”.

Некаторыя прамоўцы карыстаюцца няпоўнымі разважаннямі для таго, каб слухачы не заўважылі тыя аргументы, у праўдзівасці якіх можна сумнявацца. Студэнты часам кажуць “Відавочна, што...”, калі не могуць растлумачыць пэўны крок у доказе тэарэмы.

Логікавы аналіз улучае пошук прапушчаных умоваў (а часам і вынікаў) няпоўных разважанняў і дапамагае нам праверыць правільнасць разважанняў і пазбегнуць небяспекі быць падманутымі..

Практыкаванне 3. У наступных разважаннях прапушчаныя некаторыя умовы (або высновы). Паспрабуйце аднавіць іх такім чынам, каб атрымаліся правільныя разважанні. Ці праўдзівыя, на ваш погляд, дабаўленыя довады?

(1) Падсуднага нельга прызнаць вінаватым, калі ён не быў у Слоніме а 18-й гадзіне першага студзеня. Але вядома, што ў гэты час ён быў у Полацку. Значыць, ён невінаваты.

(2) У нас няма ніякіх доказаў ягонай віны. Таму ён павінны быць апраўданы.

(3) У нас няма ніякіх доказаў ягонай віны. Таму ён невінаваты.

(4) – матрыцы і . Значыць, ранг матрыцы не вышэйшы за ранг .

(5) Той, хто нікога не кахае, с часам ператвараецца ў эгаіста і баязлійца. Ён нікога не кахае. Значыць, ён не годны кахання.

(6) Чалавек, які некага кахае, становіцца добрым і храбрым. Ён не храбры.

(7) Толькі храбрыя годныя кахання. Яго кахаюць. Ён не храбры.

(8) Ваўкавыск ляжыць на захад ад Слоніму. Слонім ляжыць на захад ад Нясвіжу. Нясвіж ляжыць на захад ад Слуцку. Значыць, Ваўкавыск ляжыць на захад ад Слуцку.

(9) У краіне, у якой высокі ўзровень матэматычнае адукацыі, людзі ўмеюць думаць, і таму там немагчымае існаванне дыктатуры.

(10) У краіне, у якой усталяваны дыктатарскі рэжым, людзям не дазваляецца думаць, і таму там не можа развівацца матэматыка.

(11) Калі характарыстыка поля няроўная нулю, тады характарыстыка ёсць парадак адзінкі ў дачыненні да складання. Парадак элементу канцоўнай групы дзеліць парадак групы. Значыць, характарыстыка канцоўнага поля дзеліць парадак поля.

(11) Кожны сапраўдны матэматык не верыць ніводнаму недаказанаму сцверджанню і не сцвярджае таго, што не даказана. Таму матэматыка нельга падмануць і сам ён ніколі не маніць.

(12) Кожны матэматык у душы паэт. Паэт нясе людзям высокае, прыгожае, добрае. Прыгажосць і дабрыня выратаюць сусвет. Значыць, сур’ёзныя заняткі матэматыкай спрыяюць выратаванню сусвету.



РАЗДЗЕЛ 4. МАШЫНА Т’ЮРЫНГА

Алiса цярплiва чакала, пакуль Вусень не зробiць ласку гаварыць iзноў. Праз пару хвiлiн той вынуў кальян з роту, пазяхнуў – раз, другi – i пацягнуўся. Потым ён зпоўз з грыба i схаваўся ў траве, толькi кiнуўшы Алiсе на развiтанне:

– Адкусiш з аднаго боку – падрасцеш, з другога – паменшаеш!

(Льюiс Кэрал. Прыгоды Алiсы ў краiне цудаў)

Пры вывучэннi матэматыкi вы не раз сустракалiся з паняццем алгарытму і інтуiцыйна разумеце алгарытм як дакладна вызначаны парадак выканання нейкай сукупнасці пэўных правілаў для развязання задачаў аднаго тыпу. Пры гэтым вам трэба толькi механiчна выконваць паслядоўна дзеяннi паводле дадзеных правiлаў, г.зн., дзейнічаць паводле прынцыпу “рабі гэтак, як я”; ад вас не патрабуецца думаць самім і шукаць метад развязання якой-небудзь задачы; выконваць крокі (правілы) алгарытму зможа не толькі чалавек, але і машына. Прыкладамi алгарытмаў з’ўляюцца працэс дзялення “вуглом” натуральных лiкаў, алгарытм Эўклiда для адшукання найбольшага агульнага дзельнiку двух цэлых лiкаў або паліномаў, схема Горнэра. У раздзеле 1 мы сустракалiся з алгарытмамi напiсання таблiцы праўдзiвасцi для прапазiцыйнай формулы i адшукання ДНФ і КНФ дадзенай прапазiцыйнай формулы. Тэарэма пра поўнасць дае алгарытм, якi дазваляе па дадзенай формуле злiчэння выказванняў высветлiць, цi з’яўляецца яна тэарэмай злiчэння выказванняў: гэта будзе калi i толькi калi таблiца праўдзiвасцi гэтай формулы складаецца толькi з 1.

Iнтуiцыйнага разумення паняцця алгарытму звычайна бывае дастаткова для доказу таго факту, што для развязання некаторага класу задачаў iснуе алгарытм. Аднак каб даказаць, што для развязання пэўнага класу задачаў няма алгарытму, неабходна мець дакладнае азначэнне алгарытму.

У 1935 годзе А.Чорч i С.Клінi вывучалi клас функцыяў, якiя называюцца вызначальнымi функцыямi. Iмi было даказана, што гэты клас супадае з другiм класам функцыяў, якiя вывучаў Гёдэль – класам часткова-рэкурсіўных функцыяў. Чорч выказаў дапушчэнне (яно цяпер называецца тэзiсам Чорча), што клас усіх функцыяў, якія можна вылічыць з дапамогай алгарытмаў, i ёсць клас усiх –вызначальных, або, эквiвалентна, часткова-рэкурсiўных функцыяў. Гэта не тэарэма, а менавiта тэзiс, даказаць яго немагчыма, бо ў ягонай фармулёўцы ўдзельнічае інтуіцыйнае паняцце “алгарытм”.

У 1936 годзе А.Т’юрынг увёў яшчэ адзiн клас функцыяў, якiя мы будзем называць функцыямi, вылiчальнымi па Тюрынгу, i ў дачыненнi да гэтага класу выказаў аналагiчнае дапушчэнне, вядомае пад назовам тэзiс Тюрынга. Iм было даказана, што вылiчальныя па Т’юрынгу функцыi i –вызначальныя, а, значыць, i часткова-рэкурсiўныя – гэта тое самае. Такiм чынам, тэзiс Т’юрынга эквiвалентны тэзiсу Чорча. Пазней з’явiлiся эквiвалентныя азначэннi алгарытму Поста (1943 г.) i Маркава (1954 г.).

Мы разгледзiм адно з гэтых эквiвалентных азначэнняў паняцця алгарытму – ідэалізаваную вылічальную машыну машыну Тюрынга.


Машына Т’юрынга мае канцоўнае мноства нутраных станаў і бясконцую вонкавую памяць – стужку. Сярод гэтых станаў існуюць два вылучаныя – пачатковы і заключны . Стужка падзеленая на роўныя квадраты і бясконцая як направа, гэтак і налева. У кожным квадраце стужкі можа быць запісаны адвольны сымболь з пэўнага алфавіту . Лічаць, што сымболь └┘ - пусты квадрат.

У кожны момант часу машына знаходзiцца ў адным i толькi адным з нутраных станаў. Машына мае чытальную галоўку, якая ў кожны момант знаходзiцца над адным з квадратаў стужкi (мы будзем казаць, што галоўка чытае гэты квадрат). Машына дзейнiчае ў дыскрэтныя моманты часу. Калi ў момант чытальная галоўка чытае квадрат, ў якiм запiсаны сымболь , i машына знаходзiцца ў нутраным стане , тады дзеянне машыны вызначана i яна выконвае наступныя аперацыi: 1) замяняе сымболь на новы сымболь ; 2) галоўка рухаецца на адзiн квадрат налева (L) або направа (R); 3) машына пераходзiць у новы стан , i ў наступны момант часу iзноў гатовая да дзеяння. Калi ў некаторы момант машына пераходзiць у заключны стан , яе работа спыняецца. Паслядоўнасць аперацыяў 1) – 3) называецца камандай i запiсваецца . У левай частцы нiводнай каманды не сустракаецца, усе левыя часткi камандаў розныя.

Калi спачатку на стужцы была запiсаная пэўная канцоўная паслядоўнасць сымболяў, галоўка змяшчалася над адным з квадратаў стужкi i машына была прыведзеная ў адзiн з сваiх нутраных станаў, тады машына пачынае працаваць, г.зн., паслядоўна выконваць каманды. Калi ў некаторы момант работа машыны спыняецца (машына пераходзiць у стан ), тады паслядоўнасць, якая запiсаная ў гэты момант на стужцы, называецца вынiкам дастасавання машыны да паслядоўнасцi, што была на стужцы ў пачатковы момант.

Мы можам цяпер кожнай машыне Т’юрынга паставіць у адпаведнасць некаторы алгарытм у алфавiце машыны наступным чынам: запiшам адвольнае слова у алфавiце на стужку. Падвядзем галоўку да крайняга левага квадрату i прывядзем машыну ў нутраны стан . Машына пачне працаваць. Калi яна ў некаторы момант часу спынiцца, тады слова, якое ў гэты момант запiсанае на стужцы, з’яўляецца значэннем алгарытму. Такi алгарытм называецца алгарытмам Тюрынга.

Цяпер, калi мы маем апiсанне машыны Т’юрынга, дамо яе дакладнае азначэнне. Машынай Тюрынга называецца ўсякае канцоўнае мноства выразаў выгляду , дзе , такое, што нiякiя два выразы з не маюць аднолькавыя левыя часткi i нiводзiн выраз з не мае ў левай частцы . Элементы з называюцца камандамi; мноства ўсiх сымболяў , што ўваходзяць у каманды, называецца алфавiтам машыны , а сымболi называюцца нутранымi станамi машыны . Патрабуем дадаткова, каб быў нутраным станам кожнай машыны Т’юрынга.

Канфiгурацыяй машыны называецца кожнае слова выгляду , дзе – слова (магчыма, пустое) у алфавiце машыны , – якi-небудзь нутраны стан , – непустое слова ў алфавiце . З дапамогаю канфiгурацыi задаецца стан машыны i стужкi ў дадзены момант часу: ёсць слова, запiсанае на стужцы, – нутраны стан машыны ў дадзены момант, першая за лiтара – сымболь, якi ў дадзены момант чытае галоўка.

Будзем казаць, што машына пераводзiць канфiгурацыю у канфiгурацыю , калi задае стан стужкi i машыны у момант , а – у момант . Будзем казаць, што машына спыняецца пры канфiгурацыi , калi не iснуе канфiгурацыi , што .



Вылiчэнне машыны Т’юрынга ёсць усякая канцоўная паслядоўнасць канфiгурацыяў такая, што нутраны стан , для i спыняецца пры . Няхай – алфавiт, якi змяшчае ў сабе алфавiт машыны . Вызначым алгарытм наступным чынам: калi i — словы ў алфавiце , тады вынiк дастасавання алгарытму да слова ёсць слова калi i толькi калi iснуе вылiчэнне машыны , якое пачынаецца з канфiгурацыi i заканчываецца канфiгурацыяй выгляду , дзе .

Прыклад 1. Пабудуем машыну Т’юрынга , якая слова “МОЛОКО“ пераводзiць у слова “МАЛАКО“ ( у пачатковы момант галоўка чытае лiтару М ). Злева мы будзем пiсаць каманды, а справа – стан машыны i стужкi (канфiгурацыю) пасля выканання гэтых камандаў. Стрэлка паказвае квадрат, які ў дадзены момант чытае машына.
МОЛОКО МОЛОКО МАЛОКО МАЛОКО МАЛАКО

Для развязання гэтай сама задачы можна пабудаваць iншую машыну Т’юрынга , у ёй мы будзем мець толькi два нутраныя станы:



(1)

(2)

(3)

(4)

Нiжэй падаецца вылiчэнне машыны , якое пачынаецца з канфiгурацыi


МОЛОКО ;


МОЛОКО





МАЛОКО



КМАЛАКО


над стрэлкамi стаяць нумары камандаў, якiя пераводзяць дадзеную канфiгурацыю ў наступную:


МОЛОКО

МАЛОКО

МАЛАКО

Прыклад 2. Пабудуем машыну Т’юрынга , якая адвольнае слова у алфавiце пераводзiла б у слова (у пачатковы момант галоўка чытае крайнi левы сымболь):

└┘ ,

,

└┘ ,

└┘ ,

└┘ .

Нiжэй падаюцца вылiчэннi машыны , якiя пачынаюцца канфiгурацыямi


q0ba i q2abb:↑↑q0ba→ q2”a→ q2”a”→ K”ab”;↑↑↑↑

q0abb→q1”bb→q1”bb→↑↑↑

→q1”bb”→K”bba”↑↑
Работу машыны можна апiсаць наступным чынам: яна запамiнае першую лiтару першаснага слова (пры гэтым выцiрае яе), i галоўка рухаецца направа да першай пустой клеткi, у якой i запiсваецца першая лiтара.

Практыкаваннi.

Ва ўсiх наступных задачах лiчым, што ў пачатковай канфiгурацыi нутраны стан машыны Т’юрынга , галоўка чытае крайнi левы сымболь.



1. Няхай на стужцы запiсаныя некалькi адзiнак адна за адной, злева i справа ад гэтай групы адзiнак знаходзiцца сымболь “.” (кропка). Пабудаваць машыну Т’юрынга, якая колькасць адзiнак павялiчвае на 1.

2. Няхай на стужцы запiсаныя некалькi адзiнак адна за адной, злева i справа ад гэтай групы адзiнак знаходзiцца сымболь “.” (кропка). Пабудаваць машыну Т’юрынга, пасля заканчэння работы якой на стужцы застанецца сымболь “1”, калi колькасць адзiнак была няцотнай, i сымболь “0”, калi колькасць адзiнак была цотнай.

3. Пабудаваць машыну Т’юрынга, якая да адвольнага двайковага лiку дадавала б 1.

4. Пабудаваць машыну Т’юрынга, якая да адвольнага дзесятковага лiку дадавала б 1.

5. Няхай на стужцы запiсаныя два сымболi, кожны з якiх або 0, або 1. Пабудаваць машыну Т’юрынга, якая справа ад гэтых сымболяў запiша iх кан’юнкцыю.

6. Пры ўмове практыкавання 5 пабудаваць машыну Т’юрынга, якая справа ад двух сымболяў запiша iх:

а) дыз’юнкцыю;

б) iмплiкацыю;

в) эквiваленцыю.



7. Няхай на стужцы знаходзяцца два наборы адзiнак, якiя падзяляе сымболь “.”. Пабудаваць машыну Т’юрынга, у вынiку работы якой на стужцы будзе набор адзiнак, колькасць якiх роўная суме колькасцяў адзiнак у першасных наборах.

8. Няхай памiж двума сымболямi “.” запiсаная паслядоўнасць сымболяў, кожны з якiх або 1, або └┘. Пабудаваць машыну Т’юрынга, якая ўсе сымболi “└┘“ памiж сымболямi “.” заменiць на 1.

9. Няхай памiж двума сымболямi “.” запiсаная паслядоўнасць сымболяў, кожны з якiх або 1, або └┘. Пабудаваць машыну Т’юрынга, якая памiж кропкамi пакiне групу адзiнак у колькасцi, роўнай колькасцi адзiнак у зыходнай паслядоўнасцi.

10. Пабудаваць машыну Т’юрынга, якая паслядоўнасць адзiнак робiць у два разы даўжэйшай.

11. Пабудаваць машыну Т’юрынга, якая адвольнае слова у алфавiце пераводзiла б у └┘ .

12. Пабудаваць машыну Т’юрынга, якая адвольнае слова у алфавiце ператварала б у .
ЛIТАРАТУРА

1. Э.Мендельсон. Введение в математическую логику. – М.: Наука, 1976. – 320 с.

2. П.С.Новиков. Элементы математической логики. – М.: Гос. изд-во физ.-мат. литературы, 1959. – 400 с.

3. С.Клини. Математическая логика. – М.: Мир, 1961. – 480 с.

4. Р.Л.Гудстейн. Математическая логика. – М.: Изд-во иностр. лит-ры, 1961. – 164 с.

5. В.А.Мощенский. Лекции по математической логике. – Мн.: Изд-во БГУ, 1973. – 160 с.

6. А.У. Машчэнскі, У.А. Машчэнскі. Курс матэматычнай логікі. – Мн.: БДУ, 2000. – 122 с.

7. В.И. Игошин. Задачник-практикум по математической логике. – М.: Просвещение, 1986. – 159 с.

8. А.В.Корлюков, С.П.Мищенко. Методические указания к практическим занятиям по курсу “Математическая логика”. – Гродно, 1988. – 66 с.

9. Т.Сухая, Р.Еўдакiменка, В.Траццякевiч, Н.Гудзень. Тэрмiналагiчны слоўнiк па вышэйшай матэматыцы для ВНУ. – Мн.:Навука i тэхнiка, 1993. – 183 с.

10. Я.В.Радыно, П.П.Шуба, А.Б.Антоневич и др. Русско–белорусский математический словарь. – Мн.: Вышэйшая школа, 1993. –239 с.

11. Матэматычная энцыклапедыя. – Мн.:Тэхналогія, 2001. – 496 с.



ЗМЕСТ
УСТУП ........................................................................2
РАЗДЗЕЛ 1. АЛГЕБРА ВЫКАЗВАННЯЎ ..............4

§1. Выказваннi i аперацыi над iмi ............................4

§2. Прапазiцыйныя формулы ...................................8

§3. Поўныя сiстэмы злучнiкаў .................................18


РАЗДЗЕЛ 2. ЗЛIЧЭННЕ ВЫКАЗВАННЯЎ ...........24

§1. Фармальныя тэорыi ............................................24

§2. Злiчэнне выказванняў ........................................25
РАЗДЗЕЛ 3. ЛОГIКА ПРЭДЫКАТАЎ ..................31

§1. Прэдыкаты ..........................................................31

§2. Формулы логiкi прэдыкатаў ..............................39

§3. Логiкава агульназначныя формулы ..................44

§4. Тэорыi першага парадку ....................................48

§5. Уласцiвасцi тэорыяў першага парадку .............50

§6. Фармальная арытметыка ....................................52

§7. Дастасаванні да натуральнае мовы……………53


РАЗДЗЕЛ 4. МАШЫНА Т’ЮРЫНГА .....................58
ЛIТАРАТУРА .............................................................63


1   2   3   4


База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка