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

м1н1стерств0 О с в i т и украТни

харкшський державний техн1чний ун1верситет рад10електр0н1ки

СИТН1К0ВА П0Л1НА ЕДУАРД1ВНА

АЛГЕБРА П1ДСТАНОВОЧНИХ 0ПЕРАЦ1Й

ТА П ЗАСТОСУВАННЯ В АВТОМАТИЗОВАНИХ 1НФОРМАЦ1ЙНИХ СИСТЕМАХ

05.13.09 — математичне та програмне забезпечення обчислювальних машин х систем

Автореферат дисертацп на здобуття наукового ступеия кандидата техн!чних наук

ХарК1в — 1995

Дисертац1ею е рукопис.

Робота виконана на кафедр! програмного забезпечення ЕОМ Харк1вського державного техн1чногсг ушверситету радЮ-електрон!ки.

Науковий кер!вник:

— доктор техшчних наук, професор Шабаиов-Кушнаренко Юр1й Петрович.

Оф1ц1йн1 опоненти:

— доктор техшчних наук, професор ШАРОНОВА НАТА-Л1Я ВАЛЕРПВНА;

— кандидат техн1чних наук, доцент 6РОХ1Н АНДР1Й ЛЕОН1ДОВИЧ.

Пров1дна орган!зац1я — Харк1вськиЙ ав!аидйний Шститут

Мшстерства осв!ти УкраТни.

Задаст в1дбудеться . * 1995 року

о „_" годин! на засщант спец1ал13овано! вчено! ради

К 02.25.03 Харк1вського державного техтчного ушверситету рад!оелектрон1ки за адресою: 310726, Харк1в, пр. Лен1на, 14.

3 дисертащею можна ознайомитися у б!бл1отец! Харк1в-ського державного техн!чного уи!верситету радк>електрон!ки за адресою: 310726, м. ХарК1в, пр. ЛеШна, 14.

Автореферат роз1слано ¿¿¿ЫУ^Ш^О/ 1995 р.

Вчений секретар спещал1зовано1 вчено? ради БЕЗКОРОВАЙНИЙ В. В.

■ ■ ' -Г:

Актуальшсть. йаеове впровэдження обчислюваяыяи машин 1 робо?1в в народае государство, в система управлилзя, в вро-цеоя проектувэнйя 1 ковструювання нових т&хнолопчвих систем виеунуло на паршяй план досл1даэада ш штучному 1нте.яекту í привело, по-сут1, до створення щдустри ютелектуальних систем. ■

Новэ 1кформац1ййа технология* яка зараз бурхливо розви-ваеться, в!дзначаеться тим, що, по перше, за доподагою сш-ц!аЛ1зованих, формал1зованих (лог1ко-л1нгв1стичних} моделей знания представлякяься у тш±Й фарш, що стае №жливим ефек-тивне розв'язашя задач за допомогою ЕОМ 1, по фуге, лоП-ко- Л1нгв1стичне моделювання розшфило застосування ЕОМ у важко, або зовс!м не формал!вовайюс ранш галузях знания 1 сфер д!яльност1. Тим самим сшталютам забезпечено прямий доступе до ВСШ у д!алогово«у режим! для роэв'язпшя свои за- ' дач за рахунок програмно-анаратйих засоб!в штучного 1ктелек-ту 1 створення там самим ютелвктуального 1нтерфейеу ЕОМ.

Розщток штучного 1нтелвкту ставит» перед собою розв'я-заннй трьох теоретичнкх проблем: зобра^ення знань; компьютерно! л1нгв1стйкй, розв'язашя яко$ забезпечте прочее при-родаомовного сшжузання з ЕОМ; компьютерно£ логики, що мае особливо велика зиачеаня для роэвитку ексгортних систем, оскиьки и мета - моделюважн ьаркування людони,.

Мета рскйт, присвячених штучному штедекту» нолягае у створекк! машин, що виконуоть так! для яких визгам. по-тр!бш Штелект ладани. У. число загалыах наяряшав 'тех облает 1 входять автоматизован! йетоди розв'язашя задач "розумйшв* 1 перекладу Мое. доказ теореми розШзнавянкя зорових <к»раз1В, дави та 1н.

Н1д час вир!швння вказанних проблем часто зиникають- за-

да«» wp з&озться m ¡»зв'язанвя систем жпчшх ршишь. Проблемою розв'яааиня тпчтк ршть з&Шалось (fàrayo si-дешх гиенах, таких як Ш. Будь, веда, йрейдер, а,Д. Зак-рввський, П.С. Поредышй» A.A. Утк1н, А.Г. Айраавад!. Видаку pOÖOTy НО CTBOpSffiHO «8<Р0Д1В роза'яаання а<я<ебря ектченних EpejüptaTiB як кяасу догсчвшс р!ШШь доведано у ХарК1вському державному ®ехн1Чноиу умвврет®*! радюедая-трониш на кафедр! ирограмшго забвшвчешя шд керхв-ницгвом яр$есрра Шабейова-Кушаренжо ШЖ Щхзшашя у цШ облает! й1дготуевяи грунт для створення ювюс ефектяшос методов роза'язання окрвшх pjiscíb рзшишь з визяачвноа структура».

Щфр робот полагав у е^вореда! адрорйташз розв'язання Л1ягв1С5ичййх р1внянь дяя од&ркадая зяачввь обиежвного вдела ознак та ïx Hpoppa®oï реалйавд дош викорютаяня у сисм-мах «№ома?изоввяо2 обробки текстов*)! 1в$ормаци.

Йосяшешя задано? метя нотрабуе риешя ряду задач, серед «т. тжь вщшш теш:

- анализ форгизлыш: зееоШв 1нформацШих екстви;

- овлед ойяаеяей 380*кюув8йяя лопчюк равнянь i mroMis и розв'язашя;

- формудавашя ышетйзостей яадсташвочшх операвдА у &аяе«дое¥1 ш у ярвдаката, одержвяого у результат! и

д«;

- форму-швадая i довезшая влвстщос^ей oaepauiï квантор ютуйаянй як аштовочшх швраиШ*.

- розробкв методу шиттш ашжаа s предика^в, «о иайть вешу структуру;

- прагршка реал±зац1й одерквшх алгоритм»;

- оШнха екладаост! алгоритм!^ мви^^чня змштх;

- визначеиня областей використання рбзробл&них Метсдав.

Основш положения, що вшоеятаой «а эа&йст.

1.Формулювання 1 доведения властивостей г чмдстеновочтас операцШ при IX ди на рхзнх вида предикатхв.

2. Розробка мвтод1в роэв'язання р1внянь в1Дйо*жо*цмыз®йх зм!шшх на баз1 виключення зшнних, несуттевих для1'дао! постановки задач!.

3. Програмна реал1защя розроблених метод!В.

Наукова новизна робота полягае у тому, що:

- сформульоваш 1 доведено властивогп операции подстановки;

- сформульовано 1 доведено властивосп опер п.'П квантор юнування як диз'юнкци юдстановочних ошращй.

- розроблено 1 програмно реал1зовано метода: виключення зм1ншгх з р!внянь р1зноман1Тно! структура.

Практична шннють роботи. Розроблен1 у жс^г-'гщйнШ робот1 математкчн! метода роэв'язання Л1нгв1стич!шх р1внянь 1 программ засоби, що IX реалазують, шлсуть бутк використа-н± у системах автоматично! обробки тек'умв, при розв'язанн! задач лопчного висновку у "базах знань 1 експертних системах. .

РеалАзатя результата роботи. Дисертащйну роботу ви-конано на кафедр1 програмного забезпечення ЕОМ в1дггов1дйо до плану науково-дослщицьких роб1т:. держбюдаетн! теми N143-1 "Розробка теор!1 1нтелекту 1 створення на II основ! програм-но-техн1чного забезпечення ЕОМ нових покол1ньи, N142-1 "Роз-робка теори 1нтелекту та и використання для створення но-зш 1нформац1йних технолог!®", N147-1 "Побудова загально! теори л1нгв1стичното 1 програмного забезпечення для евто-матизованих систем анал1ау зображень".

Дтюбатя роботу. 0оновн1 результат« дисертащйног робота доодвдались 1 обговоривались на всесоюзной конференцл "Бюнше штелекту* (м.Харк1в, 198£р.). ттеттнчнзл тяяа-родий наук0Е0-техн1чн1й коафэреицис *%навд1онадыю-ор1енто-&ан1 1нформвц±ЙН1 оисгейи" (м.Алушта, 1993р.)

Публ1каци. За результатам» шкокашх дослшень ощб-яиювада 8 ро<Я¥.

Структура та о^еяг ъобот. Дисвртвщйяа робота склада-«ться 1з i рдения, п'яти роздШв, вйсновк1в, стоку л!тера-тури з 104 наймещвань 1 додапав, Зшст викладено на 141 сторшках: шшдасщисного тексту,

У розд!я1 1 на основ! 1ифор»ац1£ про облает! застос-у-вання 1 1сну»ч1 метода розв'язашя лоПчних р1внянь сформу-льсван! основа! задач! дослщшяя.

У роздш. 2 сформульовай! 1 доведен! властивости плд-стано&очних операций.

У роздш 3 знайдеао необхщи 1 достатн! умови зб!гу 1 ортогональноет! цредакамв, як! одержано в результат! Д1й на них р1зних шдсгановочних опйрацШ. Сформульовано власти-вост1 операци квантор юнуваиня.

У розд1Л! 4 розроблено метод вжлючення зшйних з предикатив, ЩО мають р!ЗН0И8Н1тву структуру.

У розд!л! 6 описано розробдет црограш роав'язчння Л1нгв1стамних рлвйянь. а також проведено ощнку складаост! алгоритм!в.

ЗШЗТ ЮБОТЙ

У всттоь! обгрунтовано актуальнють теми, сформульовано мету роботи 1 основн! заедания досл1джвНйя, охарактеризовано н^укову новизну 1 пракдажу цшисть одержаних ре-лультвт1Е, вказвно зв'язок .з планами нзукових досл!даень 1

щльовшя щюрршаш, приведено дан1 про апробацзю 1 лубл!-натк осиовних иауковшс яоложень, що виноеяться не захист.

У первому роз^ш вказано можладост! застосування ло-пчннх р^внявь 1 метода £х розв'язаняя.

ИЛ .1 яриевячаю® огляду формальних засоб1в «формациям* систем. Ш.д 1нформац1йними система»® будемо розумити си-ствт, що збор1Рають 1 обробляють дан! 1 знания, а £х фор-I мальн! засоби - мовк обробвд даиих 1 подання знвнь. Ун1вер-еальний формальним заообом для математичного опису природиох мови являетьсй алгебра ск!нченних предикат з.в, <жа дозволяв описувачяи за допомогою р1внянь детерм!новаН1, дяскрети! 1 ск4йченн1 хнтелектуальн! нроцеси.

ЕМ .2 присвячвно огляду областей застосування лопчних р!вняяь. Метода розв'язання систем таких р!Внянь знаходять застосування в твори автомамв, йри розв'гланя1 проблем розгПзновання образ 1в, при с-творенн! лийШстачш »абвз-печвння та в !шюх досл!джешях у галуз! штучного ютеленту*

У П. 1.3 проведено анализ юнуючих мвтоД1в роэв'язання ЛОГПШК р1ВНЯНЬ.

У ПЛ. 4 ва основ 1 прове дено!»о огляду ЛМературних да»" рел 1 ВИСНОВК1В, що !снукт метода роэв'язання лшгвютичщвс р!внйнъ ма»ть деяк! не дол пси, так! як велика склада 1 гром1зда1сть обчислшь, сильно розгалуджевий продас шбору рившъ 1 т.д., сформульовэно задач! досл1давння по створенню нових ефективша метод!» роэв'язання ршнжь алгебр» сктчв-них предика'ой (А(Ш) в!даоснс щльових зытних.

У другому созд-щ дослхдженс застосувашя операц1й подстановки до гфбдйкатгв, предстаэлешк формулами АСП.

У Л.2.1 розглядаеться д!я операцН постановки на ггз-дикат, представлений у вягляд! даз'шк'тивно! нормально! фор-

Ш ■

HexafrP - а -арр%й$ф,ашат., .задень в!д змшшх x1 ,хг,... ,хп, коша- з яких мае област1 .п^цстимих значень

ta2i}j=i'' •" МтовШЪ' Оператором

мдетановки at^(P) називаетьс». оператор, щб п^ретворюе предает Р у предикат Р, вляхом мдетановки. значения ^ зм1н-яо£ в предикат Р.

Назвемо ошратор a{j(P) = P1 звужутим, якщо для .Р i P1 виконуетьоя сп1вв1даошвкня Р1 = Р. (3)

Назвемо оператор сц^Р) = Р1 розширвтил. якщо для Р i

Р1 ВИКОНУеТЪСЯ СИ!ВВ1ДЙОШвННЯ Р1 с р. (3)

Назвемо оператор а(^(Р) = Р1 зМщукнщ, якщо для Р i Р, зе виконуютызя смввщющення (2), <3),

Роэглянемо n-арний предакат Р^.л^,...,^;, який. мае облает! припустимих зйачейь (ОНЗ) змийниао,,,, o12,..., .a1n>, {a21, Ogg,..., в^дповшо.

Роз&Ремо ycl доданкй Гфедаасата P, ар представлений у виглйд! ДНФ, на так! п'ять клас!в:

®2Jg otf

1. Ммтить доданкй вигляду х^ лхг K...xi J...хп ,

« {1....,«„>. b = ггя.

2. йютить доданкй витияду х, e...a?t • , /й «{!,...„fe а TT».

причому добуток узнавань bcix зм!нних явного стздаожника, кр!м узнавания змишо* x%t

Ч,'

жг,. '

мютиться сера д. аналог 1чних в доданках первого класу.

«13 Оц

а. Мютить доданки вигляду хх 1.гг с.. ,х1 *.. .хп 1й « « а,...,пй>, й = 17», причому амвмножних

.ЛИ' . . С, ■ т V » I як **

*г • • л*+1 " • ■« *

вшхнннй в1д аналопчних в додйнках первого класу.

4. Мютить Доданки виг ляду х^ , « (1,... ).

5. Мютить додаяки вигляду

°и1 °2г2 а*-1»*<_1 а тп

к = Т7». ■

Твардйення 1. Якщо предикат РС^„г^,...,хп) не мютить доданк1в первого класу, то оператор мдстановк Д1е

звужувчш чином»

Твердження 2. Якщо предает Р(х^ ,х2.....х ) мютить до-

данк! первого класу, еле не мютить доданк1в третього 1 четвертого КЛ8С1В, то оператор постановки д±ь ^зшфю-шн чином.

Твержения Э. Йкщо предикат Р(ху,х&,...гХ ) мютить до-данк1 первого класу, а також доданки трелого або четвертого КЛ0С1В, то оператор постановки а{^(Р) Д1е зм14уючим чипом.

У П.2.2 дослшуеться Д1Я тдстэновочно! операци на предикат, представлений у вигляд! кон'шктивно! нормально! Форш (КНФ). Июля вид!лвяня у предика*"! таких трьох клас1в елементарних яиз'кнкщй:

■ ■■■■■■

1. Спхвмнокники, в яких присутне утзнавання х, ^.

. . а,. .

2. Опвмножянки, в яких' В1дсутнв утзнавання але прясутш. 1ни1 узнаваннязм!дао1^.

3. ствмножники, ян1 зовсьи не мютять ушзнавань зм!нно1 х{, - доведено твердження:

Тзврдзення 4. Якщо предикат Р ве мютить елементарйих

диз'юнкц!» першого класу, то оператор шдстановки a^J^P) д±в звужуотда чином *

Твэрджвння 5. Якщо предикат Р мютить елвментарн! диз'шкци першого класу, ада не мютить таких же другого класу, то оператор шдстановки а{^(Р) д!е розширюючим чином.

Твердженвя в. Якщо предает Р мютить ся1множники первого та другого класу, то оператор падотаиовки Д1е

змицуюючимчином,

У П.2 з доведено залежнють вигляду операции мдстанов-' ки, що Д1в на кон'шкщю предикат!в вздвиду тезе операци по в1даошвнню до кожного з лредикат!в, що входить в кон'кяшцю.

У 17.2.4 доведено необхада 1 достатн! умови юнуваяня звужуючих, розшйрюючих 2 зм1шуючих мдетановоч т операщй для предиката, що мають вигляд ДНФ 1 ЙНФ.

У П.2.5 доведено необх!да1 1 достатй! умови юнування для ПреДйКЭТ1В у вигляд! да 1 ШФ Т8К01 посл1довяост! зау-яуючих (розширшчих) оператор« шдстановки, зэстосування тог зводало б даний предикат до нуля (одиниц!).

У третьему розд!л! досл1джено влаетивост! операщй, що застосовуються до формули АШ.

У Н.З.1 доведено необхщи 1 доотатн! умови зб!гу результата д!1 оаераШй постановки но ода±й змиаий. Доведено, що ус! з&ужум! (розшретч!) онерацН подстановки для одного предиката д!«ть одааково.

У й.3.2 доведено неоШда! ! достат умови зб!гу результата Д11 п!дотавовочних оггерац!Й по р!зним зм1ншм.

У ЕГ.3,3 хфиввдено нбобх±да! умови ортогонельност! пре-дакат!в, що одержан! в результат! д1У даох гпдетановочних операщй лю одн!# ! по р!зним зм!нним на один ! той же предикат. Шд ортогоналъними предикатами будемо розум!ти так!

'■....; 11

предиката Рл I Ра , що кон'кикщя цих предйкат!в дор1внюе нулю:

Р., а Р2 = 0.

У П.3.4 дося£джено квантор юнування як операц!» над ск1нченниш предикатами.

Д1я квантора юнування на п - м!рний предикат Р(х^ ,хг.....хп) з областями значень зм!ншис Са^}^, I =

= 1ТЯ означаеться таким чином:

п*

Таким чином, д!я операци квантор юнування эхп<Р) на пре-д1кйт Р экв1ввлентна посл!довн1й ди оператй постановки по дан!й ЗМ1НН1Й

зхк(Р) = -ящ^Р).

Доведено, цо операция квантор юнування $}ка означена на мношн! унарних предикатов Р(х), де х набув&о &лачення а,,,...,ап, задоводьняе систем! аксюм:

1) з^ ~ рг) = згр,; - агрг;;

2) Множила значень операц!! э складавт*оя з двух: (00...О), Ш...1);

3) ЩО) * О; • 4} зО) * 1;

5) а (Р)Р = Р.

Доведено також, що аксюми 2,3 1 5 у подано! систем! не окоротн!.

Доведено, що для операци квантор юнування, означено! на мнокин! п - м1рних предикат!в вшонуються аксюми 1, 3-5.

Четвертой шзлол присвячено розробц! метод!в втлтвиня зтиних з предикат!в, як! представлен! р!зними формулами алгебри ск1нченних предикамв.

\г

У П.4.1 поставлена загальна задача виключевдя зм!нних. В Сагатьох практичнях задачах, зв'язаних 1з змютово» обробкою природномовно! нформащ*, немае необхшост! зна-ходити вс! набори эначень семэнтичних ознак» а потребно одержат»: на виход! один чи двк!лька набор1в значень ознак (цаяьовйх змшшх), як! мають 1нт^рес для користувача. Часто потр1бно знайти значения тльових змшщх ори заданих лочз«-кових умовах, як! являть собой фшзований наб!р значвнь т-озивк. П!д час розв'язання таких задач зм!нн1, як! не входять у початков! умови 1 не е цольовимя виключаються з р!вняння шляхом зв'язування IX квантораш: юнування.

Загалышй метод виклвчення зм!нних полагав у наступно-

ЩГ.

йехай в р!вншня алгебри екшченних предикат!в, яке мае вигляд

/(¡^ > • • < • • ■ • » " • ' {4).

да коХна зм!нна ^,...мае область значения А,* (а{1 ,а{2.....а{й(}> ЬТТй, щт чому система ознак

те задоврлыгятй законам еправииосш

а,я . . _

V « ...V ^ 1 = I, ¿=Г7п,

та хибвости

а О. г " "I, - Г7К{.

Првдустшо також, що при эададах значениях змшшх ,,.., Юц Ац } Мають бутя обчислеи! значения зи!я-

них так!« що р!шяшя (4) буде в!рне яри деяких

значениях зшляих х^

Загашюио дану постановку задач! математично:

♦ • * • .....Vх«* 1.....^ ~

• -1, (5)

що на мов! алгебри скшченних лредикамв виглядае такт щфм:

¿ VI,3 '• • Д • ■ •;

де В!лышмк е т1льки эм1Ш1 ,... знаходження набору

значень яких в розв'язаняям поставлено! задач!.

Система р!вняяь витляду В;

= Г/г, (6)

до задовольняе умовам

.....хт) * ^¿{х^^^,..,,хт) = о, г,

може бути зведена до витляду п В,

^ У &1(х1'хг.....хт> * 1'

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

0дн1й зм1нн1й.

Твердження ?. Нехай Р « Р1 (х^, ... .лц > а ■.,

А 0 * С.,.^ ► • • • гЛЦ ) А ...

л .....)• еп!вв!дношешя

. п ЛП-1+1 ' ■ яп ■

р э б (9)

виконуеться тод! ! т1лыш тод!, кож v ¿=Г7п в!рно Р4 э => б.

'Г

8. Пехай * ^(Р), Р^ « сг^СР). Си!В-

зшошення

в!рно тод! 1 т!льки тод!, коли для пр&диката Р виконуеться

ода» в таких умов!

1) - змшуючий, a cilf, ->■ розиирюючий оператор;

2) - звужуючий, a - роэширюючий оператор;

3) alc¡ ~ звужуючий, a alg - змвдючий оператор.

3 приведения тверджень можна зробити висновки:

1. Якщо v и * TTrí pft мають розягарюючий оператор подстановки то доданок, водатоводний J-й п1дстаиовочн1й опера-Iíií, при прим1ненн1 квантора юнування вбирае ycl оншо.

2. Якщо у k - T7ñ Рр мають звужуючий оператор гадога-йовки то доданок, в1дпов1дний }-й подстановочн1й оперши при прим1неннх квантора юнування скорочуеться.

У П.4.2 розглянуте питания про б1нарну декомпозицою. предиката.

Нех.ай е ск!нченн1 множили /í1 ,/L,,...,Ап, множина В = = (о, . ,ад) i предикат Ptx, ,хг,.,. ,хп,у), заданий на множин! А1 у. А? х ... х х В. Операщей бШарно! декомпозиции предикату Pti\,xz.....хп,у) назвемо його зображення

у вигляд1 добутку б1нарних предикат1в, «ко мають одну стиль-ну змояну:

Доведено, що предйкати Gi(xi,y), { = Тд! можуть бути збудовак! таким чином: Gl{x{,i:) = з^эх^...э.т за: ... зх'урЩ \х0,...*х„*У). Це ображення предикатов е мошмалыш,

Доведено тако» твердження про зв'язок однозначносто Е1добраз:еннй X « |1, да X ~ {х^ ,x,¿,...,хп), та mosuíhbocti йображешя Ефедиката Р у вшшд! (И ).

' R.4-.-3 дойраййно :меик?д виключеяня .зм1яэд& з-'йреди--катов, в|!бдо'гавлених у вирляд! ДНФ i КК&.де кожно» шф-?арзо|} даз?юнкц1ви укарй^хфджат. ..

Прияуетимо, е мэтематичн» модели, яка представлена у вигляд! системи р1внянь, кожне з яких мае вигляд ДНФ ! ус1 понарм. ков'дакци правих чаетин р!внянь дор!вну/оть нулю.

ПОЗНаЧИВШИ ДИЗ'ЮНКШЮ у р!внянн!, в1дпув1дному огш-

су ./-го об'екту предметно! облает!, здобудемрр!вняшя ви-гляду

Тод! эзсг(Р) = V Але застосування квантора

эгг(б{^) залшае без зм!н, якщо не мютить в есб!

вм!нну,±г. У противному винадку, яюдо = ~ "

л а а?, то з.т, (б.,) = л ж . Таким чином застосу-■ пУ ч 1 ..п) я

ванна квантора екв!валентне викреслюванню ушзнавання дано! змпнног з елемеитарно! кон'юнкцп.

НехаЙ модель мае вигляд КНФ, в як!й кожна елемейтарна диз'юнкщя е унарним предикатом. Припустимо також, що ус! по-парн! кон'юнкцп правих частин те! модел! дор!внвють нулю.

Позначимо J^iJ ( з = Т7К ) - элементари1 диз'кшкцн у вигляд! унарных предо"кат!в, в!дпов!дн! опису г-того об'екту предметно! облает!. В!дзначкмо, що зв'язування квантором зм!нно! у даз'юнкци КНФ зводиться до зв'язування Ц161 ЗМ1Н-но! в кожн!й КНФ Ф(, для котро! в!рно таке р!вняння:

" Д V

Кожна Дй$ мютить в соб! диз'юнкци певного числа пре-дапсат!в уп!знаьання, в основ! яких знаходиться х^. За прий-нятими позначеннями можна записати таке р!вняння:

де 1 « ТТТ. У - об'ем предметно! облает!.

3 пршедених М1ркувань видно, що Гфоцес виключешя зм1нних з предикат1в описаного вигляду нринаймн1 не усклад-нюв ЗГх структуру , а часто приводить до зменшення числа еле-ментарних кон'шкщй або диз'юнкщй в другому випадку.

У Я.4,4 видалено широкий клас л!нгв!стичййх р!внянь, як! назван! розщеплювотми та розроблено метод виклвчення эмшшх з таких предикат!®.

Розщешшеаними названо тек! предиката, де кожний до-данок складаеться 1з сп!вмножняк!в, у яких облает! змиших не перетинаються, лричому кожний я цих сшвмношнав мае або шгдяд диз'гаятивно* нормальной форми, або таку ж структуру, що ! в&сь предикат, тобто його можна розд!лнти на до-двнк!, як! в сваю чергу сюшдаються такой 1э огишножншав, облает! зй1нншс у яких не перетинаються. Матиматично моша записатй предшат Ру вигляд!

Р ® Л, V Лг'*• ... ч/ Ан* (12)

де ксжен з предиквт!в А%, 1 = ГГн, мае вигляд:

А^ = А^ .(.^ , • • • ) л ^ • • • ) ^ •,. .

Предиката А^. I - Пл, 1 = Г7Г мають або вигляд ЯНФ, або мо-жуть бути {юзкладея! по формулах (12), (13).

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

Крон 1, Розбивэемо дачатковий предикат на доданки.

1рок Кожен !з здобу.тих додашав розбиваемо на

СВ!ВШОЙ5ЙКИ.

Крок 3.. 1з злобу тих сшвмнокьзшв вибираемо тей, який

в!д змйшох, де виключаеться.

Крон 4. Якщо цей сШвмножник мае вигляд ДНФ, то проводило виключеяня змшних з даного ствмножника. Цей процес полягае увиконанн! таких операцШ

а) знаходамо уп1зяавання дано* змшнох в кокн1й еле-ментаршй кон'юнкци ДНФ;

б) якщо елементарна кон'юнкц!я складаеться Т1льки з утзнавання дано! зм!нно1*, то вся Д® перетворюеться в оди-ницю;

в) у противному випадку робимо зам!ну даного упгзнаван-яя на одиницю, що в тотожним простому викреслюванню уп!зна-вання з елемонтарно! кон'юнкци.

Крок 5, Якщо сШвмножник представлено не у виг ляд! ДНФ, тобто в!н мае складну структуру, то виконуемо для нього вс! д!1", починаючи з кроку 1»

П'ятий ТЮЗД1Л. гтрисвячено нрактичним застосуванням ре-зультат1в досд!дкень.

У П.5.1 даеться опис програми розв'язання лшгвютичнйх р!ВНЯЙЬ у ВИГЛЯД! .Iff® ! КНФ В1ДНОСНО шльових ЗМ!ННИХ bog3oi.

Програма написана на мов! Pascal. Операц!йна система -MS BOS. Програма прение у д!алоговому режиш. ПотрЮний об'ем пам'ят! - 64 К, об*ем програми - 632 оператора. Програма bogSol мае так! обмеження: число р!внянь - не б1льше 50; число зм1нних - не б!льшв 50, к!льк!сть значень ОПЗ - не б!льшв 30.

Вх1да! дан! заноситься в файли, а тако» вводяться в д1-алоговому режим! з клав!атури. В файли заноситься !нформац!я про 1мвна втттх 1 област1 припустших значень, р!вняння системи, а також записуються кода 1меи змитих i ix значень !з облает! змшних та fx повк! назви.

3 клав!атури в дхалоговому режим! вчодяться початков! значения та 5мена тих змшшх, значения яких необх!дао одеркати.

Вих1дн! дан1 заносяться у файл, який мютить початков! умови.

У П.Б.й. проведено опис програми роав'язэння систем розщешпованих р!внянъ в!дносно щльових змшшх.

Програма FindSol нашсана на мов! Pascal. Операц!йна система - MS DOS. Програма правде в Д!элоговому pesasMi. Ио-трШий об*ем пам'ят! - 64К, об'ем програми -1500 операто-р!в. Програма FindSol мае так! обмеження: довжина р1вняння -не о!льше 3000 символз.ь; к1лькють зм1нних - не б!льгае 50; область припустимих значень - не б!льше 100.

Частика вх!дних данях заноситься в файли, решта вводиться з клав!атури. В файл записуються эм!нн!, облает! IX значень ! р!вняння системи, а також !нформац!я про новн! назви зм!ншх та значень, що кодуються.

Початков! умови i мношна щльових змшних ьводяться користувачем з кдавзатури -при мдаовщшх заштах.

ВИХ1ДН! ДЭН1 у виглэд1 л!нгв1стичн0г0 р!ВНЯННЯ ! при-родномовно! !нформацп виводяться в файл телч запису в ньому початкових умов.

У -Й..5.8 июведено оц1нку складност-i розроблеяих алго-ритмш ??.г,б у зал-iKHocTi в!д т&ких параметра: загально! у.!лькогл змиших (п _>, шлькостч змшних, для. яких звдан1

cid! ...

почэткоь 1 >ксви (пяоч), к!лькост! щлмвих зм1нних (пц1 л),

кдлькост! р!внянь (nplfj), максимально! к!Лькост^ додашиз, на як! розбквается р!Еня}мя або кожкий сп!вмножник (ядод). макез ;альчо! н!лькост! сшвмиожншав, на як1 розбивается коший доденок (п ь максимально! довжини здобуто! в к!нщ

розд!лення ДН® (пДов), максимально! глиоиви вкладення (коли доданок разбивается на ипвмножники, сшвмножники на доданки 1 т.д. до здобуття ЛЩ)(пгд) i максимально! потужност! облает! означения зм1шшх (ппот) .

'ров S n5oBWW - '><пдод(Пдод - 1)х * «on(ncn / «до>заг + "йот " ПЩл)ир1вПдов *

1з формули (14) видно, що при невеликих прл 1 ппоч робота алгоритму досить ефективна. В1дм!тимо, що в прак-тичних задачах Ц1 параметра як правило невелик!.

У П.5.4 означен! облает! практичного застосування розроблених метод!в. Показано, що семантичн! ознаки для опи-су предметно! облает! повинн! задовольняти вимогам повноти, яесуперечливост!, ортогональност!. Розроблен! метода знахо-дять застосування при розв'язанн! задач л!нгв1стики, а також в 9Коном!чних задачах, наприклад, ¡три сегментаци ринку для визначення сегменту, до якого в!дноситься даний споживач.

ОСНОВНТ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

1. Здобуто залеяшеть mik вих1дним предикатом у вигляд! ДО i КНФ ! предикатом, здобутим в результат! д!! п1д-становочно! операци.

2. Знайдено необХ!дн! та достатн! умови юнуванйя звуку »чих, розширюычих ! зм±щуючих п!дстановочних операц!й ! побудови 1гоел!довност! таких оп»рац!й для здобуття нульового або одаиичного предакату.

3. Знайдено необх!дн! та достати! умови здобуття одна-кових предикатив в результат! д!! р!зних оператор!в постановки по одн!й 1 р!зним см!нним, а також выведено умови ортогональност! здобутих предикапв.

' 20 ■ ,

4. Сформульовано i доведено влаетавост! операц1£ квантор юнування як диз'юнкци шдстановочних операцШ.

5. Поставлено задачу вшшочення зм1нних шляхом зв'я-зуаанкя i'x квантором юнування, а також роэроблено метода спрощення здобутих ьнасд1док ules операци вираз!в.

6. Сформульовано i доведено необх!дн! та достетн! умови б1нарно5" декомпозищх гредакату.

7. Разлюблено метод вкклячення змшжх з предикат!в, як i мають тгляд ДНФ, КНФ, а також 1з розщеплювзних преди-k8tíb.

8. Проведено прогрзмну реаизащю метод!в розв'язакня л1нгв1стичних рхвнянь в1дносно тльових змзнних, коли р1вняння мае вмгляд да, Kftí t розщеплюваних предикат1в.

9. йдзйснено ouíhkjí скл&днгаст! розроблених алгоритмов.

10. Означен! облает! практичного застосування розроб-лвних метод1В.

РОБСШ ПО ТЕМ ДМСЕГШЙ* .!*, Кравец O.A., Ситников.Д-3,, Ситншовя ШЭ. Решение ликг~. Биотических уравнений'относительно, целевых перейенннх. -Деп. В ШГВ. Укршш,-«' Í0?4: - Ук.: 94, 1994. -14с.

■ Кравец O.A., Оитникова Л.Э. -Принятие оценочных решений нри проектировании интеллектуального штерфайее // Меадуна- ! родная научяо-те.хдаческая конференция "Функционально- ориен- I гированние шформациониые сиетет*, Алушта. -Í9S3. с.-28. ,

3. Оитщщоа Д.З., Ойтникова Й.Э., Швбанов-Кушнаренко Ю.П. Об сперацййх подстановки на множестве конечных предикатов. 1 Сообщвние 1. -Деп. в ГНТВ Украины, N1366 -Ук. 93, 199?. j "17с. .

4, Ситников Д.Э., Ситниковз Н.Э., Шабанов-Кушнаренко Ю.П.

Об опершиях подстайошй на «шщетве конечнах предикатов.

' 31 '

Сообщение 2. -Дел. в ГЖБ Украины, N927 -Ук. Э4, 1394. -16с. 5, Сйтникова Н.Э. Об операциях подстановки на множестве конечных предикатов. Сообщение 3. -Дт. в ЙГГБ Украины, Rt6S6 -Ук. 94. 1994, -15с.

в. Ситшвсовв Н.Э. и др. Некоторые математические модели семантики лингвистических объектов. -Деп. в ГОГБ Украины, Я1272 - Ук, 92, 1992. -20с.

7. Сйтникова Н.Э. Об исключении переменных в некоторых предикатных уравнениях. - Деп. в ГНТБ Украины, N1625 - Ук. 94, 1994. -17с. ■

8. Сятюйюва П.Э., Шабанов-Кушаренко С.Ю. Компараторная идентификация механизма принятия решений // Международная научно-техническая конференция "Функцконально-оривнровая-ные информационные система", Алушта. -1993. с.14.

Sltfilkova P.S. The substitution operations algebra and Its applications for automatic information systems. The present thesis is a manuscript to complete for earning a candidate oi technical sciences, the speciality: 05.13.09 -mathematical and programing maintenance of computers and systems. 8 scientific works, which contain theoretical reseach of the substitution operations algebra. Methods of solving equations systems of finite predicate algebra with aim variables under given initial conditions have been developed on the base of theoretical reseach. fhe methods have been realize in the form of programs.

Ситникова TL3. Алге<5ра подствновочшх операций и ее применение в автоматизированных информационшх системах. Диссертация является рукописью на сойскайиё ученой степени

■ ■ 22

кандидата технических наук по специальности 05.13.09 - математическое и программное обеспечение вычислительных маши и систем, Харьковский государственный технический университет радиоэлектроники, Харьков, 1995. Защищается © научных работ* которые содержат теоретические исследования алгебра подстановочных операций. На их основе разработаны метода решения систем уравнений алгебры конечных предикатов относительно целевых переменных при заданных начальных условиях. Проведена их программная реализация.

Ключов! слова:

тдстановочва операция, квантор юнування, виключэкня

ЭМШШХ.

В1дпов1дольнкй за вдауок В.В.БбЗкороВ-зйний

Шдпу^зно до друку 21.11,95.Формэт80х84 1/16.Пап1р для мн.ап. Друк. офс. Ум. арк. .Облш,- вид.арк. 1,0. Зам. N

Тщтж 100 прим.

£ругарня УШ, т.

Сьобози, 8