ПРОЛОГ(ПРОграммирование в ЛОГике) — язык логического программирования, предназначен для решения задач из области искусственного интеллекта (создание ЭС, программы-переводчики, обработка естественного языка). Он используется для обработки естественного языка и обладает мощными средствами, позволяющими извлекать информацию из баз данных, причем методы поиска, используемые в нем, принципиально отличаются от традиционных.
Основные конструкции ПРОЛОГа заимствованы из логики. ПРОЛОГ относится не к процедурным, а к декларативным языкам программирования. Он ориентирован не на разработку решений, а на систематизированное и формализованное описание задачи с тем, чтобы решение следовало из составленного описания.
Суть логического подхода заключается в том, что машине в качестве программы предлагается не алгоритм, а формальное описание предметной области и решаемой проблемы в виде аксиоматической системы. Тогда поиск решения с помощью вывода в этой системе можно поручить самому компьютеру. Главная же задача программиста — удачно представить предметную область системой логических формул и таким множеством отношений на ней, которые наиболее полно описывают задачу.
Структура программы на ПРОЛОГе
Фундаментальные свойства ПРОЛОГа:
1) механизм вывода с поиском и возвратом
2) встроенный механизм сопоставления с образцом
3) простая и легко изменяемая структура данных
4) отсутствие указателей, операторов присваивания и перехода
5) естественность рекурсии
Этапы программирования на ПРОЛОГе:
1) объявление фактов об объектах и отношениях между ними;
2) определение правил взаимосвязи объектов и отношений между ними;
3) формулировка вопроса об объектах и отношениях между ними.
Теоретической основой ПРОЛОГа является раздел символьной логики, называемый исчислением предикатов.
Предикат – это имя свойства или отношения между объектами с последовательностью аргументов.
Например, факт black(cat) записан с использованием предиката black, имеющего один аргумент. Факт написал(шолохов, «ТИХИЙ ДОН») записан с использованием предиката написал, имеющего два аргумента.
Число аргументов предиката называется арностью предиката и обозначается black/1 (предикат black имеет один аргумент, его арность равна единице). Предикаты могут не иметь аргументов, арность таких предикатов равна 0.
Язык Пролог вырос из работ Алана Колмерауэра (A. Colmerauer) по обработке естественного языка и независимых работ Роберта Ковалького (R. Kowalski) по приложениям логики к программированию (1973 г.).
Наиболее известна в России система программирования Turbo Prolog — коммерческая реализация языка для IBM-совместимых ПК. В 1988 г. вышла значительно более мощная версия Turbo Prolog 2.0, включающая усовершенствованную интегрированную среду разработки программ, быстрый компилятор и средства низкоуровневого программирования. Фирма Borland распространяла эту версию до 1990 г., а затем компания PDC приобрела монопольное право на использование исходных текстов компилятора и дальнейшее продвижение системы программирования на рынок под названием PDC Prolog.
Три примера решения задачек на Прологе
В 1996 г. Prolog Development Center выпускает на рынок систему Visual Prolog 4.0. В среде Visual Prolog используется подход, получивший название «визуальное программирование», при котором внешний вид и поведение программ определяются с помощью специальных графических средств проектирования без традиционного программирования на алгоритмическом языке.
В Visual Prolog входят интерактивная среда визуальной разработки (VDE — Visual Develop Environment), которая включает текстовый и различные графические редакторы, инструментальные средства генерации кода, конструирующие управляющую логику (Experts), а также являющийся расширением языка интерфейс визуального программирования (VPI — Visual Programming Interface), Пролог-компилятор, набор различных подключаемых файлов и библиотек, редактор связей, файлы, содержащие примеры и помощь.
5.2. Предложения: факты и правила
Программа на ПРОЛОГе состоит из предложений, которые могут быть фактами, правилами или запросами.
Факт – это утверждение о том, что соблюдается некоторое конкретное соотношение между объектами. Факт используется для того, чтобы показать простую взаимосвязь между данными.
учится (ира, университет). % Ира учится в университете
родитель(иван, алексей). % Иван является родителем Алексея
язык_программирования (пролог). % Пролог – это язык программирования
Набор фактов составляет базу данных. В виде факта в программе записываются данные, которые принимаются за истину и не требуют доказательства.
Правила используются для того, чтобы установить отношения между объектами на основе имеющихся фактов.
Левая часть правила вывода называется головой правила, а правая часть — телом. Тело может состоять из нескольких условий, перечисленных через запятую или точку с запятой. Запятая означает операцию «логическое И», точка с запятой – операцию «логическое ИЛИ». В предложениях используются переменные для обобщенной формулировки правил вывода.
Переменные действуют только в одном предложении. Имя в разных предложениях указывает на разные объекты. Все предложения обязательно заканчиваются точкой.
мать (Х, У):- родитель (Х, У), женщина(Х).
студент (X):- учится (X, институт); учится (X, университет).
Правило отличается от факта тем, что факт — всегда истинен, а правило является истинным, если выполняются все утверждения, составляющие тело правила. Факты и правила образуют базу знаний.
Источник: studopedia.su
Язык ПРОЛОГ: основные конструкции
Аннотация: Общая характеристика языка Пролог: базы знаний и экспертные системы. Объекты и термы Пролога: объекты Пролога — имена, переменные и списки; основные и неосновные термы; атомы. Факты Пролога: синтаксис фактов; универсальные факты. Правила Пролога: проблема недостаточности фактов для описания базы знаний; синтаксис правила — заголовок и тело правила; процедура как объединение правил с одним заголовком; программа Пролога как совокупность фактов и правил. Запросы Пролога: синтаксис запроса; ответ на запрос без переменных; запрос с переменными и интерпретация переменных при выполнении программы; примеры программ с запросами для них.
Общая характеристика языка Пролог
Математическая логика дает нам ясный и точный язык для явного выражения знаний, гипотез и целей. Возможность машинного доказательства теорем , основанного на специальном выводе, названном принципом резолюций , впервые была получена Дж. Робинсон в 1965 году. Это привело к желанию построить язык программирования , который позволил бы реализовать одну из интеллектуальных сторон деятельности человека — проведение рассуждений в виде программ.
В начале 70-х годов прошлого века группой под руководством А. Колмероэ в Марселе на Фортране была написана программа для доказательства теорем , названная Прологом (от Programmation en Logique). Это привело в конце десятилетия к разработке языка Пролог и в дальнейшем развитию этого языка и в целом направления, которое получило название логического программирования.
Язык Пролог близок к модели Маркова: также основой является поиск подходящей подстановки — интерпретация переменных . Но подстановки ищутся в правилах языка (аналог рефал-предложений ), и целью является именно поиск подстановки .
Программа на Прологе состоит из правил , которые представляют собой продукции с предикатами (относительно объектов) в левой и правой части. Тем самым программа Пролога выражает некоторые знания о внешнем мире (задаче или группе задач), необходимые для решения задач. Правила, не содержащие посылки в продукции, называются фактами , а вся система правил программы образует базу знаний .
Вопрос задачи, называемый запросом , — это также некоторый предикат , истинностью которого мы интересуемся. Если запрос не содержит переменных , то вычисление его значения дает ответ «Да» при его истинности либо ответ «Нет» при его ложности. Если же в предикате запроса есть переменные , то ищутся их значения ( интерпретация ), при которых этот предикат и все предикаты программы становятся истинными. В этом и состоят вычисления программы на Прологе.
Так как каждый предикат — это функция , то Пролог является языком функционального программирования.
Итак, в языке Пролог рассматриваются объекты и 3 вида утверждений относительно объектов: факты, правила и запросы. Единственной структурой данных является терм .
Объекты и термы Пролога
Объектами Пролога являются
- имена (начинаются со строчной буквы), строки символов (заключаются в апострофы ) и числа — константные объекты или константы; например, автомобиль, дом, иван, ‘a+b’ , ‘X’ , 123;
- переменные — могут принимать значения других объектов, и мы их будем писать прописными латинскими буквами: например, X, A, W ;
- списки — их элементами являются любые объекты; списки мы заключаем в квадратные скобки, разделяя элементы запятыми; например, [] — пустой список (он является константой, мы его будем обозначать также nil и любой список завершать этим элементом, чтобы показать конец списка), [a, b, c, nil ] — список, состоящий из трех констант a , b и c ; [X, [b, Y, ‘X’, nil ], nil ] — список, состоящий из двух элементов, первый из которых — переменная X , а второй — список из трех элементов: имени b , переменной Y и строки ‘X’ .
Завершающий список элемент nil можно при записи опускать, подразумевая его в необходимых случаях. Для конкатенации (соединения) списков и элементов в один список используется точка как бинарная операция соединения левой части ( головы списка ) и правой части ( хвоста списка ). В случае операции конкатенации квадратные скобки на нулевом уровне можно опускать. Например, a.X.Y.a при X=b , Y=c есть список [a, b, c, a] , также при X=[b] , Y=[c] есть тот же список , а при X=[b, [d, e]] и Y=[[c]] есть список [a, b, [d, e], [c], a] .
Теперь индуктивно введем понятие терма . Термами являются объекты Пролога. Кроме того, термами являются составные термы . Составной терм образуется из имени функции и списка аргументов (термов Пролога) в круглых скобках. Синтаксически составной терм имеет вид
f(t1. tn),
— аргументы.
Примерами составных термов являются: холодный (вода), отец (иван, петр), list(d, list(b, nil )) и bintree(bintree( nil , 7, nil ), L, 12) .
В первом примере составным термом является высказывание с именем булевой функции 1 аргумента-константы, которое имеет логическое значение истина или ложь .
Во втором примере отношение «иван является отцом петра» задается как булева функция с 2 аргументами-константами.
В третьем примере бинарная функция с именем list и двумя аргументами имеет в качестве первого аргумента константный объект d , а в качестве второго аргумента — составной терм с именем той же функции и возвращает, по-видимому, список .
В четвертом примере функция с именем bintree и тремя аргументами возвращает в виде списков бинарное дерево с корнем 7, правым сыном 12 и левым сыном, который определяется переменной L.
Термы , в которые не входят переменные, назовем основными , а термы , содержащие переменные, — неосновными . Так, три первых примера выше являются основными термами , а четвертый пример — неосновным термом .
В логическом программировании основной структурой является предикатная функция, описываемая составным термом, которая имеет истинностное значение (истина или ложь ), возможно зависящее от значений аргументов. Такой предикат называется атомарным, или атомом .
Факты
Факты — это простейшие утверждения относительно объектов программы, которые считаются истинными, т. е. имеют смысл аксиом программы. Каждый факт оформляется в виде атомарного предиката и стрелки влево, которая находится справа от него. Так, в следующем примере
мужчина (иван)
задается, что объекты иван и петр являются мужчинами , что иван является отцом петра и что дважды два — четыре.
Почему ставится стрелка? Общий вид записи продукции «если A , то B «, где A и B — предикаты, выражается на Прологе следующим образом:
Факт не имеет посылки и читается «то B «, т. е. утверждение B рассматривается как истинный факт.
Множество фактов образуют простейшую программу Пролога. Но атомарный предикат факта может содержать переменные в качестве аргументов или неосновные термы . В этом случае по умолчанию считается, что добавлен квантор всеобщности с переменными предиката. Такие факты называются универсальными : они истинны для любых значений переменных. Например,
любит (X, яблоко)
означает, что любой объект программы «любит яблоко». Универсальные факты сокращают запись программы.
Источник: intuit.ru
Синтаксис языка Prolog
Prolog Синтаксис языка Prolog Основные элементы языка Пролог Алфавит языка Пролог включает следующие символы: A, B, C, …, Z, a, b, c,…,z — прописные и строчные буквы латинского алфавита. 0,1,2,3,4,5,6,7,8,9 — цифры. + — = * / [ ] : ; , | . —специальные знаки. Основные конструкции логического программирования — термы и утверждения.
Определение и классификация термов Логические термы Простые термы Переменные Константы Числа Составные термы Атомы Строки Числовые константы Числа в языке Пролог используются целые и вещественные. Целые числа записываются так же, как в любом другом языке программирования; целые отрицательные числа записываются со знаком, в записи положительных чисел знак можно опустить, например, 135, 0, -89.
Вещественные константы могут быть представлены в форме с фиксированной точкой и с плавающей точкой, например, 135.712 и 0.135712E+3,соответственно. Атомы Атомы Последовательность латинских букв, цифр и знака подчеркивания, начинающая со строчной буквы. Например, may, all, factorial — символьные атомы.
Последовательность специальных знаков есть атом Например, :>= *. Любое слово из букв латинского и русского алфавита и цифр, заключенное в апострофы Например, ‘Маша’,’1_мая’, ‘Arity_Prolog’. Символьные атомы не должны содержать пробелы. ‘Mary’, Переменные Имя переменной в Прологе — это последовательность латинских букв, цифр и знака подчеркивания, начинающаяся с прописной буквы или знака подчеркивания.
Например, X, All, S1 — переменные. Переменные используются для представления объектов, значения которых определяются в ходе решения задачи. Переменные записываются в качестве аргументов предикатов в Прологпрограмме и в запросах.
Анонимные переменные Если значение аргумента предиката не принимается во внимание, то этот аргумент обозначается анонимной переменной, то есть вместо имени переменной указывается знак подчеркивания «_». Строки Строки — это последовательности символов, заключенная в апострофы. Строки используются в задачах обработки текстов на естественных языках. » — пустая строка.
Строки могут включать пробелы, например, ‘1 января 2003 года ‘ есть строка, и ‘Turbo-Prolog’ тоже строка. Составные термы Составной терм — это конструкция вида f(t1,t2,…,tk), где f — символьный атом, определяющий функциональную константу или главный функтор, а t1,t2,…,tk — термы, каждый из которых может быть составным термом. Составной терм подругому называется структурой.
Примеры составных термов book(Author,Title,Year) — пример составного терма. .(H,T) – список, пример составного терма. Представление фактов Самая простая программа на Прологе является множеством фактов.
Факт — это предикатная структура, заканчивающаяся точкой, которая записывается следующим образом: ( , ,…, ). Представление фактов (продолжение) Факт представляет собой утверждение о том, что соблюдается некоторое отношение. С их помощью можно выражать произвольные отношения между объектами. Например, student(‘Иванов’,’МГГУ’).
Этот факт определяет отношение между термами, первым из которых является фамилия студента, а вторым место его учебы. Синтаксические правила записи фактов: • • Имя предиката в утверждении-факте есть символьный атом. После имени предиката записывается список аргументов в круглых скобках. Между именем предиката и открывающей скобкой ‘(‘ не должно быть пробела.
Синтаксические правила записи фактов: 3. 4. 5. Возможны нуль—местные предикаты в фактах, т.е. предикаты, не имеющие аргументов. В качестве аргументов в списке могут быть как переменные, так и константы. В конце факта обязательна точка. Переменные в фактах Переменные в фактах неявно связываются квантором всеобщности.
Это означает, что факт p(T1,T2,…Tn). где Ti –переменные следует понимать так ∀(T1) ∀(T2)… ∀(Tn) p(T1,T2,…Tn) — истина. Факты, содержащие переменные, называются универсальными.
Примеры универсальных фактах Примерами универсальных фактов являются следующие утверждения: plus(X,0,X). что означает, сумма любого числа Х с нулем равна X. proiz(X,0,0). что означает, произведение любого числа Х с нулем равна 0. Представление правил Правила это средство определения новых утверждений с помощью уже существующих в Пролог-программе утверждений (фактов и правил). С точки зрения синтаксиса языка Пролог правило это утверждение вида A: B1,B2,…Bn. (n≥0) где A заголовок правила, а конъюнкция предикатов B1,B2,…Bn называется телом правила.
Переменные в правилах В правилах, так же как и в фактах, переменные неявно связаны квантором всеобщности. Например, утверждение «Точка с координатами (X,Y) принадлежит окружности с радиусом, равным 2, и с центром в точке начала координат, если X2+Y2=4.» На Прологе будет записано следующим образом: circle(X,Y): X*X+Y*Y=4. что означает для любых X и Y, таких что X*X+Y*Y*=4, точка (X,Y) принадлежит окружности с радиусом, равным 2, и с центром в точке начала координат.
Процедуры Набор правил, заголовки которых имеют одно и то же имя и арность (число аргументов), описывает одно и то же отношение и называется процедурой. Правила, составляющие одну и ту же процедуру, должны следовать в тексте программы подряд. В процедуру нельзя включать правила с другим заголовком.
Область действия переменных Логические переменные служат для обозначения неопределенных объектов. Областью действия переменной является одно утверждение (факт или правило). Подстановки Подстановкой называется конечное (возможно, пустое) множество пар вида Xi = ti, где Xiпеременная, а tiтерм, не содержащий переменную Xi.
Подстановки и конкретизация переменных Результат применения подстановки θ к утверждению A обозначается Aθ и получается путем замены каждого вхождения в A каждой переменной Xi на соответствующий терм ti. С помощью подстановок производится конкретизация переменных (аналог присвоения значений) . Примеры утверждений Утверждение B является примером утверждения A, если найдется такая подстановка θ, что B=Aθ.
Например, факт summa(1,2,3), которое означает, что 1+2=3, является примером утверждения summa(X,Y,3) при применении подстановки θ=. Утверждение С называется общим примером утверждений A B, если найдутся такие подстановки θ1 и θ2, что C=Aθ1 и C=Bθ2, т.е. C является примером A и B одновременно.
Например, факт summa(1,2,3) является общим примером утверждений summa(X,2,Z) и summa(1,Y,Z) при применении подстановок θ1= и θ2=. Примеры утверждений Утверждение B является примером утверждения A, если найдется такая подстановка θ, что B=Aθ. Например, факт summa(1,2,3), которое означает, что 1+2=3, является примером утверждения summa(X,Y,3) при применении подстановки θ=. Вопросы (запросы).
Вопрос (целевое утверждение) это средство извлечения информации из логической программы. С помощью вопроса выясняется, истинно ли некоторое утверждение или нет. С точки зрения логики поиск ответа на вопрос состоит в определении того, является ли утверждение (вопрос) логическим следствием программы или нет.
Простые вопросы Вопросы, состоящие из одной цели, называются простыми вопросами. Конъюнктивные вопросы Вопрос, включающий в себя конъюнкцию предикатов p1,p2,…,pn , называется конъюнктивным вопросом. Каждый предикат pi называется целью. Конъюнктивный вопрос это конъюнкция целей.
Переменные в вопросах Вопрос, не содержащий переменных, называется основным вопросом, а вопрос, включающий переменные, называется неосновным. Переменные в вопросах неявно связаны квантором существования.
Переменные в вопросах Вопрос Goal: p(X1,X2,…Xn). где X1,X2,…Xnпеременные, предполагает утвердительный ответ, если существует такой набор термов t1,t2,…tn, что подстановка в предикат p дает результат “истина”. Если существует, хотя бы одна такая подстановка, то вопрос Goal: p(X1,X2,…Xn). выводим из логической программы, т.е. является логическим следствием программы.
Общие переменные в конъюнктивных вопросах Конъюнктивные вопросы обычно содержат общие переменные. Переменные называются общими, если они входят в две или более цели конъюнктивного запроса. Пример простой Прологпрограммы Программа «Родственники» является примером простой Прологпрограммы. Пусть имеется генеалогическое дерево, определяющее степень родства между людьми.
Памелла Том Элизабет Джон Эд Анна Пат Джим Отношение parent Родственные отношения можно записать с помощью фактов, соответствующие отношению parent( , ) parent(‘Памелла’,’Джон’). parent(‘Памелла’,’Элизабет’). parent(‘Том’,’Джон’). parent(‘Том’,’Элизабет’). parent(‘Джон’,’Анна’). parent(‘Джон’,’Пат’). parent(‘Элизабет’,’Эд’). parent(‘Пат’,’Джим’). Отношение person Расширим эту программу фактами, определяемыми схемой отношения person( , , ): person(‘Памелла’,’ж’,72). person(‘Том’,’м’,78). person(‘Джон’,’м’,42). person(‘Элизабет’,’ж’,35). person(‘Эд’,’м’,14). person(‘Анна’,’ж’,20). person(‘Пат’,’ж’,25). person(‘Джим’,’м’,3).
Отношение person определяет характеристики человека Текст программы parent(‘Памелла’,’Джон’). parent(‘Памелла’,’Элизабет’). parent(‘Том’,’Джон’). parent(‘Том’,’Элизабет’). parent(‘Джон’,’Анна’). parent(‘Джон’,’Пат’). parent(‘Элизабет’,’Эд’). parent(‘Пат’,’Джим’). person(‘Памелла’,’ж’,72). person(‘Том’,’м’,78). Текст программы person(‘Джон’,’м’,42). person(‘Элизабет’,’ж’,35). person(‘Эд’,’м’,14). person(‘Анна’,’ж’,20). person(‘Пат’,’ж’,25). person(‘Джим’,’м’,3).
Примеры вопросов к программе «Родственники» Вопрос 1. Вопрос ”Является ли Пат родителем Джима? ” на Прологе можно задать следующим образом: ? — parent(‘Пат’,’Джим’). Пролог-система будет искать в программе факт, совпадающий с вопросом, и, обнаружив такой факт, система выдаст ответ ‘YES’. В случае, когда соответствующий факт не обнаружен, система выдаст ответ ‘NO’.
Примеры вопросов к программе «Родственники» Вопрос 2. Вопрос ”Кто отец Элизабет и сколько ему лет? ” на Прологе можно задать следующим образом: ? — parent(Х,’Элизабет’),person(X,’м’, Y). Пролог-система выдаст ответ: X=Том Y=78 YES Если возраст не интересует пользователя, то в вопросе используется анонимные переменные, обозначаемые знаками подчеркивания ‘_’.
Примеры вопросов к программе «Родственники» Вопрос 3. Вопрос ”Кто отец Элизабет? ” на Прологе можно задать следующим образом: ? — parent(Х,’Элизабет’),person(X,’м’, _). Пролог-система выдаст ответ: X=Том YES Примеры вопросов к программе «Родственники» Вопрос 3. Приведенные примеры вопросов относятся к программе, состоящей из одних фактов.
Для того чтобы сократить и упростить вопросы в Пролог программах задаются правила. Вопрос 3 можно упростить, если задать следующее правило: “X является отцом Y, если X является родителем Y, и X – мужчина.” На языке Пролог это правило записывается так: father(X,Y):-parent(X,Y),person(X,’м’,_).
Примеры вопросов к программе «Родственники» Вопрос 3. А вопрос 3 записывается следующим образом: ? — father(X,’Jim’). Пролог-система выдаст тот же ответ: X=Том YES Лабораторная работа № 1. Простейшая программа на языке Пролог.
Необходимо выполнить следующие действия: 1. Описать с помощью фактов 4-уровневовое генеалогическое дерево в Прологпрограмме “Родственники”, включающей предикаты parent и person. 2. Написать правила, определяющие следующие отношения: “X является отцом Y” . “X является бабушкой Y” . “X является сестрой Y” . “X является племянником Y” . “X является племянницей Y” . Лабораторная работа № 1. Простейшая программа на языке Пролог. “X является родителем родителя Y” . “X является прадедушкой Y” . “X является двоюродным братом Y” . 3. Отладить программу с помощью интерпретатора SWI Prolog. 4. Продемонстрировать работу программы с помощью вопросов. 5. Составить отчет по лабораторной работе.
В закладки
Разместил пособие
mariya.koroleva.1970
Эксперт по предмету «Программирование»
Поделись лекцией и получи скидку 30% на платформе Автор24
Заполни поля и прикрепи лекцию. Мы вышлем промокод со скидкой тебе на почту
Твоя лекция отправлена! Жди скидку на почте. Есть еще материалы? Загрузи прямо сейчас
Загрузить еще лекции
Поделись лекцией и получи промокод на скидку 30% на платформе Автор24
Заполни поля и прикрепи лекцию. Мы вышлем промокод со скидкой тебе на почту
Твоя лекция отправлена! Жди скидку на почте. Есть еще материалы? Загрузи прямо сейчас
Источник: spravochnick.ru