Представление знаний с использованием логики предикатов
4.1. Логические модели и логическое программирование
Одним из способов представления знаний является язык математической логики, позволяющий формально описывать понятия предметной области и связи между ними.
В отличие от естественного языка, который очень сложен, язык логики предикатов использует только такие конструкции естественного языка, которые легко формализуются.
Т.е. логика предикатов - это языковая система, которая оперирует с предложениями на естественном языке в пределах синтаксических правил этого языка.
Язык логики предикатов использует слова, которые описывают:
- понятия и объекты изучаемой предметной области;
- свойства этих объектов и понятий, а также их поведение и отношения между ними.
В терминах логики предикатов первый тип слов называется термами, а второй - предикатами.
Термы представляют собой средства для обозначения интересующих нас индивидуумов, а предикаты выражают отношения между индивидуумами (которые обозначаются с помощью термов).
Логическая модель - это множество предложений, выражающих различные логические свойства именованных отношений.
При логическом программировании пользователь описывает предметную область совокупностью предложений в виде логических формул, а ЭВМ, манипулируя этими предложениями, строит необходимый для решения задач вывод.
4.2. Простейшие конструкции языка предикатов
Терм - это знак (символ) или комбинация знаков (символов), являющаяся наименьшим значимым элементом языка.
К термам относятся константы, переменные и функции.
Константа применяется для обозначения конкретных объектов реального мира. Пример: ласточка, птица, один, 2 и т.д.
Переменные используются для обозначения некоторого из возможных объектов реального мира или их совокупности (в Прологе начинаются с заглавной буквы). Пример: Некто, X, Who, Вещь и т.д.
Функции (структуры) - последовательность из нескольких констант или переменных, заключенных в круглые скобки, следующие за функциональным символом (функтором). Пример: сумма (1,2); +(1,2); удвоить (X).
Функторы обозначают операторы, которые после воздействия на объект возвращают некоторое значение.
Предикат - это логическая функция, которая выражает отношение между своими аргументами и принимает значение «истина», если это отношение имеется, или «ложь», если оно отсутствует.
Заключенная в скобки последовательность из n термов, перед которой стоит предикатный символ, называется n-местным (или n-арным) предикатом, который принимает значения «истина» или «ложь» в соответствии со значением термов, являющимися его аргументами.
Пример:
является (ласточка, птица)
отец (X, Джон)
Такого типа предикаты получили название атомарных предикатов и соответствуют наиболее простым предложениям нашего разговорного языка - нераспространенным предложениям.
В обычном языке из нераспространенных предложении с помощью соединительных местоимений, союзов, и других частей речи строят более сложные конструкции - сложные предложения.
4.3. Предикатные формулы
В логике предикатов сложными предложениями естественного языка соответствуют предикатные формулы. Предикатные формулы образуются из атомарных предикатов и логических связок, которые читаются как (таблица 4.1):
Таблица 4.1
Логические связки
| , | Ú | ù | ← | ↔ |
| «и» | «или» | «не» | «если» | «тогда и только» |
Логические связки имеют следующий приоритет использования:
ù
, Ú
, «
Наиболее часто в логическом программировании используются связки «И», «НЕ» «ЕСЛИ».
Пример предикатной формулы, соответствующей сложному предложению:
является (ласточка, птица) ← имеет (ласточка, крылья),
Владеет (ласточка, гнездо).
где является (_,_); имеет (_,_); владеет (_ _) - атомарные предикаты; «,» и «» - логические связки.
Однако приведенная конструкция предикатной формулы позволяет делать утверждение не только о конкретном индивидууме которым является ласточка, но и о всех индивидуумах из класса птиц, используя вместо констант переменные:
Является (Х, птица) имеет (Х, крылья), владеет (Х, гнездо)
Таким образом, ставя переменные вместо конкретных имен, мы приходим к более общим понятиям кортежа длины n, предиката и логической формулы.
Однако предикат, который содержит переменные; например,
Имеет (Х, крылья)
не может быть оценен, т.е. нельзя определить ложь он или истина, т.к. его значение определяется после подстановки в переменную некоторой константы.
Однако иногда можно определить значения предиката не делая подстановок используя кванторы общности (") и существования ($), которые обозначают «для всех» и «существует по крайней мере одно».
Тогда приведенная выше логическая формула будет записана в виде:
("X) [являться (Х, птица) имеет (Х, крылья), владеет (Х, гнездо)]
и соответствуют предложению, которое может читаться как: «любое Х является птицей если это Х имеет крылья и владеет гнездом».
Кванторы " и $ могут использоваться и для любого числа переменных. Рассмотрим их различное использование на примере двухместного предиката
любит (Х, У),
который описывает отношение «Х любит Y»:
- ("X) ("Y) любит (Х, Y) - все люди любят всех людей;
- ($Х) ("Y) любит (Х, Y) - существует человек, который любит всех;
- ("Х) ($Y) любит (Х, Y) - для каждого человека существует тот, который его любит;
- ($Х) ($Y) любит (Х, Y) - существует человек, который кого-нибудь любит.
4.4. Определение правильно построенной формулы
Комбинируя логические связки и кванторы можно рекурсивно определить составную формулу логики предикатов, называемую правильно построенной формулой (далее просто ППФ или логическая формула).
Если говорить применительно к естественному языку, то ППФ описывает обычное предложение общего вида.
1. Термом является либо константа, либо переменная, либо кортеж из n термов, перед которым стоит функтор.
2. Предикат - это кортеж из n термов, перед которым стоит предикатный символ.
3. Атомарный предикат является логической формулой.
- Если F и G - логические формулы, то (F); F,G; FÚG; ù F; F®G; F«G - также являются логическими формулами.
- Если F(X) - логическая формула, то оба выражения ("Х) F(X), ($X) F(X) является логическими формулами.
- Все результаты, получаемые повторением конечного числа n1 - n6, являются логическими формулами.
Множество всех предложений, построенных согласно данным правилам, образуют язык логики предикатов первого порядка.
Воспользовавшись этими определениями, можно, например, предложение «все люди смертны» записать в виде:
("X) [человек (Х) смертен]
4.5. Логический вывод
Логический вывод - это процесс получения из множества правильно построенных формул (S) некоторой ППФ (s) путем применения одного или нескольких правил вывода.
4.5.1. Правило резолюции для простых предложений
Наиболее простой метод логического вывода использует только одно правило вывода, называемое резолюцией, которое применяют к логическим формулам вида:
факт: А
отрицание: ù (А1,..., Аn)
импликация: А В1,..., Вm,
где Аi (i = 1, n) и Bj (j = 1, m) - произвольные предикаты.
Рассмотрим наиболее простую из форм резолюции для случая всего лишь двух S = { S1, S2 } ППФ вида:
S1 (отрицание): ù А
S2 (импликация): А В,
в которых предикат А из S1 совпадает с предикатом А левой части S2.
В результате одного шага вывода из S1 и S2 будет получена новая ППФ вида:
S: ù B
На этом шаге вывода ППФ S1 и S2 называются родительскими предложениями, а S - резольвентой, которая получается в результате применения резолюции к S1 и S2.
Резолюция в этом простейшем случае соответствует правилу вывода modus tollens, которое записывается в виде:
|
ù B
и соответствует следующему умозаключению:
допуская, что: НЕ А и А ЕСЛИ В,
Выводим: НЕ В
В еще более простом случае, когда S1 - отрицание, а S2 - факт, т.е.:
S1: ù А
S2: А
применение правила резолюции даст резольвенту - пустое отрицание
S:
и означает противоречие. Данный шаг вывода может быть записан в виде:
|
и резолюцией является рассуждения типа
Допуская, что: НЕ А и А
Выводим противоречие.
4.5.2. Правило резолюции для сложных предложений
Реальные логические модели содержат значительно более сложные предложения. Так отрицание могут содержать несколько предикатов, так же как и правые части импликаций. Поэтому более общим является случай, когда родительские предложения имеют вид:
S1: ù (A1,...,Ak,...,An)
S2: Ak (B1,...,Bm) (где 1<k<n)
Здесь некоторый предикат Аk из отрицания S1 совпадает с предикатом из левой части S2. В этом случае шаг вывода заменяет Аk в S1 на правую часть S2 и в качестве резольвенты получают отрицание
S: ù (A1,..., Ak-1, B1,..., Bm, Ak+1,..., An)
Данное правило проиллюстрируем содержательным примером.