Предикаты

Предикаты записываются в форме предикатный символ и список термов

P (t1,t2, …, tN)

Между предикатным символом и открывающейся скобкой не должно быть пробела.

По форме предикаты записываются так же как и структуры.

Они отличаются только по смыслу (семантике). Структура – это сложное понятие, сложный терм, а предикат – это функция, область значения которой является множеством из истины и лжи.

Факты

Из предикатов можно строить факты.

Rod(I,f).

Rod(m,f).

Rod(f,p).

Факты это предложения программы, в конце ставится точка.

С помощью предикатов записываются цели, это целевые дизъюнкты. Каждая цель отделяются запятыми.

?- rod(X,Y), rod…..

Правила

Имеют вид: p:- p1, p2, …pn.

Где p1…предикаты

P – голова (заголовок) правила.

P1,pn… тело правила.

Семантика пролога

Вычисление пролог программы заключается в построении доказательства методом резолюций.

Определение. Подстановкой называется множество пар вид а x_i/t_k, где x_i – переменная, а t_k – терм, таких что:

a) x_i<>x_m (переменные не повторяются, что гарантирует однозначность подстановки).

Б) x_i не входит в t_k

Подстановкой можно конкретизировать формулу.

Пример. Кто общий родитель Анны и Павла ?

?-родитель (X,a), родитель (X,p)

( X / f)

Как происходит сопоставление

Термы сопоставимы если

1 они идентичны

2 они станут идентичными, если к ним применить подстановку

Термы pnt(X,15) и pnt(X1, Y1) сопоставимы с подстановкой {X/X1, Y1/15}

/ - “заменяется, конкретизируется”.

Подстановки обычно обозначают обычно греческими буквами тетта, сигма.

Подстановка сигма является унификатором двух термов t1, t2, если её применение к ним делает их идентичными. Сигма t1, сигма t2.

Подстановка это функция, которая является отображением области переменных на область термов.

Сигма = {X/X1, Y1/15} то эту подстановку можно применить к терму

Сигма (pnt(X, 15)) = pnt(X1, 15)

Сигма (pnt(X1, Y1)) = pnt(X1, 15)

Таким образом мы получили 2 одинаковых терма и значит подстановка сигма явл. унификатором этих 2х термов.

Алгоритм Эрбрана

(bcg lkz cjgjcnfcdktybz термов и он находит наиболее общий унификатор(подстановку), которая делает два атома одинаковыми)

Для заданного множества уравнений вида t1 = t2 выполняем в любом порядке след.действия:

1. Если есть уравнение вида:

А) a=b, где – a и b различные атомарные термы,

Б) a = f, где a – атомарный терм, а f – структура,

В) f(….) = g(…..), где f и g – различные функторы

Г) f(t₁,t₂,t_n) = f(t₁,t₂,t_m) где n<.m, то завершаем алгоритм с неудачей (термы несопоставмы)

2. Если есть уравнение вида X=X, где X – переменная, то удаляем его.

3. Если есть уравнение вида a=a, где a – атом, то удаляем его.

4. Если есть уравнение вида f(t^l₁, tl2, tln) = f(t^r1, t¹₂, t¹_n) то заменяем уравнениями:

T^l₁=t^r₁, t^l₂ = t^r₂, …t^l_n = t^r_n.

(чтобы сопоставить структуры, нужно сопоставить компоненты)

5. Если есть уравнение вида t=X, где X- переменная, а t – не переменная, то заменяем его уравнением вида X=t.

6. Если есть уравнение вида X=t, где Х – переменная, а t – терм, в котором Х не встречается, и если Х встречается в других уравнениях, то заменяем в них каждое вхождение X на t.

7. Если есть уравнение вида X=t, где Х – переменная, а t- не переменная, но содержит переменную X, то завершаем алгоритм с неудачей (positive occurs check).

8. Если никакой другой шаг не применим, то успешно завершаем алгоритм.

Есть у нас список целей Кв.всеоб. g1,g2,gn.

Это дизъюнкт который имеет все эти….Есть правило вида кВ.всеоб. p:- p1,p2,pn.

Все переменные связаны квантором всеобщности. P – положительная литера, g1 отрицательная. Если раскроем g1 будет предикато pg1 (t¹_g1, t2g1, t^ng1_g1).

Точно также предикат p = p (t¹,t²,tⁿ)

Количество термов должно быть одинаковым и соответ.термы должны быть сопоставимы. Эта сопоставимость может быть задана уравнениями.

T¹_g1 должно быть сопоставимо с t1

T¹_g1 с t²

И т.д.

T^ng1_g1 с tⁿ

Эти данные явл .входными параметрами для алгоритма унификации.

Пусть этот алгоритм выдал некую подстановку сигма и в результате применения правила резолюции ……

G1 с P соединяется и вместо p заменяем

P1,p2,pn потом g2,…gn. Новый список целей и к нему применяется подстановка сигма.

………….

Исходными данными явл. множество уравнений вида t1=…

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

…..

Разберем алгоритм.

Рассмотрим первый случай А), если есть уравнение вида a=b, где a b различные атомарные термы

Б)…

В)…

Г)…

См.выше.

2) Удаляем .т.к. никакого смысла не несет

3) а=а всегда, поэтому исключается

Алгоритм Эмбрана всегда завершается, а если….

Примеры

1. { f(X,g(Y)) = f(g(Z), Z) }

(по 4) => {X=g(Z), g(Y) = Z }

По (5) => {X=g(Z), Z=g(Y) }

По 6 => {X=g(g(Y)), Z=g(Y) }

Получили НОУ ():

{X / g(g(Y)), Z/ g(Y) }

2.

{ f(X,g(X), b = f(a,g(Z), Z}

По 4 => {X=a, g(X)=g(Z), b=Z }

По 6 => {X=a, g(a)=g(Z), b=Z }

По 5 => {X=a, g(a)=g(Z), Z=b }

По 6 => {X=a, g(a)=g(b), Z=b }

По 4 => {X=a, a=b, Z=b }

По 1.а => неудача.