Логикалық программалау туралы ақпарат

Алғысөз 4 бет

Логикалық программалаудың тілі 5 бет

Логикалық өрнектер тілі ерекшеліктері 6 бет

Унификациялау 8 бет
Унификация алгоритмі 10 бет

Ең жалпы унификаторды табу алгоритмі 12 бет

Логикалық программалаудағы негізгі қорыту ережесі 17 бет

Мақсатттарды жүзеге асыру 18 бет

Қорытынды 21 бет

Қолданылған әдебиеттер тізімі 22 бет

Логикалық программалау “пролог” табиғи тілдегі сөйлемдердің граматикалық мәселелерін талқылау үшін және мәтін есептерді шешу үшін Шотландияда дүниеге келген.
Математикалық логика саласында зерттеу жасап жүрген Франция мен Англиядағы екі үлкен топтағылардың бірі, тілдерді анықтайтын программаны, ал екінщісі – математикалық сөйлемдерді анықтайтын программаны ойлап табуды көздеулерінің нәтижесінде, екеуі біріге келе осы тілдің құрылуына себепкер болған.
Ұсынылып отырған жұмыста – логикалық программалаудың алгоритмінің негіздеуін алу үшін, осы тілге байланысты алғашқы негізгі мәліметтерден бастап, рет- ретімен жүйелі түрде мақсатқа жол салынған. Педикаттар логикасының көмегімен унификациялау және ең жалпы ортақ унификаторды табу алгоритмін табуды дәлелдеп шығарып алдық. Осы негізде оның қорытындысын таптық. Яғни, егер берілген өрнектер белгілі бір

1. Анатолий Адаменко, Андрей Кучуков “Логическое программирование и Visual prolog”. Санкт-Петербург “БХВ-Петербург”.2003. – 116-118 беттер.
2. Досанбай П.Т. “Математикалық логика және алгоритмдер теориясы”. 65-67 беттер, 86-87 беттер.
3. Ершов Ю.Л., Палютин Е.А. Математикалық логика.-Москва: Наука, 1980.
4. Адаменко А.Н. От логики к программированию и программирование на основе логики.// Компьютерные этюды Петербурга, №2,1994- с.53-59.
5. Набебин А.А. Логика и Пролог в дискретной математике.- М. Изд. МЭИ, 1996.

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 26 бет
Таңдаулыға:

Реферат
Бітіру жұмысы 23 беттен, теориялық және практикалық жұмыстар
көрcетілген кіріспеден, негізгі екі бөлімнен, қорытындыдан, қолданылған
әдебиеттер тізімінен тұрады.
Бітіру жұмысының негізгі мақсаты: логикалық программалаудың ең
негізгі ерекшеліктерінің бірі – программалау есебін шешуде, есепті ң
алгоритмі жазылмайды, Осы жазылмаған алгоритмді мақсат ете отырып,
оның негіздеуін, предикаттар логикасының тіліне сүйеніп үлкен екі жақтан,
яғни унификациялау және қорыту(жалпыланған Модус Поненс ережесі)
арқылы дәлелдеулері қарастырылады. Оларға қатысты мысалдар беріліп,
осы ұғымдардан туған жаңа теоремалар дәлелденіп, көрсетілген.
Пайдаланылған сөздер (терминдер): терм, атомарлық формула, өрнек,
унификатор, іздеу ағашы, мақсаттар тізбегі (goal).

Мазмұны

Алғысөз

4 бет

Логикалық программалаудың тілі

5 бет

Логикалық өрнектер тілі ерекшеліктері

6 бет

Унификациялау

8 бет

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

10 бет

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

12 бет
17 бет

Мақсатттарды жүзеге асыру

18 бет

Қорытынды

21 бет

Қолданылған әдебиеттер тізімі
бет

Алғы сөз
Логикалық программалау “пролог” табиғи тілдегі сөйлемдердің
граматикалық мәселелерін талқылау үшін және мәтін есептерді шешу үшін
Шотландияда дүниеге келген.
Математикалық логика саласында зерттеу жасап жүрген Франция мен
Англиядағы екі үлкен топтағылардың бірі, тілдерді анықтайтын программаны,
ал екінщісі – математикалық сөйлемдерді анықтайтын программаны ойлап
табуды көздеулерінің нәтижесінде, екеуі біріге келе осы тілдің құрылуына
себепкер болған.
Ұсынылып отырған жұмыста – логикалық программалаудың
алгоритмінің негіздеуін алу үшін, осы тілге байланысты алғашқы негізгі
мәліметтерден бастап, рет- ретімен жүйелі түрде мақсатқа жол салынған.
Педикаттар логикасының көмегімен унификациялау және ең жалпы орта қ
унификаторды табу алгоритмін табуды дәлелдеп шығарып алды қ. Осы негізде
оның қорытындысын таптық. Яғни, егер берілген өрнектер белгілі бір � деген
ауыстыру арқылы теңелсе, онда оның ең жалпы ортақ унификаторы және ең
жалпы ортақ мысалы бар екнін дәлелдедік, егер жоқ болса, онда оларды
унификацияланбайтынын дәлелдедік.
Екінші негізгі бөлімде – жалпыланған Модус Поненс арқылы
алгоритмнің негіздеуін көрсеттік. Бізде мақсаттар тізімі болса, онда оны
жүзеге асырудың екі жолын қарастырдық. Яғни, қарапайым формулалар
тізбегінен және іздеу ағашынан тұратын алгоритмдер көрсетілді.

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

1)
2)
3)
4)

Альфавит:
сигнатура
логикалық байланыстар(кванторлар)
айнымалылар
техникалық белгілер

Мұндағы

предикаттар,

функцияналдар,
тұрақтылар.
Предикаттық,
функционалдық және тұрақтылар символдарының жиынын сигнатура деп, σ
арқылы белгілеймыз.
құрамындағы айнымалының әрбір мәніне сәйкес жаңа пікір білдіретін
өрнегін бір орынды предикат деп, Ал
орынды предикат деп,
құрамындағы х1, х2, ..., хn айнымалыларына нақты мәндер бергенде, пікірге
айналатын P(х1,х2,...,хn) өрнегін түсінеміз.
Логикалық программалаудағы өрнектер
Өрнек- терм немесе атомарлық формула.
Терм: не тұрақты не айнымалы не
орынды функционалдық
символ болса, онда келесі түрдегі
(
) функционалдық әрпі бар мән
болады. мұндағы
термдер. Әрбір терм осы ережелерді ақырлы рет
қолдану арқылы кұрылады.
Мысалы, v айнымалы символы мен f1 – 1 орынды функционалдық
символынан ғана тұратын барлық термдер тізімі мынандай:
v, f1(v), f1(f1(v)),..., f1(...f1(v)...),...
Термдердің қасиеттерін термнің күрделілігі бойынша индукцияны
пайдаланып дәлелдеу.
Жоғарыдағы
құрылған.

анықтама термдердің күрделілігі бойынша индукцияға
Сондықтан,
термдердің
қандай
да
бір

қасиетін

индукция арқылы дәлелдеу келесі тәртіппен жүреді.

Тұрақтылар үшін P қасиетінің орындалатынын тексереміз.

Айнымалылар үшін P қасиетінің орындалатынын тексереміз.

Алдыңғы тексерістер оң нәтиже берсін. Онда егер fm – кез келген m
орынды функционалдық символ, Егер P қасиеті осы үш шарттың барлығын
қанағаттандырса, онда P қасиеті берілген тілдің барлық термдері үшін
орындалады.
Ал t1,...,tm – P қасиеті орындалатынын термдер болса, онда fm(t1,...,tm)
термі үшін P қасиетінің орындалатынын тексереміз.
Күрделілігі 0 болатын терімдер:
,...яғни кез-келген тұрақтылар,
яғни кез-келген айнымалылар.
Күрделілігі
болатын терім:
(
) . Мұндағы
күрделілігі 0 болатын терм.
Атомарлық формула(қарапайым):
предикат,
терм,
орынды предикаттық символ болса, онда
болған кездегіні
немесе
(
түріндегі сөзді атомарлық формула дейміз. Мұндағы
терімдер.
Мысалы. Eгер Р2 екі орынды предикаттық символ, ал f1 бір орынды
функционалдық символ болса, онда
Р2(v,v), Р2(v, f1(v)), Р2(f1(v), f1(f1(v))), v = v, f1(v) = v сөздерінің әрқайсысы
атомaрлық
формуланың
мысалдары
болады.
,

– атомарлық формула болады.
Формулалар:
1) Қарапайым формулалар:
(
2)
мұндағы
программалау тілінде блай жазылады
.

;

термдер.
,В қарапайым формулалар ,бұл
мұндағы
предикат,

Логикалық программалау тілі ерекшеліктері
Формуланың түрлері:

(*)

коньюнкция(&)
дизьюнкция(
)
терістеу(not)
болса, онда шарты жоқ деген сөз. Формула n=0 деп
жазылады.
ксиомалар түрі әрқашан (*) формулаға ұқсас.
Теория: кез келген пікірлер логикасының формулаларын логикалық
программалау тілінің формулаларына
ауыстыру арқылы пайда болған
формуланы логикалық программалау тілі программасының аксиомалары деп

атаймыз.
,... ,
осындай бірнеше
формулалар тізбегі теория деп аталады.теория логикалық программалау
тілінің программасында,
аксиомалар тізбегінен тұрады. Логикалық
программалауда теорияны анықтау үшін, алдымен тілді анықтау керек.
Программалау тілімен, берілген теорияны пайдалана отырып есеп шы ғару
барысында, программа құрамына есептің логикалық программалау тіліндегі
берілісін жазамыз. Мақсаттар тізімінде (goal) сұрақтар қоямыз. Программа
алгоритмі жазылмайды. Алгоритм логикалық программалаудың негізгі деталы
ретінде программаның өз ішіне енгізілген. Біз осы алгоритмді барлы қ
зерттеулердің басты мақсаты етіп, ешқандай программалау кітаптарында
дәлелденбеген программаның негіздеуін, математикалық жолмен үлкен екі
тақрыпқа бөліп дәлелдеу жүргіземіз. Олар: унификациялау ережесі және
жалпыланған Модус поненс ережесі. Негіздеуді осы ережелерге мысалдар
келтре отрып дәлелдейміз.
Мысал ретінде
деген атпен жазылған мына программаны
қарастрайық:

.
.
).
,

).
,

).

,).
,).
).
): unaidi (), Z

.

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

Логикалық программалау тілінде айнымалыны терммен ауыстыру
o Белгілі бір
формуладағы v айнымалысын қандай да бір t термімен
ауыстыру үшін t термі формуласында v айнымалысы үшін бос болуы керек.
Егер бос болмаса, алдымен формуладағы байланған айнымалының атын
өзгертіп алып, аталған айнымалыны терммен ауыстырамыз. Мысалы
термін v айнымалысының орнына қою үшін

уS(v,у,z) формуласында у ді u мен ауыстырсақ, бастапқы формулаға парапар
uS(v,u,z) формуласын аламыз. Ал бұл формулада t термі v айнымалысы үшін
бос. Яғни, uS(t,u,z) бастапқы uS(v,u,z) формуласынан ауыстыру арқылы
алынған болып шығады.
o термді тек бос айнымалының орнына қою мен қатар, формулада
кездесетін айнымалыларының, квантордың әсер аймағында не болмаса
формула құрамына терімді енгізгеннен кейін өзінің қайталанып түспеуін
тексеру керек. Мысалы
формуласындағы
айнымалысының орнына
термін қойсақ,
формуласымен
мағынасы
айнымалысының орнына

формуласын аламыз. Ал
бірдей
формуласындағы
термін қойсақ, мағынасы өзгерген

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

өрнектер дейміз. Мұндағы

дегеніміз

өрнектеріндегі

айнымалысының орнына
термін сол сияқты
айнымалысының
орнына
термін қойғанда шыққан өрнектер
ауыстыруын (түрлендіруін)

мен
ның унификаторы деп атаймыз. Яғни унификатор дегеніміз—
{ }өрнектер жиынындағы өрнектерді бірдей қылатын түрлендіру.
Анықтама
Өрнектер
жиыны
{ }
унификацияланаған
деп
аталады,егер
теңдіктерін
қанағаттандыратын
унификаторы табылса.

өрнектер жиыны берілсін.
Онда
унификаторын қолданғаннан кейін, нәтижеде екі өрнек
ортақ бір түрге Унификацияланған болады. Яғни
түрінде. Бұл
түрлендіруді алу үшін
түрлендіруін қолдану жеткілікті. Біз сонда
ортақ мысал табамыз, осыдан

, мұнда

болады.
бұл өрнектер жиыны
унификацияланбайды, себебі ешқандай ауыстру оның ортақ формуласын
немесе терістеуіне әкелмейді.
өрнектер жиыны үшін, ең жалпы унификатор болып
ауыструы
жарайды, егер кез-келген унификаторы үшін
орындалса.
Анықтама
Өрнектер жиынының сәйкессіздік жиыны деп—төмендегі өрнектер
жиынында көрсетілген сол жақ бірінші жағдайдағы сәйкессіз ерекшеленген
терімдер
жиынтығын
атаймыз.
өрнектер жиыны үшін
сәйкессіздік жиыны
жиыны болып табылады. Себебі сол жақтағы
бірінші өрнектегі
терімі сәйкесінше екінші өректің сол жақ орнындағы
айнымалысына сәйкес емес.
Мысалы:

ден жалпыланған түрі.
бұл

унификатордың

жалпы

түрі.

осындай негізде кез-келген ортақ мысалды жасай
аламыз.
(

)Ө* = , (
)Ө* =
мен
өрнектер үшін
ең жалпы унификатор. Себебі кез—келген
унификатыр алсақ, онда мен
ның ортақ мысалы
(
)Ө*осы
бойынша
=
ең жалпы ортақ мысал болады.

Унификация алгоритмі
Анықтама
унификацияланған өрнектер жиынының ең жалпы унификаторын
табатын немесе өрнектер жиыны унификацияланбаса , оның жоқтығы жөнінде
хабар беретін алгоритымды унификация алгоритымы деп атаймыз.
Бізге екі өрнек берілсін, осы екеуі үшін унификация алгоритмін
қарастрайық. Әр өрнекке алгоритмнің әрбір бөлігінде түрлендіру
қолданылады. Белгілі бір
алгоритмінде:
өрнектер жиыны,
сәйкессіздіктер жиыны,
орындалатын ауыстру.
Унификация алгоритмі төмендегілерден тұрады:
бастапқы өрнектер жиыны,
(ештеңе өзгертпейтін
түрлендіру)
алгоритмінде:
a) егер , онда алгоритм соңы
қортынды түрлендіруі ең жалпы
унификатор.
b) егер
құрамында айнымалы жоқ болса, онда алгоритм соңында
өрнектер жиыны унификацияланбайды.
c) егер сәйкессіздіктер жиынында айнымалы
және терм
бар болса
және
құрамында болса, онда алгоритм соңында өрнектер жиыны
к,
унифликацияланбайды.
Болмаған жағдайда
қадамына көшеміз.
алгоритмінде:
,
=
құрамына кіретін әрбір өрнек үшін
к,
түрлендіру жасаймыз.
= θ (немесе
= S0
)
Ескерту
Егер өрнектер саны екіден көп болса, онда бірінші өрнек тізбекшесін
екіншісінен унификациялайды. Одан кейін нәтижесі үшіншісімен т.с.с барлы қ
өрнектер жиыны унификацияланғанға дейін немесе унификациялау мүмкін
болмағанға дейін жалғасады.
Тұжырымдама

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

яғни
термнің құрамына кірмейді.

ең

алгоритм соңында.

жалпы

унификаторы

№2 есеп:

алгоритм соңында жиын унификацияланбайды.
Унификация резолюция әдісінің негізгі бөлігі бойныша табылады. Ал
унификация алгоритмі – Пролог логикалық программалау тілінің негізгі
механизмі.
A мен B ны күрделілігі бойынша индукция арқылы немесе терімні ң
қасиетінің индукция алгоритымін пайдалану арқылы дәлелдеу жүргіземіз.
болған кезде(болмаса , end яғыный ең үлкен ортақ унификатр
жоқ).
болған кезде(болмаса , end).
т1 мен s1 үшін ең жалпы унификатрды іздейміз, егер орындалса онда t 2 мен
s2 үшін осылай рет -ретімен жалғастырамыз.

және
болған кезде.

термдері

үшін

Мысал:
тілдегі өрнек болсын. Ең үлкен унификатрды және ең жалпы ортақ
мысалды тап.

3)

))
Есептің

шешімі

ең

бойынша,
,

ең

үлкен

жалпы

унификатр

ортақ

мысал

Ең жалпы унификаторды табу алгоритмі
екі өрнек берілсін. Программада бұл өрнектердің алгоритмын
компилятордың алгоритмдері төменде көрсетілген жағдайларда қарастырады.
горитмге кіруі:
Мұнда берілген өрнектің алғашқы сұлбасы өз қалпында сақталып, ешқандай
ауыстырулар орындылмайды. Алгоритым берілген өрнектердің күрделігі
бойынша унификациялауды бастайды. Алгоритмның унификациялауды іздеу
барысы:
қадамда:
астапқы өрнекке алғашқы ауыструды қолданғанда өрнектер денесінде
сәйкессіздіктер жоқ болса, олар бірден унификацияланып ең жалпы
унификатор, алғашқы ауыструдың өзі болады . Егер өрнектер құрамында
сәйкессіздік болса, онда келесі қадамға өтеді.
қадамда:
,...,
;
,...,
,...,
өрнектер денесінің әрбір
элементінің көрінісі. Мұндағы i қолданылған унификаторлардың реті, ал
сандар өрнектер денсін құрайтын элементтердің реті.
егер мұнда
жоқ болса(сәйкес емес элемент жо қ болса) онда
ең жалпы
ортақ унификатор. Мұнда
өрнектің құрамындағы екі ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.