ТипДетали

{(*» у) I (агGОперация). (Ж_дет_оп (г) = х) Л

(тип_опер (г) = ток_обр) Д

(кон (г) > 20) А

(3"&Деталь). (тип_дет (а) — у) Д

(№_ дет (и) = х)> 24

(22)

dom (ТипДетали) «{ст_мл, вал-шест]>, dom (ТипСтанка) ={ток, фрез} dom (Времн) ={0,1,2,...}, dom (T) ={o, i}

Рис. 1.1

дет

Рис. 1.2

местные функции и предикаты. Чтобы представить в бинарной модели много­местные функции или предикаты, нужно прибегать к искусственному приему, вводя дополнительные имена сортов (классов). Так, «-местную функцию f: AiX ХА2Х... ХА_п-*~В можно заменить на (2я+1) одноместных функций f;C->*B, gj-.Aj -+С, hj: С -*-А_} (1</<я), где hj~ функция проекции декартова произ­ведения на /-ю его компоненту, ^- — функция вложения /-й компоненты в де­картово произведение.

Имеется тривиальный прием перевода л-местной функции в (я-И)-местный

предикат: f(x_h х₂,...,х_п)=у тогда и только тогда, когда предикат }{х_х..... х_п,у)

истинен. Благодаря этому «чистое» (т. е. без функций) исчисление предикатов эквивалентно с точки зрения принципиальной выразительности многосортному исчислению предикатов.

Реляционная модель данных, естественно, переводится в «чистое» исчисле­ние предикатов. Рассмотрим снова пример реляционной схемы R, который свя­зан с предметной областью «механообработка». Получаемая «чисто» предикат­ная модель данных, обозначаемая Q, составляется из двух частей: структурной части Q' и логической части Q". Структурная часть соответствует «шапкам» таблиц-реляций: Q'= {операция(№_детали, №_станка, Начало, Конец, ТипОперации),

деталь (№_детали, ТипДетали), станок (№_станка, ТипСтанка)}. В логическую часть включаются предложения, выражающие ключи и функ­циональные зависимости. Например, в Q" записываем предложения

U= V: — операция (.V, У, U, _,_), операция (X, Y, V, _, _), (23)

U=V: —операция (X, У, _,£/,_), операция (А', У, _, V, _), (24)

U~ У '— операция (X, У_, _, U), операция (X, Y, _, _, V), (25)

U = V: — операция (—., X, ^, _, U), операция (_, X, „, _, V). (26)

Предложения (23)—(25), взятые вместе, выражают то, что (№_детали, №-стаика) является ключом отношения «операция», а дредложение (26) вы­ражает то, что ТипОперации функционально зависит от №_<ст в отношении «операция».

В предикатной схеме Q использовался синтаксис языка логического прог­раммирования Пролог [Клоксин и др,, 1987], идеи которого были выдвинуты в [Kowalski, 1974]. Согласно этому синтаксису имена отношений, функций и констант пишутся малыми буквами, а переменные начинаются с заглавных букв. Знак:— является символом импликации, но записанной справа налево <<-); запятая служит символом конъюнкции. Предложения (23)—(26) явля­ются примерами так называемых правил. В правилах неявно предполагается,

26

что все переменные связаны квантором у. Таким образом, например, предло­жение (23) в обычной нотации выглядит гак:

№_ детали, уУ&№_ станка, yt/еНачало, уК^Начало, yZl e Конец, у22е Конец, yZ3& ТипОперации, у24&ТипОперации).

■операция (X, Y, U, Zl, Z2) Доперация (X, Y, V, 23, Z4)->£/= V.

Экземпляр предикатной схемы Q представляется списком так называемых фактов, т. е. атомарных константных формул. В данном примере имеем такой экземпляр (предикатную базу данных F):

деталь(1, ст-вал). деталь (2, ст_вал). деталь (3, вал-шест). деталь(4. вал-шест), станок(I, ток), станок(2, ток), станок(3, фрез).

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

ответ [X, Y): — операция (X, V, Z, V, ток-обр), £/>20, деталь (X, У). (27)

Вычисление запроса инициируется предложением? — ответ (X, Y), которое фор­мирует цель: «Найти факт, унифицируемый с ответ (X, У)». Делая попытку до­стижения этой цели непосредственно, интерпретатор начинает просмотр базы фактов F, но, не найдя подходящего факта, обращается к базе правил, пыта­ясь найти такое, которое имеет «голову», унифицируемую с ответ (X, У). Та­ким правилом является (27), из которого получается цель:

«Найти факт, унифицируемый с операция(X, V, Z, U, ток-обр)». (28)

На этот раз цель удовлетворяется при подстановке X=l, V=l, Z=5, Z=12 (см. второй факт в F). Теперь формируется цель, состоящая в выяснении не­равенства 12^=20, получаемого из второго атома «хвоста» (27) при найденной подстановке. Так как это неравенство неверно, подстановка отменяется и ин­терпретатор снова пытается удовлетворить цель (28), производя поиск в F с точки возврата. Цель удовлетворяется при подстановке Х=2, V=2, Z=10, U '=17 (см. четвертый факт в F). Однако опять получается неверное неравен­ство 17^20, и процесс поиска возвращается с отменой подстановки и выдви­жением цели (28). Шестой факт из F удовлетворяет этой цели с унифицирую­щей подстановкой ^=3, V=\, Z=16, £/=24. Так как неравенство 24>20 варно, то формируется очередная цель: «Найти факт, унифицируемый с де­таль (3, У)», которая удовлетворяется при подстановке У-вал-шест. Поскольку цели, ассоциированные с «хвостом» правила (27), удовлетворены при подста­новке ЛГ=?Д К=1, Z=16, £/=24, У=вал-шест, то получим вычисленный факт ответ(3, вал-шест). Процесс поиска продолжается по той же схеме. В резуль­тате имеем еще один вычисленный факт ответ(4, вал-шест).

Итак, основанная на «чистом» Прологе предикатная модель Q[}F характе­
ризуется следующими чертами: (1) структурная часть Q' схемы Q составля­
ется из предложений простейшего вида, задающих схему отношений; (2) логи­
ческая часть Q" схемы Q составляется из правил, т. е. предложений вида
В: — Аи А_{2.............} А_п, где В, А/ — предикатно-атомарные формулы; (3) кроме де­
кларативной интерпретации («если одновременно истинны все А), то истинно
В») правило имеет простую процедурную интерпретацию («чтобы достичь це­
ли В, нужно одновременно достичь все цели Л/»); (4) достижение нескольких
целей осуществляется с помощью механизмов унификации и поиска с возвра­
том; (5) запрос к базе данных F записывается в виде правила ответ (Хи Хг,—
...,Х_р): — Ai, А₂,...,А_п, а вычисление запроса инициируется предложением

?—ответ(*_ь Х_{3.............} Х_Р).

27

Краткая история и современные тенденции

Исчисление предикатов было создано усилиями Г. Фреге (1879 г.), К. Пир­са (1885 г.), Дж Пеано (1908 г.), А, Н. Уайтхеда и Б. Рассела (1922—1927гг.) для формального описания математического знания в связи с попытками ре­шения проблем основания математики. Формальная семантика исчисления пре­дикатов, основанная на теоретико-множественных моделях, была предложена А. Тарским (1930 г.). Полная система дедукции разработана Д. Гильбертом, П. Бернайсом и В. Аккерманом (1922—1928 гг.), а ее полнота доказана К. Ге-делем (1930 г.).

Г. Саймон, А. Ньюэлл и Дж. Шоу написали в 1957 г. машинную програм­му «Логик-теоретик», выполняющую поиск доказательств тавтологий в аксио­матической системе Рассела — Уайтхеда для пропозиционального исчисления. Первая серьезная попытка построить машинную систему для поиска логическо­го вывода в исчислении предикатов была предпринята в 1958 г. [Ван Хао, ' J970]. Важные результаты для создания эффективных систем логического вы­вода революционного типа были получены в 1963 г, [Девис, 1970] (§ 2.4).

Первая вопросно-ответная система, использующая дедукцию резолюцион-ного типа [Green, 1969], является прообразом современных «интеллектуаль­ных» информационных систем (систем дедуктивных баз данных и баз зна­ний). Рь работка и применение логических моделей для баз данных и баз зна­ний описаны в [Gallaire et al., 1978].

В [Hewitt, 1971; Kowalski, 1974] была замечена двойственность семантики импликации: имлликация рЛЯ~*-^г имеет, с одной стороны, логическую трактов­ку (так называемая «материальная импликация»), с другой стороны, операци­онную (или процедур а л ьную) трактовку («если вы хотите установить г, пы­тайтесь установить р и q»). Импликации с универсально квантифицированными переменными (связанными только кванторами V) называют также хорнов-скими предложениями. Благодаря указанной операционной трактовке последо­вательность хорновосих предложений можно рассматривать как некоторую недетерминированную программу. Детерминизация процесса вычисления по та­кой программе достигается поиском с возвратом. Эти простые, но фундамен­тальные идеи были положены в основу языков логического программирования (Плэннер, Пролог и др.).

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

Поиск по сайту: