СавельеваА.Г. Курсовая по ИИС. 2.СавельеваА.Г. Курсовая по ИИС. Исчисление предикатов основа языка Пролог

• Название: Исчисление предикатов основа языка Пролог
• Анкор: СавельеваА.Г. Курсовая по ИИС
• Дата: 30.05.2021
• Размер: 105.74 Kb.
• Имя файла: 2.СавельеваА.Г. Курсовая по ИИС.docx
• Тип: Курсовая; #211842

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВО «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ»»

ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

КУРСОВАЯ РАБОТА
по дисциплине «Интеллектуальные информационные системы»

Тема: «Исчисление предикатов - основа языка Пролог»
Студентка группы __ИЭ-61-18_________________СавельеваА.Г.

(Ф.И.О.)
Руководитель____________________________доцент, Карпович Е. Е.

(уч. степень, звание, Ф.И.О.)

Сдана на проверку
Возвращена на доработку
Допущена к защите
Оценка

Москва-2021

Москва-2018


ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

1.ЯЗЫК ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ PROLOG 6

1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ЛОГИКИ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА 6

1.2.СТАНДАРТНЫЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ФОРМУЛ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ 10

1.3.ЛОГИКА ПРЕДИКАТОВ – ОСНОВА СИНТАКСИСА И СЕМАНТИКИ ЯЗЫКА PROLOG 11

2.ПРИМЕР PROLOG-ПРОГРАММЫ 14

ЗАКЛЮЧЕНИЕ 17

СПИСОК ЛИТЕРАТУРЫ 18

ВВЕДЕНИЕ

Ключевое отличие языка Пролог от традиционных, алгоритмических языков программирования заключается в применении в программировании логики предикатов – логических функций-утверждений с одной или несколькими переменными, определенных на множестве и принимающих одно из двух значений, «истина» и «ложь», в зависимости от значений предметных переменных.

Такие предикаты-утверждения полежат доказательству – и выполнение программы состоит в попытке доказать истинность утверждения. Такие утверждения называют целевыми, а свойство, заложенное в принцип решения задачи типа:

«Существует список Х, такой, что упорядочение списка [3,1,2,7] приводит к списку Х».

- декралативностью, когда программист вместо описания процедуры решения задачи, описывает предметную область и декларирует, что именно является истинным в этой предметной области.


Рис.1.
В Prolog для описания некоторой предмет ной области и используется исчисление предикатов. Также определяются множества исходных элементов, правила построения формул, система аксиом и множество правил вывода, каждое из которых описывает способ построения новых формул из исходных элементов и уже построенных формул.

Для Пролога, где предметная область описывается с помощью хорновских предложений, в качестве способа логического вывода выбран поиск сверху вниз. Программирование на Прологе сводится к представлению описания задачи в виде множества хорновских предикатов, интерпретации этого описания с помощью Пролог  системы и затем выдачи вопросов Пролог  системе, которая отвечает на вопросы, используя для логического вывода заключений поиск сверху вниз.

Отношения на языке Пролог описываются с помощью правил. Правило, содержащее свой заголовок в качестве предиката в правой части этого правила, называется рекурсивным. Рекурсивное правило реализует повторяющиеся действия. Рекурсивные правила эффективны при программировании циклических задач, при формировании запросов к базам данных и при обработке списков.

Предложения языка Пролог являются либо правилами, либо фактами, либо запросами. Логическая программа на Прологе  это конечная последовательность фактов и правил.

Поэтому название языка было получено от фразы на английском языке “PROgramming in LOGic”, что означает – программирование средствами логики.

1. ЯЗЫК ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ PROLOG

Логическое программирование — это подход к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна. Логика предикатов первого порядка — это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений.

При использовании языка логического программирования основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать. Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать и реализовать с помощью логических программ.

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ЛОГИКИ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА

Предположим, есть некоторое множество D объектов, называемое предметной областью. Символы, обозначающие элементы этого множества, называются предметными константами, а символ, обозначающий произвольный элемент предметной области  предметной переменной.

Предикатэто логическая функция одной или нескольких переменных P(x1,x2,… xn), определенная на множестве D и принимающая одно из двух значений, «истина» и «ложь», в зависимости от значений предметных переменных. Буква P  предикатный символ. Предикат, зависящий от n переменных, называется nместным (или nарным) предикатом.

Для описания некоторой предметной области на языке исчисления предикатов (ИП) определяются множества исходных элементов, правила построения формул, система аксиом и множество правил вывода, каждое из которых описывает способ построения новых формул из исходных элементов и уже построенных формул.

Исходными элементами ИП являются следующие множества:

1. 
   Конечное множество предметных переменных {x₁,x₂,…x_k};
   
2. 
   Конечное множество предметных констант {a₁,a₂,…a_n};
   
3. 
   Конечное множество функциональных символов {f₁,f₂,…f_m};
   
4. 
   Конечное, непустое множество предикатных констант {p₁,p₂,…p_r};
   
5. 
   Логические связки:  (отрицание),  (конъюнкция),  (дизъюнкция),  (импликация).
   
6. 
   Кванторы:  (квантор всеобщности) и  (квантор существования).
   
7. 
   Специальные символы: ( ) + - */ < > . , [ ] : ;
   
8. 
   Знак пустого дизъюнкта , который является тождественно ложной формулой.
   

Правила построения формул определяются следующим образом. Формулы состоят из термов, предикатных констант, специальных символов и логических связок.

Определение терма  рекурсивно:

1. 
   Терм  это предметная переменная или предметная константа.
   
2. 
   Если f  функциональный символ, и t₁,t₂,…t_n  термы, то f(t₁,t₂,…t_n)  терм.
   

Предикат вида p(t₁,t₂,…t_n), где p  предикатная константа, а t₁,t₂,…t_n  термы, является элементарной формулой.

Правила построения ППФ (Правильно Построенных Формул) в логике предикатов 1-го порядка следующие:

1. 
   Всякая элементарная формула есть ППФ.
   
2. 
   Если A и B ППФ, а x  предметная переменная, то каждое из выражений A, AB, AB, AB, (x)A, (x)A есть ППФ.
   
3. 
   Других правил построения ППФ нет.
   

Для формул с кванторами справедливо следующее утверждение: формула Q(x₁,x₂,…,x_n) получена из формулы P(x₁,x₂,…x_n) посредством присоединения квантора, если

Q(x₁,x₂,…,x_n) = (x_i) P(x₁,x₂,…x_n) или

Q(x₁,x₂,…,x_n) = (x_i) P(x₁,x₂,…x_n).

Пусть D={a₁ , a₂, …, a_n} есть множество предметных констант, и P(x)  предикат, определенный на множестве D, тогда справедливы утверждения:

(x) P(x) = P(a₁) P(a₂) …P(a_n) и

(x) P(x) = P(a₁)  P(a₂)  …P(a_n).

Система аксиом исчисления предикатов включает в себя аксиомы исчисления высказываний А1А11 и две аксиомы с кванторами А12 и А13.

A1) A (BC)

A2) (A(BC)) ((AB) (AC))

A3) AB A

A4) AB B

A5) (AB) ((AC) (ABC))

A6) AAB

A7) BAB

A8) (AC) ((BC) (ABC))

A9) (AB) (BA)

A10) A A

A11) A A

A12) (x) A(x) A(t)

A13) A(t) (x) A(x), A(x) ППФ, t терм, не содержащий x. Все аксиомы тождественно истинны.

Выводом P называется такое линейно упорядоченное множество элементов, что всякий элемент P является либо аксиомой, либо заключением применения некоторого правила вывода. Формула является выводимой, если можно построить вывод, заканчивающийся этой формулой.

В исчислении предикатов определены следующие правила вывода:

1. 
   Все аксиомы выводимы.
   
2. 
   Правило подстановки.
   

Подстановка (t_i вместо x_i) есть множество  = {x₁=t₁,x₂=t₂,… x_k=t_k }, где x₁,x₂,…,x_k  попарно различные предметные переменные, x_ix_j при ij , t₁,t₂,…,t_k  термы, если x_i= t_i, то t_i отличается от x_i.Правило подстановки означает, что если P(x₁,x₂,…x_k) выводим, то и формула P(t₁,t₂,…t_k) = (P(x₁,x₂,…x_k))  выводима.

3. 
   Правило Modus Ponens (MP).
   

Если А  выводимая ППФ, и A B выводима, то B  также будет выводима.

4. 
   Правило обобщения.
   

Если B A(x) выводимая ППФ, и B не содержит вхождений x, то формула B (x)A(x)  также будет выводима.

5. 
   Правило конкретизации.
   

Если выводима формула A(x)B, и B не содержит вхождений x, то формула (x)A(x) B  также будет выводима.

6. 
   Правило переименования переменных.
   

Если Aвыводимая ППФ, имеющая квантор  и (или) , то одна связанная переменная может быть заменена другой, не меняя истинностного значения формулы. Полученная формула также будет выводима.

7. 
   Других правил вывода нет.
   

2. СТАНДАРТНЫЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ФОРМУЛ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

Приведение логических формул к одной из стандартных (нормальных) форм представления позволяет упростить алгоритм доказательства общезначимости формул. По тем же причинам язык программирования Пролог является подмножеством языка исчисления предикатов, в Прологе используется клаузальная форма записи формул исчисления предикатов.

Клаузальной формой (клаузой или предложением) в исчислении предикатов называется формула, представляющая собой несколько предикатов или их отрицаний, объединенных знаками дизъюнкции. В общем случае клаузу можно представить в следующем виде:

A₁A₂…A_kB₁B₂ … B_n , где элементарные формулы (предикаты) A_i и B_j называются литерами, причем B_j  положительная литера, а A_i  отрицательная литера.

Если k1 и n=1, то такая клауза имеет вид A₁A₂…A_kB и называется клаузой Хорна или хорновским дизъюнктом. Хорновский дизъюнкт содержит не более одной положительной литеры.

Дизъюнкт Хорна можно преобразовать с помощью правила де Моргана:

(A₁A₂…A_k)B, а эта формула равносильна формуле A₁A₂…A_kB, что соответствует правилам “Если …,то”.

На языке Пролог дизъюнкт Хорна записывается в другом виде B: A₁,A₂,…,A_k. При такой записи «,» соответствует знаку конъюнкции , а знак “:” соответствует знаку импликации .

В языке Пролог используются только хорновские дизъюнкты, называемые правилами. При этом B называется заголовком правила, а конъюнкция A₁,A₂,…,A_k называется телом правила. Знак “:” читается как “Если”. Таким образом, правило является условным предложением языка Пролог.

В клаузе Хорна атомарные формулы A₁,A₂,…,A_k могут отсутствовать, т.е. k=0, n=1. В этом случае правило имеет пустое тело:

B: .

Это означает, что предикат B истинен всегда, такая конструкция в языке Пролог называется фактом.

Если в хорновском предложении отсутствует заголовок правила, т.е. k1, n=0, то правило принимает вид:

? : A₁,A₂,…,A_k.

Такое выражение называется вопросом или запросом, а предикаты A₁,A₂,…,A_k называются целями, или целевыми утверждениями.

Если в хорновской клаузе k= n=0 , клауза называется пустым дизъюнктом, имеет обозначение  и интерпретируется как тождественно ложная формула.

Предложения языка Пролог являются либо правилами, либо фактами, либо запросами. Логическая программа на Прологе  это конечная последовательность фактов и правил.

3. ЛОГИКА ПРЕДИКАТОВ – ОСНОВА СИНТАКСИСА И СЕМАНТИКИ ЯЗЫКА PROLOG

Основными конструкциями логического программирования в Prolog являются логические термы (переменные, константы, свойства, составной терм), а также утверждения 3х видов:

1. 
   Факты – это предикатная структура, обязательно заканчивающаяся точкой. Например:
   

<имя предиката>(<терм₁>,<терм₂>,…,<терм_n>).

student(‘Иванов’,’МГГУ’).

- где в скобках записываются аргументы. Факты являются простейшим видом утверждений в логических программах и с их помощью можно определять свойства объектов, если аргумент один, или описывать отношения между объектами, если аргументов два и больше.

Совокупность фактов в Прологпрограмме является аналогом реляционной базы данных, а вопросы к программе подобны запросам к базе данных.

Факты, содержащие переменные, называются универсальными. Например:

plus(X,0,X). - сумма любого числа Х с нулем равна X.

2. 
   Правила - это средство определения новых утверждений, используя уже существующие в Пролог-программе утверждения. Например:
   

A: B₁,B₂,…B_n. (n0)

circle(X,Y): X^2+X^2=4.

- где A  заголовок правила, а конъюнкция предикатов B₁,B₂,…B_n
называется телом правила.

В Прологпрограмме может быть записано произвольное число фактов и правил. Набор правил, заголовки которых имеют одно и то же имя и арность, описывает одно и то же отношение и называется процедурой.

3. 
   Вопросы - это средство извлечения информации из логической программы. С помощью вопроса выясняется, истинно ли некоторое утверждение или нет. С точки зрения логики поиск ответа на вопрос состоит в определении того, является ли утверждение (вопрос) логическим следствием программы или нет.
   

Вопрос, включающий в себя конъюнкцию предикатов p₁,p₂,…,p_n , называется конъюнктивным вопросом. Каждый предикат p_i называется целью. Конъюнктивный вопрос  это конъюнкция целей. Вопросы, состоящие из одной цели, называются простыми вопросами. Вопрос, не содержащий переменных, называется основным вопросом, а вопрос, включающий переменные, называется неосновным.

Переменные в вопросах неявно связаны квантором существования. Это означает, что вопрос ?p(X₁,X₂,…X_n). где X₁,X₂,…X_n  переменные, предполагает утвердительный ответ, если существует такой набор термов t₁,t₂,…t_n, что подстановка {X₁=t₁,X₂=t₂,…X_n=t_n} в предикат p дает результат “истина”. Если существует, хотя бы одна такая подстановка, то вопрос
?p(X₁,X₂,…X_n).
выводим из логической программы, т.е. является логическим следствием программы.

Конъюнктивные вопросы могут содержать общие переменные. Переменные называются общими, если они входят в две или более цели конъюнктивного запроса.




Рис.1.1.


Также, для упрощения алгоритма доказательства общезначимости формул используют приведение логических формул к одной из стандартных (нормальных) форм представления. По тем же причинам язык программирования Пролог является подмножеством языка исчисления предикатов, в Прологе используется клаузальная форма записи формул исчисления предикатов.

2. ПРИМЕР PROLOG-ПРОГРАММЫ

Эд

Программа «Родственники» является примером простой Прологпрограммы. На рис 2. показано трехуровневое генеалогическое дерево.

Родственные отношения можно записать с помощью фактов, соответствующие отношению parent:

parent(‘Памелла’,’Джон’).

parent(‘Памелла’,’Элизабет’).

parent(‘Том’,’Джон’).

parent(‘Том’,’Элизабет’).

parent(‘Джон’,’Анна’).

parent(‘Джон’,’Пат’).

parent(‘Элизабет’,’Эд’).

parent(‘Пат’,’Джим’).

Расширим эту программу фактами, определяемыми схемой отношения person.

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 можно упростить, если задать следующее правило:

“X является отцом Y, если X является родителем Y, и X – мужчина.”

На языке Пролог это правило записывается так:

father(X,Y):-parent(X,Y),person(X,’м’,_).

А вопрос 3 записывается следующим образом:

?-father(X,’Jim’).

ЗАКЛЮЧЕНИЕ

Prolog — язык логического программирования. Логическое программирование — функциональное программирование, радикально отклоняется от основного пути развития алгоритмических языков программирования. Логическое программирование строится не с помощью некоторой последовательности абстракций и преобразований, отталкивающейся от машинной архитектуры фон Неймана и присущего ей набора операций, а на основе абстрактной модели, которая никак не связана с каким-либо типом машинной модели. Логическое программирование базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера, а компьютер должен выполнять инструкции, свойственные человеку. В своем предельном и чистом виде логическое программирование предполагает, что сами инструкции даже не задаются, а вместо этого явно, в виде логических аксиом, формулируются сведения о задаче и предположения, достаточные для ее решения.

Язык Prolog строится на описании предикатов – утверждений, отношений между аргументами и их свойствами, в котором используется логика предикатов первого порядка в форме фраз Хорна.

СПИСОК ЛИТЕРАТУРЫ

1. 
   Учебное пособие «Программирование на языке Пролог», Карпович Е.Е. 2002г.
   
2. 
   http://masters.donntu.org/2009/fvti/bandurka/library/article3.htm