Можно определить метки типов, используя так называемый Аристотелев подход, - через род (genus) в различие (differentia). Тип определяется исходным типом род и высказыванием, называемым различие и отделяющим новый тип от исходного. Например, Посылка - «событие (род), которое происходит, когда два человека, отправитель и получатель, обеспечивают перемещение предмета по почте (различие)». Формально:

Тип Посылка (х) есть (род)

Конкр(х, событие)

(различие)

Определение типов можно формализовать с помощью л-выражений. Пусть t -метка типа, лxF - л-выражение. Тогда тип t(x) есть F, где тело F этого л-выражения является различием метки t, а t(x) - её родом. На следующем рисунке приведено определение типа ресторана с использованием концептуального графа.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

30. Язык Prolog. Операторы. Синтаксис операторов

Напомним, что функциональный терм - это имя функции с аргументами в скобках. Само имя функции представляет собой нечисловой атом. Вообще же нечисловой атом - это функциональный терм без аргументов. Любой терм можно представить в виде дерева, корню которого приписано имя внешней функции, а ветвям соответствующие наборы аргументов. Например, терм f(x, g(y,z)) задаётся следующим деревом:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Такое представление является канонической формой: она не зависит от способа записи термов. Каноническую форму полезно бывает использовать в тех случаях, когда требуется уточнить представление термов (некоторые термы могут быть записаны многими способами). В частности, для термов с одним или двумя аргументами функциональное обозначение можно заменить именем операции, причём имя функции-операции записывается как унарный префиксный (или постфикный) оператор, либо как бинарный инфиксный оператор: ор1 с а ор2 b вместо ор1(с) ор2(а,b). При этом именам функций-операций (ор1 и ор2) надо придать статус операторов с приоритетом. Очевидно, что выражения а ор2 b и ор2(а,b) задают один и тот же объект:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Новые имена функций и предикатов можно записывать в виде операторов. Например, a+b*c и +(a*(b,c)) один и тот же терм; его дерево выглядит так:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Приоритет «+» ниже, чем у «*» (как обычно). Подчеркнём, что a + b * c - терм Пролога, а не числовой оператор, описывающий процедуру вычисления.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

31. Прототипы. Схемы и схематические кластеры

Определить какой-то тип можно ещё путём демонстрации нескольких примеров индивидов «некоего типа» и утверждая, что всё, чем похожи индивиды, относится к обсуждаемому типу. Прототип - это конкретизация типа или, иначе, типовая конкретизация. Метод прототипов описывает скорее типичного индивида некоего класса, чем произвольного представителя этого класса с набором характерных свойств.

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

Схемы и схематические кластеры

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

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

· Канонически графы имеют семантические ограничения, представляя нечто «семантически корректное» или «понятное».

· Схемы включают «специфические знания» об области рассуждений (экспертизы), представляя всё правдоподобное.

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

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

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

Каждую схему можно формализовать с помощью л-выражений действуя так как при определении типа посредством рода и различия. Пусть лxF - представляющее схему л - выражение. Формальный параметр х будет представлять концепт того типа, который требуется определить, а тело F укажет один из способов применения этого типа. Здесь F - логическая формула или представляющий её канонический граф.

Определим схематические кластеры с помощью л-выражений. Схематический кластер для класса t есть множество {лx1F1, … , лxpFp} л-выражений, где каждый формальный параметр xi принадлежит типу t и каждое выражение лxiFi - схема для типа t.

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

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

Прототип р для типа t есть л-выражение лxF со следующими свойствами:

· Формальный параметр х принадлежит типу t.

· Прототип р получается сочетанием (по правилу конъюнкции) одной или нескольких схем из схематических кластеров для t и ограничением (по правилу ограничения) части или всех концептов этих схем только концептами-совокупностями (без индивидов).

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

32. Язык Prolog. Арифметические действия

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

+ сложение

- вычитание

* умножение

/ деление

mod модуль, остаток от целочисленного деления.

Следующий вопрос - наивная попытка произвести арифметическое действие:

?- Х =1+ 2

Пролог-система «спокойно» ответит

Х = 1+2

а не Х=3, как возможно ожидалось. Причина этого проста: выражение 1+2 обозначает лишь прологовский терм, в котором + является функтором, а 1 и 2 - его аргументами. В вышеприведенной цели нет ничего, что могло бы заставить систему выполнить операцию сложения. Для этого в Прологе существует специальный оператор is (есть). Этот оператор заставит систему выполнить вычисление. Таким образом, чтобы правильно активизировать арифметическую операцию надо написать

?- Х is 1 + 2

Вот теперь ответ будет

Х=3

Сложение здесь выполняется специальной процедурой, связанной с оператором +. Мы будем называть такие процедуры встроенными.

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

?- Х is 3 / 2,

Y is 3 // 2.

ответ должен быть такой

Х = 1.5

Y = 1.

Левым аргументом оператора is является простой объект. Правый аргумент - арифметическое выражение, составленное с помощью арифметических операторов, чисел и переменных. Поскольку оператор is запускает арифметические вычисления, к моменту начала вычисления этой цели все ее переменные должны быть конкретизированы какими-либо числами. Приоритеты этих предопределенных операторов выбраны с таким расчетом, чтобы операторы применялись к аргументам в том порядке, который принят в математике. Чтобы изменить обычный порядок вычислений, применяются скобки (тоже, как в математике). Заметьте, что +, -, *, /, // определены как yfx, что определяет порядок их выполнения слева направо. Например,

Х is 5 - 2 -1

понимается как

Х is (5 -2) - 1

Арифметические операции используются также и при сравнении числовых величин. Мы можем, например, проверить, что больше 10000 или результат умножения 277 на 37 с помощью цели

?- 277 * 37 > 10000

yes

Заметьте, что так же как и is, оператор `>' вызывает выполнение вычислений.

Предположим, у нас есть программа, в которую входят отношения рожд, связывающее имя человека с годом его рождения. Тогда имена людей, родившихся между 1950 и 1960 годами включительно, можно получить при помощи такого вопроса:

?- рожд( Имя, Год),

Год >= 1950,

Год <= 1960.

Ниже перечислены операторы сравнения

X > Y X больше Y

X < Y X меньшеY

X >= Y X больше или равенY

X =< Y X меньше или равенY

X =:=Y величины X и Yсовпадают (равны)

X =\=Y величины X иYне равны

Обратите внимание на разницу между операторами сравнения `=' и `=:=', например в таких целях как X = Y и X =:= Y. Первая цель вызовет сопоставление объектов X и Y, и если X и Y сопоставимы, возможно приведет к конкретизации каких-либо переменных в этих объектах. Никаких вычислений при этом производиться не будет. С другой стороны X =:= Y вызовет арифметическое вычисление и не может привести к конкретизации переменных. Это различие можно проиллюстрировать следующими примерами

?- 1+2 =:= 2+1

yes

? - 1+2 =2+1

no

?- 1 + A = B + 2

A = 2

B =1.

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

Если заданы два целых числа Х иY, то их наибольший общий делитель Д можно найти, руководствуясь следующими тремя правилами:

1) Если Х иY равны то Д равен Х.

2) Если Х >Y, то Д равен наибольшему общему делителю Y и разности Х - Y.

3) Если Y < Х, то формулировка аналогична правилу 2), если Х иY поменять в нем местами.

На примере легко убедиться, что эти правила действительно позволяют найти наибольший общий делитель. Выбрав, скажем, Х=20 и Y=25 мы руководствуясь приведенными правилами, после серии вычитаний получим Д=5.

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

длина( Список, N)

Которая будет подсчитывать элементы списка Список и конкретизировать N полученным числом. Как и раньше. Когда речь шла о списках, полезно рассмотреть два случая:

1) Если список пуст, то его длина равна 0.

2) Если список не пуст, то Список = [Голова| Хвост] и его длина равна 1 плюс длина хвоста Хвост.

Эти два случая соответствуют следующей программе:

длина([],0).

длина([_| Хвост], N):-

длина( Хвост, N1) ,

N is 1 + N1.

Применить процедуру длина можно так:

?- длина( [a,b, [c,d], e], N).

N=4

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

N is 1+N1

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

Итак

· Для выполнения арифметических действий используются встроенные процедуры.

· Арифметические операции необходимо явно запускать при помощи встроенной процедуры is. Встроенные процедуры связаны также с предопределенными операторами +, -, *, /, // и mod.

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

· Значения арифметических выражений можно сравнивать с помощью таких операторов, как <, =< и т.д. Эти операторы вычисляют значения своих аргументов.

33. Рассуждения, использующие семантические сети

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

Возр(Жак_2, 45_лет)Адрес(Жак_2, ул_буля_7)

Сем_пол(Жак_2, холст) Конкр(Жак_2, проф_унив).

Эти предикаты указывают, что Жаку 45 лет, он проживает на улице Буля дом 7, холост и принадлежит типу профессоров университета.

Различные имена предикатов, связанные с узлами-индивидами образуют первое множество гипотез (некой теоремы). Например, вопрос об адресе Жака выражается предикатом Адрес(Жак_2, х). Этот предикат составит цель (заключение) теоремы, достоверные гипотезы которой - названные выше свойства Жака. Доказательство сводится к поиску конкретизации для х, позволяющей вывести заключение из гипотез. Проверка показывает, что такой является ул_буля_7.

Иначе обстоит дело с вопросом: «Какой диплом у Жака?», ибо мы не находим гипотезы вида Диплом(Жак_2, …)

Но если воспользоваться связью Конкр, можно получить подходящую гипотезу. Связанная с узлом проф_унив часть графа представима логической формулой:

Конкр(х, проф_унив) (Диплом(х, доктор) Место(х, унив) Это(х, проф) Это(х, сотр_унив)).

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

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

По-русски: Каково значение некоего индивида по отношению к некоторому свойству?

Логически: Свойство_i(индивид_j, x)

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

По-русски: Значение некоторого индивида по отношению к некоторому свойству есть …

Логически: Свойство(индивид_j, значение_i).

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

По-русски: Если индивид принадлежит типу t, то он имеет дополнительное множество значений по отношению к дополнительному множеству свойств.

Логически:

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

34. Язык Prolog. Синтаксис списков

Списки - это последовательности символьных элементов, которые сами могут быть списками. Эти структуры данных очень полезны и популярны в символьном программировании и в ИИ. В прологе для записи списков используют символьный атом [] пустого списка и пары с точками - бинарные функциональные термы. Точка - имя функции. Например, списками являются: [] .(a,X) .(a,.b[]))

Рекурсивное определение:

· атом [] является списком и представляет пустой список,

· если L - список и Т - произвольный терм, то .(T,L) - список с головой Т и хвостом L.

Например, список, состоящий из элементов a,b и с есть терм вида .(a,.(b,.(c,[])))

Однако для списков существует несколько лучший синтаксис:

· символьный атом [] представляет пустой список,

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

Например, [a,b,c], [эта, маленькая(шапка),[для, кюре]]

Непустой список допускает две эквивалентные записи «с точками» и «в квадратных скобках». Например, [a]?.(a,[]) [a,b,c]?.(a,.(b,.(c,[])))

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Представление деревьями - одно и то же для обоих обозначений (см. рис. 6.3). Обозначение [T|Q] представляет собой список с заголовком Т и хвостом Q. [A,B,C|Q] представляет собой список с заголовком А,В,С и хвостом Q. Эти обозначения, использованные для удовлетворения целей, годны для анализа списков:

? - [T|Q]=[a].

- - - > T=a, Q=[]

? - [A1,A2,_,A4|Q]=[прекрасная, маркиза, ваши, прекрасные, глаза]

- - - > А1= прекрасная, А2 = маркиза, А4 = прекрасные, Q=[глаза]

35. Сцепки. Фреймы и слоты. Явные фреймы. Функциональные фреймы

Сцепки.

Предположим, что мы хотим представить фразы

1: Жак пишет книгу.

2: Жак посылает эту книгу Мари.

3: Мари читает эту книгу (которую Жак ей послал).

В БД с этими фразами использовались конкретизации Жак_2, Мари_4, Посылка_8 и Книга_22 для ссылок в объектном языке на имена концептов метаязыка, упомянутые в этих фразах. Если расширить БД, то добавятся новые концепты и дополнительная информация о них.

Для использования знаний полезно собрать все факты о данном концепте в одно множество, называемое сцепкой (по-английски Unit). В нашем элементарном примере сцепкам Жак_2, Мари_4 и Книга_22 будут соответствовать логические формулы:

Жак_2

Пишет(Жак_2, Книга_22)

Посылает(Жак_2, Мари_4, Книга_22)

Мари_4

Посылает(Жак_2, Мари_4, Книга_22)

Читает(Мари_4, Кника_22)

Книга_22

Пишет(Жак_2, Книга_22)

Посылает(Жак_2, Мари_4, Книга_22)

Читает(Мари_4, Кника_22)

Фреймы и слоты.

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

Посылает(Жак_2, Мари_4, Книга_22)

Преобразуется в произведение бинарных предикатов

Отправитель (Посылает, Жак_2)

Получатель(Посылает, Мари_4)

Объект(Посылает, Книга_22).

Концепту «посылает» соответствует следующий фрейм:

ФРЕЙМ

Посылает (объект)

Отправитель Жак_2 (слот_1)

Получатель Мари_4 (слот_2)

Объект Книга_22 (слот_3)

(атрибуты или (значения или

имена слотов) значения слотов)

Каждая пара (атрибут, значение) фрейма называется слотом или (имя_слота, значение_слота). Сам фрейм по-английски - slot-and-filter notation. В этих обозначениях различные слоты сгруппированы вокруг объекта, охарактеризованного фреймом.

Явные фреймы.

Мы знаем, что часто бывает полезно представление знаний с явным указанием всех ссылок. Именно поэтому мы постулировали в нашем примере существование вполне определенной Посылки_8. Фраза «Жак посылает книгу Мари» бинарными предикатами представляется так:

Посылка_8

Элем посылки

Отправитель Жак_2

Получатель Мари_4

Объект Книга_22

Следовательно, в процессе выявления ссылок можно не только дать явные значения аргументов и имена предикатов, но также имена, представляющие высказывания логических формул. Например, Посылка_8 - имя высказывания Посылает(Жак_2, Мари_4, Книга_22). Такой формализм называется явным фреймом. (по-английски case-frame).

Функциональны фреймы.

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

Посылка_8

элем : (элем_из посылок)

отправитель : Жак_2

получатель : Мари_4

объект : Книга_22

Форма «элемент_из» в слоте имеет имя «элем» для указания того, что описанный фреймом объект является элементом некоторого множества (в нашем примере это множество посылок). Определенный таким образом фрейм называется функциональным.

36. Язык Prolog. Представление списков

Список - это последовательность, составленная из произвольного числа элементов, например, энн, теннис, том, лыжи. На Прологе это записывается так

[энн, теннис, том, лыжи ]

Однако таково лишь внешнее представление списка. Как мы уже видели, все структурные объекты Пролога - это деревья. Списки не являются исключением из этого правила.

Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом []. Во втором случае список следует рассматривать как структуру, состоящую из двух частей:

1) первый элемент, называемый головой списка;

2) остальная часть списка, называемая хвостом.

Например, для списка

[энн, теннис, том, лыжи ]

энн - это голова, а хвостом является список

[теннис, том, лыжи ]

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

.( Голова, Хвост)

Поскольку Хвост - это список, он либо пуст, либо имеет свои собственные голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:

.( энн, .( теннис, .(том, .( лыжи, [] ) ) ) )

На следующем рисунке изображена соответствующая древовидная структура.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Заметим, что показанный пример содержит пустой список []. Дело в том, что самый последний хвост является одноэлементным списком:

[ лыжи ]

Хвост этого списка пуст

[ лыжи ] = .( лыжи, [] )

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

?- Список1 = [a, b, c],

Список2 = (а, .(b, .( c, []) ) )

Список1 = [a, b, c],

Список2 = [a, b, c]

?- Увлечения1 = .( теннис, .(музыка, [] ) ),

Увлечения2 =[ лыжи, еда ]

L = [энн, Увлечения2, том, Увлечения2].

Увлечения1 =[теннис, музыка]

Увлечения2 = [лыжи, еда]

L =[энн, [теннис, музыка], том, [лыжи, еда]]

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

На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть

L = [a, b, c]

Тогда можно написать:

Хвост =[ b, c] и L= .(a, Хвост)

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

L = [a | Хвост]

На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ «|», а после этого - список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:

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

Подытожим:

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

· Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде:

[Элемент1, Элемент2, …]

или

[Голова | Хвост]

или

[Элемент1, Элемент2, …| Остальные]

37. Рассуждения, использующие объектное представление. Паросочетание

Рассуждения, использующие объектное представление.

Объектные представления были введены фактически по прагматическим причинам. Эти представления часто связаны с вполне определенными классами проблем. Объектно-ориентированные языки (известнейший из них Смолток) характеризуются взаимопроникновением структур данных и процедур. Связанные с этими представлениями законы вывода, вообще говоря, лишены формальной строгости правил вывода логики предикатов. Концепция объектных представлений больше направлялась заботой об эффективности исчисления, чем стремлением к его полноте. Очевидно, можно было бы развить для них системы выводов, эквивалентные использованным в логике предикатов. Такой синтаксис был бы весьма громоздок, и его применение лишило бы объектное представление его прагматических достоинств. Вместо того. Чтобы покоиться на полном множестве законов дедукции, различные используемые в ИИ системы используют сокращенные версии классических законов вывода.

Паросочетание

Рассмотрим следующее определение.

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

Если наша цель построить язык запросов(query language) для извлечения информации из БД, то нужно более ограниченное определение паросочетания. Операция паросочетания вообще не должна быть симметричной в том смысле, что она связывает заключение (объект-цель) с гипотезами (объектами-фактами). Объект-цель «паросочетается» с объектом-фактом, если влекущая объект-цель логическая формула унифицируется с одним из сомножителей объекта-факта, представленного конъюнкцией гипотез и аксиом.

В терминах доказательства теорем это означает, что операция паросочетания может осуществляться тогда и только тогда, когда цель можно доказать из гипотез и аксиом.

Рассмотрим фрейм-гипотезу

Посылка_8

элем : (элем_из посылок)

отправитель : Жак_2

получатель : Мари_4

объект : Книга_22

Можно установить паросочетание этого фрейма-факта с фреймом-целью

z(x)

элем : (элем_из посылок)

отправитель : Жак_2

получатель : х

объект : у(х)

Фрейм-цель интерпретируется как вопрос: Кому Жак послал книгу? Паросочетание фрейма-цели и фрейма-факта приводит к подстановке {(z, Посылка_8) , (х, Мари_4), (у, Книга_22)}, которую можно интерпретировать как ответ на вопрос.

38. Язык Prolog. Некоторые операции над списками

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

· проверка, является ли некоторый объект элементом списка;

· конкатенация (сцепление) двух списков, что соответствует объединению множеств;

· добавление некоторого объекта в список или удаление некоторого объекта из него.

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

Мы представим отношение принадлежности как

принадлежит ( Х, L)

где Х - объект, а L - список. Цель принадлежит ( Х, L) истинна, если элемент Х встречается в L. Например, верно что

принадлежит ( b, [a, b,c])

и наоборот, не верно, что

принадлежит ( b, [a, [b,c] ])

но

принадлежит ( [b,c], [a, [b,c] ])

истинно.

Составление программы для отношения принадлежности может быть основано на следующих соображениях:

1) Х есть голова L, либо

2) Х принадлежит хвосту L.

Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе правило:

принадлежит (Х, [Х | Хвост] ).

принадлежит (Х, [Голова | Хвост] ) :-

принадлежит (Х, Хвост).

Сцепление (конкатенация)

Для сцепления списков мы определим отношение

конк( L1, L2, L3)

Здесь L1 и L2 два списка, а L3 - список, получаемый при их сцеплении. Например,

конк( [a, b], [c, d], [a,b,c,d])

истинно, а

конк( [a, b], [c, d], [a,b, а. c,d])

ложно.

Определение отношения конк, как и раньше, содержит два случая в зависимости от вида первого аргумента L1:

1) Если первый пуст, тогда второй и третий аргумент представляют собой один и тот же список (назовем его L), что выражается в виде следующего прологовского факта:

конк ([], L, L)

2) Если первый аргумент отношения конк не пуст, то он имеет голову и хвост и выглядит так

[X | L1]

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

? - конк (L1, L2, [a, b, c] )

L1 = []

L2 =[a, b, c];

L1 = [a]

L2=[b, c];

L1=[a,b]

L2=[c];

L1=[a,b,c]

L2=[];

no

Список [a, b, c] разбивается на два списка четырьмя способами, и все они были обнаружены нашей программой при помощи механизма автоматического перебора.

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

? - конк ( До, [май | После], [янв, фев, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек]).

До=[янв, фев, март, апр]

После = [июнь, июль, авг, сент, окт, ноябрь, дек]

Далее мы сможем найти месяц, непосредственно предшествующий маю, и месяц, непосредственно следующий за ним, задав вопрос

?- конк(_, [Мсяц1, май, Месяц2 | _],[янв, фев, март, апр, май, июнь, июль, авг, сент, окт, ноябрь, дек])

Месяц1 = апр

Месяц2 = июнь

Более того, мы сможем, например, удалить из некоторого списка L1 все, что следует за тремя последовательными вхождениями элемента z в L1 вместе с этими тремя z. Например, это можно сделать так

? - L1 = [a, b, z,z, c,z, z, z, d, e],

конк (L2, [z, z, z | _ ], L1).

L1 = [a, b, z,z, c,z, z, z, d, e],

L2 = [a, b, z,z, c]

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

принадлежит1( X, L) :-

конк(L1, [X |L2], L).

В этом предложении сказано: «Х принадлежит L, если список L можно разбить на два списка таким образом, чтобы элемент Х являлся головой второго из них. Разумеется принадлежит1 определяет то же самое отношение, что и принадлежит. Мы использовали другое имя только для того, чтобы различать таким образом реализации этого отношения. Заметим, что используя анонимную переменную, можно записать вышеприведенное предложение так

принадлежит1( X, L) :-

конк(_, [X |_], L).

Добавление элемента.

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

[X | L]

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

добавить(Х , L, [X | L] ).

Удаление элемента

Удаление элемента Х из списка L можно запрограммировать в виде отношения

удалить (Х, L, L1)

где L1 совпадает со списком L, у которого удален элемент Х. отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:

1) Если Х является головой списка, тогда результатом удаления будет хвост списка.

2) Если Х находится в конце списка, тогда его нужно удалить оттуда.

удалить (Х, [X | Хвост], Хвост).

удалить (Х, [Y | Хвост], [Y | Хвост1]) :-

удалить (Х, Хвост, Хвост1).

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

? - удалить (a, [a, b, a, с,a], L).

L = [b, a, с,a];

L= [a, b, с,a];

L= [a, b, a,с];

no

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

Отношение удалить можно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во всевозможные места списка [1, 2, 3] вставить атом а, то мы можем это сделать задав вопрос: «Каким должен быть список L, чтобы после удаления из него элемента а получился список [1, 2, 3]?»

?- удалить (a, L, [1, 2, 3] ).

L=[a,1, 2, 3];

L=[1,a, 2, 3];

L=[1, 2, a,3];

L=[1, 2, 3,a];

no

Вообще операция по внесению Х в произвольное месть некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:

внести( Х, Список, БольшийСписок):-

удалить(Х, БольшийСписок, Список).

В принадлежит1 мы изящно реализовали отношение принадлежности через конк. Для проверки на принадлежность можно также использовать и удалить. Идея простая: некоторый Х принадлежит списку Список, если Х можно из него удалить:

принадлежит2(Х, Список) :-

удалить( Х, Список, _).

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

Функциональные атрибуты

Атрибуты описывают множество характеристик связанных с функциями функционального фрейма. Атрибут не обязательно является конкретизацией некоторых данных вроде Жак_2; с тем же успехом он может быть функциональным выражением. Рассмотрим фразу «Жак посылает книгу Мари, а Поль получает письмо от человека, которому Жак послал книгу». Ее первая часть выражается фреймом

Посылка_8

элем : (элем_из посылок)

отправитель : Жак_2

получатель : Мари_4

объект : Книга_22

Вторая часть представляется фреймом, для которого некое функциональное выражение является атрибутом «отправителя»:

Посылка_9

элем : (элем_из посылок)

отправитель : получатель(Посылка_8)

получатель : Поль_6

объект : Письмо_3

Мари_4 и получатель(Посылка_8) - два разных способа представления одного и того же лица.

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

Предположим, что поставлен вопрос: «Посылала ли Мари что-нибудь кому-нибудь?», представленный фреймом-целью

z(x)

элем : (элем_из посылок)

отправитель : Мари_4

получатель : х

объект : у

Множество фреймов-фактов содержат Посылку_8 и Посылку_9. Так как получатель(Посылка_8) может получить значение Мари_4, то фрейм Посылка_9 получит Мари_4 в качестве значения функции отправитель. Ответ на вопрос даст паросочетание фрейма Посылка_9 с фреймом z.

С помощью подстановки {(х, Поль_6), (у, Письмо_3)} можно получить ответ «да, Мари отправила письмо Полю»

Автоматические рассуждения, использующие фреймы

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

Язык KRL - объектно-ориентированный, основанный на представлении знаний фреймами. В нем все знания описаны в терминах UNITS-KRL. Ограничимся двумя примерами:

[Путешествие UNIT Абстрактное

<SELF (Событие)>

<способ (ИЛИ АВИА Авто Поезд)>

<назначение (Город)>]

[Путешествие UNIT Абстрактное

<SELF (Взаимодействие)>

<визитер (Человек)>

<визит (Множество из (Человек))>]

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

Иерархические рассуждения, использующие фреймы.

Операция паросочетания аналогична унификации из логики предикатов. Можно также связать объектное представление с более мощными правилами вывода, такими как теорема дедукции.

Рассмотрим лишь частный случай одного нередко используемого закона дедукции, в соответствии с которым с помощью импликации приписываются свойства каждому элементу определенного множества. Речь идет о свойстве наследования, который мы уже рассматривали. Займемся иерархией, где типы «профессор университета» и «профессор» заменены соответствующими множествами. Концептуальный граф, окружающий узел Жак_2, представляется объектно и логически следующим образом:

Объектные обозначения

Жак_2

элем : (элем_из проф_унив)

возр : 45_лет

адр : ул_буля_7

сем_пол : холост

Логические обозначения (Факт)

Элем (Жак_2, проф_унив)

Возр (Жак_2, 45_лет)

Адр (Жак_2, ул_буля_7)

Сем_пол (Жак_2, холост)

Мы видели вопросы наподобие «Сколько лет Жаку?» или «Кто проживает по улице Буля дом 7?» представимы фреймом целью или логическим заключением:

Объектные обозначения Логические обозначения

(Цель)

· Жак_2

возр:х Возр(Жак_2,х)

· у

адр: ул_буля_7 Адр(у, ул_буля_7)

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

Далее рассмотрим вопрос «Какой диплом у Жака?», формализованный следующим образом:

Объектные обозначения Логические обозначения

(Цель)

Жак_2

дипл: у Дипл(Жак_2, у)

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

Объектные обозначения Логические обозначения

(Правило)

{х| проф_унив} Элем(х, проф-унив)

дипл: доктор (Дипл (х, доктор)

место: унив Место (х, унив))

Осуществим паросочетание и унификацию целей с правилами для получения новой цели

Объектные обозначения Логические обозначения

(Цель)

Жак_2

элем: Элем(Жак_2,

(элем_из проф_унив) проф_унив)

Эта новая фраза точно соответствует фразе «Жак - профессор университета», что является фактом. Ответ «Жак имеет степень доктора» также найден. Такой вид доказательства отвечает системе прямой индукции.

Если нельзя ответить на вопрос, рассматривая свойства индивида (Жак_2) или содержащего его множества (проф_унив), то обратимся к новому множеству (проф), подмножеством которого является прежнее. Подмножество профессоров университета связано с множеством профессоров следующим образом:

Объектные обозначения Логические обозначения

Проф_унив

элем: подмож в проф Подм (проф_унив, проф)

Рассуждения с умолчаниями

Используемые экспертами в большинстве областей правила лишь приблизительно точны и не всегда применимы. Многочисленные описания вида «все х имеют свойство Р» надо считать лишь приблизительно истинными. Например, можно говорить, что все птицы летают (за исключением страусов, пингвинов и т.д.).

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

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

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

Жак_2

элем : (элем_из проф_унив)

дипл : магистр

то паросочетание вовлекает унификацию (у, магистр) и ответ таков: магистр (Жак имеет диплом магистра). Наоборот, если фрейм-факт по Жаку говорит лишь, что он профессор университета:

Жак_2

элем : (элем_из проф_унив)

то механизм паросочетания использует фрейм

{х| проф_унив}

дипл: доктор

и ответ - доктор.

40. Язык Prolog. Декларативный и процедурный смысл пролог программ

Следует различать два уровня смысла программ на языке Пролог, а именно:

· декларативный смысл и

· процедурный смысл

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

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

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

Размещено на Allbest.ru