Білім беру бағдарламасы білім алушыларына арналған. Лекциялар жинағы «Техника және ақпараттандыру»
жүктеу/скачать 316.11 Kb.
|
- Бұл бет үшін навигация:
- Ұсынылған әдебиеттер
- ЛЕКЦИЯ № 2 Тақырыбы : Прологтың логикалық негіздері ЛЕКЦИЯ ЖОСПАРЫ
- ЛЕКЦИЯ МАЗМҰНЫ
| Бақылау сұрақтары:
1. ПРОЛОГ аббревиатурасына трактовканы беріңіз. 2. ПРОЛОГ тілінің қолдану аймақтарын атаңыз. 3. ПРОЛОГ императивті тілден айрмашылығы неде? 4. ПРОЛОГ тілін құру мақсаты неде? 5. ПРОЛОГта драйверді жазуға болады ма? 6. ПРОЛОГ неге декларативті тіл деп аталады? 7. ПРОЛОГта операцияны анықтауға болады ма. Болмаса неге? 8. Тілдердің версияларын атаңдар. Ұсынылған әдебиеттер 1. Дүйсенов, Н.Ж. Логикалық бағдарламалау [Мәтін]: Оқу құралы / Н.Ж. Дүйсенов, М.Ж. Кошкинбаева.- Шымкент, 2019.- 92б. 2. Cюарт, Р. Жасанды интеллект.3-том. Жаңашыл әдіс. Логика. Оқулық-Алматы,2016-540б (ҚР БЖҒМ «Оқулық» орталығы бекіткен). ЛЕКЦИЯ № 2 Тақырыбы: Прологтың логикалық негіздері ЛЕКЦИЯ ЖОСПАРЫ Хорновтың дизъюнктері. Резолюция принциптері. Əмбебап алгоритімі. Хорновтық дизъюнктер үшін резолюция əдісімен теоремалар дəлдігі процедурасы. Прологта кері əсер етуші біліммен жұмыс істеу ерекшеліктері. ЛЕКЦИЯ МАЗМҰНЫ Бұл лекция Пролог тілінің теориялық негіздеріне арналған. Пролог тілінде математикалық логикалар тереңдігіне берілмей-ақ жақсы бағдарламалар жазуға болады. Бұл мағынаның өзінде бұл тарауды факультативті қажетті емес деп санауға болады. Бірақта, “ол қалай айналатындығы” жайлы бігісі келген адамға Пролог не мақсатта негізделгенін, оның құрылысын түсіндіруге тырысамыз. Бастапқыға оралайық, біз келіскендей тыңдаушылардан ерекше қаситтің қажеті жоқ. Ол үшін біз Прологтың негізінде жатқан бірінші тəртіптегі логикалар түсінігін қарастырайық, ол тəртіпке математикалық логика курсы кіреді. Əрине математикалық логиканы оқып білу үшін бір дəріс жеткіліксіз. Сол себепті біз Пролог тіліне қатыстысын ғана қарастырамыз Соның өзінде біз қолданылатын түсініктер бөлімі “кадрдан тыс” қалып қояды. Қандай да бір формальді Ф жүйесі берілген, егер мыналар анықталған болса: 1. жүйе алфавит- символдар жұп жиынтығы; 2. жүйе формулалары- алфавитқа жататын символдардан құралатын барлық сөздердің кейбір көпшесі. (көбіне жүйе алфавиті символдарынан формулалар құруға мүмкіндік беретін процедуралар беріледі). 3. жүйе аксиомалары- жүйедегі белгіленген формулалар көпшесі. Жүйе шешімін шығару тəртібі- жүйенің формулалар арасындағы қатнастардың соңғы көпшесі. Пролог негізделетін бірінші тəртіп логикасын (немесе предикаттар логикасы) береміз. Предикаттар логикасы тілі – адам тіліне жақын, формальді тілдердің бірі. Бірінші тəртіптегі логика алфавиті келесі символдарды қамтиды: 1. айнымалылар (оларды ағылшын алфавитінің соңғы əріптерімен белгілейміз u,v,x,y,z ); 2. константалар (оларды ағылшын əріпінің бірінші əріптерімен белгілейміз a,b,c,d); 3. функционалды символдар (оларды f жəне g); 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 эквиваленттігімен пайдаланып, импликацияны жоямыз; 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)формуласы У айнымалысына тəуелсіз болғандықтан істеуге болады Егер ол тəуелді болғанда байланысқан У айнымалысын өзгертуге болар еді. Екінші қадам. Алынған формула сколемизациясын келтіреміз. Əрекет ету кванторы сол жағында жалпыға бірдей квантор орналасқан, сонда У-ке кіретндердің барлығын жаңа х-ке тəуелді унарлы функцияланған символмен ауыстыру қажет. Сколемовсктің нормалды формасындаы формуланы аламыз: 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=ε деп алайық. 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 —резольвента. Егер ата- аналық дизъюнктер тек контрарлы литералдардан құралса, онда резольвентті – бос дизъюнк болып табылады. жүктеу/скачать 316.11 Kb. Достарыңызбен бөлісу:
|