Категория: Руководства
Министерство образования и науки Российской Федерации
ФГБОУ ВПО Сибирский государственный технологический университет
С.П. Якимов, Е.М. Товбис. Логическое программирование. TurboPrologV.2.0: учебное пособие для студентов направлений 230100 «Информатика и вычислительная техника», 231000 «Программная инженерия», очной, очной сокращенной, заочной, заочной сокращенной форм обучения / С.П. Якимов, Е.М. Товбис - Красноярск: СибГТУ, 2013.- 44 с.
Рекомендуется студентам для получения базовых основ в области логического программирования и программирования на языке TurboProlog.
Утвержден на заседании кафедры информационных технологий
03.04.06 г. протокол № 9
Рекомендован к изданию редакционно-издательским советом
© ФГБОУ ВПО «Сибирский государственный технологический университет»
© Якимов С.П. Товбис Е.М.
Содержание1 Введение в логическое программирование 5
2 Основные конструкции логического программирования 9
3 Структура программы на языке Пролог 13
4 Вычислительная модель логических программ 15
5 Управление выполнением программы на языке Пролог 19
5.1 BAF- метод (Backtrack After Fail– возврат после отказа) 20
5.2 CAF– метод (Cut And Fail– отсечение и отказ) 20
5.3. UDR– метод (User-Defined Repeat– повторения, управляемые пользователем) 21
6 Рекурсивные структуры данных 22
7 Программирование баз данных 25
7.1 Управление встроенной базой данных 25
7.2 Управление внешней базой данных 25
8 Лабораторный практикум 30
Все лабораторные работы выполняются и предоставляются на проверку на компьютере в среде Пролог. Для защиты лабораторных работ необходимо ответить на контрольные вопросы, указанные в конце лабораторной работы. 30
8.1 Основные конструкции логического программирования.
Факты и правила (2 часа) 30
Контрольные вопросы 31
8.2 Вычислительная модель логических программ. Логические схемы (4 часа) 31
Контрольные вопросы 35
8.3 Управление выполнением программы на языке Пролог. Оконный интерфейс (4 часа) 35
Контрольные вопросы 36
8.4 Рекурсивные структуры данных. Списки (4 часа) 36
Контрольные вопросы 38
8.5 Программирование баз данных. Базы данных (4 часа) 38
Контрольные вопросы 39
Библиографический список 41
Приложение А Ключевые слова 42
Дисциплина «Логическое программирование» относится к вариативной части профессионального цикла и изучается в 4 семестре. Для освоения дисциплины требуются знания в области математической логики, в особенности, в части логики предикатов первого порядка. Желательно знакомство с курсом структурного программирования. В свою очередь, материал дисциплины используется в дальнейшем при изучении курсов «Интеллектуальные системы», «Теория формальных языков и компиляторов», «Параллельное программирование». Цель лабораторного практикума – дать общее представление о логическом программировании на примере языка Турбо Пролог.
Успешное освоение лабораторного практикума способствует формированию у обучающихся направления 230100 следующих профессиональных компетенций:
ПК-5 – разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технологии программирования;
ПК-6 – обосновывать принимаемые проектные решения, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности.
Успешное освоение лабораторного практикума способствует формированию у обучающихся направления 231000 следующих профессиональных компетенций:
ПК-12 – навыки моделирования, анализа и использования формальных методов конструирования программного обеспечения;
ПК-16 – навыки использования различных технологий программного обеспечения.
Пролог принципиально отличается от традиционных языков программирования в первую очередь тем, что в нем требуется описывать логическую модель предметной области в терминах объектов и отношений между ними без подробного описания алгоритма задачи. Программа на языке Пролог состоит из множества утверждений, каждое из которых является либо фактом (аксиомой) из заданной предметной области или правилом (теоремой), указывающим, как решение связано с заданными фактами или правилами. В настоящее время наиболее известны реализации Arity -Prolog ,MProlog ,TurboProlog . Все эти версии разрабатывались независимо и поэтому сильно отличаются друг от друга. Говорить о каком-либо стандарте языка затруднительно: можно изучать теоретические основы языка и какие-то его конкретные реализации.
В настоящем учебном пособии в качестве инструмента для изучения основ логического программирования используется разработка фирмы BorlandInternational (США, 1985)– Турбо Пролог, версия 2.0.
1 Введение в логическое программированиеЛ
огическая программа – это множество аксиом (утверждений, не требующих доказательств) и правил, задающих отношения между объектами. Вычислением логической программы является вывод следствий из программы. Основные конструкции логического программирования–термы иутверждения. Имеется три основных вида утверждений:факты ,правила ивопросы .
Для обозначения факта используется запись вида «Q. »–предикат. вслед за которым ставится точка. Предикаты бывают 0-местные (без аргументов) илиn - местные (сn аргументами). Предикат без аргументов обозначается одним именем. Предикат с аргументами обозначается именем, вслед за которым в скобках через запятые записываются все его аргументы. Аргумент предиката– синтаксическая конструкция, называемаятермом. Определение предиката в обозначениях Бэкуса-Наура:
Т
ерм– это либоконстанта. либопеременная. либоструктура .
Структура– более сложное, чем константа и переменная, образование, характеризуется именем (функтором) и компонентами– составными частями структуры. Каждый компонент структуры в свою очередь является термом.
Например, библейское утверждение «Авраам родил Исаака» (иначе: объект Авраам связан с объектомИсаак отношениемfather 1 ) в терминах языка Пролог может быть записано как факт с использованием двуместного предиката 2 :
По аналогии: факты, представленные в Пролог-программе одноместными предикатами:
можно интерпретировать как утверждения: «Адам является мужчиной» (объект Адам обладает свойствомman ), «Ева является женщиной» (объектЕва обладает свойствомwoman ), соответственно. Эти же утверждения могут быть реализованы несколько иначе:
При этом одноместный предикат homo_sapiens подчеркивает, что объектыАдам иЕва . несмотря на очевидные различия, все-таки относятся к одному и томе же биологическому виду. В приведенном примере предикаты man иwoman выступают в качестве аргумента для предикатаhomo_sapiens .
Конечное множество фактов образуют простейший вид Пролог-программы. Такой подход лежит в основе программирования баз данных и, в принципе, уже сейчас, используя только один вид утверждений– факты, можно написать небольшую, но достаточно эффективную программу на Прологе, описывающую фрагмент генеалогического дерева одного весьма известного российского семейства (см. рис. 1). Кроме уже рассмотренных предикатовman иwoman в программу для описания родственных отношений введены предикатыchild1 иpair2 .
объявление указателей индексации базы данных.
В секции DATABASE объявляются факты, которые предполагается менять (добавлять, удалять, редактировать) в процессе работы программы. Все остальные факты и правила объявляются в секцииPREDICATES . Все факты и правила описываются в разделеCLAUSES . РазделGOAL обязателен только в том случае, если предполагается создание загрузочного модуля.
Назовите разделы пролог-программы.
Для чего предназначен раздел DOMAINS?
Для чего предназначен раздел PREDICATES?
Для чего предназначен раздел CLAUSES?
Для чего предназначен раздел GOAL?
4 Вычислительная модель логических программЦентральное место в вычислительной модели логических программ составляет алгоритм унификации. Унификация является основой автоматической дедукции и логического вывода в задачах искусственного интеллекта. Введем необходимую для математического описания алгоритма терминологию.
Н апример, термыpair(“Петр I”, X) иpair(Y, ”Екатерина I”)унифицируемы :унификатором для них будет подстановка <X= ”Екатерина I”, Y= “Петр I” >, дающая в результате термpair(“Петр I”, ”Екатерина I”) (см. рис. 2).
Рис. 2. Наиболее общий унификатор
Алгоритм унификации находит наиболее общий унификатор двух термов, если такой существует. Если термы не унифицируемы, алгоритм сообщает об отказе .
При согласовании целевого утверждения с базой данных делается попытка унификации этого утверждения с каким-либо фактом или правилом путем их сопоставления. В роли образцов при этом выступают термы, являющиеся аргументами сравниваемых предикатов, имена которых, естественно, должны совпадать. При сравнении образцов приняты следующие соглашения:
?1. Если оба сравниваемых образца– константы, для успешного сопоставления они должны совпадать:
?2. Если один из сравниваемых образцов не конкретизированная переменная, т.е. переменная, которой не приписано никакое значение, то второй образец может быть любым термом. При этом если этот терм– константа или константная структура, то переменная, выступающая в роли первого образца, конкретизируется: ей приписывается значение, которое является вторым образцом. Если второй образец– другая не конкретизированная переменная, то между первой и второй переменными устанавливается прямая связь: в случае дальнейшего означивания одной из них вторая автоматически получает то же значение. Если же второй образец является структурой, содержащей другие переменные, между ними и исходной переменной устанавливается более сложная «функциональная» связь. Так, сравнение образцовhomo_sapiens(man(Y)) иhomo_sapiens(X) приводит к сопоставлению переменнойX и структурыman(Y) . Дальнейшая конкретизация переменнойY . например, в результате подстановкиY= “Адам” приведет к конкретизацииX=man(“Адам”)
Основной режим изучения Пролога - интерпретация программ из файла, или непосредственно с консоли.
Быстрый стартУдобно рассматривать Пролог - программу, как базу данных, часть информации в которой хранится в "неявном виде", т.е. может быть извлечена с помощью правил. Второй вариант - представить такую программу как выполнение некоторого перебора вариантов (факты - область исходного перебора, правила - способ перехода к области результатов).
Первая моя программа будет содержать два факта: Мэри и Джон любят яблоки. Запускаем gprolog.exe (как Вам удобнее - через Иконку на рабочем столе или напрямую - из каталога). Видим "шапку" и приглашени к вводу:
Текст программы теперь в памяти Интерпретатора - вы можете его вывести с помощью директивы listing. Если Вы хотите увидеть только часть программы (предикатов), то в скобках можно уточнить listing(like). - не забывайте точку в конце директивы.
Теперь Вы можете задавать Вашей программе вопросы (Кто любит яблоки): После первого найденного решения, программа останавливается и выводит. теперь Вы можете набрать ; - и т. д. Просто ввод - прервать поиск решений.
В режиме редактирования строки Вы можете пользоваться управляющими клавишами и спец. комбинациями Ctrl + P - предыдущая строка в истории, Ctrl + N - следующая, весь список кодов Вы можете получить комбинацией клавиш Esc + ? (Esc - удерживайте)
Вы можете сохранить набранную Вами Пролог-программу в файл. С помощью следующей, довольно сложной директивы: Самое время напомнить о возможности использования Cut & Paste в окне интерпретатора Пролога (пункт меню Edit ).
Возможности редактирования программы, хранящейся в потоке [user] ограничены - вы можете еще раз открыть поток, и добавить правила (конструкции вида: children(X,Y) :- parent(Y,X). ). Но попытка добавить факт, приведет к удалению фактов предыдущей программы (с такими же именами), при этом правила и факты с другими именами сохранятся!Блог изучающего Пролог
хорошо, как скажете.
Вот задача. В Н-ской части служили 5 офицеров: генерал, полковник, майор, капитан и лейтенант. Один из них сапер, другой -- пехотинец, третий -- танкист, четвертый -- связист, а пятый -- ратиллерист. У каждого из них есть сестра. И каждый из них женат на сестре своего однополчанина.
Вот что известно еще об этих офицерах. По меньшей мере, один из родственников связиста старше его по званию.
Капитан никогда не служил в Горьком.
Оба родственника пехотинца и оба родственника танкиста служили раньше в Ленинграде. Ни один родственник генерала в Ленинграде не был.
Танкист служил в Киеве вместе с обоими своими родственниками, а лейтенант там не служил.
Полковник служил в Свердловске. Там служил только один из его родственников.
Генерал служил с обоими своими родственниками в Горьком, а в Свердловске он не бывал.
Артиллерист не служил ни в Горьком, ни в Киеве.
Определите, кто из офицеров какое звание имеет?
Вот её решение с десятью вариантами решения :
?-solve(Ans),show(Ans),nl,nl,nl,fail.
show([]).
show([m(Z,P,W)|Tail]):-write(Z),write(" yavlyaetsya "),write(P),
write(" i zenat na sestre "),write(W),nl,show(Tail).
starshe("general",_).
starshe("polkovnik",X):-X=\="general".
starshe("maior",X):-X=\="general",X=\="polkovnik".
starshe("kapitan","leitenant").
brother("generala","general").
brother("polkovnika","polkovnik").
brother("maiora","maior").
brother("kapitana","kapitan").
brother("leitenanta","leitenant").
u1(L):-member(m(Svyazist,"svyazistom",_),L),rodstvennik(S vyazist,L,RSvyazista),
starshe(RSvyazista,Svyazist).
u3(L):-member(m(Pehotinec,"pehotincem",_),L),rodstvennik( Pehotinec,L,RPehotinca1),
rodstvennik(Pehotinec,L,RPehotinca2),RPehotinca1=\ =RPehotinca2,
not(rodstvennik(RPehotinca1,L,"general")),not(rods tvennik(RPehotinca2,L,"general")).
u4(L,RTankista1,RTankista2):-member(m(Tankist,"tankistom",_),L),rodstvennik(Tan kist,L,RTankista1),
rodstvennik(Tankist,L,RTankista2),RTankista1=\=RTa nkista2,
Tankist=\="leitenant",RTankista1=\="leitenant",RTa nkista2=\="leitenant",
not(rodstvennik(RTankista1,L,"general")),not(rodst vennik(RTankista2,L,"general")).
u5(L,RTankista1,RTankista2):-member(m(Artillerist,"artilleristom",_),L),Artille rist=\="general",
not(rodstvennik(Artillerist,L,"general")),Artiller ist=\=RTankista1,Artillerist=\=RTankista2.
solve(L):-
L=[m("general",PGenerala,WGenerala),m("polkovnik",PPo lkovnika,WPolkovnika),
m("maior",PMaiora,WMaiora),m("kapitan",PKapitana,W Kapitana),
m("leitenant",PLeitenanta,WLeitenanta)],
P=[PGenerala,PPolkovnika,PMaiora,PKapitana,PLeitenant a],
permutation(["saperom","pehotincem","tankistom","svyazistom","a rtilleristom"],P),
W=[WGenerala,WPolkovnika,WMaiora,WKapitana,WLeitenant a],
permutation(["generala","polkovnika","maiora","kapitana","leite nanta"],W),check(L),
u1(L),u2(L),u3(L),u4(L,RTankista1,RTankista2),u5(L ,RTankista1,RTankista2).
Вторая задача. решена с ошибкой. вот задача :
У Светы в отличие от Сергея на щеках есть ямочки. Вероятность того, что у Даши гомозиготная пара признаков - 65%. Какова вероятность, что у их дочери тоже будут ямочки на щеках?
sum([],0).
sum([H|Tail],S):-sum(Tail,S1),S is S1+H.
p("Sveta",[a,a],0.65).
p("Sveta",[a,b],0.35).
p("Sveta",[b,b],0).
p("Sergei",[a,a],0).
p("Sergei",[a,b],0).
p("Sergei",[b,b],1).
p("Dochka",[X,Y],P):-findall(A,p("Sveta",[X,_],A),L1),
findall(B,p("Sveta",[_,X],B),L2),
findall(C,p("Sergei",[Y,_],C),L3),
findall(D,p("Sergei",[_,Y],D),L4),
sum(L1,S1),sum(L2,S2),sum(L3,S3),sum(L4,S4),
PX is (S1/2)+(S2/2), PY is (S3/2)+(S4/2), P is PX*PY.
p(Ans):-p("Dochka",[a,a],P1),p("Dochka",[a,b],P2),p("Dochka",[b,a],P3),Ans is P1+P2+P3.
Вылетает ошибка - Error! 10: No sense at line 19, after clause 9.
Look in the help for this error.
1 error, 0 warnings.
Помогите её убрать.
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Вот так на Visual 5.2 работает:
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
спасибо за помощь но мне нужно именно в Strawberry prolog :( сам не шарю если можно как-то на этот пролог перевести её то помогите.
Логическое программирование — это направление современного программирования, возникшее первоначально в рамках работ по искусственному интеллекту и получившее свое развитие во второй половине восьмидесятых годов, благодаря японскому проекту ЭВМ пятого поколения. Наиболее полное выражение идеи логического программирования нашли в языке Prolog (PROgramming in LOGic — программирование в терминах логики). Первоначальный вариант языка Prolog был разработан под руководством Алэна Кольмероэ (Alain Colmerauer) в Марсельском университете в 1972 году. В настоящее время существуют разнообразные версии для DOS (PDC Prolog, Arity Prolog и др.), Windows (Visual Prolog, Strawberry Prolog, Trinc Prolog и др.), Linux (Arity Prolog, Visual Prolog и др.).
Теоретической основой Prolog является раздел символьной логики, называемый исчислением предикатов. Prolog присущ ряд свойств, которыми не обладают традиционные языки программирования, что делает его мощным средством в области логического программирования. К таким свойствам относятся механизм вывода с поиском и возвратом, встроенный механизм сопоставления с образцом и простая, но выразительная структура данных с возможностью ее изменения. В Prolog отсутствуют указатели, операторы присваивания и GOTO. Естественным методом программирования является рекурсия.
Программа на Prolog есть совокупность утверждений. Утверждения состоят из целей. В конце утверждения ставится точка «.». Иногда утверждение называется предложением.
Основная операция Prolog — доказательство целей, входящих в утверждение.
Существуют два типа утверждений:
Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.
Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.
Выберем для реализации систему Visual Prolog (www.visual-prolog.com).
Решим задачу о родственных отношениях, так как Prolog хорошо приспособлен для обработки нечисловой информации.
Тот факт, что Том является родителем Боба, можно записать на Prolog так:
Здесь мы выбрали родитель в качестве имени отношения, том и боб — в качестве аргументов этого отношения. Записываем имена, как том. начиная со строчной буквы. Все дерево родственных отношений (семантическая сеть)
описывается следующей программой на языке Visual Prolog:
Для программирования необходимо
1. Запустить систему Visual Prolog.
Рис. 12.1. Окно Visual Prolog 5.0
2. Ввести программу File ® New .
3. Протестировать цель Project ® Test Goal .
На заданный вопрос: «Является Боб родителем Пат?» — система ответит yes (да), найдя такой факт в программе.
Другой вопрос: «Кто является родителем Лиз?»
Вопрос «Кто дети Боба?» можно передать в такой форме:
Программе можно задавать и более общие вопросы: «Кто чей родитель?» Сформулируем его таким образом:
Найти X и Y такие, что X - родитель Y.
На Prolog это записывается так:
Система будет по очереди находить все пары вида «родитель-ребенок».
Определить правила: женщина, мужчина, родитель, родители, дедушка, бабушка.
Определим правило женщина, исходя из только описываемого мира.
Аналогично правило мужчина.
Цели можно поставить следующие.
Решим задачу о родственных отношениях семьи Романовых, и найдем детей Алексея Михайловича.
Найдем всех цариц с помощью составного вопроса.
Добавим несколько правил: брат (brother), сколько_правил (how_reign).
Правило определения брата можно прочитать так:
Для любых X и Y, X является братом Y, если
В процессе достижения цели Prolog осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Иногда требуется его ограничить или исключить вовсе.
Для этого в Prolog существует ограничивающая перебор цель «отсечение» (!), которая безусловна верна.
Найдем только одного сына Алексея Михайловича
Опишем предикат, определяющий из двух целых чисел максимальное.
Эти правила являются взаимоисключающими. Если выполняется первое, второе обязательно потерпит неудачу. Можно видоизменить при помощи отсечения правила.
Prolog содержит стандартный предикат, выполнение которого заканчивается всегда неудачей — fail. Предикат fail инициирует процесс бэктрекинга (backtracking), то есть поиска новых решений, или передоказательства целей. Покажем на примере.
Для реализации отрицания используется предикат not. Особенность его использования состоит в том, что все переданные переменные должные быть связанными, то есть конкретизированными. Например, ответ на вопрос: «Леонард не отец Джейсону?» будет найден.
не будет восприниматься системой. Можно переформулировать цель: «Кто из известных системе отцов не является отцом Джейсона?».
Таким образом, нельзя получить знание из незнания, и предикат not используется только для проверки целей.
В приведенных программах на Visual Prolog можно выделить и дополнить:
