«Пролог логикалық программалау тілі»


Негізгі əдебиет 1[15- 38]



бет2/6
Дата01.07.2016
өлшемі458.5 Kb.
#169566
1   2   3   4   5   6

Негізгі əдебиет 1[15- 38]

Қосымша əдебиет 1 [5-29]

Бақылау сұрақтары:

1. ПРОЛОГ аббревиатурасына трактовканы беріңіз.

2. ПРОЛОГ тілінің қолдану аймақтарын атаңыз.

3. ПРОЛОГ императивті тілден айрмашылығы неде?

4. ПРОЛОГ тілін құру мақсаты неде?

5. ПРОЛОГта драйверді жазуға болады ма?

6. ПРОЛОГ неге декларативті тіл деп аталады?

7. ПРОЛОГта операцияны анықтауға болады ма. Болмаса неге?

8. Тілдердің версияларын атаңдар.

2 дəріс тақырыбы. Прологтың логикалық негіздері

Хорновтың дизъюнктері. Резолюция принциптері. Əмбебап алгоритімі. Хорновтық дизъюнктер үшін резолюция əдісімен теоремалар дəлдігі процедурасы. Прологта кері əсер етуші біліммен жұмыс істеу ерекшеліктері.



Дəріс конспектісі: Бұл лекция Пролог тілінің теориялық негіздеріне арналған. Пролог тілінде математикалық логикалар тереңдігіне берілмей-ақ жақсы бағдарламалар жазуға болады. Бұл мағынаның өзінде бұл тарауды факультативті қажетті емес деп санауға болады.

Бірақта, “ол қалай айналатындығы” жайлы бігісі келген адамға Пролог не мақсатта негізделгенін, оның құрылысын түсіндіруге тырысамыз.

Бастапқыға оралайық, біз келіскендей тыңдаушылардан ерекше қаситтің қажеті жоқ. Ол үшін біз Прологтың негізінде жатқан бірінші тəртіптегі логикалар түсінігін қарастырайық, ол тəртіпке математикалық логика курсы кіреді. Əрине математикалық логиканы оқып білу үшін бір дəріс жеткіліксіз. Сол себепті біз Пролог тіліне қатыстысын ғана қарастырамыз

Соның өзінде біз қолданылатын түсініктер бөлімі “кадрдан тыс” қалып қояды. Қандай да бір формальді Ф жүйесі берілген, егер мыналар анықталған болса:

1. жүйе алфавит- символдар жұп жиынтығы;

2. жүйе формулалары- алфавитқа жататын символдардан құралатын барлық сөздердің кейбір көпшесі. (көбіне жүйе алфавиті символдарынан формулалар құруға мүмкіндік беретін процедуралар беріледі).

3. жүйе аксиомалары- жүйедегі белгіленген формулалар көпшесі.

Жүйе шешімін шығару тəртібі- жүйенің формулалар арасындағы қатнастардың соңғы көпшесі.

Пролог негізделетін бірінші тəртіп логикасын (немесе предикаттар логикасы) береміз.

Предикаттар логикасы тілі – адам тіліне жақын, формальді тілдердің бірі.

Бірінші тəртіптегі логика алфавиті келесі символдарды қамтиды:

1. айнымалылар (оларды ағылшын алфавитінің соңғы əріптерімен белгілейміз u,v,x,y,z );

2. константалар (оларды ағылшын əріпінің бірінші əріптерімен белгілейміз a,b,c,d);

3. функционалды символдар (оларды f жəне g);

15

4. предикатты символдар(оларды p,q,r əріптерімен белгілейміз);



5. ақиқат жəне жалған константаларының орналасуы(trueжəне false);

6. логикалық байланыстырушы;

7. кванторлар;

8. қосалқы символдар.

Əрбір предикатты жəне функционалды символ анықталған аргументтер ие. Егер предикатты символ n аргументтерге тең болса, олn- орнықты предикатты символ деп аталады.

Терм деп айнымалылардан жəне константалардан құралған, ол функцияларды қолдануда болуы мүмкін, ал анығырақ айтсақ:

1. Кез- келген айнымалы немесе константа терм болып табылады;

2. Егер t1….tn терм болады, f – n- орнықты функционалды исмвол болса, онда f(t1…tn) терм болады;

3. Басқа термдер жоқ.

Жұмыс барысында Пролог бағдарламада барлық объектілер термдер түрінде болады. Егер терм айнымалыларды қамтымаса, ол негізгі немесе константты терм деп аталады. Атомды немесе қарапайым формулаларды термдерге предикаттарды қолдану жолымен алынады, P(t1,…,tn), мұндағы P-n орнықты предикатты символ, ал t1,…, tn- термдер. Логиканың бірінші тізбектегі формулалары келесі түрде алынады:

1. кез-келген атомды фрмула формула болып табылады;

2. егер А жəне В- формулалар болса, ал х-айнымалы, онда А(«А емес» немесе «А-ны

жоққа шығару»), A B ( "A жəне B" оқылады), A B ("A немесе B" оқылады), A B ( "A баулыйды B-ны"), хA (“қандайда бір х” үшін оқылады немесе “х бар болғаны”)жəне xA (“кезкелген х үшін” оқылады немесе “барлық х үшін” )– формулалар; 3.басқа формулалар жоқ;

Егер формула xA немесе хA түрде болса, ондағы А x немесе х кванторларының əрекет обылысында орналасса, онда ол байланысқан кіріс деп аталады. В қарама-қарсы жағдайда айнымалының формулаға кірісі еркін деп аталады.

Дəрістің көлемін үлкейтпеу үшін біз аксиомалар жəне бірінші тізбек логикасы шешімінің ережесін қарастырмаймыз. Олардың ішінде жұмыс барысында сəйкес келген жерде келтіріледі.

Литерал деп атомды немесе жоққа шығарылған атомды формуланы атаймыз. Атом- оң литералдар, ал оның терісі(отрицаниесі)-теріс литералдар деп аталады.

Дизъюнк- бұл литералдардың соңғы дизъюнкцияланған саны. Егер дизъюнк литералдардыды қамтымаса, онда ол бос дизъюнк жəне 0 символының жабдығы болады.Резолюция əдісімен жұмыс істейтін дизъюнктер көпшесіне кез-келген формуланы келтіруге болады, оны толығырақ қарастырайық. Ол үшін бізге қалыпты форма анықтамасы қажет болады.

Егер коньюнкция дизъюнктердің соңғы саны болатын болса, онда формула коньюнктелген қалыпты формада орналасқан. Мұнда кез-келген кванторсыз формула үшін формула бар екендігі жайлы теорема орын алады, яғни ол формула бастапқының логикалық эквиваленті жəне коньюнктелген қалыпты формада орналасқан.

Формула қалыпқа келтірілген формада орналасады, егер Q1x1,...,QnxnA, мұндағы Qi – бұл квантор немесе , ал А формуласы кванторларды қамтымайды. Q1x1,...,Qnxn белгісін префикс деп атайды, ал А формуласы- матрица.

Формула сколемовскидің қалыпты формасында орналасады, егер ол қалыпқа келтірілген форма түрінде болса жəне кванторлар қамтымаса.

Дизъюнктер көпшесіне предикаттарды есптейтін туынды формула алгоритімі.

Бірінші қадам: Бастапқы формуланы қалыпқа келтірілген форма түріне келтіреміз, ол үшін:етуші обылысы деп аталады. Егер х формулаға кіруде x немесе х кванторлар əрекет ету

1. A B ¬A B эквиваленттігімен пайдаланып, импликацияны жоямыз;

16

2. барлық теріске шығаруларды формула ішіне кіргіземіз, олар тек атомды формулалар алдында орналасу керек, ол үшін келесі эквиваленттілікті қолданамыз:



3. ¬(A B) ¬A ¬B

4. ¬(A B) ¬A ¬B

5. ¬( xA) x¬A

6. ¬( xA) x¬A

7. ¬¬A A

8. байланысқан айнымалыларды біздің формулада кездеспейтіндей, сондай-ақ

байланысатындай жəне еркін етіп өзгертеміз.

9. эквиваленттілікті қолдана отырып кванторларды формула басына шығарамыз:

QxA(x) B Qx(A(x) B), егер B x айнымалысын қамтымаса, ал Q { , }

QxA(x) B Qx(A(x) B), егер B x айнымалысын қамтымаса , ал Q { , }

xA(x) xB(x) x(A(x) B(x)) xA(x) xB(x) x(A(x) B(x)) Q1xA(x) Q2xB Q1xQ2y(A(x) B(y)), мұндағы Q { , } Q1xA(x) Q2xB Q1xQ2y(A(x) B(y)), мұндағы Q { , }

Екінші қадам. Сколемезациялау жүргіземіз. Ол үшін əр бір кванторға келесі алгоритмді орындаймыз. Егер əрекет етудегі алынып тасталатын квантор –формула префиксндегі ең сол жақтағы квантор, осы квантормен байланысты барлық формулалардағыларды айнымалылармен ауыстырамыз, ол кванторды сызып орнына жаңа константа жазамыз .

Егер олкавнтордан солырақ жалпыға бірдей квантор болса, формуладағыларды сол кавнтормен байланысқандардың барлығын айнымалылрамен ауыстырамыз, ол ол кавнторларды сызамыз.

Бұл үрдісті жүргізу арқылы сколемовский қалыпты формасындағы формуланы аламыз.

Кванторларды алып тастау алгоритмін 1927ж Сколем ашқан. Мұнда орындалу мағнасында формула жəне оның сколемизациялау эквиваленттігі.

Үшінші қадам. Жалпыға бірдей кванторларды элиминирлейміз. Алынған формула, орындалу мағынасында бастапқы экиввалентті жəне кванторсыз болады.

Төртінші қадам. Формуланы конъюнктелген қалыпты формаға келтіреміз, ол үшін дистрибутты белгіленген эквиваленттілікті қолданамыз:

A (B C) (A B) (A C)

A (B C) (A B) (A C)

Бесінші қадам. Формуланы дизъюнктер көпшесі түрінде белгілеп конъюнктерді элиминирлейміз.

Бастапқы формулаға эквивалентті дизъюнктерді аламыз, оның мағынасы келесі теоремада.

Теорема. Формула тек қана одан алынған дизъюнктер орындалмайтын жағдайда ғана жалғанға тең болады.

Ескерту, формулалар көпшесі-егер осы көпшедегі барлық формулулур ақиқат екендігін білдіретін бір бір айнымалылыр болмаса орындалмайтын деп аталады.

Мысал: x(P(x) y(P(y) ¬Q(x,y))) формуласын эквивалентті дизъюнктер көпшесіне айналдырамыз.

Бірінші қадам. Бастспқы формуланы бастапқы нормалды формаға келтіреміз.Импликацияна элиминирлеу арқылы x(¬P(x) y(P(y) ¬Q(x,y))) формуласын аламыз. У айнымалысын жақша сыртына шығарамыз: x y(¬P(x) (P(y) ¬Q(x,y))).

Мұны ¬P(x)формуласы У айнымалысына тəуелсіз болғандықтан істеуге болады Егер ол тəуелді болғанда байланысқан У айнымалысын өзгертуге болар еді.

17

Екінші қадам. Алынған формула сколемизациясын келтіреміз. Əрекет ету кванторы сол жағында жалпыға бірдей квантор орналасқан, сонда У-ке кіретндердің барлығын жаңа х-ке



тəуелді унарлы функцияланған символмен ауыстыру қажет. Сколемовсктің нормалды формасындаы формуланы аламыз: x(¬P(x) (P(f(x) ¬Q(x,f(x)))).

Үшінші қадам. Жалпыға бірдей кванторларды элиминирлейміз: : ¬P(x) (P(f(x))

¬Q(x,f(x))).

Төртінші жəне бесінші қадамдарда қажеттілік жоқ, өйткені формула өздерімен дизъюнкті білдіреді: ¬P(x) P(f(x)) ¬Q(x,f(x)).

Біз қарастырып көретін пролог негізінде жатқан келесі техника, ол- унификакция.

Унификация бірінші тізбектегі логика формулаларын бос айнымалылардың термдерімен ауыстыру жолымен теңестіріледі.

Қойылым- бұл көпше түрі {x1/t1,..., xn/tn}, мұндағы барлық і- лер үшін, хі- айнымалы, ал ti – терм, яғни хі= ti (айнымалылардың термдерге ауысу белгісі). Сонымен қоса қойылымға кіретін барлық айнымалылар түрлі (кез-келген i j xi xj )

Е символымен бос қойылымды белгілейміз. Қойылымдағы барлық термдер негізгі болса- негізгі қойылым деп аталады. Қарапайым белгілеу – бұл терм немесе атомды формула. Егер А- қарапайым белгілеу, ал Ө- қойылым болса, онда АӨ А-дағы айнымалылардың кірістері бір уақытта сəйкес келетін термдерге ауысу жолымен алынады. АӨ А- белгісінің жеке жағдайы деп аталады.Қойылым қамти отырып хі айнымалысының кірістерін tі термдерімен ауыстырады.

Ө жəне η - қойылым болсын делік, θ={x1/t1,..., xn/tn}, η ={y1/s1,...,yn/sn}. Θη компазициясы {x1/t1η,...,xn/tnη,y1/s1,..., yn/sn} көпшесінен xi/tiη жұбын жою арқылы, мұндағы xi tiη жəне yi/si мұндағы yi xj –ң біреуіне сəйкес келеді.

Мысал. θ={x/f(y),y/z}, η={x/a,y/b,z/y}болса, θη құрамыз. Ол үшін {x/f(b), y/y,x/a,y/b,z/y} көпшесін аламыз, одан y/y жұбын алып тастаймыз(өйткені ауыстырылатын айнымалы терммен сəйкес келеді), x/a,y/b (өйткені η қойылымынан ауыстырылатын θ қойылымынан ауыстырылатын айнымалымен сəйкес келеді). θη={x/f(b),z/y}жауабын аламыз. Егер η=θγ қойылым болса θ қойылымы η қойылымына қарағанда көбірек жалпыға бірдей болады. Θ- қойылымы АжəнеВ қарапайым белгілерінің унификаторы деп аталады, егер Aθ=Bθ болса.

Мұндай жағдайда А жəне В жайлы унифицирленген дейді. Унификация Прологта берілгендер құрылымының компазициясы жəне декомпазициясы үшін қолданылады.

Мысал. A=p(f(x),z) и B=p(y,a) унифицирленетіндер. Олардың унификаторы ретінде {y/f(x),z/a}қойылымын немесе {y/f(a),x/a,z/a}қойылымын алуға болады. Жалпы айтқанда екі формула шексіз көп унификаторларға ие болуы мүмкін. Ө унификаторын А жəне В қарапайым белгілердің жалпы(немесе қарапайым) унификаторы деп атайды, егер ол А жəне В қарапайым белгілерінің басқа унификаторларына қарағанда жалпыға көбірек болса.

Мысал: Жоғарыда қарастырылған мысалдардан көбірек жалпы болып {y/f(a),z/a}қойылымы болып табылады.

S- қарапайым белгілердің соңғы көпшесі делік. d(S) қарама- қайшылықтары көпшесін анықтайық.Сол жақтағы позицияны қоғалтпай қоямыз, онда S-ң барлық белгілеріне бір символ қойыла бермейді.d(S)-ке S белгісінен белгіше кіргіземіз, ол осы позициядан басталады.

Мысал. S={p(f(x),h(y),a),p(f(x),z,a),p(f(x),h(y),b)} болса. S қарамақайшылық көпшесі үшін d(S)={h(y),z}.

Унификация алгоритімі.

S қарапайым белгісінің соңғы көпшесі үшін жалпы унификаторын іздеу алгоритімін берейік.

Егер көпше унификацияланбайтын болған жағдайда алгоритм сол жағдайды табуға міндетті.

1 Қадам. k=0, 0=ε деп алайық.

18

2 Қадам. Егер S k – бір элементті көпше болса, алгоритмді тоқтатамыз, k – S үшін жалпы унификатор болады. Қарама-қайшы жағдайда d(S k) теңсіздік көпшесін құрып, үшінші қадамға көшеміз.



3 Қадам. Егер х t-ға кірмейтіндей болып екеуі де d(S k)-ға жататын болса, онда k+1= k{x/t}теңдеуін шығарамыз.k бір бірлікке көбейтеміз, сөйтіп екінші қадамға көшеміз. Басқада жағдайларда алгоритмді тоқтамыз, S көпшесі унификацияланбайды. Назар аудурыңыздар, унификация алгоритімі өзінің жұмысын қарапайым белгілердің кез-келген соңғы көпшесі үшін қадамдардың соңғы қадамында тоқтатады, өйткені біз əр қадамға өткен сайын айнымалылар санын азайтамыз.Өйткені қарпайым белгілер көпшесі де ондағы түрлі айнымалылар көпшесі де соңғы, олай болса түрлі айнымалылар санын көбейтпейтін əр қадамдар санынан кейін алгоритм аяқталады.

Бекітілу, S қарапайым белгілердің кез-келген соңғы көпшесінің унификациялануы үшін унификация алгоритмі өз жұмысын аяқтайды жəне S үшін жалпыға бірдей унификатор береді- бұл унификация теоремасы деп аталады.

Енді резолюция əдісіне қарастыруға көшсек болады. Негізінде есеп мағынасы неде? Біз сұраққа автоматты түрде жауап беретін алгоритм құрғымыз келді, ол үшін қолымызда бар көпшелердің қандайда бір қорытындысын келтіруге болады ма? Бізге белгілі жалпы жағдайда бірінші тізбектегі логиканың өзіне мұндай алгоритм мүмкін емес. Ереже бойынша, мұндай алгоритмдер құруға болатын формалды жүйелер көрнекті күшке ие. Оларға мысал ретінде бір орынды предикаттар жəне айту логикасын келтірсек болады.

Бірақ та Робинсон автоматты шешім кезінде компьютер қолданылатын ережелер “адам” шешім шығаруда қолданылатын ережелерге сəйкес келуі міндетті емс деп есептеді. Ол A и A B B шығараын "modus ponens" шешім шығару ережесінің орнына оның жалпылама түрін, яғни адмға түсіну қиынға түсетін, ал компьютерде тиімді жүзеге асырылатын резолюция ережесін қолданған дұрыс деп ойлады. Бұл ережені талқылайық.

Резолюция ережесін айтылу логикасы үшін келесі түрде формулалауға болады.

Егер екі дизъюнктондар үшін бір дизъюнкке оң кіріс, ал екіншісіне теріс кіріс болатын атомды формула болса, онда дизъюнктердің бірінен атомды формулаға сəйкес келетін кірісті сызып, ал екіншісінен-терісін сызып жəне ол дизъюнктерді қосу арқылы, резольвентті деп аталатын дизъюнк аламыз. Мұндай жағдайда бастапқы дизъюнктер ата-аналық немесе резольвирленген деп аталады, ал сызылған дизъюнктер – контрарлы литералдар деп аталады.

Резольвентаның басқа символдары-бұл дизъюнк, ол контрарлы литералдарды сызып ата- аналық дизъюнктерді қосу арқылы алынады.

Бұл ереженің графикалық түрі:

(A B, P ¬P)/A B

Мұнда A P и B ¬P- ата-аналық дизъюнктер, P и ¬P – контрарлы литералдар, A B —резольвента.

Егер ата- аналық дизъюнктер тек контрарлы литералдардан құралса, онда резольвентті – бос дизъюнк болып табылады.

Негізгі əдебиет 5 [20-38]

Қосымша əдебиет 1 [5-29]

Бақылау сұрақтары:

1. Хорновтық дизъюнктері дегеніміз не?

2. Резолюция принципінің мағынасы неде?

3. Жүйе алфавитіне анықтама беріңіз жəне оларды атаңыз.

4. Жүйе аксиомасы түсінігіне анықтама беріңіз.

5. Жүйе формуласына анықтама беріңіз жəне оларды атаңыз.

6. Жүйе ережесіне анықтама беріңіз. Мысал келтіріңіз.

7. Дизъюнк деген не?

19

8. Литерал түсінігі. Олардың түрлері.



9. Резолюция ережесі.

10. Логикалық бағдарлама дегеніміз не?

11. Бектринг бағдарламамен не істейді?

12. Сколемовскидің нормалды формасы деген не?

13. Клозамалар түсінігіне анықтама беріңіз.

3 дəріс тақырыбы. Прологтың негізгі түсінігі.

Айғақтар мен ережелер. Ішкі жəне сыртқы мақсаттардың қарым-қатынасы. Еркін жəне байланысқан айнымалылар. Анонимді айнымалы. “Жасыл” жəне “қызыл” қималар.

Прологтың семантикалық моделдері: декларативті жəне процедуралы.

Дəріс конспектісі: Бұл дəріс Пролог тілінің негізгі түсініктеріне арналған. Осы жəне келесі дəрістерде біз Прологта бағдарламалардың жазылуының негізін оқимыз.

Б экус-Наурдың (БНФ) қалыпты формасымен танысамыз, оны 1960 жылы Джон Бэкус жəне Питер Наур ойлап тапты жəне бағдарламалау тілінің синтаксисін формальді жазуы үшін қолданылады. БНФ алғашында Алгол-60 тілінің синтаксисін жазғанда Питер Наурмен қолданылды.

Құрылым синтаксисін жазуда келесі белгілер қолданылады:

::=белгісі “анықтау бойынша” (“бұл”, ”бар”) деп оқылады. Бөлгіштің сол жағында түсіндіретін түсінік орналасады, оң жағында –оны айқындаушы конструкция.

Мысалы,

< Ат > ::= < Идентификатор >

Бұрыштық жақшаларда тілдің синтаксистік құрылысын белгілеуге арналған бөлігі жоғарыда келтірілген мысалда ол < Ат > жəне < Идентификатор > белгісі БНФ нотациясында “немесе” білдіреді. Ол анықталатын түсініктің түрлі баламалы талқылаулардың бөлінуі үшін қолданылады.

Мысал, Ондық санды келесі жолмен анықтау керек:

< сан > :: = 0|1|2|3|4|5|6|7|8|9

Синтаксистік құрылыс бөлігі тік жақшамен қоршалған,міндетті емес (болуы да, болмауы да мүмкін);

Мысал. Жазба

< бүтін сан > :: = [-]< оң бүтін сан >

Бүтін санды оң алдында минус таңбасы тұруы мүмкін бүтін сан арқылы табуға болатынын көрсетеді. белгісі синтаксистік құрылыс бөлігі. Таңдалынған санмен ( нөл жəне үлкен ) қайталануы мүмкін екенін білдіреді. Кейде * белгісінің орнына жүйелі жақша ({,}) қолданылады.

Мысал, БНФ нотациясыда оң бүтін санды былай анықтауға болады.

< оң бүтін сан > ::= <сан>[<сан>]*.

Яғни оң бүтін сан бір немесе бірнеше саннан тұрады. Пролог тіліндегі программа оны кейде білім негізі деп атайды.Ол сөйлемдерден тұрады (немесе бекітулерден ) , əрбір сөйлем екі түрлі болады : дерек , ереже.

Сөйлем түрі

A:-


B1,... , Bn.

А сөйлемнің басы деп аталады, ал B1,... , Bn -денесі.

Бұл жайлы өткен дəрісте айтылды. Бірақ онда теориялық тұрғыдан бұлт түсініктерді қарастырған жоқпыз, ал қазір бағдарламалау жағынан тəжірибелі болады. Дерек объектер арасындағы кейбір қатынастардың орындалуын айқындайды.Ол тек қана тақырыптан тұрады. Факті-денесі жоқ сөйлем деп есептеуге болады.

Мысалы, бізге белгілі факт , Наташа Дашаның анасы, ол мына түрде жазылуы мүмкін:

Мама ( Наташа, Даша ).

20

Факт шындық дəлелді көрсетеді.



Өткен лекцияда танысқан математикалық логикада қатынастарды предикаттар деп айту қабылданған. Егер Бэкус-Науэрдің қалыпты формасын қолдансақ , онда предикатты келесідей анықтауға болады:

<Предикат>::=<Аты> <Аты>(<аргумент>[,<аргумент>]*), яғни предикат не тек аттан ,не атау мен одан кейін жақшаға алынған аргументтен тұрады.

Предикаттың аргументі немесе параметрі константа айнымалы немесе құрамды объект болуы мүмкін .Предикат аргументінің саны оның арностью немесе местностью деп аталады.

Айнымалылар туралы сəл-пəл кейін айтамыз,ал тұрақтыларды толық қарастыруды бесінші дəріске қалдырамыз.

Т урбо Прологта предикат аты латын əріптерінің реттілігімен тұруы керек жəне асты сызылатын əріптер мен белгілерден басталады. Прологтың басқа версияларында предикат аты тек ағылшын алфавитінің əріптерін ғана емес басқа да жəне ұлттықтанда , мысалы орыс тілінен тұруы мүмкін. Сəйкесінше ,жоғарыда келтірілген факт мысалын Турбо Прологта былай жазуға болады:

mother("Наташа", "Даша").

Кейбір предикаттар жүйеде белгілі олар стандартты немесе құрылған деп аталады.

Турбо Прологта атау бірдей предикаттан тұратын сөйлемдер бірінен соң бірі жүруі керек.

Сөйлемдердің мұндай жиынтығы процедура деп аталады.

Жоғарыда келтірілген мысалда ,Наташа Дашаның мамасы екендігі , мама – бұл екі аргументті предикаттың аты, оның жолдық тұрақтысы “Наташа” бірінші аргумент ,ал “Даша” – екінші .

Е реже –бұл ұсыныс , оның шынайылығы бір немесе бірнеше ұсыныс шынайылығынан тұрады.Əдетте ереже бірнеше мақсаттарды қамтиды , олар шынайы болуы керек , сонда ереже де шынайы болады.

БНФ нотациясында ереже түрі мынадай болады:

<Ереже>::=<предикат>:-<предикат>[,<предикат>]*.

Мысал. Адамның əжесі – оның анасының немесе əкесінің анасы екені белгілі. Сəйкес ереже түрі мынадай:

əже(X,Y):-

мама(X,Z), мама(Z,Y).

əже(X,Y):-

мама(X,Z),папа(Z,Y).

":-"белгісі “егер” дегенді білдіреді , жəне оның орнына if жазуға болады.

"," белгісі –бұл логикалық байланыс “жəне” немесе конъюнкция , оның орнына and жазуға болады.

Бірінші ереже бойынша Х Y –тің əжесі ,егер Z –Y –тің мамасы. Екінші ереже бойынша ХY-тің əжесі болып табылады.,егер мынадай Z болса ,Х Z-тің мамасы ,ал Z-Y-тің əкесі.

Берілген мысалда X,Yжəне Z – айнымалылар.

Т урбо прологтағы айнымалы аты латын алфавитінің əріптерінен , сандардан , белгілеу белгілерінен тұруы мүмкін жəне жазба əріптен басталуы керек. Бұл уақытта ережедегі айнымалылар жалпы квантормен байланысқан. Прологтағы айнымалы алгоритімдік програмалау тілімен салыстырғанда объекті білдіреді. Прологта құрылымсыз иемдену механизмдерін қолдамайды.

Айнымалылар еркін жəне байлаулы болуы мүмкін. Еркін айнымалы –ол əлі мəн алмаған айнымалы. Ол нөлге де, бос орынға да тең емес; оның ешқандай мəні жоқ. Мұндай айнымалылар нақтыланбаған деп те аталады.

Қ андай да мəн алған айнымалы жəне белгілі бір объектпен байланысқан айнымалы байлаулы деп аталады. Егер айнымалы нақты болса жəне оған белгілі объект берілсе ,онда ол айнымалы өзгертуге келмейді.

21

П рологтағы айнымалының əрекет облысы бір сөйлем болып табылады. Түрлі сөйлемде түрлі объекті белгілеу үшін бір айнымалының аты қолданылуы мүмкін. Əрекет облысын анықтау ережесінен ерекшесі жасырын айнымалы ол ″-″ белгісімен белгіленеді . Жасырын айнымалы , айнымалы мəні елеусіз болғанда қолданылады. Əрбір жасырын айнымалы-жеке объект.



Прологтың үшінші арнаулы құжаттық сөйлем түрі сұрақтар болып табылады.

Сұрақ тек денеден тұруы мүмкін жəне БНФ-ң көмегімен былайша көрсетілуі мүмкін:



<сұрақ>::=<предикат>[<предикат>]*

Сұрақтар бағдарламада көрсетілген кейбір объектер арасындағы қатынастың орындалуын айқындау үшін қолданылады. Жүйе сұрақты мақсат ретінде қарастырады. Сұраққа жауап оң жəне теріс болуы мүмкін.

Прологтағы бағдарлама бағдарламаның ішінде сұрақты ұстауы мүмкін (ішкі мақсат деп аталады) . Егер бағдарламаның ішкі мақсаты болса, онда бағдарламаны орындауға қосылған соң жүйе берілген мақсаттың жетістігін тексереді.

Е гер бағдарламада ішкі мақсат болмаса , онда бағдарлама іске қосылғаннан кейін жүйе диалогты режим де сұрақ енгізуді сұрайды (сыртқы мақсат) . Орындалатын файлда компиляцияланатын бағдарлама міндетті түрде ішкі мақсатқа ие болуы керек. Егер мақсат орындалса, онда жүйе (″Yes″) сұрағының шынайылығы туралы нəтиже жасауға мүмкіндік береді. Егер сұрақта айнымалылар болса, онда жүйе оның мəнін береді егер шешім болса, (″No solunion″) деген шешім болмаса хабарлайды.Егер мақсатқа жетпесе , онда жүйе (″No″) деген жауап береді.

“No” деген жауап əрқашан сұрақ орындалмайды дегенді білдірмейді. Жүйе мұдай жауапты ақпарат жоқ болған жағдайда да беруі мүмкін.

Бекіту – бұл ереже ал дерек немесе сұрақ – бұл оның жеке жағдайы.

Бірнеше мысалды қарастырайық. Бағдарламада келесі байланыстар берілген болсын.

Мама («Наташа», «Даша»)

Мама («Даша», «Мама»).

Жүйеден Дашаның анасы Наташа ма деп жүйеден сұрауға болады. Бұл сұрақты мына түрде беруге болады.

Мама («Наташа», «Даша»)

Жүйеден __________сəйкес дерек тауып, жүйе «Yes» деп жауап береді. Егер біз сұрасақ:

Мама («Наташа», «Мама») десек, онда «No» деген жауап аламыз. Сонымен қатар Дашаның анасының атын сұрауға болады.

Мама (х, Даша).

Жүйе бірінші дерекпен сұрақты салыстырады да, Наташа мəндə Х айнымалысын нақтылау жəне жауап береді:

Х= Наташа

1solution

Наташаның қызының аты туралы сұрақ былайша жазылады:

Мама (Наташа, Х)

Сəйкес жауап

Х=Даша

1Solution



Сұрақ беру арқылы жүйеден барлық белгілі аналар мен қыздарының аттарын табуды сұрауға болады:

Мама(Х,У)

Жүйе біртіндеп бар сұрақтарды бағдарламадағы сөйлемдердің біріншісінен соңғысына дейін сəйкестендіруге тырысады. Қолайлы унификациядан соң Х айнымалысы анасының атын, ал У айнымалысы оның қызының атымен берілетін болады.

Нəтижесінде мынадай жауап аламыз:

22

X=Наташа У=Даша



Х=Даша У=Мама

2 solution

Егер барлық аналардың атын алу керек болса, жасырын айнымалыны қолдануға жəне сұрақ жазуға болады:

Мама (Х, - )

Жауап :

Х=Наташа


Х=Даша

2 solution

Егер сұраққа жауап алу керек болса: «Мама – қызы» қатынасындағы адамдар туралы ақпарат бар ма, онда оны мына түрге келтіруге болады:

Мама (-,-)

Берілген жағдайда бізге нақты аттар қажетсіз, ал біздің базамызда сəйкес бір деректің бар болуы. Бұл жағдайда жауап тек “yes” болады.

Біздің ережелер бағдарламамызға «əже-немере» байланысын анықтайтын ереже енгіземіз,

«ана болу» терминдерінде:

Əже (Х,У):-

Мама (Х,Z),

Мама (Z, У).

Істің барысында бұл жерде бір адам екіншісінің əжесі, егер ол оның анасының анасы болса, əрине дəлдік үшін екінші ережені жазуға болады. Əже – ол əкенің анасы, егер бағдарламаға əкелер туралы дерек енгізсек.

Біздің бағдарламамызда əже қатынасымен байланысты бір де бір дерек жоқ. Соған қарамастан жүйе əжелер туралы сұрақтарға жауап табуға бейім. Мысалы, Егер Наташа кімнің əжесі екені қызықтырса онда біз бұл сұрақты былай жазуымызға болады:

Əже («Наташа», Х).

Сұраққа жауап табу үшін жүйе біздің базамызды басынан аяғына дейін қарайды, сөйлем табу керек.

Max (X, У,У):-

Х=У/* егер бірінші сан екіншісіне тең болса, максимум ретінде екінші сана аламыз */

Соңғы сөйлемді екінші немесе үшінші сөйлеммен біріктіруге болады. Сонда процедура екі сөйлемнен тұрады:

Max (X,Y,X):- X>Y./* егер бірінші сан екіншісінен үлкен болса, онда бірінші сан максимум */

Max (X, У,У):- X<=Y./* егер бірінші сан кіші немесе екіншісіне тең болса, максимум ретінре екінші санда аламыз */

Дегенмен алынған процедура шындықтан əлі алыста. Бір жағынан, (Х>У) бірінші тексеру шарты орындалмаған жағдайда, екінші шарт (Х<=У) тексеріледі. Екінші жағынан, егер бірінші шарт орынды болып жəне бірінші сан екіншісінен үлкен болса, онда Пролог – жүйе предикаттың үшінші аргументін мах бірінші аргументпен байланыстырылады, содан кейін екінші сөйлемді солғастырғысы келеді. Бізге белгілі болғандай максимум анықталғаннан кейін ешнəрсе жасаудың қажеті жоқ. Басқа нұсқаның болуы мүмкін емес.

Бұл жағдайда бізге құрылымды предикат керек, ол ағылшынша cut деп аталады, орысша қима, ал Пролог бағдарламасында ол леп белгісімен «!» белгіленеді. Бұл предикат бағдарлама жұмысының тиімділігін арттыру мақсатымен іздеу кеңістігін шектеуге арналған, ол əрқашан сəтті аяқталады.

Қиманы қолданып біздің шешіміміз қысқа болады:

Мах 2 (Х, У, Х) : -

23

X>У, !./* егер бірінші сан екіншісінен үлкен болса, онда бірінші сан мак симум */



Мах 2 (-,У,У) /*басқа жағдайда екінші сан максимум болады */

Егер қима жұмыс жасаса, ол тек Х>У шарты шын болғанда ғана мүмкн, Пролог – жүйе альтернативті екінші сөйлемді қарастырмайды. Екінші сөйлем шарт дұрыс болмаған жағдайда ғана жасалады. Бұл жағдайда үшінші аргументке екінші аргументтің мəні беріледі.

Бұл жағдайда бірінші аргумент неге теңелгені бізге қажет еместігіне назар аударыңыз жəне оны жасырын айнымалымен алмастыруға болады.

Қиманы қолданудың барлық жағдайында «жасыл» жəне «қызылға» бөлу қабылданған.

Лақтыру кезінде бағдарлама қима кезіндегі мəндерді беруді тоқтатпау жасыл деп аталады. Егер қиманы алып тастау кезінде бағдарлама дұрыс шешім бермесе, онда мұндай қималар қызыл деп аталады.

«Қызыл» қиманың мысалы мах2 предикатын жүзеге асыруда бар ( егер қиманы алып тстасақ, предкат максимум ретінде екінші санды береді, ол бірінші саннан кіші болса деп аталады). «Жасыл» қиманың мысалын мах предикаттың жазбасына қиманы қосу арқылы алуға болады ( предикат олармен де, оларсыз да бір шешімді береді).

Прологта қима көмегімен тарамдалу сияқты императивті тілдерді моделдеуге болады.

Процедура

S:-

<шарт>, !, P,

S:-


P2.

If <шарт> then P else P2 операторына сəйкес болады, яғни шарт орынды болса, онда P орындайды, əйтпесе P2. Мысалы, максимум жағдаында біздің процедурамызды « егер Х > Y, онда M = X, əйтпесе M = Y» деп ашып жазуға болады.




Достарыңызбен бөлісу:
1   2   3   4   5   6




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет