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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ Институт автоматики и процессов управления.

-Г

/

На правая рукописи

АРТЕМЬЕВА Ирина Лэонидовна

РАЗРАБОТКА И ЙССЛ8ДОВШЕ СКСТЕШ ШООПРЕДВЛЕКНОГО ВЫВОДА ДЛЯ ДЕКЛАРАТИВНЫХ ПРОДУКЦИЯ

05.1а 11 - математическое -и програмшюэ

обеспечениз Ешкслителышх малин, кошшзксов, систем и сетей

Автореферат

диссертации яа соискание ученой степени кандидата технических наук

Владивосток - 1992

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

Научный руководитель - доктор физико-математических наук

А. С. Клоазоя

Официальные оппоненты - доктор технических наук ■

А. Л. Синявский

кандидат технических наук Е К. , Бломроз -'

Вадуцае предприятие: Институт систем ин4орматики

Скблросого отделения РАН (г. Новосибирск)

Защита состоится "_"_ 1992 г. в _часов

на заседании Специализированного совета К. 003.60. 01 в Институте затодатики и процессов управлении Дальневосточного отделения. РАН но адресу:

690041 , г. Владивосток, ул. Радио, 5

С диссертацией жшо озиакошться в библиотеке Института аыоиатики и процессов'управления ДВС РАЕ

Автореферат разослан "_"_;__1992 г.

УчольД секретарь (Зшгцкшшниров&нного совета

к. т. :и с & И. Коган

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Слетам продулся (ОТ) ппгрсяоэ

рзспростряпо1.г0 К'1;С срЭДОТБО ПрЭДСТВЧЛЭЙЖ! СЯЕПЯ (ГО) 3 £-Г?(?ПврТЯНХ системах (ЯС). Прл ясшшьзоскеи CII егигяя ярздотег^'пггея ь виде comtynaocTTi прогкл, сгаснвавдкх взвамосвязи тана 'ест-то* кздяу л.ош!«!и пргггзтаой области (ПО). В настоящее Ергш ре^-ргбатг.» ряд Р0СЛПЗЗШ1Й СП, G ТОМОЯЬИ »OTOPZ г"ЯЛ2;Пг »'ЛЭГЛО tyzssxsszs 20 (ПЗС)

Огя"." 'тз классов СП язязкдся дояясрзтвггсад ' ягозтъгл, осиокт достзэт-ство Ktjropîix состе::.: л «сч, что для ras tíc;/íc-r?yer eooöxo-даость указать, как ксгяртий Фргп.'сп? catrín .здг^ои быть ис-ПОЛЬЙОГОТ II» "теп C-TW-λ 0iíí>r;nf"«r*cetca пшохковвисэ

ОДНЛЕ ТЭХ ""! "i*".MHZ

К socroFur- • -.^кглЗ -^"""Т"" детоеггэкмо

лг'злст,';п"я^ь п ы: • r-.-.itpî^-лзгтап-;, ¡пгетасть я tnwanswy д?кпшс и агяаЗ. ^"".onurcaiexi ггтау/л^г^зтл- -X r..z?.ix??t а СП

rnvtr?; з штора га г.гзлч Р'^л^.'ггтр^^^гся ♦^йязшшз

(Cj^i:! газерзп» у rxrs тго ^cre.urn--'',.-'1--; логлс-ст-

взг.-ял т^мяозг»гл2:). 5 ггел сс-г¿ о a гс^гла-.

гжзж^г.з чгз^еггге (rsvrс.гг'лнзя (мэ-рд), когетт*! гсгв^^кяуякм n s r*cro?cjr:j Cx^'ors ск?г»7,олэш:осги :: гг.:; eye.':-,.;••. •":;•. " "г л пзготеое-хн, рнсло-

rrsr^íCKTÍ и г.Д. ПрЗ^'Ь'Д ЯОГСГПГЗ гэр, С^З^итУХ С rVn3;TKÛÏîIS

rCSZ22î, ргЗЗСТПТЛ срЯДЯ SîOïCGLt готло но?-

ггл C^tyr? Stîîco, ' ïoqpiîî "оч-зт-ма

л ГрЗХГЗ. '

Л ¡-як» тем caCTacrMírrcj rrep пользуется „тс-тпгс-

кггссг» тзр-апя (бэттл тс:сгч7Ъ з stch сяггаа, что пско.пьпуохся плтзегт^ягая стг'-'-ь ); "йо^кско", ".'¡огля бить",

"рзтж^сттз", ель", ^-.■^озггзйЮ'' я т.л. В этом случаэ в ус-

ггпп ^rjxciciCTîSJ зеь*.*ггг-г:0тся crrr'ov .чор вхоасгг

дгг^я, а г. - ßEsruiriT к?р стссдгг*»« хгшшд.

С'гтг.-0 гат;г?2стгспггз, так я ткпостшягауэ кодола неокродо-¿m-z-ar.i «фудгга стаодьзеззть с гфайгпч'зсгсо: гф;и...,г'ею!ях, nocsc/xuv ixcst-icroaEirsje в ^ыпвсииесчиэ K?pi яаялвтоя суй-ектшяаам, зк.:т гарвг EOOICTBO ткэшогят isicne ousmett, я, кроьй птего, созультзти Ба«хжз кзгяятса tpyjs» шггервретпрчгегадлв № шльзопателл. Это сг:-',r;."irpv'öT aasLU-stasis гсискя НОЕСДС-Й '.фздстаплла».'! нвопрвдол^нпс"-;!

данных н зншшй в СП.

Не лью диссертационной работ« йвляэгся разработка системы докла-рагшзиух продукций, которая "позволяла Ca экспорту задавать объективную 'информация о неопределенности данша к знаний, а пользователю получать понятно штерцрзтаруеалзэ результаты вывода в SC.

Для того, чтобы удовлетворять. эяеи свойствам, СП долша быть основана на хорошо иктерлрэязруекой ко дели представления неопределенности. Одной из таких имдэлзй является недоопроделонкая .(НД) модель, предложенная Ä.C. Нараньяна. Для представления неопределенности двгпшх е этой ШД8ДИ используется аппарат ЦЦ объэктоь разлач-1шх типов. При оирэделшаа Щ объектов задается информация о свойствах ja значений (игла 1Щ ситвгия)„ а сами значения (денотаты) могут бить не задана. Прснзсс вывода/вачасденай в рассматриваемой модели состоит в уточнении ВД сиачешй на основе опродзляеиых моадг объектами соотношений. В настоящее время неслодоваяы различные типы -ВД объектов-и разработан ряд систем, рещавдих вычислительные и ло-гтосте задачи с испаяьзашяех ВД объектов. ВД модели ллкены субъективности в представлении нзопродэлвнности, имеют простую интерпретаций результатов, допускает организацию дедуктивного вывода. Однако вопросы использована! 1Щ моделей а СП к, особенно, в систеках декларативных продукцкЗ (СДП) к настоящему времени пе исследованы. В диссертационной работе 1ЭД иодоль A.C. Иаркньпшг применяется как средство моделирования Еэопрвдэлвнности в системе дакпэоатшншх. продукций.

Для достижения поставленной цели в диссертационной работе необходимо решить следущио оадэта: ■

- разработать модель декларативных ■ продукций, с недоопреде-. ленными объектами;

- определить на этой модели процесс йжода как процесс уточнения НД значений объектов;

- исследовать сеойотвэ класса систем продукций; определяемых разрабатываемой моделью;

- разработать.мотода реализация НД логического вывода;

- на основе разработанных методов выполнить реализацию система продукций с НЦ объектами. -

У!:]УУная_нов'лзнэ работы состоит в следующем:

- тершо разработана модель декларативных продукций с ВД ооъ-иктада различных классов, в том числе КД функциями к НД отно-а&шитаи;

- определен пооцесс ВД логического вывода как процесс уточ-

пения НЯ модели, вшювняяакй два тсгпз тапюдз: •юх.'.ктет» верися-' тов 1Щ значений: сбьзг.тсз есэх классов; расагареанэ области определения НД звзчеиай НД фулгсттай и ВД стнояэтгпй;

- исследовала своЗстоа процесса НД дэгачоского п?шода: ыопо-кяшость, константность и конечность;

- разработаза матог?! реализации СДП с 1Щ ейгсктс-гп, орган тирозашшэ на коотчляцап, в том шслэ ядд правил и уиюр'иепьй система декларативен продукция с 1ГД сйт,м;та:з впздвпа кс-яокпчос-

коя фортза и совокупн^мъ Пр30бр83СВ5НйЗ з зтоа фор;э;

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

Прзктпчоская ценность рзбатц вакла-гезтся в следущем:

- предложен иозий кш систем поядериш 1Щ логического швода: срода НД яоппоского шзода;

- на основа .ргзработгешш: катодов создан язячсккей гаочессср (ЯЛ) РШРО-1. перзносгаай; на разлэтшз типа ЗЕМ.

ЯП РЕПРО-Х попользуется согрудгпзса'Я 1ШП ДВО РАН, стулентсмл и преподавателям! 'Базовой. ксф>дра прогрекжюго обзстачевяя ЗВУ ДВГУ пря КАПУ ДВО РАН._Кро;ло 5гого, ЯП РШЮ-1 ппдрзп и используется в других организациях. О сокоаьа ЯП Р£ПК)-1 разработан гибкий компилятор бз в СП, а тйкйэ ряд- пэс в рззлпшх по.

Апробация габота. осно&жо. шшмяния дяссэртацк! доклздыва-лпсь п обсуздалась на Всесоззяой гкзкфзронцгы "¿ктуахышв проблемы спстеьгаого програ?гТ.С!ров£Шл" (Таллинн, 1930 г.), Научно-технической сколе "Новые информационные технологии" (Одесса, 1990 г.), II Всо-сокгной кон$ерокщ?и по искусственному гателлзкту (Уияск, 1390 г.), Всесоюзной научно® .конференция "¡йтголязктуалззащш састом управления" (Баку, 1991 г.), V ВсесОгешсГГ конференция "Система баз детали и знаний" (Львов, Г991 г.), ЕсэсогзгкпТ научяо-гграгстнчоской конференции "Гкбрадшо интеллекту алкше слстеки" (Терскол, 1991 г.).

Основ1шэ результат опублжованк в II работах.

Структура и объем работа. Диссертационная работа состоит га ^ведения, четырех глав, заключения, списка литературы, включаисего 103 наименования, и приложения. Работа содерют 147 страниц тексте., 9 рисунков.

'6

СОДЕЕШШ РАБОТЫ

Ik2íi3fi_i:¿jli. Д-íc^jрхац-uii еэдарет? обзор литература. В ней приводятся сярсдавлане СП', язахгнруьхся гашгсвсгвзшшв и качест-вэптао модели прздставдопгзл ^определенности в СП, а тамге сшасава-ercíi недоэпродвлеиаая кодс-ль A.C. НарвньяЕи.

üil^fflSíS-Eá&isl даосврмеда оярелелждса догааративзые продук-ШГ.5 с ВД объектами, 1®ляяай5.-л дсю^раг.шно-процедурноП (ДП.) моделью цродстаблешя гпаяай? JW шдэль определяется как vpo&ta: шо-хество К код алей £ратштов из ьлсотороИ ПО (состоянии Casa

оканий (БЗ) ПО), кюаэс'й» £ шделей фрагментов действительазстя состояний база дашшх (БД)) и отшгаикэ Л'соотвототвпя мезду ваг®.

Со стоящие оазя знят;Я. Состожш БЗ к é К определяется парой Je = <0, М>, где о - ¡.аскостьо (здоеь и шз;з оудем иметь в виду конечные множества) pffiiotn-ß! объектов» 'J - описание декларатив-..во-процздурной БЗ (шюсзство сЕЯсгшгЗ кодулой БЗ). Элементы шо-кветва 0 содаркат Екфэр^зщио о рз&ягшз объектах- ПО (моделируют объект ПО), ä определяет щзоцесс рзссуищеяня (ПР).

Кгиюй элемент о е О 'Зэдаагся -шкиркой <ncnie(o), äeo(o), üX(o), ZO(o)>, где плгае(о) - пая одшгга, äac(o) - описатель объекта, üXfoj - описатель опрадэяэЁзоста аханий об объекте, ¿OfoJ -ошоатоль значения объекта, прз»сы 20(0} шеэт отсутствовать.

Идя объекта - это термин ПО. Ibaca всох объектов различии.

Описатель объекта определяет tes'шдода объекта ПО; в модели ¡-гадай обгект имеет класс с (а) ОЫ U ÜH, СИ » ("неструктурный", "логическая", "указатель", "структурный".?, йг«Г'Фуа5сдан,' "ошоиз-кае".!. Ecjffl'cCoj - "неструктуршай'*,'тр объект.ПО является признакам, моделируемым числом, строкой, абстрактным дабо шзмоническш обоз-эначением. Тип модели опрздаляэтся в этой случае сортом объекта, идавдим одно из значений;'целый, вэвественннЯ, строковый, интервальный, абстрактный или ;скалярный. Если с"логический", то объект ПО являатся признаком н его модель» является логическое значение, опроделящее присутствие (истина) либо отсутствие (ложь) признака. Если а(о; « "указатель", то объект ПО является ссылкой на другой объект, который, в свою очэредь, также может быть ссылкой. Если о(о} = "структурный"» то обгект ПО является либо упорядоченной совокупностью сшютюдоих объектов, либо упорядоченной совокупность» 'разнородных ооъоктоз. Если с(о) = "отяогюнш" и число аргументов отиоиэаия рвано I, то объект НО является множеством однородных ок.ек'соа (понятием), в противном случае - отозванием между носколь-

кими объектами, модели которых определяются списателяга аргументов данного оишенпя. Наличие класса указатель у аргумента позволяет вводить отношения, у которих аргумента могут сить сшлкклп на неко-торио другие объекты. Если с(о) - "функция", то объект ПО определяет соотвэтстпио шхщу некотором ¡тбороч объектов (аргуиентода &унк~ ции) и уругш объектом (результатом функции). Модель аргумента определяется описателем аргумента, кгдэль результата - списатол'зм результата. Как аргумент, так и результат футшгя могут бить ссцлксЯ на некоторые объекты.

Все объекта д-элптсл на точкиэ я похосираг^тше, кпх объекта определяется Ж(о). 2начмгае «wins обмктеэ (лзпотв?) пэ пзкэггяот-ся в IP, а для 1!Л оГлэктсз в IIP угстгется гокоторая síssocrnsn информация о дэнотатэ. Для 1Щ сбъттоп, kzscs поторих яз ОЫ, к началу Ш' асявт Сзть известно пэсяозакэ вгрзептов зпочоккй. сроет которых пихаются дзяотйт. Для оСъггггоэ. пйззс которих пз FH, Бозмгпм тгл типа нздоопраямзвпоста ШШ>.

Опесзтзяь гтотояяя обгокта zote» олрэдаляэт дал точного обьск-га его денотат лгбо слсссб игтеягкая дзпотота, а для ¡П обгегста -либо совокупность воок-сглазс вараеятеэ, ердп иотораг язаддится дэ~

еотст, mío с0б0п?ш10с?ь еозиоззих еерлилоз c10cg60b ьычпзлзнял

деаотатз <з этоа случза. объект вааывгзтся вдешелагдог).

Овасвдю яовягрэтввно-щедеязртоа БЗ сосговт сэ описг-яяя подудя упраапэшга (ГС) н описания ссгоггуш-остп иодулаз БЗ í.'í^J, ксториэ бввоот процедурявкя ."Ибо яолпэстагх.

Опвсандо стдуля управлеязп ¿'С есть ршеапяэ соотвэтстпуюаого алгоритма, записанного на плгорчгелпсскс:i «гаке (АЛ) я енрэдзлягэю-го послэдовательность вшюлнолия процедура п лопткняшх г,модуле Я.

Опиесапэ модуля БЗ Bj - зто я:бо -.этзэркэ <123?^, £?Pj, Oj. L0G^> (логический уодуль), либо чотазряа <I2?j, EKPj, Ojr ¿!Oj> (процедурный модуль), где IEPj - кногветпо описснпЯ Екпортяруеких объектов, EXPj - множество ошсашй эасгирткрувках объектен. -Пйоазство описаний имен локальных сбъокгоз модуля, WGj- списание модуля декларативных знгспШ ШЯЗ), AUJj ~ оппсскпэ алгоритма решения подзадачи. Имена локальных объектов из О у а та'сго таена импортируемых обгоктов нз IMP j обрззувт шюгаство 03j.

.отшеанио wmop-nipyewix объектов 14Pj опред? -mr глоамь mix объектов, информация о которых требуются для вшюлп?1тя i,гаду ля. При определении гатортаруемого объекта могут бить гсш-энош хэрактп рпстики его педоопроделошгости.

Описание экспорпфуедах об>ектов 711', определяет вмккг гло-

бальных объектов, информация о которых, полученная при выполнении мои ля iíj, становится доступной вйз атого «оду ля •

Алгоритм решения подзадачи AI£j описывается средствам М, расширенными функциями работы с объектами из ОН у

Описание модуля дакларатшшх знаний WGj есть четвзр::а кстч-гш югоявств LOCj =» <R]LBj, STATIj, SfAT2j. STAT3j> (индекс J в обозначении множеств далее будем опускать, когда все иновества относятся к одному к тому ке кодули).

Элементы :ск«сества ШШ определяют взаимосвязи типа "если-то" мовду значшмяш объектов. Эломэнтаз множества WIS являются правша rule вида если' Q(X) то Ut'(Xf') & V£'(X2') & ... & Un'(Xn'J, гда п с NAí, Q(X)- формула, И^(Хг'),..., ar'(Хп') - простыв формулы, в X, '.....-X ' - tóiosocwja переменных. Условие правила Q(X)

является логическим выражением, состезленныа из простых формул с использованием киаков логических операций "и", "или" и знака отрицания, Кокшшкрлшм ияохмтелем следствия U1'(Xf ')&... & ип'(Хп'> является простая формула.

Элемента шакества STAT1, STAT2 в STAT3 опроделяьх условия, которым дЪляш удовлетворять ааачанвя объектов. Элементами кно-кеетва :JTAT1 яглявтоя утверждения otatl вида Q(X), где Q(X) - конъюнкция простых формул, Л мнокеогао пэреыанжх.

Элементами множества STAT2 являются утверждения atat? вида Q}(Xt) QR QJX¿) OS...OS QlíXl), гда OR обозначает операции "или", при любых 1=1..,1 Ql(Xl) - конъзисщия простых формул, Xt - кно-K8CTBO переменных. Утварзденио atatS определяет условие, состоящей го совокупности возмошнх вариантов.

Элемон'тля множества STAT3 являются утверждения síot3 вида Qt(Xt) £OR Q2(a2) XOR...XOR Q^XJ, где XOR обозначает операцию "ясклкчаицэв ила". Утверздепие state определяет условие, состоящее из совокупности возможных альтернатив.

Определим состав простых формул "модели., Простыми формулами являются положительная в отрицательная элементарные формулы nr(vt) и 'nr(vt) (vt - вектор термов), соотношения над термами, юля объекта логического класса, в также точечная и множественная формулы (последние две формулы позволяют определять НД значения функций и fiTHomém-fl в некоторых точках области определения).

Соптояша Jeóaü.jagraai Состояние БД ti í 'D есть конечное мно-объектов od oci), daclíoá), г{оЛ)>,' где титэ(ой) -

уЗъькта, dacl(cti) - описатель объекта, zíoá) - денотат объекта.. Тида обраиом. d яьляется точной моделью действительности.

Отношение соотвотсгвкя кзжду вашими и действительностью.

Будем говорить, что состсянае БЗ ft € й соответствует состоянию БД d е D тогда и только тогда, когда (¡г, а) е Я. Определение R проведено последовательно посредством определения отнозоютя соответствия мэаду отдельтпяя частгает п составнют элгдантЕУЯ БД и БЗ,

Будем считать, что (P., d) с R тогда п только тогда, когда (О d) í R1, а (И, d) € Я2. Отношение R1 означает, чтс доданы Снть выполнены следущие условия: для каждого объекта из 0 должен быть одноименный объект в d, причем йэс(о) deol(od), а денотат z(od) долкеи согласовываться о 7(о) ют F(o) (в случае их наличия в О). Отнесение Я2 означает, что для каждого объекта пз d дояээп быть одноименный объект в 0 .либо в одном из 0}, для которого вшоднешг приведенные Esse условия, а тахте onsoamte всох модула ft "s долгое соответствовать d.

Для логического модуля последнее услсшяэ означает, что (LOG. d) í S222. Отноэение R222 справедливо, есяя а с! шткгаш все правилу н утверждения, т.е. при лзбой подстановке К (гвачотй г^зсто пэре-ганнах) значение 1st |Х7 = "кстгпа", где et - обозначает прапило jaco утверждение, a fat | к] - зпзчеизд, пояучоеясе в результате подстановки в st значеппя к п значений объектов из с2.

дяссертгшйл спрэдэдяэтся гзддель предстзэле-еия 1Щ значений для всех «дассов объектов, допускйекдс ЯП ?юдель» и описшавтся операция над ВД спячешята: приводятся формальное опнслняе ПР кок процесса уточнения ВД знпчокгЗ глобальннх объектов; описывается структура состояния IIP,, а такго правда уточнения значок!:.!: глзбальша. осъектоэ- - п процессе рассуждения, а локальных - в процесса «аштодаэшш грс:юдуриого ваз логического модуля БЗ; для логического гдгугл лпетсп стещ^фигащи задачи, ро-пеомой з пропессе .логического вывода (ШЗ), ошсшзаэтсл прзгпла логического внсода (ЛВ) и пс&лэдуется своЗстга ПЕЗ: монотонность, конЭетонтность л конечность.

ИД зпачанж» птсляе'-ого объактз о представляется многмстом Еаркентов способа вычисления его зпачення: Р(о) ■* Г/,Го), fJoK '""fn(0)(°)}* п(о) е НАГ, п для любого1 i «f„..., nfo), /"¡(о)-формула, если с(о)с {"отазЕенкэ", "лспнесштЗ'Ч, л f,ío)~ торы, если о(о) £ f"отношение", "логическая"J.

Если объект о не является вы'Еиоляекш и с(о) е üLT,ir> ¡ш значение представляется соэяуппостьа зярзгзнтоз значений: 7Л1 ot-{znt(0), 2Пг(0).....¡7ln(oJlO¡).

Если объект о не является вичнслязицм п с(о) í и?. то ií/¡

значение' такого объекта представляется парой множеств Ш(о)= <00(о), Шо)>, гда пзрЕге задает состояние фактической области отправления, а „тороэ - варианты соответствия результатов аргументам. Если СО второй Т1Щ, то п(о)- 1.

Евделено два особах случая НД значений: а) НД значение - полная Леопределеннос^ь (0); 0) ВД еначевио - пероопшдалэнд (3).

Над ВД значениями объектов введены следувдие операции: рас-шрениэ -значения ВД «О ( б ), исключениа некоторой совокупности вариантов (\»3 п другие.

На шоаэстве всех возможных НД значений 1/У(о) об-акта о в1;бдено сигарное отаоаенае частичного порядка >• (отношение уточнения): оаш объект о является шчисля&щм либо о(о)фЫ, то для двух НД значений В (о) и &Ч'(о) имеет кзсто ¿№(о) >-2Н'(о) тогда и только тогда, когда (о) = гЯ'(о); если о(о) € т, то, в случае, когда-<80 имеет первый ТНД гн(о) >• Ш'(о) тогда и только тогда, когда выполнено условие (ОО(о)* СО'(о)) & (И)(а) = РО'(о)); в случаэ, когда ВД 50 имзот второй ТНЦ, 1Н(о)>'121'(о), если игаолвмо условие (ОО(о)с 00'(о)) & (РВ(о)сРй'(о)); если ВД €0 имеет гретнй' ВД, то Ыо)>-а1'(о), когда 00(о) с ООЧо) & Ш,(0)10010))сриго;.

Пусть 0* - некоторое множество объектов. ВД шдэль» действительности, определяемой О', называется мнокзстоо 5(0')^{<папэ(о), ОзаКо), П1(о)> |о « 0'), где 221(о) - некоторое фиксированное значение объекта'о: осли объокт недооопродоленный, то £И(о) есть некоторое ВД значена» объекта о из 1/У(о); если объект о точный, то 2Я<о) - либо некоторое точное значение, либо О. Б(О') 'является полностью неопредолэ1Д?ой, вела для всех о € О' пдает.шето Ш!о)=Я; &'(0') нереопраддлэнз. если хотя Он для одного из объектов о его значение £К(о)- 2. На шояоетво НД моделей действительности определено бинарное отабиенао частичного порядка »•; для из которой пары В(О') и Б'(О') имеет место »■ Б'(О') (модель БЧО") точнее

5(0')) тогда и только тогда, когда вшо/лены следуида условия: для любого о к О' аибо 31(0) = ЯЯЧо), либо )><гН'(о) п существует „хотя ба один объект о € О' такой, что 2в(о) >- гЯ'(о).

По аналогии с подстановкой значений вместо переменных введем понятие "подстановка точных стечений вместо имей ооъектов" и обозначим т) {»1}/'П1ше{ог), шлыно.,),..., и£а(.0> ат(0.;)). где т(0')- мошачегь множества 0', г. какдое у - либо томное значе-яис, либо вариант ЦД значения объекта о1. Отметим, что в случае, когда с(о,) * Щ, и и обозначает {, вариант соответствия результант эигуист-эм. а ес-пи объект является нэтисляоиад..то г,, обозна-

чаат значошш, вычисленное no i1 варианту способа ьичислоиня. Ef-v::j значение объекта есть ft, то vtl ■шс.з о. Обозначил конечное шю-кество всех подстановок т) через Н.

Для объекта с именем nccpsfo^) зафиксируем вариант у', обозначим через WV/Vj-meCo^)) конечное множество Пи((/ naneio^, v{z/v.rj?.e(o?),.... vlk_1/mr.3(oh_l) .vV-Kr-efc^) ,vihf (/ нее кг оЫ}). "••• vim(o>) / namef0nfo'04eBH®10« ift»'/ паявio^)) с II.

Введем обозначения;

fiFIMlr)J - значение, получаемое в результата поаледоватольно-го выполнения в КЯАХЕ, X) подстановок i и ч я выполнения затем действий, определяемых формулой (термом) Р;

[[F\\]\U] - шоиество ШР(7Ш2, XJ|XJ|t)J | 7) € И).

ПР определен как последовательность иегов, на каждом из, которых , кроме первого, в соответствии с алгоритмом таг-происходит выполнение процедурного или логического модуля, в результате чего да-ает быть уточнена !ГД модель действительности, определяемая множеством глобальных объектов О CS}(Q))\ в силом начале ПР НД модель действительности полностью нэ определена, и на первом шаге она формируется с использованием информации о значениях глобальных объектов, полученной из описания Eg, ii откуда-либо извне.

Процесс внполнония модуля (ПБМ) определен как последовательность из четырех пагов.

На первом шаге ПБМ на основе информации о значениях импортируемых объектов, полученной из состояния ПР SjiO), описания ins портируемых объектов модуля Ы - 1Ш> и информации ,о значениях локальных объектов, полученной из описания ЕЗ tn/awi откуда-либо извне), форщтруется НД модель действительности w (0М>.

На втором шаге ПШ по ВД модели к^(GM) формируется НД модель действительности wJOU) - либо в результате выполнения 11ЛВ (в случае, когда И - лолтркий модуль), либо в результате илюлпоши алгоритма, определимого описанием АШ (в случае, когда Я - процедурный модуль).

На третьем шаге ПШ по НД модели wJOB) на основе онисашш экспорта - ЕХР формируется состояние экспорта ЕХ,

На последнем шагэ IBM фзрмируотбя еякжэство уточненных гяо*-чений экспортируемых обшггад ZE - па основе вдфэрмяции о з^ач«-1шях экспортируемых глобельшх объектов из S (ОJ и Ж.

Но каждом й-ом цчге вырабатывается значение яря&ш>.>"1

успешности внполнонил шага efc. Если хотя'бы для одного гшп'пнч.' к ■получено о, - "ложь", то следутие вал н<) шполнчпчч » «орквру

б7ся в = "ложь". В противном случае формируется е = "истина".

¿ели в - "ложь", то следующее состояние ПР совпадает с

8^0). В противном случае ^ + = (<псвг£(о),бес1(о)1(о)\ (о <■ о \ ое & = гпл(о)) ч, (о е о£& = ггео;;. здесь

02 - множество экспортируемая объектов модуля.

Спецификация класса задач, решаемых МДЗ, представляется в виде четверки ТСХ = <У, а. 1?, (}>, где V- множество возможных наборов неходок данных; а - отношение согласования набора исходных данных не (У и модели действительности с? е № - множество возможных результатов, К = Сш); {5: 2Ш ~> Ш - способ определения результата.

Результатом решения задача является 1Щ кодель действительности, которая строится из кшокества точхих шдэлэ2 ¡¡иЪ = Ы с Ш | С и, <1> с а, СЬОО, (I) € шсредстЕШ езэрзцгз т.е. то

ПЛВ определен как пороздавдий процесс, состояний из послзйо-вйгвльноста пагов, на кавдоы из которых шгэт быть уточнена ¡ВД «¡одаль действзтольшстп дл^, определяемая шо&зствш ОМ.

Не первом ваге текущим является начальпоэ состоякиз щг. Текущим на он шаге лвдяэтея состояние, йолучешкю в фоадтатаз» выполнения J-ого шага.

Если текущее состояние ПЛВ оказалось протнБорзчлкй!, г.в. хотя бы одна объект о € 01 получил значений 5? то ПЯЗ счатаатся зеворшошю,:, а его результатом является состояшэ гр^

В противном случае по текущему состояния ШВ ояределяэтея иозиошость пркзшэЕия хотя бы одного правила либо утвервдбшга {ПУ) аз КДЗ. Если га одно ПУ из ВДЗ не применимо в то ШВ считается завацзоннам, а да^ - его результатом. Если ее в сушствуат хотя

оы одно 1ф2г,-.э15ш03 11у, то еосфедстсо:,! выполнэ2шя одного ез пшызни-••их ПУ строится повоз состояние

Если па > посланием оаго ШВ было построено состоянии.' то формируется празпак ускешосш завершения выполнения сага ШЮ е2 « "лош.", в сротшзноы случае е2= "истина".

Существует три -шла уточнения: (I) уточнение значения О, (2) вычисление значения КЦ ФО в новой точке области отправления и (3) исключение вариантов значащий, не удовдетворякаях некоторому усло-пию. С ПУ различного вида связаны различные правила ЛВ. причем как-домт 13У ::сит соответствовать не одно правило ЛВ, а несколько. 1!а некотором <дагэ ШВ выполняотся одно из этих правил ЛВ.

ПриЫ/ем ооштй вид правил ЛВ, производящих уточнение первого I® лто)к^о типа (в мучг.о отсутствия противоречия):

(qpij,* A. st) (ut (st* Л» Wj) &

(ti2 (at. X, qxij, vrV3.....ту

|- <3^,, = nU at, X, gsij, tj},t)2,..., y^).

Здесь .ni fot, A,, qm^ обозначает условие, которому долааш удовлетворять значения элементов ПУ при \ и qrij (например, ' для утверждения второго типа - значение единственного дизъюнкте должно иметь неопределенное значение, тогда хшк осталу да дозъжнктн \ ложны), u2(at, qnij, Т}}, т),,..., обозначает условие суиоство-вания решений T)>f..., T)h, подстановка которых в ПУ нэ приводит к противоречивому состоянию, mi(et, X.qntj,т)(,т)(,..i)^) обргшячоет действия, выполняемые в результате применения ПУ. Решение»? ипгшл-ется такая подстановка значений вместо имен объектов, при которой значение ПУ равно "истина". Выполнение действий состоит и следуй-аш: если значение некоторого объекта о при дп^ равно Q, то производится замет О m ИД значение .....\}'< вст значение объекта

о (в данном случае НД ФО) отлично от Q, то производится расвирврз значения НД ФО с использованием операции С. Отметим, что кцадд ни основе продукционных правил ДП модели организуется ira осчоие к.ль modua ропепа, так и mocius tolltna.

Приведем вид правила лА производящего утешение трот ьаго

типа:

(дпгк,эг ;гз о iom\т^о) / Ш а гз vit.... v\ | fV i, H U l) (v\ e 2iyo,)v y't i iyojj.i (liât | H(v't /тжв(о))] - {"яоаь'"Л / & (3 v4 Ztijiolv t>" с iJj(o)) i

([lat |Я.J | H(v"/ncsne(o))J f- {"ложь")} 1" " at. o, ь'г),

где действия mS(qpij, A., st, o. o'j,..., v'x) состоят в замене зиа чения ZHj(Q) на = ZNj(o) \* iw',.....и'^.

Приведем вид правил перехода в проишорэ'швоо

состояние:

(qirij. st) (t«pfal, Л, qiïij)) * qmp,

где upist. X, qra) обозначает условие возникновения противоречия при выводе: попытка расширить 'на новые точки значения Щ 40 с .первым ТНД; формирование ВД.'йЦ'еиия в новой точке для НД ФО со втор»м' ТНД; необходимость иск.таочнюя всех вариантов некоторого. НЯ значения.

Доказаны следушго свойство 1ЩВ..

Теорема I (о монотонности ШЬ). Если S -Ь- S', то существует объект о тедой, что если <naae(o), Z№(o)>iS, а <пате(а),2К,(о)> € S', то Ш(о) >• Zh'(o) и S »• S'.

Тоороыа 3 (о коаф^птности_ГШ2.; Пусть S, S', S" - состошшя ПЛВ. Если сдастауш вывода £=>S' и ¿=>S", то существует ненротаво-р&чкьоэ состояние ШШ S'" такое, что S'=>S''' и S"=>S"\

Творена 3.(о конечности ДДВ). Если существует ún е Ш, такое, что iLOG, от) с R222 и (v,án) е а, го ШВ заканчивается за конечное число ввгов N и V, с I + т}(о}). + тг(а2)+ ... + (I - число

объектов в OMJ. причем, в случао, когда

- cfOjJ е СП или ot - НЯ ФО с перши ТВД значение т((о1) равно числу вариантов ВД значения, заданного в v, либо максимальному числу термов в структурных термах и векторах тер,юв из LOG;

- ot - Iffi ©О со вторим ВД, EJtfotí = m(00'(oi))-m(00(ot)), где и(00,(о1)) - число элененяов области определения функцаи с именем пат(а') кз <£д, a m(00(ot)) - число олэглэнтов области определения функции из v;

- о{ - НЕ ®0 с трэтькл ТВД, то значение ratfotJ= f fглгЬOG^^('0oí,, где ufOjJ = m(00'(ot)),~ m(00(ot)), а гпах^- максимальное число TSp<JOB а структурных термах и вэкторах торшз кз LOG.

Теорема 4. (О свойствах ШВ). Если ШВ закапчивается в состоянии S* t q¡ni , то S*»- P(Buí). При этом, если- шсЯкаство 03 содержит только объекты, у койэрнх с(о) е СИ лпбо НД ®0 с первым ТЩ, то справедливо раюаство S* = p(BvL).

Теорема Б (о конфиоенткостп тт наличии противоречия). русть S, S', S" - различные непротиворечивые состояния ПЛВ. Если сувдствуют синода S -> S' -> Sp к S => S". то существует швод S=>

=> S** => S .

р

В чогаэруой глава анализируется схема организации процесса ЛВ для ковфгшенпшх СП; рассматриваются особенности поиска означиваний для двух типов правил ВД ЛВ; для ВУ вводится каноническая форма (КФ) и определяется совокупность преобразований баз ПУ к этой форме; приводится структура подпрограмм на АЯ, соответствующих элементам канонической форма.

Канонической формой ниюторого ПУ ¡называется совокупность различных форм этого ПУ, так\т», что каадому элементу КФ соответствует одт.слвышое правило ЛВг Формой ПУ, которой соответствует правило ЛО. йЬои'Лч'Дяыае уточгыме первого или второго типа, является ут-корад^ния. Формой ПУ. которой соответствует правило ЛВ, производя-име утешение третьего типа, - правила сдаиазльшго вгдо. Утноржце-

низ .вдодат в состав КФ некоторого НУ, еслл ¡1У содержит икзнн 1{Д объектов, чей класс из СИ либо икена ЦД 00 с першгя ила третьпа ТВД. Правило специального гида вхоялт в состаа К? некоторого ПУ, если кягалззпо условие преобразования ПУ к агс:«у краврду.

Для всех правил модллй кагодзяотся иреобрсговаояэ к обоот,зп-ио.1 дизъюнктивной нормальной фор?,:а с использоввЕкем нзвэотпоЗ вквн-гзл&нтяости юяшпсацш к дозыснгасш, а правая де-Иоргсна. П

результате вшкнашпзя долгах преобрпзовогай прясло будет иметь форгду утверздзпяй второго тша. Иогучешов утвзргдопк--*, а та**?ж любое утверждение второго ткни кокат б»ггь преобрпяоглно но более, чем к I правилам споцпал>кого вида:

если та, с г (]„ ог... сг О, 4 ог 0,.. от... от и,) & "

I 1 — 7 I г 7 I

£ Г/,' А... ТО & й...- А . (Г

где г/1г/,п"с -- состгсззиия, ссдерза-цта констьО.тц, иеромен-ше, тлена объектов, чей г.эсс пз СЫ; /1я*£ - полоеттоль-

ше (отрицательные) элешптарпно формула ллбо равенства, содержания функцйональнае терна!. «орчулы г/4п"I, /4П*1

являются формулам! дизъЕякта (^.Кзздоэ {-сэ правило входят в КФ данного ПУ, если (п* 1 >0 ) & J.' где uv(Qi) - условие вхоздеячя переменных получаемого следствия во (.агохество пврзшшшх получаемо -го условия для 1-ого правила.

Утверждения пврзого тала могут быть преобразованы не более, чем к п правила;.! следукпего вида:

если, q}(xf) & Яг(?г) &

Некоторое (-ов правило входит в КФ в случае, котра ьч<Сд{) и Я((х1) - либо положительная ("отрицательная; элементарная формула, либо равенство, содержащее функциональные термы.

Каноническур *.фртвд утверадений третьего типа образую!' семя утверждения, совокупность правил вида (-1), получаешх в результате преобразования, описанного выше для утверждений второго тага, а также совокупность правил следующего вида;

если (¡.(Х^ & Ш,; 4 Шг) &...& ?(<!«_,.)& РШ ,) РОЗ*)

то V, » ^ & ... & к.

Здесь Р(Ог).....конъшкцкя всех формул дяаъвшйгоа

¡21..... ак баз .... Некоторое .1-ое правило входит в КФ

утверждений третьего типа ¿"случае, когда"/^к).

Правило являетбя активным при некоторемгекущом состоянии ПЛВ. ■зела в птом состоянии ПЛБ содержатся ^тличннв от ,15 значения всех

объектов, входящих в условна правила; утверждение является активным в случае» когда в текущем состоянии ШШ содержатся отличные от И значения всех объектов, входила в утвэрзщэнкэ.

Правила КО являются аналогом прсвкл скзтвш дэхашратпзннг про- ■ дукщгй. Для на озяачкванке - зто ипогяство фактов, па которых ес-шшо условие правила; эш правка содзркит парзкеш.'ыо, то в озна-чкваниэ входит значение подстановки л. Утвврвдэш) Е5 аршэглаа яа некоторой ваге ШШ, если судаству&т хотя ба с»ш варзгпт 1Щ еаьча-ния некоторого объекта, который можат быть мсгиздаа, т.о. озаачЕи;-ЕКв для утввраденал содврит этот вариант к куя огЬокга.

Все значэиЕя подстановки \ определяются и рэзультатв просмотров всех 00(а); процесс их поиска организуется таг-игл образе.", чтобы изСааать повторных просмотров 00(о).

Для пояска ьсох возможных кшездатов на исклаченив (КИ) с кал-дым вариантом связывается признак, принимающий одно кг.значений: "да" и "нот". До выполнения операции поиска все щшшшв гаюззт значение "да". Если существует некоторая подстановка т;, щи которой = "истина", то значения всех признаков, соотЕзуствукза вариантам дз т), равняв "да", заменяется па ЗЕЗчепаэ "пет" с одновременным подсчетом таких замен. Разге.ца шеду суйггарЕза чкаки вариантов и количеством произведенных замен опрэдеяяэт каЕлчество КМ, а сагли КИ определяются по связанному с вариантой признаку: еэкото-рьй вариант является КИ в случае, когда после окончания поиска значение признака равно "да".

Язык ПЗ (ЯОЗ) продукционного типа ыояет использоваться двояко: кзк средства ПЗ либо как объектный язык при ш&шлнщт БЗ (КБЗ). В первом случав ПУ записываются вручную сродстваш ЯШ, а во второй случь'з получается автоматически. Очевидно, что во втором случае ба-"о ПУ являетря промвЕУТочннм представлением, по вей ЯП форкарует совокупность .подпрограмм на АЯ (ПАЯ), причем время комляцаи (Ей) можот бить значительным. Сокращение ВК достигается созданием набора ПАЯ, реализующих семантику вычислений для модулей и элементов КФ, и ЛАЯ, содержащей их вызовы и обеспечивающей управление выполнением ЛВ. При эток сами объектные ПАЯ могут Сыть подготовлены вручную разработчиком компилятора >13, а компилятор ВЗ должен формировать лишь множество их выаовол. Вторая возможность повышения эф£ектив-нос.:' г-шгаляеиия КБЗ связана с уменьшением объема генерируемого кслеллятс^чи БЗ кода на АЯ за счет вндилония сходных по структуре эломентев ¡(5 (имовдих одну и ту же схему) и формирования для них од-.шств«11хой ПАЯ. Тогда при КЬЗ буду? сформироваться конкретизации

этих схем с передачей значений параметров, опредэл8бг.:их копира та^м элементом КФ. Множество схем определяется при спецификации метода КБЗ, причем число схем значительно меньше числа кошере газаций. В частности, число схем для компилятора баз медицинских знаний равно 24, а число формируемых при КБЗ правил на ЯГО РЕПРО-1 ~около 5000.

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие основные результата:

1. Разработана декларвтиьно-процэдурная модель ГО, объединяющая различные средства ПЗ: декларативные правила и докларативнйе утверждения; разл!чные модели данных (индивида, функции и отношения); средства организации модульных БЗ как совокупности мод:'лей, обменивающихся значениями объектов как через систему"Ф8йлов. так я через глобальную базу деншх.

2. Определены ПР по модульной БЗ я процесс выполнения модуля. ЯР по модульной БЗ является процессом уточнения НД значений глобальных объектов, а в НЕМ уточняются НД значения ; локальных и импортируемых объектов модуля. Для логического модуля специфицирована задача, решаемая в процессе /О, определены правила НД ЛВ при отсутствии противоречий, а танко правила перехода процесса в противоречивое состояние. Процесс уточнения значений включает два типа уточнения: исключение Вариантов НД значений объектов всех классов; -расширение областей определения ДД ФО на новые точки. Показано, что любому ПУ.может соответствовать несколько правил ЛВ.

3. Исследованы свойства процесса НД ЛВ: монотонность, ь*очеч-ность и конфлюентность. Показано, что при налички рротигорсчмч свойство кснфшоентиости сохраняется.

4.. Разработаны метода реализации системы декларативных продукций, ориентированные ■ яа компиляцию. Для ПУ системы декларативных продукций'введена 'каноническая форма как совокупность рьешгшых форм ПУ, таких, что квздочу элементу КФ соответствует единственное правило ЛВ. Определены правила преобразования Г1У К КФ. Для каждого элемента КФ определена структура объектной подпрограммы на ЛЯ.

5. Разработаны' метода реализации виртуальной машгаш, организу ющей процесс НД ЛВ..Дано отоэдолэние активного ПУ- канонической Сор-мы. Введено понятие . "означившие" для всех типов элементов КФ. Определен процесс поиска означиваний.

6. Предложен новый тип систем поддержки НД ЛВ: среда КД . Яч основе разработанных методов создан ЯП . ЗТРО-1, перенесший на раз -

.чтч1Г!:о тит.: ЗШ. С вшеаш ЯП РЕПГО-1 разработан гибкий компилятор. Ы к 011. а vasssa ряд 1ШС в различных предметных областях.

Осдогзю гг.зульташ дгссортащщ опубликованы в работах:

1. А^мзика В.И., Артош>ева И.Л., Грибова В.Б. и др. Проект PiaiiO: сойторлко и пзрспзктЕШ // 2 Всесоюзн. конф. "Ис-кусствзишй шпшюхг-вО*: Тез. доия.. т.1,Мнкск, 1990. С.35-37. • 2. Артемьева ИЛ. представления знаний РЕПРО // Ги<5-

рплгшз вчтоагакедоаь'вав сгэтбиы: I'üs. докл. Всос. научно-практич. кокф., Терскол, ISS3. С 63-85. Ч. t.

3. Арк;:ц.&зэ И.Л. юдосвредэлавЕэго вывода в системах, иролмгл// ЗГС5С1, Н Т, 1Ш. С. 68-53.

4. Артагаева ll.il. Kp-sa^ri рл^АКДзацлл иэдоояроделониого ло-гкчзокого ыжожа» lipain». Бдадкьосааз: КАПУ ДВО РАН, 19Э2. 34 с.

Б. üpicaAsa К.Л., Екюш ¿.С. Кздавь иодоопредв.гэнного выводи в cücra-з ЕШи // Ех^э к£орештояшэ технологии: Тез. дою:. zpwxs^tw.o'2 кглви и га;~орчоскоЗ шстажж, Одесса»

1SS0. С. 1&Ч

6. 11. Л., lisitsza A.C. Pßo-.йрзнвав иодаль х-лашра-' %гжт ъ£'дяра«2£х Ofap. Б^-кзаагаг: lläJEf ДВО АН СССР. 1991.35с.

7. tpxsüun^a С.Л.» Ьг^'л» /.С. г.тазд в сзсп&зх псодуг-цй с не дсопрэд-зл ягтад оСкдакьм. Крседи» ргосуглсгэй, ш-дуаькэа СваоД b.^-j-sr.:.: Hjrasp. Вггдаваетж:: U£ffir Д20 РДЯ* IS3S. 31с.

е. дрхесшм t:.2.» Квгвд» A.C. Е^х-д в сгск&ах вродувдгй с вдооБред&Евшгя объегияиз. Пр-коаг ¿эпяоскгах) гэдэхз! Препр. Еладаиозток: ШЕГ JJSD KS, IS32. 41 с.

'9. Ьр-шшьЗй П.Л., rjrs;;oD A.C., ЛгСзгц А.Й. s др. iloa; врод-с?аг-пвЕ2я snrsi! ШПи// fc.i/0i:2K0-opr.öJi'icpoac^2C кгогра^роеи-кив: Таз. докл. Егежкж. глиф. "Ак'гуадьшл вроа^а сгодгйяаго прсгржгроБста". Scacaa, 16-18 января ISS0. • " С. 84-Ой.'

Ю. Артемьева ПЛ.» Ежйза A.C., ¿¿.¿ад AJ5. п др. 1:зрз-шсиш& генератор аксззрягзх. саэтии FEHP0 // СЗгскпа-сризглуро-вшдасс! програаияровааЕз: Таз. д;ск. Есэсоазн. koesJ. "Агатвлнихг проблемы системного прзгр^црззкга"» Тпмгато. 16-Ю ягхара f&iiü. I9S0. С.

'1. .Артемьева К.Л.. Xs£oat А.Я., Пззс Г.Я. Пр^сгяш резхяз-ции тк-доэра рксяэртивх слстеи IfJFO// Катод» и сродства соода-. ш!я а kcw довали;; экспертных сгстен. Вгадазостзк: АН ОХР. ¡-./л. с. ие