Лещинський Володимир Олександрович

УДК 519.7

МОДЕЛІ БІНАРНИХ ЛОГІЧНИХ МЕРЕЖ ТА ЇХ ЗАСТОСУВАННЯ

В ШТУЧНОМУ ІНТЕЛЕКТІ

05. 13. 23 – Системи та засоби штучного інтелекту

А В Т О Р Е Ф Е Р А Т

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків 2006

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

Робота виконана у Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник: доктор технічних наук, професор Шабанов-Кушнаренко Сергій Юрійович, Харківський національний університет радіоелектроніки.

Офіційні опоненти: доктор технічних наук, професор Асєєв Георгій Георгійович, Харківська державна академія культури, завідувач кафедри інформаційних технологій;

кандидат технічних наук, доцент Шостак Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, доцент кафедри програмного забезпечення комп’ютерних систем.

Провідна установа:

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

Захист відбудеться 17.01.2007 р. о _13___ годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел. (0572) 702-14-51.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, м. Харків, пр. Леніна, 14.

Автореферат розісланий 12.12.2006 р.

Вчений секретар

спеціалізованої вченої ради Чалий С.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Використання механізмів природної мови в інформаційно-комп'ютерних і людино-машинних системах забезпечує створення якісно-нових засобів обробки інформації для інтелектуалізації роботи з текстами. На сучасному етапі розвитку інтелектуальних систем автоматизованої обробки природно-мовної інформації, не зважаючи на те, що багато механізмів природної мови вже формалізовано, проблема формалізації природної мови є актуальною. Необхідно розробляти нові та удосконалювати розроблені формальні математичні моделі механізмів природної мови на різних рівнях: морфологічному, синтаксичному, семантичному та ін. Схемна реалізація формалізованих засобами алгебри скінченних предикатів та предикатних операцій математичних моделей природно-мовних механізмів приводить до побудови бінарних логічних мереж, які в свою чергу складають основу ЕОМ паралельної дії, заснованих на принципах мозку, що отримали назву мозкоподібних ЕОМ.

В області штучного інтелекту існує проблема застосування наукових знань про природну мову у розв’язанні різних практичних задач, серед яких автоматичний машинний переклад, розпізнавання рукописних текстів та звучащої мови, автоматичне індексування та реферування текстів, складання лінгвістичних корпусів текстів природної мови, морфологічна, синтаксична, семантична розмітка текстів і таке інше. Дисертаційна робота вносить вклад у розв’язання цієї проблеми за рахунок розробки алгебро-логічних моделей та методів бінарних логічних мереж для формалізації морфологічних структур природної мови засобами алгебри скінченних предикатів та алгебри предикатних операцій. Методи побудови бінарних логічних мереж, що розробляються в дисертаційній роботі, базуються на принципі паралельної обробки символьної інформації, дають можливість створювати математичні моделі різних інформаційних процесів, у тому числі і моделі механізмів природної мови.

Актуальність дисертаційної роботи визначається перспективністю використання отриманих методів для розробки ЕОМ паралельної дії, заснованих на принципах мозку; формалізації багатьох інформаційних процесів, у тому числі і розробки інтелектуальних систем спілкування з комп'ютером на природній мові; розвитку апарату алгебри предикатів і предикатних операцій як універсального засобу формального опису об'єктів різної природи.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася згідно з планом науково-технічних робіт Харківського національного університету радіоелектроніки в рамках держбюджетної теми №159 "Розробка теорії штучного інтелекту на базі дослідження механізмів інтелекту людини та її застосування для проектування систем штучного інтелекту", розділ 1 "Розробка математичного і програмного забезпечення системи логічної підтримки проектування систем штучного інтелекту" (№ ДР 0103U001545).

Мета і задачі дослідження. Метою дисертаційної роботи є підвищення ефективності роботи систем автоматизованої обробки природно-мовної інформації за рахунок розробки комплексу алгебро-логічних засобів моделювання бінарних логічних мереж для формалізації морфологічних структур природної мови.

Для досягнення поставленої мети потрібно розв’язати наступні задачі:

- проаналізувати теоретичні та практичні наукові досягнення в області розвитку обчислюваної техніки, формалізації структур природної мови;

- розробити метод роботи моделей бінарних логічних мереж засобами алгебри скінченних предикатів і предикатних операцій;

- розробити метод функціонування логічних мереж засобами алгебри скінченних предикатів і предикатних операцій;

- побудувати бінарну логічну мережу, що моделює процес словозміни регулярних іменників російської мови;

- розробити програмний продукт, в основу якого покласти розроблений апарат моделювання бінарних логічних мереж;

- провести експериментальну перевірку правильності роботи моделі бінарної логічної мережі словозміни регулярних іменників російської мови.

Предмет дослідження – алгебро-логічні моделі бінарних логічних мереж та їх застосування для формалізації морфологічних структур природної мови.

Об'єкт дослідження – алгебро-логічний апарат моделювання природної мови.

Методи дослідження. Основним математичним апаратом обрані логічний аналіз, алгебра скінченних предикатів та алгебра предикатних операцій, теорія перемикальних ланцюгів, теорія графів.

Наукова новизна отриманих результатів.

1. Уперше розроблено метод потактової роботи бінарних логічних мереж засобами алгебри скінченних предикатів, який базується на бінарній декомпозиції відношення, що описує об’єкт моделювання. Це дозволяє паралельно обробляти символьну інформацію у вузлах бінарних логічних мереж та забезпечує більшу швидкість її обробки.

2. Уперше розроблено метод функціонування бінарних логічних мереж засобами алгебри предикатних операцій, який базується на лінійному логічному операторі та дозволяє розв’язувати систему бінарних рівнянь логічних мереж, а також схемно їх реалізовувати.

3. Уперше розроблено математичну модель бінарної логічної мережі словозміни регулярних іменників російської мови засобами алгебри скінченних предикатів і алгебри предикатних операцій, що дозволяє апаратно їх реалізовувати та використовувати для автоматичного розв’язання задач аналізу, синтезу та нормалізації словоформи.

4. Одержав подальший розвиток математичний апарат алгебри предикатних операцій за рахунок розробки кванторної алгебри предикатних операцій, що дозволяє формалізувати процес функціонування бінарних логічних мереж.

Практичне значення отриманих результатів. Результати проведених досліджень використано для розробки алгоритмічного забезпечення формування вхідної інформації при проведенні тестування автоматичних телефонних станцій (АТС) та програмного забезпечення комплексу моделювання функцій навколишнього середовища, що впроваджені в ОКБ Харківського державного приладобудівного заводу ім. Т.Г.Шевченка (акт впровадження від 10.10.2005 р.) для проведення електричних випробувань обладнання АТС і відпрацювання функціонального програмного забезпечення АТС на стенді підприємства. Це значно спростило створення бази даних для проведення тестування АТС, скоротило час підготовки програм тестування, що у сукупності забезпечило економне використання ресурсів обладнання та скоротило час проведення приймально-здавальних випробувань.

Розроблені математичні методи було використано при розробці програмного комплексу, що впроваджено в приватному підприємстві “Енергія” (договір №05-09 на створення науково-технічної продукції від 15.02.2005 р., акт впровадження від 11.05.2005 р.), для автоматизованого контролю технологічного процесу підприємства. Це дозволило значно зменшити час на прийняття рішення оператором, що контролює технологічний процес підприємства, ймовірність прийняття неправильних рішень та витрати підприємства. Крім того зменшилась кількість затраченого часу на розробку проекту автоматизації всього технологічного процесу.

Теоретичні результати дисертаційної роботи були використані у навчальному процесі на кафедрі програмного забезпечення ЕОМ Харківського національного університету радіоелектроніки при підготовці курсів лекцій “Теорія інтелекту” та “Логічний аналіз” для спеціальності "Програмне забезпечення автоматизованих систем" (акт впровадження від 17.10.2005 р.). Програмне забезпечення, розроблене в дисертації, використовується в курсовому й дипломному проектуванні, у науково-дослідній роботі студентів на кафедрі програмного забезпечення ЕОМ.

Особистий внесок здобувача. Всі результати, представлені в роботі, отримані автором самостійно. Їх основний зміст викладено у роботах [1-6]. У роботі [1] автором запропоновано формальний апарат бінарних логічних мереж мозкоподібних ЕОМ. У роботі [2] автором досліджено питання про функціонування бінарних логічних мереж, в рамках якого розглянуто питання про перетворення математичної формули лінійного логічного оператора в технічну схему. У роботі [3] запропоновано метод синтезу бінарних логічних мереж, розглянуто метод потактової роботи та здійснено програмну реалізацію бінарної логічної мережі на прикладі розв’язання булевого рівняння. У роботі [4] автором розглянуто питання про функціонування бінарних логічних мереж, в рамках якого розглянуто поняття лінійного логічного оператора як інструменту розв’язання лінійних логічних рівнянь, проаналізовано існуючі алгебри предикатних операцій, введено поняття кванторної алгебри предикатних операцій. У роботі [5] автором запропоновано інтерпретацію деяких базових понять теорії категорій у термінах алгебри предикатів. У статті [6] автором розглянуто, формально описано засобами алгебри скінченних предикатів та доведено до відтворення на бінарній логічній мережі мозкоподібної ЕОМ механізм словозміни регулярних іменників російської мови. У роботі [7] автором для проведення бінарної декомпозиції предикатів, одного з етапів моделювання бінарних логічних мереж, запропоновано використовувати додаткові змінні. Робота [8] присвячена розв’язанню логічних рівнянь алгебри скінченних предикатів за допомогою бінарних логічних мереж. Робота [9] присвячена розгляду питання виникнення парадокса Расела в бінарних логічних мережах при введенні числових імен для значень предметних змінних. У роботі [10] автором описано універсальну програму для побудови та тестування бінарних логічних мереж. У роботі [12] розроблений формальний апарат бінарних логічних мереж застосовано для розв’язання булевого рівняння. Роботи [11, ] присвячено застосуванню розробленого апарату бінарних логічних мереж для формалізації механізмів природної мови.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на VIII Міжнародному молодіжному форумі “Радіоелектроніка та молодь у ХХІ столітті” (Харків, 2004 р.); 11-ій Міжнародній конференції з автоматичного управління “Автоматика-2004” (Київ, 2004 р.); 10-ій Ювілейній Міжнародній науковій конференції “Теорія і техніка передачі, прийому та обробки інформації” (Харків-Туапсе, 2004 р.); науково-практичній конференції “Інформаційні технології – в науку та освіту” (Харків, 2005 р.); Восьмій Всеукраїнській (Третій Міжнародній) студентській науковій конференції з прикладної математики та інформатики (Львів, 2005 р.); IX Міжнародному молодіжному форумі “Радіоелектроніка та молодь у XXI столітті” (Харків, 2005 р.); 12-ій Міжнародній конференції ‘Mixed design of integrated circuits and systems’ (Краків, 2005 р.).

Публікації. Основні результати роботи опубліковані в 13 наукових виданнях, з них 6 статей опубліковано у наукових спеціалізованих виданнях, затверджених ВАК України, 7 – тези конференцій.

Структура й обсяг дисертаційної роботи. Дисертаційна робота складається з вступу, п’ятьох розділів, висновків, списку використаних джерел, додатка. Повний обсяг роботи – 160 сторінок. Дисертація містить 37 ілюстрацій на 29 сторінках, 14 таблиць на 11 сторінках, 1 додаток на 3 сторінках, список використаних джерел з 176 найменувань на 15 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми, сформульовано основну мету і задачі дослідження, наведено відомості про зв’язки обраного напрямку досліджень із планами організації, де виконана робота. Дано загальну характеристику роботи, сформульовано основні положення, винесені автором на захист, визначено їх практичну цінність.

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

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

Перехід до загального поняття предметного простору приводить до загального поняття заданої на ньому алгебри предикатів. Логічна мережа зберігає у загальних рисах свою структуру для будь-якого предметного простору, за винятком лише того, що у скінченномірному випадку вона містить полюсів , а у нескінченномірному випадку – нескінченний набір полюсів , де . Відповідно, у логічній мережі містяться два набори і з гілок кожен – у скінченномірному предметному просторі та два нескінченних набори та гілок і – у нескінченномірному.

Бінарні логічні мережі працюють за тактами. Кожний такт ділиться на два напівтакти – перший і другий. У першому напівтакті -го такту для кожного зі своїх рівнянь вигляду ( – це відношення, задане таким рівнянням) бінарна логічна мережа відшукує:

1) за відомим знанням про значення змінної на початку -го такту знання про значення змінної у кінці -го такту:

,

де – область визначення змінної .

2) за відомим знанням про значення змінної на початку -го такту знання про значення змінної у кінці -го такту:

,

де – область визначення змінної .

У другому напівтакті кожного такту логічна мережа знаходить загальну частину всіх знань про значення кожної з своїх предметних змінних , котрі поступають по гілках мережі з усіх боків до полюса :

.

Отримане знання потім використовується в ролі стану полюса у початковий момент -го такту. Символ означає число гілок, що підходять до полюса . До початку -го такту в кожному полюсі формується знання-множина , яке завжди виявляється включеним до знання-множини , що містилося в тому ж полюсі на початку -го такту. Отже, єдиним результатом роботи логічної мережі є уточнення знань, що містяться у всіх її полюсах відповідно до початкових даних. У подальших тактах стан мережі вже не змінюється. Цей факт служить сигналом до припинення роботи логічної мережі.

У третьому розділі розвивається алгебра предикатних операцій, що має практичну значущість для застосування цього апарата при функціонуванні логічних мереж. Запропоновано метод функціонування бінарних логічних мереж, у основі якого лежить поняття лінійного логічного оператора як інструменту розв’язання логічних рівнянь бінарних логічних мереж. Проведено порівняльний аналіз існуючих алгебр предикатних операцій. Проаналізовано булеву алгебру предикатних операцій, алгебру предикатних операцій з константами та змінними, диз'юнктивно-кон'юнктивну алгебру предикатних операцій, фундаментальну алгебру предикатних операцій і алгебру підстановочних предикатних операцій. Дано визначення кванторної алгебри предикатних операцій. Сформульовано та доведено твердження про рівносильність фундаментальної та кванторної алгебр предикатних операцій. Запропоновано варіант скорочення базису кванторної алгебри предикатних операцій.

Введемо необхідні визначення. Кожному предикату , визначеному на , відповідає відображення , діюче з у . Якщо для існує , такий, що , то говорять, що відображення ставить у відповідність предмету предмет , і пишуть . Якщо , то предмет називається образом предмету , а предмет – прообразом предмету відносно відображення .

Сукупність всіх образів предмета відносно відображення називається повним образом предмета відносно відображення : або . Сукупність усіх прообразів предмета відносно відображення називається повним прообразом предмета відносно відображення : або .

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

; (1)

. (2)

Перетворення (1)-(2) називаються лінійними логічними операторами і з ядром . Функціонуюча логічна мережа є системою взаємодіючих лінійних логічних операторів. Кожна дуга бінарної логічної мережі є двонаправленою шиною, яка описується парою операторів (1) і (2)

Кванторною алгеброю предикатних операцій називається будь-яка алгебра предикатних операцій з базисом операцій, що складається з диз'юнкції , кон'юнкції і заперечення , кванторів існування і спільності , замін змінних , їх перестановок і підстановок , і з базисом елементів, що складається з предикатів 0 і 1, предикатів пізнавання предмету та змінних (, ).

Твердження 3.1. Про рівносильність фундаментальної та кванторної алгебр предикатних операцій. Фундаментальна та кванторна алгебри предикатних операцій, що мають один і той же носій, рівносильні.

Елементи виражаються через базис кванторної алгебри предикатних операцій за допомогою залежностей:

,

де операція рівносильності визначається як , – деякі сталі предикати.

Квантори існування та спільності виражаються через диз'юнкцію, кон'юнкцію і підстановки за формулами:

;

.

Операції послідовним застосовуванням законів

;

;

переміщуються безпосередньо на предикати 0,1 та і на предикатні змінні , а потім зовсім виключаються за допомогою залежностей:

якщо ;

Предикатні змінні виражаються за формулою

через диз'юнкцію, кон'юнкцію, предикати пізнавання предиката і постійні предикати.

Наслідок 3.1. Кванторна алгебра предикатних операцій при будь-якому носії повна.

Виключення операцій диз'юнкції (кон'юнкції), заміни, перестановки, підстановки та предикатів 1 (0) робить базис кванторної алгебри предикатних операцій нескоротним при збереженні ним властивості повноти. Операції диз'юнкції (кон'юнкції) виключаються з формул кванторної алгебри предикатних операцій за допомогою законів де Моргана , для предикатних операцій , .

Операції заміни, перестановки та підстановки виключаються за допомогою наступних тотожностей:

;

;

.

Предикати 0 або 1 виключаються за допомогою законів істинності та помилковості для предикатів пізнавання предмета , , якщо , та предикатів пізнавання предиката , , якщо , які справедливі для .

Квантор спільності виключається з формул кванторної алгебри предикатних операцій за допомогою тотожності:

.

Таким чином, базис кванторної алгебри предикатних операцій складається з операцій диз'юнкції (кон'юнкції), заперечення, з кванторів існування , з предикатів пізнавання предмету , де – число предметів в множині , з предикатних змінних і константи 0 (1).

Четвертий розділ присвячено розробці математичної моделі бінарної логічної мережі для формалізації морфологічної структури природної мови. На прикладі алгебро-логічної формалізації процесу словозміни регулярних іменників російської мови розглядається метод побудови алгебро-логічних структур, які приводять до побудови бінарних логічних мереж.

Для формального опису процесу словозміни регулярних іменників російської мови введені предметні змінні: – рід форми слова із значеннями М – чоловічий, С – середній, Ж – жіночий; – число форми слова із значеннями Е – однина, М – множина; – відмінок форми слова із значеннями И – називний, Р – родовий, Д – давальний, В – знахідний, Т – орудний, П – місцевий; – ознака істотності форми слова із значеннями Н – не істота, О – істота; – ознака вживання форми слова із значеннями С – сучасний, А – архаїчний; – закінчення форми слова із значеннями А, АМ, АМИ, АХ, Е, ЕВ, ЕЙ, ЕМ, ЕЮ, Ё, ЁВ, ЁЙ, ЁМ, ЁЮ, И, О, ОВ, ОЙ, ОМ, ОЮ, У, Ь, Ы, Ю, Я, ЯМ, ЯМИ, ЯХ, НУЛЬ; – номери впливу контексту із значеннями 1,2,…,29, які визначаємо номерами чарунок парадигматичної таблиці. Тип словозміни визначаємо із залежності , де – остання буква основи слова із значеннями Б, В, Д, З, Л, М, Н, П, Р, С, Т, Ф, Г, К, Х, Ж, Ч, Ш, Щ, Ц, А, Е, Й, О, У, Ы, Ю, Я, И; – ознака наголошеності основи слова із значеннями У – наголошена, Б – ненаголошена; – ознака пом’якшення слова зі значеннями Т – тверда, М – м’яка.

У результаті виявлення відношень між введеними предметними змінними та проведення їх бінарної декомпозиції отримано 10 відношень , , , , , , , , , , що задаються дводольними графами та формулами відповідних предикатів. Для прикладу представимо одне із отриманих бінарних відношень у вигляді формули алгебри скінченних предикатів та дводольних графів:

.

Рис.1 Зв'язок: тип контексту – відмінок

Предикат математичної моделі словозміни регулярних іменників російської мови має наступний вигляд:

Предикату моделі відповідає відношення моделі , що пов'язує між собою предметні змінні , , , , , , , , , , , яке зображено у вигляді бінарної логічної мережі на рис.2.

Рис.2 Будова логічної мережі словозміни

регулярних іменників російської мови

Електронну схему, відповідну цій бінарній логічній мережі, використовують для автоматичного розв’язання класу задач, що відносяться до словозміни регулярних іменників російської мови. Прикладом задачі цього класу може служити задача синтезу, аналізу і нормалізації словоформи.

У п’ятому розділі розглянуто питання про перетворення математичної формули лінійного логічного оператора в технічну схему. Засобом математичного опису при цьому служить апарат алгебри предикатів, а засобом технічного опису – апарат перемикальних ланцюгів теорії інтелекту. Розроблено програмну реалізацію бінарних логічних мереж. Програмно протестовано модель бінарної логічної мережі словозміни регулярних іменників російської мови.

Введемо необхідні визначення. Довільне відображення , що діє з в ( ), ставить у відповідність набору значень аргументів множину , рівну , де – предикат, відповідний відображенню . Нехай – координати множини , тоді:

;

;

.

Набір характеризує множину .

Використовуючи координатне представлення, можна будувати схеми лінійних логічних операторів. Нехай , тоді запишемо формулу (1) у наступному вигляді:

.

Нехай – характеристика множини , а – характеристика множини ; . Таким чином,

;

. (3)

Тоді

;

;

(4)

.

З урахуванням (3) вираз (4) записуємо у вигляді

;

;

(5)

.

За формулою (5) будується схема лінійного логічного оператора. При цьому множини і задаються своїми характеристиками.

Наведемо приклад побудови таких схем для лінійних логічних операторів. Візьмемо предикат , що пов’язує тип впливу контексту і відмінок форми слова з моделі словозміни регулярних іменників російської мови. Будуємо відповідне йому відображення , {1,2,…,29}, {И, Р, Д, В, Т, П}:

(6)

Схема, що реалізує відображення (6), має вигляд:

Рис.3

За цією схемою можна знаходити повний образ предмета. Наприклад , тоді , , , , , , і повним образом предмета 5 є {В}.

Для знаходження прообразу предмета необхідно будувати схему, що реалізує відображення, зворотне заданому, тобто схему, що діє у зворотний бік (рис.4). Наприклад , тоді , , , , , ; {4, 5, 8, 12, 18, 19, 24, 25, 28, 29}.

Рис.4

Для того щоб знаходити образ множини, необхідно замінити предикати пізнавання предмета на :

(7)

Схему, що знаходить образ множини предметів відносно відображення (7), представлено на рис.5.

Рис.5

Наприклад візьмемо наступну множину типів впливу контексту {2,5,9,24}, які відповідають закінченням а, я регулярних іменників. Схема породжує множину можливих відмінків: {2,5,9,24}{И, Р, В}.

Для знаходження прообразу множини відносно відображення (7) будується схема, що діє у зворотний бік (рис.6).

Рис.6

Візьмемо, наприклад, {И, Р, В}, тоді , , , , , . Схема породжує множину можливих типів впливу контексту {1, 2, 4, 5, 8, 9, 10, 12, 15, 16, 18, 19, 22, 23, 24, 25, 26, 28, 27, 29}.

Результат вираження лінійного логічного оператора, ядром якого є предикат , за формулою (5) співпадає з виразом (7). Наприклад

.

Таким чином, перемикальний ланцюг на рис.5, що знаходить образ множини відносно відображення (7), реалізує лінійний логічний оператор з ядром . Отже, кожна дуга логічної мережі на рис.2 являє собою двонаправлену шину, яка реалізується парою перемикальних ланцюгів, подібних зображеним на рис.5 та рис.6. Отримані схеми дозволяють будувати логічні мережі мозкоподібних ЕОМ, використовуючи лінійний логічний оператор в якості основного будівельного елемента.

У додатку наведено акти впровадження теоретичних і практичних результатів дисертаційної роботи.

ВИСНОВКИ

У дисертаційній роботі наведено результати, які в сукупності є розв’язанням актуальної наукової задачі – розробки алгебро-логічних засобів формалізації морфологічних структур природної мови у вигляді комплексу математичних і алгоритмічних моделей. У результаті розв’язання сформульованої задачі:

1. Проаналізовано основні теоретичні та практичні наукові досягнення в області розвитку обчислюваної техніки, формалізації структур природної мови, створення формального алгебро-логічного апарату для моделювання природної мови, які обумовили вибір напрямку наукових досліджень, формулювання мети та задач дисертаційної роботи.

2. Розроблено метод потактової роботи бінарних логічних мереж засобами алгебри скінченних предикатів, що дозволяє обробляти інформацію у вузлах бінарної логічної мережі паралельно. Результатом роботи бінарної логічної мережі є уточнення знань, що містяться у всіх її полюсах відповідно до початкових даних.

3. Розроблено метод функціонування моделей бінарних логічних мереж, в основі якого лежить поняття лінійного логічного оператора. Функціонуюча логічна мережа є системою взаємодіючих лінійних логічних операторів. Кожна дуга бінарної логічної мережі являє собою двонаправлену шину, яка описується парою лінійних логічних операторів і реалізується парою перемикальних ланцюгів, побудованих з використанням координатного представлення відповідних множин.

4. Одержав подальший розвиток математичний апарат алгебри предикатних операцій. Розроблено різновид алгебри предикатних операцій — кванторну алгебру предикатних операцій, що дозволяє описати процес функціонування бінарних логічних мереж. Сформульовано та доведено твердження про рівносильність фундаментальної та кванторної алгебр предикатних операцій, наслідком якого є повнота кванторної алгебри предикатних операцій при будь-якому носії. Запропоновано варіант скорочення базису кванторної алгебри предикатних операцій.

5. Розроблено модель бінарної логічної мережі словозміни регулярних іменників російської мови. Виділено предметні змінні, що описують об'єкт моделювання, і бінарні відношення між ними. Побудовано дводольні графи, відповідні виділеним бінарним відношенням. Розглянуто клас задач (аналіз, синтез і нормалізація словоформи), які розв’язує побудована модель бінарної логічної мережі. Проведено експериментальну перевірку коректності роботи моделі бінарної логічної мережі словозміни регулярних іменників за допомогою розробленої програми “BiLogicNet”, яка дозволяє моделювати будь-які бінарні логічні мережі і тестувати їх роботу за заданими ознаками.

6. Результати дисертаційної роботи використано для розробки алгоритмічного забезпечення формування вхідної інформації при проведенні тестування АТС та програмного забезпечення комплексу моделювання функцій навколишнього середовища для проведення електричних випробувань обладнання АТС і відпрацювання функціонального програмного забезпечення АТС на стенді підприємства (ОКБ Харківського державного приладобудівного заводу ім. Т.Г.Шевченка, акт впровадження від 10.10.2005 р.).

7. Отримані методи синтезу бінарних логічних мереж застосовано при розробці програмного комплексу для автоматизації контролю технологічного процесу підприємства (приватне підприємство “Енергія”, договір №05-09 на створення науково-технічної продукції від 15.02.2005 р., акт впровадження від 11.05.2005 р.).

8. Теоретичні результати дисертаційної роботи використано у навчальному процесі на кафедрі програмного забезпечення ЕОМ ХНУРЕ при підготовці курсів лекцій "Теорія інтелекту" та "Логічний аналіз" для спеціальності "Програмне забезпечення автоматизованих систем" (акт впровадження від 17.10.2005 р.).

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Бондаренко М.Ф., Дударь З.В., Ефимова И.А., Лещинский В.А., Шабанов-Кушнаренко С.Ю. О мозгоподобных ЭВМ // Радиоэлектроника и информатика. – 2004. – № 2. – С.89–105.

2. Вечирская И.Д., Дударь З.В., Иванилов А.А., Лещинский В.А. Линейные логические операторы в виде схем и графов // Бионика интеллекта.– 2004.–№1(61). – С.38–41.

3. Ефимова И.А., Лещинский В.А. О методе построения моделей бинарных логических сетей // Восточно-Европейский журнал передовых технологий. – 2005.– №4.– С.121–124.

4. Лещинский В.А. Алгебра предикатных операций в моделях бинарных логических сетей // Восточно-Европейский журнал передовых технологий. – 2005.– №5.– С.110–113.

5. Дударь З.В., Лещинский В.А., Вечирская И.Д., Иванилов А.А. О категорном анализе алгебры предикатов // Вестник НТУ “ХПИ”: Сб. науч. трудов. Тематич. вып.: Новые решения в современных технологиях. – Харьков: НТУ “ХПИ”, 2002. – № 20. – С. 38–42.

6. Ефимова И.А., Лещинский В.А. Моделирование механизмов естественного языка с помощью бинарных логических сетей // Вестник НТУ “ХПИ”: Сб. науч. трудов. Тематич. вып.: Новые решения в современных технологиях. – Харьков: НТУ “ХПИ”, 2005. – № 57. – С. 3–10.

7. Лещинский В.А., Ефимова И.А., Иванилов А.А. Бинаризация двоичных булевых операций и ее реализация в виде логических сетей // 8-й Междунар. молодежный форум “Радиоэлектроника и молодежь в ХХІ веке”: Сб. материалов. – Харьков: ХНУРЭ, 2004.– С.67.

8. Лещинский В.А. Решение линейных логических уравнений с помощью бинарных логических сетей // Автоматика-2004: Материалы 11-ой Междунар. конф. по автоматическому управлению.– Киев: НУПТ, 2004. – Т.1. – С.30.

9. Ефимова И.А., Лещинский В.А. Интерпретация парадокса Рассела для логических сетей // 10-ая Юбилейная Междунар. науч. конф. “Теория и техника передачи, приема и обработки информации”: Сб. тез. докл.– Харьков: ХНУРЭ, 2004.– Ч.2. – С.303–304.

10.  Лещинский В.А., Лыков Д.А. Программный модуль проектирования и анализа работы бинарных логических сетей // 9-й Междунар. молодежный форум “Радиоэлектроника и молодежь в XXI веке”: Сб.материалов. – Харьков: ХНУРЭ, 2005.– С.375.

11.  Шабанов-Кушнаренко Ю.П., Хаханов В.И., Процай Н.Т., Вечирская И.Д., Лещинский В.А., Иванилов А.А., Обризан В.И. Логическая сеть как технология моделирования естественного языка // Информационные технологии – в науку и образование: Материалы науч.-практич. конф. – Харьков: Изд-во ХНУРЭ, 2005.– С.30–33.

12.  Єфімова І.О., Лещинський В.О. Моделювання логічних мереж для булевих рівнянь // Восьма Всеукр. (Третя Міжнар.) студентська наук. конф. з прикладної математики та інформатики: Зб.матеріалів. – Львів: ЛНУ, 2005.– С.128–129.

13.  Bondarenko M.F., Chetverikov G.G., Karpuhin A.V., Leshchinsky V.A. Synthesis methods of multiple-valued structures of bilogical networks // Proceedings of the 12th International Conf. ‘Mixed design of integrated circuits and systems’ (MIXDES 2005).– Krakow (Polska), 2005.– P.201–204.

АНОТАЦІЯ

Лещинський В.О. Моделі бінарних логічних мереж та їх застосування в штучному інтелекті. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – системи та засоби штучного інтелекту - Харківський національний університет радіоелектроніки, Харків, 2005.

Дисертація присвячена побудові методів формального представлення відношень за допомогою апарата бінарних логічних мереж, зокрема, природно-мовного відношення словозміни регулярних іменників російської мови з їх подальшою програмною та схемною реалізацією.

Отримані методи побудови логічних мереж застосовано для розробки алгоритмічного забезпечення формування вхідної інформації при проведенні тестування АТС та програмного забезпечення комплексу моделювання функцій навколишнього середовища для проведення електричних випробувань обладнання АТС і відпрацювання функціонального програмного забезпечення АТС на стенді підприємства, а також при побудові комп'ютерного комплексу для автоматизованого контролю технологічного процесу підприємства.

Ключові слова: природна мова, формалізація природної мови, алгебрологічний апарат, предикат, предикатна операція, алгебра скінченних предикатів та предикатних операцій, лінійний логічний оператор, бінаризація, логічна мережа.

АННОТАЦИЯ

Лещинский В.А. Модели бинарных логических сетей и их применение в искусственном интеллекте. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 – системы и средства искусственного интеллекта – Харьковский национальный университет радиоэлектроники, Харьков, 2006.

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

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

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

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

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

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

ABSTRACT

Leshchinskyi V.O. The model of binary logical networks and their application in the artificial intelligence. – Manuscript.

The thesis on competition of the scientific degree of the Candidate of Technical Science in the speciality 05.13.23 – Systems and Means of the Artificial Intelligence – Kharkov National University of Radio Electronics, Kharkov, 2006.

The thesis is devoted to construction of the relations formal representation methods using logical networks apparatus, in particular, the natural language relation of regular nouns inflection, with their further realization in electronic circuits.

The obtained methods for logical networks construction used for development of the input information formation algorithmic support when testing automatic telephone exchange (ATE) and software for environment functions simulation complex for electric testing of the automatic telephone exchange equipment and approbation of the ATE functional software at the bench of the enterprise as well as construction of the computer complex intended for the automated control of the enterprise technological process.

Key words: a natural language, formalization of a natural language, apparatus of logic algebra, a predicate, predicate operation, algebra of finite predicates and predicate operations, linear logical operator, binarization, a logical network.

Відповідальний за випуск Руденко О.Г.

Підп. до друку 27.11.2006 р. Формат 60841/16. Спосіб друку – ризографія.

Умов. друк. арк. 1,2. Облік. вид. арк. 1,0. Тираж 100 прим. Зам. № ______.

Надруковано в навчально-науковому видавничо-поліграфічному центрі

Харківського національного університету радіоелектроніки.

Україна, 61166, м. Харків, просп. Леніна, 14.