Простейшие правила логического вывода

Простейшие правила  логического вывода

Правила вывода это соотношения  между посылками и заключениями, которые в рамках логического  вывода являются истинными всегда.

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

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

Применяется, когда нет переменных ни в фактах, ни в вопросе.

 

Студент (иванов, юфу)

?-студент (иванов, юфу)

Yes

 

Есть_доступ_к_информации (иванов, штатный, всегда)

?- Есть_доступ_к_информации (иванов, штатный, всегда)

Yes

 

2. Правило обобщения- если есть такая подстановка, что вопрос NТ- выводимый из этой программы, то вопрос N- так же выводимый из этой программы.

Применяется, когда в вопросе  есть переменная, а в фактах нет.

 

Существует ли некоторый Х, штатный, который имеет доступ к информации всегда?

?-Есть_доступ_к_информации (Х, штатный,  всегда)

 

Подстановкой называется множество  пар вида: {X1=T1, X2=T2}, где Xi- логические переменные, а Ti- термы.

N={X=иванов}- применить подстановку.

Терм В является примером терма А, если существует такая подстановка N, которая дает АВ=В.

 

3. Правило конкретизации- из утверждения программы Р, с квантором всеобщности, логически выводится вопрос PN, при любой подстановке N.

Переменные есть в фактах, но нет  в вопросе.

 

Любой штатный сотрудник всегда имеет доступ к информации.

Есть_доступ_к_информации(Х, штатный, всегда)

Для любого Х N={X=иванов}

PN= Есть_доступ_к_информации(иванов, штатный, всегда)

 

4. Переменные есть в вопросах и фактах.

 

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

p1(a,X)

?-p1(Y,b)

N={Y’=a, X’=b}

P(a,b)

 

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

 

Унификация

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

Унификация является основным вычислительным шагом в логическом выводе. С ее помощью выполняется 3 вида действий:

1. Сопоставление термов
2. Проверка условий
3. Передача параметров в процедуры

Правила унификации:

1. Если термы Т1 и Т2 являются константами, то они успешно унифицируются только тогда, когда эти константы совпадают.
2. Если Т1 и Т2 являются неконкретизированными переменными, то унификация всегда успешна, а Т1 и Т2 становятся сцепленными. Это означает, что если одна из переменных будет конкретизирована некоторым значением, то и вторая будет конкретизирована им же.
3. Если Т1- неконкретизированная переменная, а Т2- некоторый терм, не содержащий эту переменную, то унификация всегда возможна, причем переменная конкретизируется значением второго терма.

Т1=Х, Т2=а        Т1=Т2=>Х=а

4. Если Т1 и Т2- составные термы, то они успешно унифицируются, при выполнении следующих условий:

-имеют одинаковое имя

-одинаковую  арность

-их соответствующие аргументы попарно успешно унифицируются

 

T1=f(X) T2=f(5)            T1=T2  X=5

Общая схема согласования целевых утверждений.

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

В результате возможны 2 ответа: утвердительный и  нет, что означает «нельзя дать утвердительный ответ». В случае успешного вычисления, в качестве побочного эффекта, возникает некоторая подстановка θ, которая содержит значения переменных, при которых Q является следствием программы. Неудача может означать следующее:

1. Невозможность вывода Q из программы
2. Если возникают бесконечные вычисления, то это так же дает отрицательный ответ.

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

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

%процедура  дед /2

Дед(Х,У):-отец(Х,Z), мать(Z,Y).         \\1

Дед(Х,У):- отец(Х,Z), отец(Z,Y).           \\2

%процедура отец/2

Отец (иван, анна).          \\3

Отец (иван, петр).          \\4

%процедура мать /2

Мать (анна, михаил).        \\5

?-дед(X, михаил).

R0=дед(X, михаил).

Т1= дед(X, михаил).

Т2= Дед(Х,У).

Θ={Y,михаил}

Правило 1 сопоставимо с целью

R1=отец(X,Z), мать(Z,Y).

\\3

Т1= отец(Х,Z).

Т2= Отец (иван, анна).

Θ={X=Иван, Z=анна}

R2=мать(анна, михаил)

Цель в резольвенте унифицируется  с правилом 5. Тело правила пустое, значит R3-пусто, значит «успех».

Порядок просмотра базы данных.

Рассмотрим отношение однокурсник.

Студент (Х,К)

Х-имя

К-курс

Однокурсники (Х,У):-студент(Х,К1), студент(У,К2), Х\=У, К1=К2.

?-однокурсники(Х,У).

База:

Студент(иванов,1)

Студент(петров,4)

Студент(сидоров,2)

Студент(кузнецов,4)

Будем использовать 2 маркера: Ϫ1 означает факт, который используется в текущий момент для согласования первой цели студента; Ϫ2 согласование второй цели

Управление вычислениями. Предикат fail.

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

Max(X,Y,X):-X>=Y.

Max(X,Y,Y):-X<Y.

Первые 2 аргумента это сравниваемые значения, третий это результат наибольшее.

Эта цель согласуется с помощью первого правила, но остается возможность применить второе, что не имеет никакого смысла. Очевидно, что необходимо иметь возможность указать в первом правиле, что если оно выполнено, то ко второму обращаться не нужно. Для этой цели в прологе имеется предикат отсечения cut, который обозначается «!». Отсечение включается в конъюнкцию целей наряду с обычными целями.

Св-ва отсечения:

1. Если в процессе согласования целей отсечение еще не достигнуто, то оно не оказывает влияния на процесс вывода.
2. При прямой трассировке целей, отсечение прозрачно.
3. Отсечение не мешает пересогласованию целей правее себя.
4. Действие отсечения проявляется при возврате, когда мы «натыкаемся» на него. Оно не проницаемо и неудачей заканчивается не только согласование текущего правила, но и всей процедуры в целом.

У отсечения имеются противники. Основной их аргумент- применение отсечения  меняет декларативный смысл программы.

Для управления выводом можно применять  предикат fail, который никогда не согласуется. Этот предикат часто применяется вместе с отсечением (!,fail).

Отрицание в логических программах.

Логическое программирование строится на основе специальной логики предикатов, которая называется dause Хорна. В этом варианте предикаты не имеют отрицания. Представлена только позитивная информация. Так как в программах иногда необходимо отражать и негативную информацию, то в логике предикатов моделируется ограниченная форма отрицания. Множество утверждений, из которых состоит логическая программа, называют миром. Логическое программирование строится на предположении замкнутости мира, т.е. знаниями является только то, что содержится в логической программе. Если некоторые утверждения не представлены в программе, то считается, что представлено его отрицание, поэтому не делается различие между ложностью и отсутствием утверждения.

Чтобы представить отрицание, в  логическом программировании реализуется  предикат not(Х), который имеет следующий смысл: если Х не выводимо из программы, то цель not(X) согласуется и наоборот.

?-not(X).

Для ответа на вопрос применяем 1 правило.

Предположим, Х согласуется с логической программой, тогда выполняется ! и fail, в результате not(Х) не согласовалось.

?-not(X).

no

Если Х не выводится из программы, то 1 правило применять нельзя, а 2-факт, который всегда успешно согласуется.

?-not(X).

Yes

Представление списков  в логических программах.

Списки в языках ИИ являются основной структурой данных, однако они рассматриваются  иначе, чем в традиционном программировании.

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

В ИИ списки определяются рекурсивно. Список разбивается на голову и хвост. Голова это элемент, а хвост это список. В роли элемента-заглушки выступает пустой список.

Список- это структура, которая  состоит из головы и хвоста, причем хвост является списком.

Исторически первая форма представления  списков использовала функтор обозначаемый точкой.

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

Унификация списков.

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

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

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

Примеры:

[L]=[ ]- унификация невозможна. L должна унифицироваться с элементом, но в пустом списке элементов нет.

 

[L]=[a|[ ]]- унификация успешна

L=a

 

[L,b]=[a,b]

L=a

b=b

 

[[L],b]=[a,b]- унификация невозможна т.к. голова первого списка- список, а второго-атом.

 

[a|L]=[a,b,c]

a=a

L=[b,c]

 

[a|L]=[a,b|[c]]

            [a|[b,c]]

Предикат классификации list.

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

Декларативное описание: для любого терма L отношение list будет истинным, если L либо пустой список, либо его хвост является списком.

Процедурная трактовка: чтобы проверить является ли терм L списком, нужно разбить его на голову и хвост и убедиться в том, что хвост является списком (рекурсивное правило). Если L- пустой список, то L- список (ловушка).

1. List(L):-L=[] если L унифицируется с пустым списком, то отношение истинно.
2. List(L):-L=[H|T], list (T).%2

List([]).  %1

List([_|T]):-list(T).   %2

Пример:

?-list[1,2,3]

%2 ?-list([2,3])

%2 ?-list([3])

%2 ?-list([ ])

%1 да

Принадлежность элемента списку.

Member (элемент, список)

Декларативная трактовка: для любого элемента и  для любого списка отношение member будет истинным, если элемент совпадает с головой списка, или присутствует в его хвосте.

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

Member(X,[X|_]).    %1

Member(X,[_|T]):-member(X,T).     %2

Примеры:

Member(b,[a,b,c]).

%1 b=a

X=b      (a|[b,c])

[X|_]=[a,b,c]

X=a b=a    нет

%2

X=b T=[b,c]

?-member(b,[b,c]).

 

?-member([b,c], [a,[b,c]])

%2

?-member(a,[b,c])

?-member(a,[c])

?-member(a,[ ])   no

 

?-member(X,[a,b]) Есть ли какой-то X, который является элементом списка?

X=a ->

?-member(X,[b])

Вычисление длины списка.

List_length

Декларативная трактовка: для любого непустого списка L, его длина на 1 больше длины хвоста. Длина пустого списка =0.

Процедурная трактовка: чтобы вычислить  длину непустого списка, необходимо вычислить длину хвоста и прибавить 1.

List_length([],0)    %1

List_length([_|T],N):-list_length(T,NN), N is NN+1             %2

?-list_length([a,b,c],N)

R1=list _length([a,b,c],N1)

%2      T=[b,c] N1=N

R2=list_length([b,c],NN1), N is NN1+1

% R3=list_length([c],NN2), NN1 is NN2+1, N is NN1+1

% R4= list_length([],NN3), NN2 is NN3+1, NN1 is NN2+1, N is NN1+1

% R5= NN3=0, NN2 is NN3+1, NN1 is NN2+1, N is NN1+1

Слияние списков.

Пусть даны 2 списка L1 и L2, нужно построить список L3, который образуется путем слияния, т.е. путем присоединения L2 в конец L1.