автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Линейные и билинейные операторы и их применение в автоматизированных информационных системах

М1Н1СТЕРСТВО О С В I Т И У К Р А I Н И

ХАРКШСЬКИЙ ДЕРЖАВНИЙ ТЕХН1ЧНИЙ УН1ВЕРСИТЕТ РАД10ЕЛЕКТР0Н1КИ_

РГ В На правах рукопису

г . ,

РОТ1Н 1ГОР МИХАЙЛОВИЧ

УДК 681.3.016

Л1Н1ЙН1 ТА Б1Л1Н1ЙН1 ЛОГ1ЧН1 ОПЕРАТОРИ ТА IX ЗАСТОСУВАННЯ В АВТОМАТИЗОВАНИХ 1НФОРМАЦ1ЙНИХ СИСТЕМАХ

05.25.05 — 1нформацШн1 системи 1 процесн

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

X ар к I в — 1994

- Роботе виконана на ка$едр1 програмного еабввпечення ЕСМ Харк1воького державного , тешчного ун1верситету радювлектрониш.

Науковий квршшк:

>» ааолуканий д1яч науки та техниш Укряхниу

-доктор тезш1чвих наук, професор Г).П. ШаОаяов-Кушнаренко,

0фЩ1йн1 опонакта;

доктор техмчних наук, профеоор 0.0, Росьл

кандидат тодичних наук, от. наук. сп!вр. К.М, Буслис,

Цров1дна орган1зац1я: Харк1вський двряаввяй пол1техн1чний

ун1вврситет.

Захист дисертаци вЩудвться/У/119Жр. о годин! на аас1данн! специшвованох ради К 068.37.01 в Харк1вському державному унгверситвт! радюелвктрон1ки эа адресов: 910726, к. Харков, пр. Лен1на, 14. Хах: (0672) 40-91-13. ■ . "

3" дисартащею мохва оанайомитись у б1блютец1 ун!верситету.

Автореферат розюлано

Вчешй секретер спец1ал1зованох ради кандидат твхн1чних наук професор

Я7 - зм^

ж

Е.О. Дедков

ЗАГАЛШ ХАРМТЕРЙСТШ РОБОТИ

Актуаидють i ступ1нь дослздаености тематики

дасартаци, Зсстосування кош'юторноз: тэхшки, п шввдгай

рознится обушвлаз висок1 чвшт. розвитку. матоди» побудова ШТ&лдУлуаяышх оаогеы з piaran пркзначошзян. В тепврэтвхй чао ase розроОлопо ыатодолопчннй i тахшлшй шдхода до paspe-Cira i винорнсташш 1нформацШш: систем. 1снуш1 1ятвлектуальн1 1нфор?;шц1йн1 система пдши виконувата функцИ, як1 ранило сули вшишчно прерогативою лэдини: доводата матвматкчн! теордая, первкладатл тексти з одн1<з£ шва на 1ншу, д1агпосгувати хвороби i вшанувата багато 1нешс Функций. Однак в рорсшзктив! 1дештьна обчнсяювальна шшзша повинна порэверзуватм зд1бност1 лвдини лоПчно кзслига« виконувата опалю шфорлаци, що недщякть» вкршувати склада! задач!, взазмод1ята з яавхолжш ссредоашдем.

Одшза з яфэютваих ушверсальнш; цатематггоmx sacoOlB для опасу 1Еформаци в алгебра продакапв та хгоедккаткях ompsuifi. Коков щи алгебр лэгко 1 зру'шо ошсувати р!зну щфоркацих, що формал1зу8тьсл, здлйснкшак! зашзтн до баз до них та моделгазата д1ллыисть лскиш. ДасэртацШа рс'сгга црзсвячэна розробШ элгеорп л1н18ишс црэданатаих спорадш, внвч&вгаэ mix властавостой та способ1а завдашя, а такса ггетод!в Хх застосувшшя • для опксу лшхЫспряш seKOHoyipaccToñ 1 вир1шэнш> кванторшк прздахотшп: р!внякь. &зготв1сть засгосування л1Н1Йшп предакатшя оперзцШ для пог1чпого Elсводу, для спису isjopáams» що форМ8Л1зуеТЬря, тагаютЕчних евконом1рноет.'ей та росв'лзакша задач

розшааавання та класиф1яац1Х об'ста визяачае актуальнють давой теми.

Мета та ОСНОВН1 аавданвя наукового дооладкэння. Метою

роботи в розробка теори л1Я1йних та бшяияих лоПчних оадраторхв для И подалыпого викорнотання в автоматизованих 1нформац1йннг системах.

Ссновн1 аавдання наукового досл1даення:

- онал1з формальних засо01в йнтелвктуадьких систем;

- внал!з м9тод1в алгебразсзаци домки;

- акал13 ваотосуванпя лдаядах ошраторлв у Л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вац12 то впровадааннл наувовкх розробок.

ДнсертацШга робота виконана в±дпов1дяэ планам настуших нвуково-досл1дшк роб1Т ун1вар«1т9ту: тема ГР 01900059650 "РозроОка математичного га програмного аабезпечеяня 1нфо|М8ц1йно-пошуково1 система обробки даннх", Д9рябюдавтн1 теш М 80051472 "Розробка теор1£ програмно-обчислювальшх засо<31в та л1нгвнстичного забвзтачекня обчнолюгэльш! темшш новях поколшь", Л 11021352 "Розробка теор!£ ннтелекту та побудова на 15 основ! програмпо-технпчкого забээпеченя ЕОМ нових поколть".

Результат дисортщано! ирац1 впроввдаен! у виробництво та учбовий процэо, впровадаення тдтвердаена вадповАдншя документа!.«!

Апробац1я робота. Основа! результата дисертац1ЙШ01

робота доповлдалпсь та обговорювалася на IX Всееоюзпшу оишоз1ум1 "Ефвктявшсть, якють та надхйнють систем ■ лэднка-твхниса" { Вороная, 1950 ), на йсэсовзн1й хонферешиз: "Ороектування, ощяка та оптим!зац1я функцюнуваяня систем ладша-теншса" < Сэваотополь, 1990 ), ал V Всбсслзн1й икол1-сем1нар! "Бюниса штэлокту" з запроиенням заруошш учасшсав (Ха?к1в, 1991), на Ш1 М1лрзпональаому семшар! "Ерговоша та еуСактзвиЮть систем лвдина-техн1каи (1гнал1на, 1Э91 ), яа V Воесошн±й конферэкци "Банки данях га знань " ( Льв1в, 1991 ), на 1 Всаукрашсынй конференци * Обробка сзгназна 1 зобравепь 5а розп!знавання образу" ( 1и1в, 1992 ), на М1шардн13 каукоБо-твХЕ1ч21й кснфоранцИ

пфункц10налън0-0р1йЕ'1'0Еан1 обчислювальн! оаотеки ШЮп (Алушта, 1993), на мишвродаому теоратичнанаракотшоыу сэы1нар1 " Кодаьшврн! ъъгттги г заотосуваная до техшлшх., вколомчних, комерцШшх, кадаотрових, ввдавншда; та нввчаяыщх проблем ( Льв1в 1594 ) а твксш на ряд1 р9спубл1канських «а еональнах форумах.

Публ1каци. 8а матар18лаш даооертацИ оаубл1коввно 6

роб1т, сэрэд ник одна монограф!я.

Структура та обсяг дасертащШох робота» дасэртацШа

робота складаатьоя 31 туну« н'яти роад1л1в„ шшовк1а» списку ллтератури в 104 на&мэвуваняь та додах-к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 прэдакаютх операций двт9рм1нован1 1 дискрвтш 1нформацЦ5н1 нроцэси спнсувться за допскогоэ в1даов1Д!шх р1внянь, що з устном узгодауеться з р±знззш моделями представления внань 1 щлхом в1дгтоШдав особлнвостям ингэлектуальных вродес1в оброскя даних

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

IЬ ссдов! 8Д1йсеэного анэл!зу моааа ваззэсти, що алгзбра предяка?1з I прадвкатних оператй^е ун!ворсальннм фор/;алыдз.1 засоОсм для опасу р!зного вяду 1иформаци, що влкористовузгьса 1нтелектуальшма система. Проте у мзках

влгебри предакатних опврацШ ш було розглянухо цредикатн! огирац!*, що мають ваалив! властивоси Л1Н1ЙН0СТ1 та однор1дкостг,як1 в1добраиають специфису шфорлаци, що • фэрмал1зуеться, ЗвАдки вишшвао основнкй напрянюк досл1дкэ:шя : розробити алгебри а лиийними 1 йиивишими преднкатшмн операцшш.

У другому розд1л1 розглянуто питания оинтвву

алгвбра1чних валекноствй у цроотор1 дво!чнкх код!в. Вивчево

• влаотивоо'П простор1в. Розроблано влгебри з првдикаушши та

л1л12шша првддкатниш ошрац!ями. Обгрунтовуетьоя

наооххдають та доцшькють розробки алгебри з лШйними

првдикатиима операщями. При розроощ твори л!н!йнях

предикатних ояератор!в виникав нвобх1дн1сть у викориотанн!

п п

властивоствй пввного типу лопчних проотор1в Е 1 Ел над

допчнш полем Е={0,1>. Доведано, що мновдна Е , що б п-им

дакертовкы ступенем маожани В 13 введониш на н1Й операц1ями

п

даа'шкци дов!шшх олемешчв X, У « В за правилом: X у ТГ - ( х, V У1.....V у ),

п

1 кон'шкц1Х довш>них елемант1в Я е Е к X « Е за правилом:

А. А X » ( Я. л х.....л, л х ),

п

р лопчним простором, що позначавться Е^.

Доведено тверадення про юнування у лопчному простор!

п

Е^ базисное система вектор!в 1 понноту цього простору, Йшраючись на доведен! твервдвкня, одержано формулу для однозначного розкладу довшшого вектора X по ф1ксованому базису лопчного простору.

. X - V (С, л е.).

(=1 п

да Се^^ бааисна система у простор! Е , а С{ * Е.

Уведено лопчний простлр Ел , що в дзо*чнам до простору

п

Еу Внвчено метрича1 властивост! лопчних простор1в.

При опио! об'ект1в I вшояень мовою алгебри скипенних предакат1в вшшказ яеобхцщють у запасу р1зшх умов, що зсм задовольнягть предиката, вживен1 у ц±й алгебр!. 3 ц1ею метою Я.П. Шабановим-Куширонко була уводена алгебра предакат1в. Природним розвитком ц1е! алгебри в кванторна алгебра оредикатних операщй, що розроблявться в дисертац1йн1й роботл.

йэхай О ун!версальна мяойина прэдмет!в, а мнозиша Ы в

п

ун1варсумом прэдакат1в. Шохину М назвемо предикатним

простором, а елбменти простору - предикатшми векторами.

п

Довишну функцио Г( Х^, ... Дп ) = 2, шо д1о 13 мноаини М

в мнокину Ы, назвемо предикатною оператею. Множину ус1х

п

предякатних огорац1й, що в1добра»авть мноаину № в й, незначимо буквою в.

П1Д кванторнок предикатною оператею будемо розум!ТИ операцио, що д!е 1а множили С в 8 га наступили правилом:

3 х{ в А Р (х1 , ... ,хп)= 0 (X, , ... ,хп), де А непуста п1даюжккв множили и.

Кванторною алгеброю преднкатних операц1й назвемо таку алгебру предикатных операц1й над в, у як1й баанснами операц!ями е спереди, що мають вигляд :

з х1 * А Р (х1 , ... ,хп) 1 операЩ! запэречення 1 кон'шкцН, а баэисниш элементами з предиката р1вност1 Щх.,, ( £ «з ) та зишл

продаати Х{.

У робот! доведено твервдення про пошоту кванторнох алгебри. Встаноолено, що дов!льну предакатну операц!» 1з

ыножини прадикатдах опвратй 6 маша виразитн васобаын кванторно* алгебр!, грунтуючиоь на тому, що yot базисш. элемента i Оазися1 операции даз'шкишно-кон'шктивно! алгебра шауть бути виракэн1 через базиса* елемэнтя i базисн! оторац« кванторно! алгебри.

1з шоииш yets предикатних опэрац1й у робот! ввдшна i вивчбно клао лиийнкх предикатных операдлй.

Лш1йков в1даосно диа'шкцп аредякатвоа олерац1ею . аазвеьзо теретворешш шояшни H у сабе, яке з адово дыша аастушшм умовам:

l.Fj(PvQ)- ïb(P) v *i«m 2. = 0, да О нульовий предшшт.

Ыно&ану ycix Л1ы1йних предиката опарацИС, що виавачен! вэ множит Ы, назвемо Л1н1йнш влдносно операци да'шкцИ класом i позцачимо чараз L. У робот! розглшнуто OûHOBUi власишосп вщцленого клаоу.

Довэдаао, що клао вредикатних onepauifi L в ваыкнутйй в1даооно onapauiâ днз'шкци i оуперпозици. Показано, да такай клао в вашшутш Б1дносно одараци коа'юнкцИ тод1, коли для будь-якйх предикатных операц1й F1 « L и IJ2 « 1 мае мюце 1мш!1кяд1я

<?,< Q ) А ?а< Р » V ( V Р ) А ( ï2 )l Q > => -> С * ïа )( Q ) V ( Pt А Р2 )i Р ).

Проте одержаний вираз на е тотоанютю для ycix. Л1н1йних предикатних оаерацш is L, Отка, клао лтших предикатних опарац!й ае а аажнутшл в1дносно onepauiï коа'кшщх.

п2

Вотаыовлеао, що клао л1Я1йних операц!й нютить 2

и

р!зкихелэ?г9ит!з. Текли чином, часяо влэ^энив гласу ь рост© 0Г:спопзнц10льт ia зб-иьязнням п, що означав еяльшу сп1льн1сть властавост! лйШност-1 предикатно! опэраци. Яодувчи довллш! прэдаатя у вкгляд! дбозмних ввкгорхв яопчкогэ простору, опэреци над предикатами могша ототокшта а даретворенкям лоитаого простору в1двов1дно1 роз:! ipHO Q" i ,

Для б1льш яовного застосуванпя вйразшп ножяивостей нова кванторно! алгебра предакатннх операщй при ошс1 лопчнвж доов, що хм вадовольняють предщсяти, ПОТр10НО нивчити властявост! базиснкх опаращй i сазиснкх. влвмьнт1в Щвзс адгэбрн. У робот! доведено, до гаантсрн! продикатн! оверац!Е, як! е базнсишми операцией! у квааторяШ елгебр!, являать собою окрвмий вкладок л1Н1Ших прэдккатних операц1й.

оск1лькп в5ф83

3 X ( Р(Х) л К< X, у ) )

в кванторнвм записок л!В13ного лопчного оператора, прэдвкатн Р( х ) i Н{ х, у ) в з!дпов1дво унаришот 1

0±наршми дошлыткп праднкатеш, гцо задан! нэ унхаэроум! Ü.

У трэтьсну розд!л1 розроблеэо алгебра Л1я!йнпх

лопчних ошратср1з. Прэдякатшй просир М !э внзначешш на ньому класом ллнй&нх предккетних опэрмглй { ?L ) яазивзетьсялиийнзм прэдэкатпш простором i гозначаеться символом

Л1а12шй£ ломчпяя прост!? Ь 1 Л1н1йшй цредаяаяай простер наэшовтея 1зомсрфй!С£И, явдо И1а 52. влемвнтамя коша встаноантя взаекио одаозначну в!да>в!да1сть ф таку, що

якщо

ф ! X — > X*. ф : У -> У*.

* *

X, У « 1, X , У «

то

ф : X у У--> X V У ,

» »

Ф : а, д X -> а, а X .

У робот! доведено, що лзяИйий предикатный просир

в

иэоморфний д1Н1йяоыу лопчноыу простору Е^ при в!даов1дному

вибор1 п. ЛХнШими операщяш на лопчшх просторах

оаерувати вручниае, нля довиьнида предикатами опэратями.

Цэ дозволяв вастооовувати р1зноман1тиий математичний впарат

для досл1даення властшзоствй цих операц1й, анвлопчний

математичному апарату л1Н1йН01 алгвбри, У робои Л1н1йна

предикатна ошращя роаглядаетьоя як Л1н1йний лопчний

п

оператор И, що д1в 13 лопчного простору Е^ в себе, 1 аадовольняе наотушшм умовам :

1. р(Х V У) « С(Х) V В(У) для будь-яких Х,У « в";

л

2. к X) *> к к Б(Х) ДЛЯ будь-яких X « 1 \ « Е,

Доведено твэрзденнд про аагальний вигляд л1н1йиого

лопчного оператору. Встановлено, що якщо Ю е Л1н1йний

п

лопчний оператор, який д1в а простору Е^ в оебе, то оператор 0 однозначно вианачаатьоя матрицею коеф1диент1в (й^) разм1ру п * п, Доведено, що вшшв оператора В на вектор вианачаатьоя формулой, записавою . в матричному вигляд 15

<ц, ... <цп h

й'Л) Ш У „ * «я

Ч

Встаяовлэна взаемио одаояначау вйщовццИоть та

матрицаi® раэм1ру n х п э елешнташ 13 Е i л1н1йниш

логичннщ . операторами. Розв'пзано задачу 1дентиф1кацц

лШ1йного лопчного оператора. Доведено, що стовщ1 матрщ1

л1и1йного логхчного оператора точно спизпадають з векторами,

що являвть собою результата вплнву оператора на сазисн1

вэктори, прнчому перший стовгоць матрищ оператора спшпадав

а вектором, в який переводиться базисной вектор, у якого

перэа координата доризнюз одишвд, другий стовбець мивпадаз

а вектором, в який переводиться базясний вектор, у якого

друга координата дор1вш>з одишади Таким чином вкзначаються

yol п стовшцв матрщ1 оператора.

У робот1 дооллдавно клао регулярная: лтшш. лопчних

-1

оператора. Доведено, до оператор D , обернвни® до

л!лШюго лопчного оператора D, такса лиийний, -причому,

матриця оборненого оператора D спшгадав з транспонованок»

матрицею оператора D. Отримано критерлй рох*уляр:юст1

оператора D. доведено, що л1л1йний лопчнзй оператор D в

рэгуляршш в тому i илька тому випэдку, коли в когаому

рядку i стовпд! матриц! такого оператора знаходоться один 1

Т1льки один елемвнт рлвний одяншц. Показано, цо лхнШшЗ

п

лЬнчвий оператор,який переводить баэио простору Е^ в себе е регулярним, 'фичому есього юнугз ni р1знюг. регулярних оператор ib, що дють з простору Е в свбэ. Доведено, що

V i

суперпозтшю двох лнийнкх лопчши операгориз з матрацам::

у е д1д1йний оператор о матрице» оператора ® = * ¡3, яркому, якщр едемэнтй а<Й, в^ и Сц нвленать в1дпов1дао

ыатрицям 41, 85 я® то с^ = V ( л а^ ) («,/ « ).

• Й*1 я

Нехай X 1 Y - довшьн1 векторл з простору Тод!

1шл1кац1й X => У ( X <=> У } а ютшою, явдо 1стшш

1мшшкаци вщювщшх координат. Доведено, що оператор В,

п

якиа задозольаяа ривнянва В(Х) -> X для уо1£ X « мзэ матрица виду:

А О ... О О А ... О

О О ... А ,

де аамють в!рочок коготь стояти довшд1 вкачокпя. 1з

вагального внгляду матриц1 Оезпосерэдньо вишивае, т всього п

юнуе 2 операторю, язи зберхгаать 1шл1кац1ю • ■* 1 для

будь-яких вектор!в. У робот! доведено, що оператор який

«

задовольаяв рхвнянно ЩХ) *• X для ус1х X « Е^, мае катрищ» веду:

1 а. •1

А 1

всього юнуе 2

1з вагального вотляду ыатриц1 оператору 0 ВЕПливае, що пг-п

оператора, як1 з(5ер1гають 1кпл1кад1ю ' п

<= 'для будь-яких X « Б .

V

Нэхай А 1 в л!н1йн1 лог1чн1 оператора, визначен1 на п

простор1 Еу. Диз'шкциеи ТЕг.он'юнкцибю) цюс операторов н&зиваетьоя оператор 0, що отримуеться у результат! в1дп0в1дннх г-елементних диз'шкцлй (кон'юнкщй) ыатриць

глгаратор1в А 1 В. ¥ робот1 доведено, до р!внявня

( к V В И X ) - А( X ) у В( X )♦ п

а тотокаюта для уо1д X « Проте .для того, щоО Л1я!йн1 ¿»14431 оператора А 1 В задовольняли р1вноот1

■ ( А л в )( X ) =■ А( X ) л В( X ), .

ваобидио л достатньо, щоб коефщиенти матрнць цах снератори» задовольняли ршюот!

/ е* &

для всех ( в 1 ,,,,, п.

Вааливою ввдаетьоя задача виэначешш л!нШгаго лопчвого оператора, що задовольняа р!вност!

А { X л у ) - А(Х> л

п

дэ Х.У в Е^. У робот! доведено, до такиЗ л!Н1йшй лопчний

оператор А мае матрица сяератора, а кожному рядку лко*

епаходаться не бш>ш, та один елэмент, по дор1внюе

оданкц!, причому наведена умова е неойходноа 1 достатньою.

п п

На простор1 Е^ моянэ визначити (п + 1) оператора, що

вадовольняоть ц1й влзстивост!. Очевидно, що уо1 рэгулярн1

опораторп задовольцяють так1й влаптивост!, яка вишшваэ !з

твердаення про загальний вигляд регулярного оператора.

У четвертому раздш розроблено алгебри бШягйних

преддкатних операщй. Б1Л1н1йноо в!дносно даз'юнкци

предикатно:) операцюю Р 2 називаеться гюретворэняя

2 1

предикатного простору Ы в М, яке мае так! властивоот!.

2

^ 1. Для дов1льних пар предикатов ( Р, СЦ) « И 1 (Р, С^} а й в!рна р!вн!сть

Рг2( р^ От V а2 } а ?т?( р' ^ ) V р 9(Р. Оо)>

Ь X

2. Для довшышх пар преднкамв ( 0) «и ± <р£, а) « М мае мюце ровнють

^ Р1 V 0 > к р1» 0 > V * а* р2' 9 >-

3. Р 2(0, 0) « О.

X

4. Р 0(Р, О) - О.

X2

Доведено» що клао бИИнШшх нредикатнта операцШ г?

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

Предикатний проспр М2 8 вязначеним на ньому класом бшнойних предшштних операций С Р 2 ) незивавтьоя

бШнШша предикативы простором 1 позначветься символом

Ъг ьг

Б1л1п1Лний лопчний проот!р Ь2 1 б1Л1н1йний предикатний -вроет 1р 8 називаються 1зомор$1Шми, яхщо млж за. елемэнтами X2

мовда остановите взаеыао однозначну в1дпов1днють Ц> таку, що явдо

Ф : X —-> X , ф : У —> У , г « *

X2

то

* • *

ф : X V У --> X V У ,

* *

ф : X д X --> л Д X .

У робот! доведено уверздешя про озомрфозм просторов

71 п

3 И Е * Е . при в1дпов!дному вмбор1 п.

£а V V.

1а 1зсшрф1зму, що був доведений, шшливаа вивначання

б!л1н1йного лопчного оператора. Оператор В(Х,У), що Д1в в п п п

простору Е х Е в В , називааться 61я1н1йшш лоПчним

Г V V V

оператором, шцо от за довольна а таким умовам :

п п

1. Для вс!х (X, (X, Уа) « Е к В те м±сцв

i £ v V

р1ВНЮТЬ

В( X, У, V ь ) = В( X. > V В( X, Уй ). 1 й п п 1 й

г. Для ВСIX (X, У) а Е х Е 1 будь-якого X а В МЭв

глсцэ р1внють

В( X, \ л X ) =» X л В( х, У ),

п

3. Для В012 { X,, У ), ( У ) 6 Еу * мае

ш.сц0 ривнють

В( Х1 V Хр. У2 ) - В( Х1, У > у В( Хд, У ). с л и

4. Для вс1х (X, У) в Е X Е и любого X а в мае м1сцэ

v v

р1внють

В( К Л X, У ) » К Л В( X, У ). У робот1 доведено, що явдо в( X, У ) б1лля1йщ$ лопчний оператор, то В1я взаемно однозначно внзначасться

и

ыатрщею коаф«щент1в вй « Е, ( и « ) I

вплнэае на тгару (X, У) за формулою:

п и

ай « V < х, л у л в ' >.

Бишийний ломчний оператор В(Х, У) назвемо симетричним, якщо В( X, У ) = В( У, X ). Доведено, що для того, щоб 61Л1Л1ЙЕИЙ лоПчвнЗ оператор був сшетрачним, необидно 1 достатяьо, щоб конна натриця розм1ру п х п, що отримувться з матрту. оператору при фиссовакому к « 1,...,п, була симетричною, тобто - в,, для к е

iß

Розв'яаана задача 1дбнтиф1к8ц*х биннШого ошратора. Для того, щоб видаовиго матрицы оператора аа взктораш, на ßKi оператор вшшвае, та векторами, що отрккуетьоя в результат! впливу оператора, достатньо внати, як вin д1в на пари базисних векторов, Л1НШ1 операторы у ) i 8Д{ X ) спшшдавть, якщо öUiiHlüHsa оператор В( X, Y ) сЕчетритаай. Д1йсно, оператор В( X» У ) сшлвтричшй, зв1дки п ij п ij

tj ji

Оскизьки Вй = Bft , то матриц! л1пШш; лопчявх оператора Вд( X ) i ВА( У } сп1впадають.

Актуальною е зворотна задача: чн моада, знаачи jmiiäai оператора ВА(Х) i ВА(У), в!дношти 61л1н1й1шй оператор В(Х, У)?. У рсбот1 знайдеш окрэм1 ришення поставлено! аадач1, показано, що у загальному вкладку ця авдача невиринувана. Доведено, що яюцо Р(х) Q{y) - ллншл регулярн1 оператора, то за парою { Р(х), Q(y) J моакяа визпачлти оператор В(х, у), цркчому за парами i P(z), Q(y) > i С Q(y), P(x) > в1даовлшться pisKl бшниш опоратори^ якщо оператора P(x) i Q(y) сп!шадаа>ть, то вшовщий 01л1н1йний оператор е сшатричним.

п

Подання еленопив наград! ланШюго

ломчеого оператора у вягляД1 в*' - а1 л й* для yeiz i,J **

. i п t п

, дз а1 1 с*' елоыенти шсшн С а 3{=1 и ( aJ )

в1дпов1дно, називаетьсл кон'шктивним поданяям матриц! лш1йного оператора.

Для дов1льного л1н1йного оператора не юнуз його кон'шктнвного подання. Д1йсно, на для Оудь-якох мнокшш

п I п {

ко0ф1Шент1а хснують дв! ьшошни { а )(=1 ! {

, так!, да в4^ « а4 л о^. У робот! доведено, що

мсихшвють кон'з.шктквбого подвння матриц! дзялВного

допчного оператора екв1вадентна вирадсмоот! настушох

сиотеыя ' '

А <-а1 л о, > - 1.

У ( а, л о^ ) =о.

БазначениЗ критар!й легко ааотосувати для матрица

дов1льно1 розшрност!. Показано, що довшьну матрица

рр.зм1ру п х п ио£аа подата у вигляд! диа'юняци не б!лыа та

и матриць, що кон'енктибно розклаяет.

Подання 61л!н1йного лоПчного оператору у нигляд!

кон'внкци двк1лысох лилйних оператор!в пазкваеться

кон'шктивнш подвнням. доведено тверадення, що ятацо В( X, У

) б1л1н!йний, а А( X ) и 0( Т ) Л1Н1ЙН1 лог!чн! оператора,

то в!рно наотупнэ кон'тактивне подання:

В( X, У ) = А(Х) л 0(У)

И 4 3

а тому 1 тллькн в тоыу випадку, ящо вд = ай л сл.

Вотаионлеко, що дов1льяпй бшшйний оператор не моаэ

бути подамел у вигляд! кон'шкцп двох л!н!йнйх лсччних

оператор1в. Показано, що для довшьного • б!л1н1Дного

лоПчного оператора Юяуе таке подання : п п

В(Х. У) - V ВДХ, У) - V ( АЛХ) л О,(У) ), 1*1 1 4=1 1 *

дз ¿¿(X) I 0{(У) - Л1Н1ЙН! ломчн! оператори.

У робот! розглянуто оововн! влйстивост! 61л1н:шн0г0

лопчного оператора. Встановлено, що рштсть ( В1 V ... у Вп )< х, у ) - В,< X, у ) V у В„{ х, у в тотожнютю при будь-яких <Х, У) в ЕП * е"»

v V

Доведено, що р1внють :

(вдс ) (X, У) « в(х, У) д <цх, У), виконуеться в тому випадку, коля коеф1щенти штрщь щж. операторлв ведов^льняють р!вност!

п ^J Хт V ( в, лс ) . О

1*1

ДЛЯ ВС1Х ь.

У п'ятоыу роздш. розгляшуто практичн! вастосування

результаив досл1дквняя. На основ! теорп л1н!йних лопчних оператор!в розроолэно ! програмно реал!зовано алгоритм риаепня кванторного предикатного ршшння виду: 0( у ) - Э X <Р( X ) л К( у, X ), Розроблвний алгоритм дозволяв знаходити невадомий предикат Р(х) за биааршш предикатом К( у, х ), ! унарнин предикатом 0( у ), що задан!, зиклачапчи частково чи повнютыо повний пвреСЯр.

При розв'язанн! багатьох задач в галуз! обробки ! збер1гання ифрмацш: вшшае веойх!дн1сть анал!зу 5ЖШЛИБ00Т! виводу НОВО! 1Нф0рМ8ЦИ 8 Д0НИХ, ЯК! в В баз! знань хнформацЩаа систем, а також безпосереднього визначення алгоритму виводу.

п

Дов1льний елемент X а Е \ 3 наводиться з нноашни Б,

УЛ

якщо його кояна отримати в результат! застосуваиня кищэвого

I

числа операции даз'шкцох або кон'шкцох до елементов

шокини S. Розв'яааво задачу: дня доволышх 3 i X визначати,

чи виводатьея X з S, 1 якщо так, то якоо конкретно

послодовнютю опэрацой. Будемо позначен! колькость одшшць в О) Ю>

елемант! X через X , а к!льк!оть нулиа через X .

Доведено, що для того, щоб X можна було вивеста а 3

необидно 1 доотатньо, щоб X южна було подати у виг ляд! s

г (D

х = V <М s >, г s х ,

де Gf ( S ) з кбн'кнкцоя елеметча, то складають подмнояину !з S. На основ! твернденяя, що було довадене, побудовано ! програшо рэалозовано алгоритм выводу. Вказано галуз! аастосування отршавих методов i алгоритм1в.

В додатках наведено копи про впровадаепня та Ъйяористанпя результатов дцсертацойнох роботи, а такоа розпечатка програм, як! реалоэувт розроблан! метода. ОСНОВШ РЕЗУЛЪТАТИ ТА ВИСНОВКИ

1. Дослодаено мзтричн! властивосто логочних просторов, IX повноту та замкнен!оть.

2. Розроблено кванторн! алгебри з лонойними прадикатними оперецоями. Доведено озоморфность лояойних предикатних та лопчних простор1в..

3. Отримано загальний вигляд лонояного логочного

»

оператора, Розв'язано задачу одентифокацозс таких операторов.

4. Вивчено омпликативно ачастивост! . лонойних логочних операторов. Еидолено i вивчено клас лонойних регулярннх операторов.

б. Розроблено алгебру болонойних логочних операторов, отримано загальний вигляд болояойюго оператора.

6. Розроблено метод подання б1л1Н1йного лопчного

)

опара юра у вигляд1 дез'шкцП яшшш лопчвех оператор ни Досл1даепо ' диа'шктивш. i кон'внктивн! властивоот! б1)11н1йних лопчннх onepaïopiB.

7. Розроблено i програмно реал1.зовано алгоритм розв'язання кванторшх ярэдакатних р1вняннь деякиг окрэмих

вид1в.

0. Побудоваво i програмно реал1зовано алгоритма розв'язання задач1 виводу в алгебр1 доячних код1в.

Освоений smict днсертаци опубл1ковано у таких роботах:

1. Ротин И.Ы. Шабанов-Нушарбнко В.П. • Линейные логические операторы и их применение в информационных системах. - Харьков: Деп. в ГНТБ Украины 17.10.94 N 2020 -Ук 94. 117 о.

2. Ротин И.М. О билинейных логических операторам. -Харьков: Деп. в ГНТБ Украины 17.10.94 H 2019 - Ук 94. И о.

3; Ротин И.Ы., Ситников Д.Э. О дизъшктивно-конъшктивных вввасимоотях. - Харьков: Деп. в ГИГБ Украины 10.04.93. К 1441. - Ук 93. И о.

4. Ротин И.М,, Ситников Д.Э., Шлбанов -Кушнаранко D.II. О д^ъшкашночюш,шктивных 'занисишстях в алгебре двоичных кодов, Сообщеша 1. - Харьков: Деп. в ГНГБ Украины 13.09.93. H 1336 - Ук 93. 18 о.

Б. Ротин n.M., Ситников Д.Э. О ' дизшпшшао-кокькактивных йавкск-.гостях в. алгебра двоичных кодов. Сообщэнзэ 2. - Харьков: Доп. в ГНТБ Украшщ 15.05.93. N 33S5 - Ук 93. 14 с.

6. Ротин U.U., Рублинзцкйа В.И. Задача вывода в алгебра

двашннх кодов, - Харьков: Дэп. в УЕГВ йсрашш 10.05.93. I? 1462 - И» .93, р 7, ' '

МотацИ,

Ротам й.М» Линейные и бшшнвйнне логические операторы и на прамвдвиаа в автоматизированных информационных. системах. Диссэртащш па соисканий ученой степени • кандидата технических наук по специальности 05,25,05 - Ешформационныэ еиотзш л процессы, Харьков яай государственный технический университет родаэ лек^еронаки, Харьков» 1094. Установлено, что предложенная в работе ивааторяая алгебра предикатных операций является полной. Показано, что кзанторчуэ операцию, гшштщуюоя базисной в кзанторной алгебра, моаш представать в виде линейного и билинейного логического оператора. Разработан метод щентифаиацви тетх операторов я решения соответствующих кванторах предикатных уравнений. Осуществлено внедрение предлогенных катодов формализации я вдон-пфкациа информации. . .

P.otin 1,11. Llr/sar and bilinear logical operators and their application in automated informational systems. A Hieslo ior the scientific degree of Candidate of Sciences Technology, speciality code 05.25.05 - Informational systems and processes, Kharkov State Technical University of Radioelectronlca, Kharkov, 1994. She quantifier algeb.-a of predicate operations suggested in the Thesis ia ahoim to be complete It is proved that the quantifier operation which ia a basis one In the quantifier algebra can Da represented aa a linear or bilenear operator. A method is developed for identifying such operators and solving appropriate quantifier predicate equations. The . suggested method of

formalizing and identifying Information is applied in practical problems.

KjoHQBi слова. ЛомчниЗ оператор, кванторва алгебра, 1дентиф1кац1я.

Шдписано до друну 5,12.94р. Об'ем 1,5 д.а, Ум. -друк.а. 1,25

Беаплатно Тира*- 100 пр. Формат паперу 50x84 Зам. .</11£9 Друкарня ХЫ', вул. Сумська, 77/79