Технологии искусственного интеллекта. Представление знаний с использованием логики предикатов. Логическое программирование

Логика предикатов - это языковая система, которая оперирует с предложениями на естественном языке в пределах синтаксических правил этого языка. Язык логики предикатов использует слова, которые описывают:

· понятия и объекты изучаемой предметной области - термы;

· свойства этих объектов и понятий, а также их поведение и отношения между ними - предикаты.

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

Терм - это знак (символ) или комбинация знаков (символов), являющаяся наименьшим значимым элементом языка. К термам относятся константы, переменные и функции.

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

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

Функции (структуры) - последовательность из нескольких констант или переменных, заключенных в круглые скобки, следующие за функциональным символом (функтором). Пример: сумма +(1, 2). Функторы обозначают операторы, которые после воздействия на объект возвращают некоторое значение.

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

Заключенная в скобки последовательность из n термов, перед которой стоит предикатный символ, называется n-местным (или n-арным) предикатом, который принимает значения «истина» или «ложь» в соответствии со значением термов, являющимися его аргументами. Пример: является (ласточка, птица).

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

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

1. «не»

2. & «и», ∨ «или»

3. ← «если», ↔ «тогда и только»

Пример: является (ласточка, птица) ← имеет (ласточка, крылья)

Если использовать вместо констант переменные, делать утверждение не только о конкретном индивидууме, но и о всех индивидуумах из этого класса. Пример: является (Х, птица) ← имеет (Х, крылья).

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

Используя кванторы общности (∀ - «для всех») и существования (∃ - «существует по крайней мере одно»), иногда можно определить значения предиката не делая подстановок. Пример: (∀ X) [являться (Х, птица) ← имеет (Х, крылья).

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

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

1. Термом является либо константа, либо переменная, либо кортеж из n термов, перед которым стоит функтор.

2. Предикат - это кортеж из n термов, перед которым стоит предикатный символ.

3. Атомарный предикат является логической формулой.

4. Если F и G - логические формулы, то (F); F, G; F G; F; F G; F G - также являются логическими формулами.

5. Если F(X) - логическая формула, то оба выражения (Х) F(X), (X) F(X) является логическими формулами.

6. Все результаты, получаемые повторением конечного числа n1 - n6, являются логическими формулами.

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

Логический вывод - это процесс получения из множества правильно построенных формул (S) некоторой ППФ (s) путем применения одного или нескольких правил вывода.

Наиболее простой метод логического вывода использует только одно правило вывода, называемое резолюцией, которое применяют к логическим формулам вида: факт: А; отрицание: (А1,..., Аn); импликация: А ← В1,..., Вm, где А_i (i = 1, n) и B_j (j = 1, m) - произвольные предикаты.

Рассмотрим наиболее простую из форм резолюции для случая всего лишь двух S = {S1, S2} ППФ вида:

S1(отрицание): А; S2 (импликация): А ← В (предикат А из S1 совпадает с предикатом А левой части S2)

В результате одного шага вывода из S1 и S2 будет получена новая ППФ вида: S: B.

S1 и S2 называются родительскими предложениями, а S - резольвентой, которая получается в результате применения резолюции к S1 и S2. Резолюция в этом простейшем случае соответствует следующему умозаключению: допуская, что: НЕ А и А ЕСЛИ В, выводим: НЕ В.

Реальные логические модели содержат значительно более сложные предложения. Так отрицание могут содержать несколько предикатов, так же как и правые части импликаций. Поэтому более общим является случай, когда родительские предложения имеют вид: 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).

Рассмотренные выше правила применяются на каждом шаге вывода только к двум родительским предложениям. Вместе с тем описание любой области знания содержит множество ППФ.

В ходе логического вывода пользуются унификаторами. Унификатором называется множество присваиваний вида:

Θ = {X1: = t1,..., Xn: = tn}, где Хi - переменная, а ti - терм, применение которых к двум выражениям дает одинаково общие примеры.

На практике унификаторы определяют, сравнивая по очереди соответствующие аргументы предикатов и выписывая те присваивания термов переменным, которые сделали бы эти аргументы одинаковыми.

Решение задачи с использованием логического программирования разбивается на 3 этапа:

1. На первом этапе необходимо сформулировать наши знания и допущения о предметной области в виде множества ППФ.

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

3. Третий шаг выполняется компьютером, который пытается решить задачу, строя доказательство от противного. Он строит вывод сверху вниз, начиная с исходного отрицания, и порождает последовательность отрицаний D1, D2,..., D. Если может быть построен вывод, заканчивающийся отрицанием Dn = ∅ (противоречие), то этот вывод, называемый успешным выводом, сразу дает решение поставленной задачи.