Логіко-обчислювальна семантична мережа як модель подання знань

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

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова

УДК 519.876.2:004.822

ЛОГІКО-ОБЧИСЛЮВАЛЬНА СЕМАНТИЧНА МЕРЕЖА ЯК МОДЕЛЬ ПОДАННЯ ЗНАНЬ

Спеціальність 01.05.02 - Математичне моделювання та

обчислювальні методи

АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня

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

ЯЛОВЕЦЬ Андрій Леонідович

Київ 2008

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

Робота виконана в Інституті проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України

Науковий консультант: доктор технічних наук, професор Кондращенко Володимир Якович, Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України, завідувач відділу

Офіційні опоненти: доктор фізико-математичних наук, професор, член-кореспондент НАН України Перевозчикова Ольга Леонідівна, Інститут кібернетики ім. В.М.Глушкова НАН України, завідувач відділу автоматизації програмування;

доктор фізико-математичних наук, професор, заслужений діяч науки і техніки України Анісімов Анатолій Васильович, Київський національний університет імені Тараса Шевченка, декан факультету кібернетики;

доктор технічних наук, професор Тоценко Віталій Георгійович, Інститут проблем реєстрації інформації НАН України, завідувач відділу аналітичних методів інформаційних технологій.

Захист відбудеться “ 28 ” лютого 2008 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м.Київ-164, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м.Київ-164, вул. Генерала Наумова, 15.

Автореферат розісланий “ 23 ” січня 2008 р.

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

спеціалізованої вченої ради Д 26.185.01 Семагіна Е.П.

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

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

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

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

· подавати як декларативні, так і процедурні знання;

· подавати як чіткі, так і нечіткі знання;

· подавати ієрархічну структуру знань;

· подавати знання в термінах природної мови;

· подавати логічні операції;

· подавати семантичні відношення досліджуваної ПО.

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

Для рішення проблем обробки знань використовуються обчислювальні методи, до яких, в загальному випадку, можна віднести методи логічного виводу на поданих знаннях, а також методи верифікації і тестування поданих знань. Такі обчислювальні методи, як правило, мають спеціалізований характер, оскільки вони призначені для виконання обробки знань, поданих за допомогою цілком визначеної МПЗ. Як наслідок, в процесі рішення задачі розробки МПЗ виникають додаткові (й не менш важливі) актуальні задачі розробки спеціалізованих методів обробки знань, серед яких особливе місце займає задача розробки метода логічного виводу, яка не може розглядатись без врахування властивостей класу задач, вирішуваних на знаннях, поданих за допомогою МПЗ, що розробляється. Так, у відповідності до класифікації Д.Пойа існує два достатньо загальних класи задач: задачі на знаходження і задачі на доказ. За своїми властивостями названі класи задач є діаметрально протилежними: якщо задачі на знаходження характеризуються тим, що явно задані вхідні дані і невідомий шуканий об'єкт, і необхідно знайти невідомий шуканий об'єкт, який задовольняє умовам задачі, то задачі на доказ - тим, що відомі як умови задачі, так і шуканий об'єкт, і необхідно довести, що шуканий об'єкт визначається з умов задачі. Слід підкреслити, що задачі на знаходження складають клас практично значимих задач, рішення яких вимагає використання методів і засобів ШІ. Внаслідок цього актуальним є вибір класу задач на знаходження у якості досліджуваного класу задач. Виходячи з властивостей названих класів задач, для рішення задач на знаходження доцільно використовувати прямий („від даних”) вивід, в той час як для рішення задач на доказ - зворотний („від цілі”) вивід. При цьому, на відміну від методів зворотного виводу, достатньо глибоко теоретично досліджених і широко використовуваних при побудові СЗЗ, методи прямого виводу вимагають свого розвитку як в теоретичному, так і в прикладному напрямках. Виходячи з цього, актуальною є задача розробки методу прямого виводу на знаннях, поданих за допомогою МПЗ, що розробляється.

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідження по дисертаційній роботі виконувались у відповідності з планами науково-дослідних робіт Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України в рамках наступних науково-дослідних тем: „Адаптивні методи та засоби оптимізації і моделювання складних систем мережової топології” (шифр - Циклод-3), РК №0199U000258 (1999-2001р.р.), виконавець; „Методи та засоби моделювання, логічного виведення та оптимізації для організаційно-технічних систем з складною сітьовою структурою внутрішньосистемних відношень та масоенергетичних потоків” (шифр - Циклод-4), РК №0102U000902 (2002-2004р.р.), виконавець; „Розробка методів та комп'ютерних засобів підтримки прийняття рішень в задачах ситуаційного та технологічного управління в енергетиці” (шифр - Управління), РК №0102U005589 (2002-2006р.р.), відповідальний виконавець розділу.

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

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

· Розробити модель подання знань. Для цього:

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

– побудувати математичну модель, яка би мала множину виявлених властивостей.

· Розробити методи обробки знань, а саме:

– метод прямого логічного виводу;

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

– методи статичної верифікації поданих знань;

– методи генерації множини тестових випадків на поданих знаннях.

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

Об'єкт дослідження - подання і обробка знань.

Предмет дослідження - модель подання знань і методи обробки знань.

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

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

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

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

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

4. Розроблено методи статичної верифікації знань, поданих у ЛОС-мережі. На відміну від відомих методів статичної верифікації баз знань, які дозволяють виявляти аномалії (можливі помилки в базі знань), розроблені методи дозволяють виявляти фактичні помилки в поданих знаннях.

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

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

СЛМ-технологія використовується для вирішення прикладних задач: в Управлінні планування та моніторингу Головного управління МНС в Запорізькій області (де використовується для рішення задач реагування на розлив небезпечних речовин) та в НДЦ „ТЕЗІС” НТУУ „КПІ” (де використовується для розробки системи підтримки прийняття рішень). Крім того, результати дисертаційних досліджень (в тому числі і СЛМ-технологія) впроваджено в навчальний процес: в Національному університеті харчових технологій і в Національному університеті „Києво-Могилянська академія”.

Особистий внесок здобувача. В роботах, написаних у співавторстві, автору належать: в [5] - всі результати, за винятком реалізації систем МЕТОД і ПРИЗМА, авторство на які належить д.т.н., професору Кондращенко В.Я.; в [18] - методика, що покладена в основу оцінки часової складності алгоритму виводу; виконання оцінки часової складності алгоритму.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались і обговорювались на Міжнародній конференції з управління “Автоматика-2000” (м.Львів, 2000р.), Міжнародній конференції “Искусственный интеллект-2000” (м.Кацивелі, 2000р.), Міжнародному семінарі “Фундаментальные и прикладные проблемы мониторинга и прогноза стихийных бедствий” (Стихия-2001) (м.Севастополь, 2001р.), Російсько-українському науковому семінарі “Интеллектуальный анализ информации” (ИАИ-2002) (м.Київ, 2002р.), Міжнародному семінарі “Фундаментальные и прикладные проблемы мониторинга и прогноза стихийных бедствий” (Стихия-2002) (м.Севастополь, 2002р.), Міжнародній науково-практичній конференції “Искусственный интеллект-2002” (м.Кацивелі, 2002р.), Російсько-українському науковому семінарі “Интеллектуальный анализ информации” (ИАИ-2003) (м.Киев, 2003р.), Міжнародній конференції “Информационные технологии в управлении энергетическими системами” (ИТУЭС-2005) (м.Киев, 2005р.), конференції “Моделирование-2006” (м.Київ, 2006р.), Десятой национальной конференции по искусственному интеллекту с международным участием КИИ-2006 (м.Обнінськ, Росія, 2006р.), а також на щорічних науково-технічних конференціях Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України в 2000-2004р.р.

Публікації. Результати дисертації опубліковані в 41 роботі, в тому числі: в 36 статтях в професійних наукових журналах і збірниках наукових праць, що входять до переліку, затвердженому ВАК України, та в 5 публікаціях в матеріалах конференцій. До автореферату дисертації включено 30 основних публікацій, виданих в фахових наукових журналах і збірниках наукових праць, що входять до переліку, затвердженому ВАК України.

Структура та обсяг дисертації. Дисертація складається із вступу, 9 розділів, висновків, списку використаних джерел та 18 додатків, які видані окремою книгою. Загальний обсяг роботи складає 366 сторінок. Дисертація містить 102 рисунки та 24 таблиці, що займають 33 сторінки. Список використаних джерел включає 290 найменувань на 25 сторінках. Обсяг додатків складає 198 сторінок.

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

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

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

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

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

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

Розглянуто проблему валідації і верифікації (V&V) СЗЗ. Показано, що на сьогоднішній день відомі методи V&V СЗЗ призначені для рішення задач статичної верифікації та емпіричного тестування продукційних СЗЗ.

Виконано аналітичний огляд відомих методів та програмних засобів статичної верифікації продукційних СЗЗ, по результатах якого сформульовано множину вимог до методів статичної верифікації, що необхідно розробити. Виходячи з цих вимог, методи статичної верифікації повинні: дозволяти виявляти фактичні (а не можливі) помилки в поданих декларативних і процедурних знаннях; не передбачати завдання користувачем будь-яких додаткових метазнань (семантичних обмежень); не засновуватись на використанні механізму логічного виводу. Показано, що відомі методи статичної верифікації одночасно не задовольняють всім наведеним вимогам.

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

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

На основі виконаного огляду сформульовано задачі досліджень.

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

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

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

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

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

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

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

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

Обґрунтовано, що для подання логічної структури імені, що є словом (словосполученням), необхідно і достатньо трьох логічних операцій: повної диз'юнкції (), кон'юнкції (&) та заперечення (?), де операція ? вводиться як частка (або приставка) „не” до імені. Логічна операція повної диз'юнкції є n-арною (де n ? 2), і має наступну формулу еквівалентних перетворень:

Формула (1) приймає значення „істина” тоді і тільки тоді, коли істинна одна і тільки одна з підформул A_i (i = 1,n), що до неї входять.

На основі узагальнення результатів рішення задач (1) (3) показано, що структура декларативних знань про довільну ПО може бути подана у вигляді простого ациклічного кінцевого зв'язного однонаправленого графа ієрархічної мережної структури, в якому кожна вершина має ім'я, яке позначає цілком визначений об'єкт ПО; кожній нетермінальній вершині ставиться у відповідність цілком визначена логічна операція, що належить до системи операцій ,&); вершині може бути зіставлена операція заперечення, яка вводиться як частка (або приставка) „не” до імені вершини.

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

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

В процесі рішення задачі (2) властивості імен вершин, що входять до складу структури процедурних знань, досліджено з двох сторін: зі сторони іменування вершин за допомогою імен параметрів, що визначаються в результаті рішення задач, зіставлених вершинам, та зі сторони іменування вершин за допомогою імен методів, використовуваних для рішення задач, зіставлених вершинам.

В результаті вирішення задачі (3) доведено, що для подання логічної структури процедурних знань необхідно і достатньо двох логічних операцій: ,&).

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

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

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

Визначення 3.1. Під логіко-обчислювальною семантичною мережею LCSN=(V,E,Д) розуміється простий ациклічний однонаправлений кінцевий зв'язний граф, який має наступні властивості:

1. Кожна вершина v?V однозначно характеризується кортежем <id_v,n_v,m_v,t_v>, де id_v - унікальний ідентифікатор вершини v; n_v - ім'я вершини v; m_v - ім'я метода, зіставленого вершині v; t_v - тип вершини v.

2. Кожна дуга e?E описує зв'язність між вершинами і має орієнтацію Д(e)(v_i > v_j), де v_i,v_j?V; v_i належить до нижчого рівня ієрархії графа в порівнянні з рівнем ієрархії, до якого належить v_j.

У відповідності до визначення 3.1, кожна вершина v?V ЛОС-мережі однозначно описується кортежем <id_v,n_v,m_v,t_v>, де n_v ? N, m_v ? M, t_v ? T; N - непуста кінцева множина імен об'єктів досліджуваної ПО; M - кінцева множина імен методів, виконуваних у досліджуваній ПО; T - множина типів вершин (T={0,1,2,3,4,5}). Загальна характеристика елементів, що належать до вищенаведеного кортежу, наведена на рис. 1. Зазначимо, що існують наступні типи t_v ? T вершин: термінальні вершини (0), логічні І-вершини (1) і логічні АБО-вершини (2), обчислювальні І-вершини (3), умовні І-вершини (4) та ітераційні І-вершини (5). Таким чином, тип t_v вершини дозволяє відобразити логічні (і в деяких випадках обчислювальні) властивості вершини v ? V. Будь-яку ЛОС-мережу, побудовану у відповідності з визначенням 3.1, будемо називати правильно побудованою ЛОС-мережею.

Існує дві суттєві відмінності властивостей дуг ЛОС-мережі від властивостей дуг в більшості інших відомих різновидах семантичних мереж.

По-перше, дуги в ЛОС-мережі є непоміченими (тобто їм не ставиться у відповідність сутність відображуваного відношення - типу “is-a”, “part-of” і т.п.). Змістовна інтерпретація відношень, що моделюються за допомогою дуг, в кожному конкретному випадку стає зрозумілою з контексту, що відображається в структурі ЛОС-мережі.

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

Множина імен термінальних вершин (вершин типа 0) ЛОС-мережі відповідає універсуму вхідних параметрів, за допомогою яких виконуваний опис різноманітних ситуацій в досліджуваній ПО. Інші вершини (вершини типа 1 5) можуть виступати тільки у якості нетермінальних вершин ЛОС-мережі.

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

Для подання процедурних знань введено вершини типа 3, 4 і 5. Вершина типа 3 називається обчислювальною І-вершиною. Сутність цієї вершини подібна сутності вершини типа 1 з тією різницею, що вершині типа 3 зіставлений обчислювальний метод. Вершина типа 4 називається умовною І-вершиною, а вершина типа 5 - ітераційною І-вершиною.

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

Оператор присвоювання є властивим для всіх типів вершин і виконується в результаті завдання вершини у якості вхідного параметру (для вершини типа 0) або виведення вершини (для інших типів вершин).

Механізм виклику процедур є властивим для вершин типа 3 і типа 4.

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

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

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

Під розгалуженням алгоритмів розуміється припис, відповідно до якого необхідно застосувати до вхідних даних алгоритм ? або алгоритм ? в залежності від виконуваності деякої умови Ф, де Ф є розпізнаючим алгоритмом, який у випадку успішного виконання зіставленої йому умови породжує 1, а в супротивному випадку - породжує 0. Програмування розгалуження алгоритмів в ЛОС-мережі полягає в побудові композиції вершин, яка включає (див. рис.2): вершину типа 4 (умовну І-вершину), якій зіставлений метод Ф, що зв'язується дугами відповідно з вершиною, яка має ідентифікатор, помічений постфіксом _1 (наприклад, Х_1), якій зіставлений алгоритм ? (для випадку, коли внаслідок виконання Ф отримано результат 1) та вершиною, що має ідентифікатор, помічений постфіксом _0 (наприклад, Y_0), якій зіставлений алгоритм ? (для випадку, коли внаслідок виконання Ф отримано результат 0).

Під повторним використанням алгоритму розуміється повторення використання алгоритму ? до поточних даних до тих пір, поки виконується деяка умова Ф (де під Ф розуміється деякий розпізнаючий алгоритм). Програмування повторного використання алгоритму в ЛОС-мережі полягає в побудові композиції вершин, яка включає одну вершину типа 4, одну або декілька вершин типа 3 і одну вершину типа 5. Вершина типа 5 є ітераційною І-вершиною.

Виходячи з вищевикладеного, показано, що для адекватного подання процедурних знань в ЛОС-мережі необхідно і достатньо п'яти типів вершин: типа 0, типа 2, типа 3, типа 4 і типа 5.

Наведено приклади подання декларативних та процедурних знань в ЛОС-мережі (приклад подання процедурно-декларативних знань в ЛОС-мережі див. на рис. 9). Виконано порівняння функціональних можливостей ЛОС-мережі та пропозиціональної семантичної мережі (S.C.Shapiro), процедурної семантичної мережі (H.Levesque, J.Mylopoulos) і блочної семантичної мережі (G.G.Hendrix) на конкретних прикладах подання знань. Продемонстровано, що ЛОС-мережа за своїми функціональними можливостями перевершує перелічені мережні моделі.

Показано, що ЛОС-мережа задовольняє всім пред'явленим до неї вимогам.

У розділі 4 побудовано обчислення, що формалізує логічні властивості ЛОС-мережі, виконано формалізацію структури ЛОС-мережі, формалізовано поняття логічного виводу та викладено метод прямого виводу на ЛОС-мережі.

У відповідності до визначення 3.1, ЛОС-мережа представляє собою орграф з вищевикладеними властивостями, до структури якого входить множина V вершин, де V=V_t ? V_nt; V_t - кінцева множина термінальних вершин ЛОС-мережі, V_nt - кінцева множина нетермінальних вершин ЛОС-мережі, V_t ? V_nt = {?}.

Множина V_t включає вершини, імена яких є елементарними іменами досліджуваної ПО, які не мають власної логічної структури в рамках досліджуваної ПО і безпосередньо позначають відповідні об'єкти досліджуваної ПО. Ідентифікатори термінальних вершин, імена яких не містять заперечення (частки (або приставки) „не”), будемо називати атомами. Атом або заперечення атома будемо називати літералом. Як наслідок, ідентифікатор будь-якої термінальної вершини є літералом.

Множина V_nt включає вершини, імена яких є складними іменами, тобто такими, що мають власну логічну структуру в рамках досліджуваної ПО. Будь-яке складне ім'я може бути сформовано з елементарних імен шляхом зв'язування їх логічними операціями, що належать базису ,&,?). Як наслідок, кожній нетермінальній вершині ЛОС-мережі може бути поставлена у відповідність деяка формула, побудована з атомів, зв'язаних між собою логічними операціями, що належать базису. В зв'язку з тим, що ідентифікатори вершин мають складну структуру, для позначення формул будемо використовувати прописні готичні букви: A, B, C, … (можливо, з індексами).

Побудовано C-обчислення, що формалізує логічні властивості ЛОС-мережі. Задано алфавіт (множину символів) C-обчислення, визначено правила утворення формул C-обчислення та введено правила висновку для C-обчислення.

Знаки, що використані для побудови C-обчислення, поділяються на дві групи: (1) символи; (2) формули - кінцеві послідовності символів.

1. Символи

1.1. Логічні символи: повна диз'юнкція ; кон'юнкція &; заперечення ?.

1.2. Ідентифікатори: множина букв A, B, C, … (можливо, з індексами).

1.3. Допоміжні символи: ліва скобка (, права скобка ).

2. Формули

Формулою C-обчислення будемо називати вираз, що задовольняє наступному індуктивному визначенню:

Атом є формулою.

Якщо A - формула, то (?A) - формула.

Якщо A₁, …, A_n - формули, то (A₁ & … & A_n), - формули, де n - натуральне число.

Інших правил утворення формул немає.

Будь-якій вершині ЛОС-мережі можна поставити у відповідність цілком визначену формулу C-обчислення, і навпаки. Покажемо це на прикладі довільної ЛОС-мережі, зображеної на рис. 4, в якій вершинам B₃ і D зіставлена операція повної диз'юнкції (про що свідчать „дужки”, які зв'язують дуги, що заходять в ці вершини), а вершинам B₁, B₂, C - логічна операція кон'юнкції. Наприклад, вершина B₃ подає в структурі ЛОС-мережі формулу. В свою чергу, вірно і зворотне, тобто наведена формула подана в структурі ЛОС-мережі за допомогою вершини B₃. В цілому формула, яка відповідає всій ЛОС-мережі, заміщується формулою D, і має наступний вигляд:

Як слідує з (2), скобки в формулах відображають порядок входження підформул у формули.

Поняття підформули формули C-обчислення визначається індуктивно:

A є підформула формули A;

Якщо (B₁&…&B_n), є підформула формули A, то (B₁,…,B_n) є підформулами формули A;

Інших правил утворення підформул немає.

На основі вищевикладених положень виконано формалізацію структури ЛОС-мережі. Оскільки будь-якій вершині ЛОС-мережі може бути поставлена у відповідність деяка цілком визначена заміщуюча формула, що позначається ідентифікатором такої вершини, і враховуючи, що ЛОС-мережа являє собою зв'язний орграф, показано, що структура ЛОС-мережі може бути адекватно описана за допомогою множини відображень виду: A_i>{B₁,…,B_m}, де A_i - ідентифікатор довільної вершини ЛОС-мережі (i?I; I=card(V)); B₁,…,B_m - ідентифікатори вершин, суміжних вершині A_i по дугах, що з неї виходять.

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

Визначимо поняття нелогічної аксіоми стосовно до C-обчислення. Для цього визначимо поняття інтерпретації для формул C-обчислення: під інтерпретацією розуміється таке приписування значень істинності літералам, при якому кожний з них приймає логічне значення „істина” (І) або „хиба” (Х), але не те і інше одночасно. Тоді будь-який літерал, що прийняв в даній інтерпретації логічне значення І, будемо називати нелогічною аксіомою (далі - аксіомою).

Введемо поняття фрагмента ЛОС-мережі. Для цього виконаємо розріз ЛОС-мережі з формуванням m орієнтованих кореневих дерев, у яких всі дуги орієнтовані до кореня і довжина шляхів будь-якої дуги дорівнює 1, де m=card(V_nt). Кожне таке ордерево будемо називати фрагментом. Корінь фрагмента будемо називати кореневою вершиною фрагмента. Вершини фрагмента, суміжні його кореневій вершині, будемо називати висячими вершинами фрагмента.

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

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

Поняття безпосередньо вивідної формули (в рамках C-обчислення) визначається індуктивно:

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

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

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

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

Будь-яка формула є безпосередньо вивідною тільки в силу п.п.1-4.

Відношення, що існують між породжуючими формулами і безпосередньо вивідною формулою, формалізуються за допомогою правил висновку. Розрізняються правила висновку для кон'юнктивного і диз'юнктивного фрагмента. Показано, що правила висновку формалізують відношення вивідності формули B з формул A₁,…,A_k (символічно: A₁,…,A_k |- B), де значення k залежить від виду правила висновку. Таким чином, отримання безпосередньо вивідної формули пов'язано з застосуванням одного з правил висновку до деякої множини породжуючих формул.

На основі визначених понять формалізовано поняття логічного виводу для ЛОС-мережі. Будемо говорити, що безпосередньо вивідна вершина id_vi є розв'язною, якщо метод, зіставлений цій вершині, успішно виконано (де під id_vi розуміється ідентифікатор вершини v_i ? V_nt).

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

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

Алгоритм виводу включає 4 кроки.

Крок 1. Вибирається вершина id_i?O₁ (де i ? I; I = card(O₁)), яка запам'ятовується як id, і виконується формування доповнення до множини вершин, суміжних вершині id: = V_nt \ ID, де ID вибирається з відображення {id>ID}?S. Вершина id додається до U: U = {id} і виконується перехід до кроку 2.

Крок 2. Виконується формування множини U: для ?({id_j>ID_j})?(S\{id_j>ID_j})

(де j?J; J = card(S\{id_j>ID_j}) перевірити, якщо , то відповідний елемент id_j додати до множини U. По завершенню кроку 2 перейти до кроку 3.

Крок 3. Виконується формування множини множин R за рахунок перетворення множини U. По завершенню виконання кроку 3 виконується очистка множини U: U={?} і здійснюється перехід до кроку 4.

Крок 4. Виконується формування вивідних вершин. Для цього послідовно вибираються R_n?R. Для ?(id_m)?R_n (де m ? M; M = card(R_n)) знаходяться множини ID_m (в {id_m>ID_m}?S), над якими виконується операція перетину. У випадку, якщо множина, що отримана в результаті операції перетину, містить більше одного елемента, виконується ОСТАНОВ роботи алгоритму з діагностикою логічної помилки структури ЛОС-мережі. В супротивному випадку така множина буде містити один елемент idⁿ, що є вершиною, породжуваною з множини породжуючих вершин id_m?R_n. По idⁿ в множині Q визначається логічний тип вершини idⁿ:

1) Якщо тип вершини - І-вершина, то для ?(id_m)?R_n перевірити, що id_m?O₁. У випадку неуспішного завершення перевірки додати R_n (така множина називається нерозв'язною) до R і виконати перехід до кроку 4.