Лінійні логічні перетворення та їх застосування в штучному інтелекті

Размещено на http://www.allbest.ru/

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

Автореферат

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

Лінійні логічні перетворення та їх застосування в штучному інтелекті

Вечірська І.Д.

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

Харків 2007

Вступ

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася згідно з планом науково-технічних робіт Харківського державного університету радіоелектроніки в рамках держбюджетної теми № 202 “Розробка принципів побудови мозкоподібних ЕОМ” (№ ДР 0106U003292), розділ 1 “Розробка та застосування логічних мереж мозкоподібних ЕОМ” (виконавець теми).

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

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

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

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

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

розробити метод обчислення лінійних логічних перетворень, який дозволяє збільшити розмірність ядра лінійних логічних перетворень;

побудувати алгоритми та програмно реалізувати розроблені методи.

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

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

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

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

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

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

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

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

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

Розроблені математичні методи було використано для побудови комп'ютерного комплексу для автоматизації керування фірмою та узгодження роботи її відділів (ТОВ фірма „Регіон. Будзв'язок”, акт впровадження від 09.06.2007 р.). Це дозволило зменшити час на прийняття рішень і тим самим привело до ефективного використання праці співробітників різного профілю та повного своєчасного їх інформування про стан роботи.

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

Особистий внесок здобувача. Усі результати, представлені в роботі, отримані автором самостійно. Їх основний зміст викладений у роботах [1 - 15], деякі з них написані в співавторстві. В роботі [1] досліджувались способи представлення багатомісного відношення у вигляді композиції бінарних предикатів, особисто автором було наведено формальну постановку задачі та обґрунтовано її актуальність. В [2] особисто автором було розроблено приклад побудови дводольного графа відношення між першою буквою закінчення повних неприсвійних прикметників і родом, реалізовано вихідним та зворотними ланцюгами перемикання. В роботі [3] було досліджено внутрішню структуру алгебро-логічного апарату для побудови логічних мереж, а саме вивчено закономірність, на основі якої було виведено та досліджено формулу для побудови n-ого перетворення в загальному вигляді. В [4] особисто автором було наведено формули для знаходження елементів матриці перетворення в загальному вигляді. В [5] було розв'язано обернену задачу для лінійних логічних перетворень. В статті [6] особисто автором було доведено твердження про ступінь лінійного логічного перетворення, наведено приклад застосування. В роботі [7] особисто автором було проведено теоретичну роботу по інтерпретації поняття категорії з об'єктами. В роботі [8] особисто автором було доведено узагальнення твердження про вигляд лінійного логічного перетворення на випадок трьох змінних, наведено формули для обчислення лінійних логічних перетворень в залежності від способу задання області визначення. В статті [9] особисто автором було наведено приклад суперпозиції лінійних логічних перетворень та наведено метод знаходження n-ого лінійного логічного перетворення.

У тезах доповіді [10] особисто автором було проведено аналіз областей застосування логічних мереж для формалізації природної мови. У тезах доповіді [11] особисто автором було доведено твердження про суперпозицію лінійних логічних перетворень. У тезах доповіді [12] особисто автором було проведено аналіз методів розв'язання бінарних предикатних рівнянь. В [13] особисто автором було доведено твердження про загальний вигляд лінійного логічного перетворення на випадок n змінних. У тезах доповіді [14] було наведено приклад розв'язання оберненої задачі для лінійних логічних перетворень, коли вхідний та вихідний вектори задані базисними векторами. У тезах доповіді [15] особисто автором було обґрунтовано роботу логічної мережі з точки зору лінійних логічних перетворень.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на наступних конференціях: 1) науково-практична конференція “Інформаційні технології - в науку та освіту”, (м. Харків, 21-22 березня 2005 р.); 2) VIII Міжнародна науково-практична конференція “Наука та освіта 2005”, (м. Дніпропетровськ, 7-21 лютого 2005 р.); 3) 9-й Міжнародний молодіжний форум “Радіоелектроніка та молодь в 21 столітті”, (м. Харків, 19-21 квітня 2005р.); 4) Міжнародна науково-практична конференція “Дні науки 2005”, (м. Дніпропетровськ, 15-27 квітня 2005 р.; 5) Міжнародна науково-практична конференція “Наукові дослідження та їх практичне застосування”, (м. Одеса, 1-15 жовтня 2005 р.); 6) Міжнародна наукова конференція “Горизонти прикладної лінгвістики та лінгвістичних технологій” (MegaLing'2007), (м. Партеніт, Крим, Україна 25-28 вересня 2007 р.).

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

Структура й обсяг дисертаційної роботи. Дисертаційна робота складається з вступу, п'ятьох розділів, висновків, списку використаних джерел, додатків. Повний обсяг роботи - 149 сторінок. Дисертація містить 14 рисунків на 11 сторінках, 13 таблиць на 12 сторінках, 3 додатки на 3 сторінках, список використаних джерел з 102 найменувань на 9 сторінках.

1. Основний зміст роботи

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

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

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

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

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

Логічним простором назвемо непусту множину векторів над полем скалярів , де для скалярів і векторів виконуються відповідно закони ідемпотентності, комутативності, асоціативності, нуля та одиниці, а зв'язок між скалярами та векторами описують за допомогою законів лівої та правої дистрибутивності (відносно відповідно диз'юнкції скалярів та диз'юнкції векторів) та законів нуля та одиниці.

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

,

де - коефіцієнти комбінації.

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

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

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

.

Нехай система залежна, тоді існує вектор

,

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

Тоді породжуюча сукупність перестає бути мінімальною, що суперечить умові. Звідси випливає, що сукупність являється незалежною.

Tвердження. Будь-яка максимальна (за кількістю векторів) незалежна сукупність векторів є породжуючою.

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

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

для будь-якого , де - предикат з

Таким чином було введено поняття лінійного логічного перетворення на логічних просторах.

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

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

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

: ,

де

,

була лінійним логічним перетворенням, необхідно та достатньо, щоб вона мала вигляд:

для будь-якого , де задана на

 , .

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

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

Далі наведемо правило обчислення лінійного логічного перетворення з в за аналогією з формулою (аналог повторного інтеграла) матиме вигляд:

,

де .

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

,

де .

Ми розглянули простий випадок, де усі змінні перетворення визначені на універсумі. Виявляється, при іншому заданні області визначення зміниться й саме правило обчислення.

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

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

.

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

.

Далі виразимо правило обчислення лінійного логічного перетворення з в наступною формулою:



.

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

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

Було проведено також дослідження дій над лінійними логічними перетвореннями, а саме знаходження ступеня лінійного логічного перетворення. Виведено формулу для знаходження -ого ступеня лінійних логічних перетворень:

, де

, де.

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

.

На наступному етапі необхідно знайти кон'юнкцію всіх суперпозицій ядра лінійного логічного перетворення та вхідного вектора.

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

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

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

Введемо необхідні визначення та твердження.

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

Поняття досконалої диз'юнктивної нормальної форми (ДДНФ) визначається так, як і в алгебрі логіки, проте слід відмітити, що в даному випадку змінні, які входять до ДДНФ, можуть приймати значення не тільки 0 та 1.

Твердження 1. Будь-яку булеву форму можна привести до ДДНФ.

Твердження 2. Будь-яку булеву форму можна виразити:

Твердження 3. Для будь-якої булевої алгебри рівносильно .

Виразимо далі систему у вигляді рівняння , де - параметри, а - змінні. Щоб привести цю систему до канонічного вигляду. За допомогою твердження 3 виразимо систему в такому вигляді:

,

де - змінна. Отже, виразимо задачу у канонічному вигляді:

.

Твердження 4. Рівняння (2) має хоча б один розв'язок, тоді и тільки тоді, якщо , де

Сам розв'язок у цьому випадку виражається деякою формою:

,

.

Твердження 4. Будь-який елемент , який задовольняє рівнянню

можна представити наступним чином

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

Перейдемо до самого опису методу. Спочатку розв'язуємо рівняння (3) відносно змінної , вважаючи - параметрами. Для цього випадку отримаємо критерій існування розв'язку (твердження 4):

,

де

Таким чином, для того щоб перевірити виконання критерію існування розв'язку рівняння необхідно знайти функцій. Сам розв'язок буде виражено деякою булевою формою (твердження 5):

.

Далі аналогічно розв'язуємо рівняння (3) відносно змінної , де - параметри. Розв'язок буде виражено деякою формою:

.

Нарешті, знаходимо рівняння

,

де

Критерій існування розв'язку цього рівняння

,

де

.

Сам розв'язок буде виражено деякою булевою формою:

.

Надаючи параметру , можливі значення, отримаємо всі розв'язки рівняння.

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

,

де , , - як і раніше, розмірності відповідних вектор-стовпчиків.

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

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

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

,

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

,

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

Далі визначимо на першому напівтакті значення (4) та/або (5). Щоб перейти до наступного такту, на другому напівтакті -го такту необхідно знайти як перетин знайдених знань про значення змінної :

,

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

 .

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

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

лінійний логічний предикатний

Висновки

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

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

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

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

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

Отримані методи побудови логічних мереж впроваджені у комп'ютерному комплексі для автоматизованого керування фірмою та узгодження роботи її відділів (ТОВ фірма „Регіон. Будзв'язок”, акт впровадження від 09.06.2007). Результати, які отримано в дисертаційній роботі, знайшли своє практичне застосування при розв'язанні задачі знаходження гіпотетично зв'язаних абонентів АСКР інтегрованої інформаційно-обчислювальної системи підприємства електрозв'язку ВАТ “Укртелеком” (акт впровадження від 09.03.2006 р.). Теоретичні результати дисертації були використані у навчальному процесі на кафедрах програмного забезпечення ЕОМ та прикладної математики ХНУРЕ під час підготовки курсів лекцій “Теорія інтелекту” та “Алгебраїчна логіка” для спеціальності “Програмне забезпечення автоматизованих систем”(акт впровадження від 12.06.2007 р.).

Список опублікованих автором праць за темою дисертації

1. Синельникова О.И., Вечирская И.Д. Представление многоместных отношений в виде композиции бинарных отношений // Радиоэлектроника и информатика. - 2001. - № 3. - С.147 - 150.

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

3. Вечирская И.Д. Действия над линейными логическими преобразованиями // Новые технологии. - 2005. - № 1 - 2 (7 - 8). - С. 162 - 168.

4. Вечірська І.Д., Дудар З.В. Розв'язання задачі ідентифікації довільного лінійного логічного перетворення // Східно-Європейський журнал передових технологій. - 2006. - № 5/2 (23). - С.63 - 66.

5. Вечирская И.Д. О решении обратной задачи для линейных логических преобразований // Бионика интеллекта. - 2006. - № 2 (65). - С.36 - 40.

6. Вечирская И.Д., Шабанов-Кушнаренко Ю.П. О методе нахождения n-ого линейного логического преобразования // Искусственный интеллект. - 2007. - № 3. - С. 382 - 389.

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

8. Вечирская И.Д., Иванилов А.А. О вычислении линейных логических преобразований // Вестник НТУ “ХПИ”: Сб. науч. трудов. - Харьков: НТУ “ХПИ”, 2005. - № 18. - С. 29 - 32.

9. Вечірська І.Д., Шабанов-Кушнаренко Ю.П. Про дослідження властивостей лінійних логічних перетворень // Системи обробки інформації: Зб. наук. праць. - Харків: ХУПС, 2007. - № 6. - С. 86 - 90.

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

11. Вечирская И.Д., Иванилов А.А. Суперпозиция линейных преобразований предикатов // Наука и образование 2005: VIII междунар. науч.-практич. конф. Днепропетровск, 7-21 февраля 2005 г. - Днепропетровск; Белгород, 2005 - Т. 22. - С. 3 - 4.

12. Вечирская И.Д., Иванилов А.А. Логическая сеть как метод решения системы бинарных уравнений алгебры предикатов // Радиоэлектроника и молодежь в 21 веке: 9-й междунар. молодежный форум. Харьков, 19 - 21 апреля 2005г. - Харьков, 2005. - С. 14.

13. Вечирская И.Д., Шабанов-Кушнаренко Ю.П. Об общем виде линейных логических преобразований // Дни науки 2005: междунар. науч.-практич. конф. Днепропетровск, 15-27 апреля 2005 г. - Днепропетровск; Кривой Рог; Запорожье; Желтые Воды; Белгород; Прага, 2005 - Т. 18. - С. 21 - 22.

14. Вечирская И.Д. Об обратной задаче и задаче идентификации для линейных логических преобразований // Научные исследования и их практическое применение. Современное состояние и пути развития: междунар. науч.-практич. конф. Одесса, 1 - 15 октября 2005 г. - Одесса, 2005 - Т. 9. - С. 74 - 75.

15. Вечирская И.Д., Валенда Н.А., Колтун Ю.Н., Токарев В.В., Четвериков Г.Г. О формальных аспектах реализации фрагмента русского языка логической сетью // Горизонты прикладной лингвистики и лингвистических технологий: междунар. науч. конф. Партенит, 23 - 29 сентября 2007 г. - М.; Симферополь; К.; Харьков; СПб., 2007. - С. 257 - 259.

Размещено на Allbest.ru

...