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

Колесников Дмитро Олегович

УДК 004.8:004.93

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

05.13.23 - системи та засоби штучного інтелекту

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

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

Харків 2003

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

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

Науковий керівник | доктор технічних наук, професор

Шабанов-Кушнаренко Юрій Петрович,

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

радіоелектроніки, професор кафедри

програмного забезпечення ЕОМ.

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

доктор технічних наук, професор Авраменко Валерій Павлович, Харківський національний університет радіоелектроніки, професор кафедри інформаційних управляючих систем;

кандидат технічних наук, доцент Ситнікова Поліна Едуардівна, Харківський гуманітарний інститут "Народна українська академія", доцент кафедри інформаційних технологій та документознавства.

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

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

Захист відбудеться “19” березня 2003р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розіслано “18” лютого 2003р.

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

спеціалізованої вченої ради Саєнко В.І.

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

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

Однією з головних задач, поставлених перед теорією та практикою штучного інтелекту, є моделювання функцій людського інтелекту. Як наслідок, задача розробки ефективного логіко-математичного інструментарію, спеціально призначеного для таких цілей, а також подальшого його вивчення, є актуальною з теоретичної та практичної точок зору. Значні результати в цій області отримані ученими В.М. Глушковим, Д.А. Поспєловим, Ю.П. Шабановим-Кушнаренком,
Р. Монтегю, Д. Ленатом та ін.

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки в рамках держбюджетної теми № ДР 0197U012126 "Розробка теорії штучного інтелекту на базі дослідження механізмів розуму людини та її застосування для проектування та побудови інтелектуальних систем". Здобувач брав участь у виконанні робіт з теми як виконавець.

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

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

-

-

-

-

Об’єкт дослідження: логіко-математичні поняття як базові елементи інтелектуальної діяльності людини.

Предмет дослідження: предикатні моделі логіко-математичних понять і методи розв’язання логічних рівнянь.

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

Наукова новизна отриманих результатів. Наукова новизна результатів, отриманих у процесі виконання роботи, полягає в наступному.

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

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

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

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

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

2. Розроблені в роботі предикатні моделі логіко-математичних понять та методи розв’язання логічних рівнянь були використані при розробці системи керування дедуктивною базою даних, що є складовою частиною системи логічної підтримки прийняття рішень (довідка про упровадження від 20.02.2001, Інститут фізики високих енергій та ядерної фізики при Національному науковому центрі "Харківський фізико-технічний інститут"). Застосування розроблених моделей дозволило формулювати запити до бази даних з використанням відповідних понять, що підвищило рівень абстракції системи запитів, а також дало можливість реалізовувати обчислення відповідей на такі запити. Застосування розробленого методу розв’язання рівнянь алгебри предикатних операцій з невідомими предикатами дозволило ефективно обчислювати відповіді на деякі запити, що визначають відносини в термінах своїх заперечень. Упровадження даних результатів дозволило забезпечити надійність прийнятих рішень за рахунок реалізації коректного логічного виводу при обчисленні відповідей на запити які формулюються з використанням логіко-математичних понять, а також запити, що визначають відносини в термінах своїх заперечень.

3. Розроблені методи розв’язання логічних рівнянь були використані при побудові системи керування базою знань, яка базується на численні предикатів першого порядку, для розв’язання задачі умовної мінімізації за кількістю букв формул, що представляють фрагменти бази знань (акт упровадження від 20.08.2001, Харківське виробниче об’єднання "Радиореле"; акт упровадження від 10.09.2001, НДТІ Приладобудування). Упровадження даних результатів у підсумку дозволило досягти економного представлення інформації в базі знань.

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

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

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

Апробація результатів дисертації. Основні результати дисертації апробовані на міжнародній конференції "Автоматика – 99" (м. Харків, 1999); 4-му Молодіжному форумі “Радіоелектроніка і молодь у XXI столітті” (Харків, 2000 р.); 6-й Міжнародній конференції “Теорія і техніка передачі, прийому та обробки інформації” (Харків-Туапсе, 2000 р.).

Структура дисертації. Дисертаційна робота складається зі вступу, п’яти розділів, висновків та трьох додатків на 20 сторінках. Повний обсяг дисертації – 155 сторінок. Дисертація містить 2 ілюстрації, список використаних літературних джерел з 119 найменувань на 10 сторінках.

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

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

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

Для формалізації інформаційного об’єкта досить визначити його структуру на тому чи іншому рівні абстрагування. Під структурою об’єкта варто розуміти сукупність стійких взаємозв’язків об’єкта, що забезпечують його цілісність і тотожність самому собі, тобто незмінність властивостей об’єкта при різних зовнішніх та внутрішніх взаємодіях. Експлікацією структури є поняття моделі (чи реляційної системи) у теорії алгебраїчних систем, під якою розуміється пара <N, P>, що складається з множини N, і предикатів (відносин) P, заданих на цій множині. Для того, щоб відрізнити таке визначення поняття моделі від інших видів математичних моделей, введемо термін предикатна модель. Таким чином, предикатна модель є експлікацією поняття структури і, займаючись побудовою предикатної моделі інформаційного об’єкта ми, тим самим, займаємося вивченням його структури. У дисертаційній роботі розглядаються питання побудови предикатних моделей логіко-математичних понять.

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

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

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

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

Модель рівності являє собою пару P, U2, де U – предметний універсум, P – предикат, зумовлений одним із таких виразів: х, уU (Р(х, у) ~ АU (А(х)~А(у))); х, уU (Р(х, у) ~ аU (хауа)) чи х, уU (Р(х, у) ~ U (х ~ у)). Визначено дві аксіоматичні характеристики рівності: xU P(x, x); AU x, yU (A(x)P(x, y) A(y)) і xU P(x, x); x, yU (P(x, y)~P(y, x)); x, y, zU (P(x, y)P(y, z)P(x, z)); xU !yU P(x, y). Дані аксіоматичні характеристики еквівалентні в тому змісті, що вони обидві однозначно визначають модель рівності.

Проаналізовано проблему порівняння об’єктів реального світу. Показано, що відношення рівності, так як воно визначено в математичній літературі, для порівняння об’єктів реального світу не може бути реалізовано. Для порівняння таких об’єктів запропоновано використовувати поняття рівності з набору властивостей, яке припускає визначення рівності об’єктів x та y, виходячи з перевірки для них виконання властивостей A з деякого фіксованого набору властивостей S. Предикатна модель має вид PS, U2, предикат PS визначається виразом

х, уU (РS(х, у) ~ АS (А(х) ~ А(у))), (1)

де S 2U – деяка множина властивостей, що є параметром моделі. Відношення PS є відношенням еквівалентності. Якщо в сукупність властивостей S, за яким має вестися порівняння об’єктів, входить властивість S рівності об’єктів за значенням деякої їхньої характеристики , то в цьому випадку предикат рівності за набором S матиме вигляд:

PS(x, y) = PL(x, y) p(x, y), (2)

де L = S\S – множина властивостей S без властивості S, p – предикат рівності на множини всіляких значень характеристики .

Результатом логічної ідентифікації декартового добутку є модель вигляду P, U2, де U – предметний універсум, предикат P визначається виразом x, yU (P(x, y) ~ A(x) B(y)). Дана модель має два параметри: предикати A і B. Співвідношення між A, B і P таке: ці предикати являють собою характеристичні функції множин A, B U і P U2 таких, що A B = P. Отримано аксіоматичну характеристику декартового добутку: x, yU (P(x, y) ~ (xU P(x, y)) (yU P(x, y)). Доведено, що будь-яке ненульове розв’язання останнього рівняння розкладається єдиним способом у кон’юнкцію двох предикатів: P(x, y) = A(x)B(y), де предикати A і B визначаються за формулами: A(x) = yU P(x, y) і B(y) = xU P(x, y). Виходячи з побудованої моделі доведено найбільш широко використовувані властивості декартового добутку.

Предикат P, носій моделі декартового добутку, назвемо декартовим предикатом. Виходячи з результатів ідентифікації поняття декартового добутку, звичайно підійти до наступного його розширення: декартовим предикатом будемо називати будь-який предикат, який представлений у вигляді кон’юнкції двох чи більше предикатів меншої розмірності із непересічними наборами змінних. Формально описаний клас декартових предикатів як підмножина множини всіх багатомісних предикатів. Багатомісним декартовим предикатам поставимо у відповідність визначену математичну конструкцію. Нехай дано деяку систему множин, записуючи кон’юнкцію відповідних предикатів з непересічними наборами змінних, одержимо предикат, якому відповідає деяка множина. У випадку двомісних декартових предикатів надана конструкція збігається з декартовим добутком. Таким чином, декартовим предикатам поставлена у підмножин А. Тоді операціям об’єднання, перетинання і доповнення, які задані на множині всіх підмножин А, поставимо у відповідність предикати R, S і T таким чином: R(y1, y2, y3) = 1Y1Y2=Y3; S(y1, y2, y3) = 1Y1Y2=Y3; T(y1, y2) = 1 Y1 = Y2, де множинам Y1, Y2, Y3 A привласнені назви y1, y2, y3 B. Моделі теоретико-множинних операцій мають вигляд: <R, B3>, <S, B3>, <T, B2>. Предикати R, S і T визначаються виразами: у1, у2, у3В (R(у1, у2, у3) ~ хА ((P(x, у1) P(x, у2)) ~ P(x, у3)); у1, у2, у3В (S(у1, у2, у3) ~ хА ((P(x, у1) P(x, у2)) ~ P(x, у3)) і у1, у2В (Т(у1, у2) ~ хА (P(x, y1) ~ P(x, у2)), де предикат P – довільний предикат належності на AЧВ. Доведено твердження про функціональність предикатів R, S і T: для будь-яких у1, у2 B існує один у3 В, такий що R(y1, y2, y3) = 1; для будь-яких у1, у2 B існує один у3 В, такий що S(y1, y2, y3) = 1; для кожного у1 існує один у2 B, такий що T(y1, y2) = 1.

Формалізовано зв’язок між відображеннями і відношеннями. Нехай A і B – будь-які множини, 2B – множина усіх підмножин B, C – система назв множин з 2B. Між відношеннями на AB і відображеннями з A у 2B існує взаємно-однозначна відповідність наступного вигляду. Нехай P – деяке відношення на AB, тоді йому відповідає відображення f:A2B, таке, що f(x) = Sx= {y|P(x, y) = 1} для будь-якого xA. Відображення f формально задамо предикатом F(х, z) на АС, що зв’язує елемент хА з назвою zС множини Sx. Предикат F виражається через Р наступною формулою: хА, zС [F(х, z) ~ уВ (Р(х, у) ~ (у, z))], де – предикат належності на BC. Таким чином, побудована модель <F, AC> поняття відображення. Зворотний перехід від предиката F до предиката Р описується залежністю хА, yB [Р(х, у) ~ zС (F(х, z) ~ П(у, z))]. Таким чином, побудована модель <P, AB> поняття відношення.

Нехай A – довільна множина, C – система назв усіх підмножин A. Розбивкою множини A називається будь-яка сукупність непорожніх, попарно непересічних підмножин A, що дають в об’єднанні A. Модель поняття розбивки має вигляд <F, AC>. Предикат розбивки F визначається виразом хА, zС [F(x, z) ~ yA (E(x, y) ~ П(y, z)], де П – предикат належності на AC, E – предикат еквівалентності на множині A. Параметр моделі П задає назви класам розбивки. Розбивка має аксіоматичну характеристику, що складається з наступних трьох виразів: zC (xA F(x, z) yA П(y, z)); z1, z2A (xA (F(x, z1) ~ F(x, z2)) D(z1, z2); xA zC F(x, z), де П – предикат належності на AC; D – предикат рівності на C.

Модель еквівалентності має вигляд <E, A2>, де A – довільна множина елементів. Предикат еквівалентності E визначається виразом x, yA [E(x, y)~ zC (F(x, z) F(y, z))] чи x, yA [E(x, y) ~ zC (F(x, z) ~ F(y, z))], де F – предикат розбивки на AC, C – система імен усіх підмножин A.

Третій розділ присвячено розробці методів знаходження загальних розв’язань рівнянь алгебри множин. Визначено критерії можливості розв’язання та знайдено загальні розв’язки рівнянь алгебри множин з невідомими множинами та невідомими перетвореннями. Наведено і доведено властивості перетворень, рівнянь та їх загальних розв’язань алгебри множин.

Нехай 2U – множина усіх підмножин деякого універсума U, сукупність АМ= <2U, > являє собою алгебру множин з носієм 2U, і сигнатурою = <, , >, що складається з теоретико-множинних операцій об’єднання , перетинання і доповнення . За допомогою множин з 2U та операцій з можна будувати різноманітні формули алгебри АМ. Формулу F(P), що ставить кожній множині P з 2U у відповідність множину F(P), можна розглядати як відображення з 2U у 2U. У цьому випадку можна говорити, що на 2U задане перетворення F алгебри АМ.

Для будь-якого перетворення F позначимо: EF = F(U) F(). Доведено таку теорему: рівняння F(P) = U має рішення тоді і тільки тоді, коли EF = U. У випадку можливості розв’язання загальне розв’язання вичерпується множинами вигляду P = C~F(C) =F() F(U) C, де C – будь-яка множина. З теореми випливає, якщо рівняння F(P) = U має рішення, то його загальне розв’язання складається з таких і тільки таких множин P для яких виконується F()PF(U).

Доведено наступні властивості перетворень рівнянь алгебри множин. Для будь-якого перетворення F і будь-якої множини C виконуєтьсяF() F(U)C = (C~F(C)) EFC. Для будь-якого перетворення F і будь-якої множини C виконується F(F() F(U)C) = F(C~F(C)) = EF. Рівняння F(P) = U розв’язується тоді і тільки тоді, коли F(C*~F(C*)) = U, де C* – довільна фіксована множина. Рівняння F(P) = U еквівалентно рівнянню P = P ~ F(P). Рівняння P ~ F(P) = U еквівалентно рівнянню P = F(P). Рівняння P = F(P) розв’язується тоді і тільки тоді, колиF(U) F() = U. У випадку можливості розв’язання загальне розв’язання вичерпується множинами вигляду P = F(C), де C – довільна множина. Як критерій можливості розв’язання може виступати рівність F(C*) = F(F(C*)), де C* – довільна фіксована множина.

Множину P з 2U назвемо нерухомою точкою перетворення F, якщо для неї виконується рівність P = F(P). Якщо перетворення F не має жодної нерухомої точки, то його будемо називати виродженим, у противному випадку – невиродженим. Областю значень перетворення F визначаємо множину = {F(P)|P2U}. Доведено, що множина всіх нерухомих точок невиродженого перетворення збігається з його областю значень. Позначимо для будь-якого перетворення F множину HF = {C ~ F(C)| C2U}. Показано, якщо рівняння F(P) = U розв’язується, то пара HF, є решіткою з нулем та одиницею, причому як нуль та одиниця виступають, відповідно, множиниF() і F(U).

Доведено наступні твердження. Множина всіх нерухомих точок невиродженого перетворення F, частково упорядкована відношенням включення, являє собою решітку з нулем та одиницею, у якості яких виступають образи множин і U. Кожному невиродженому перетворенню відповідає відношення еквівалентності, що має рівнопотужні класи вигляду B ={~|HF}, . Всяке невироджене перетворення породжує взаємно однозначне відображення (, ) = ~ множини HF на множину 2U. Для кожного невиродженого перетворення F існує співвідношення між потужностями множин на якій воно задано, області значення та загального розв’язання рівняння F(P) = U: |2U| = || |HF|.

Доведено наступну теорему: рівняння F(P1, P2, ..., Pn) = U відносно невідомих множин P1, ..., Pn розв’язується тоді і тільки тоді, коли

= U,

якщо рівняння розв’язується, то компоненти його загального розв’язання (P1, ..., Pn) задаються через довільні параметри C1, C2, ..., Cn у вигляді

Pj = Pj(Cj, ..., Cn) = Cj ~.

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

Формулу F(P1, ..., Pn), яка ставить кожному набору множин P1, ..., Pn з 2U у відповідність множину F(P1, ..., Pn) можна розглянути як відображення з (2U)n у 2U, у цьому випадку будемо говорити, що на 2U задане n місцеве перетворення F алгебри АМ, котре відповідає формулі F(P1, ..., Pn). Слід зазначити, що не будь-яке відображення з 2U у 2U є перетворенням алгебри АМ, а тільки таке, якому відповідає деяка формула алгебри АМ. Доведено таку теорему: рівняння F(P1, P2, ..., Pn, G1, G2, ..., Gm) = U алгебри АМ з n невідомими m місцевими перетвореннями Pj = Pj(G1, G2, ..., Gm), j = 1, ..., n розв’язується тоді і тільки тоді, коли для будь-яких G1, G2, ..., Gm виконується рівність

,

якщо рівняння розв’язується, то компоненти його загального розв’язку (P1, ..., Pn) виражаються через довільні параметри C1, C2, ..., Cn у вигляді

Pj(Cj,..., Cn, G1,..., Gm) = .

Четвертий розділ присвячений розробці методів розв’язання рівнянь алгебри предикатних операцій з невідомими предикатами.

Алгебра предикатних операцій є потужний інструментальний засіб опису інформаційних об’єктів і процесів. Нехай U деяка множина, M – множина всіх предикатів, заданих на Um, де m – кінцеве натуральне число. Будь-яка операція на множині M, називається предикатною операцією (ПО). Створимо множину R усіх предикатних операцій. Алгеброю предикатних операцій АПО називається будь-яка алгебра, задана на носії R. На тому самому носії R можуть бути задані різні сигнатури, що і визначать ту чи іншу конкретну алгебру предикатних операцій. Рівнянням алгебри АПО з n невідомими предикатами X1, ..., Xn називається рівність F(X1, ..., Xn) = 1, де F – задана ПО із R, 1 – ПО зі значенням, рівним тотожно істинному предикату. У дисертаційній роботі розроблений метод розв’язання таких рівнянь. Для викладу методу розглянемо дві спеціальні алгебри: алгебру підстановочних операцій і алгебру предикатних операцій з константами і змінними.

Серед множини R усіх ПО виділимо такі: константні ПО – ПО, значення яких рівні деяким фіксованим предикатам; тотожні ПО – ПО, значення яких збігаються зі значеннями деяких їхніх змінних. Алгеброю предикатних операцій з константами і змінними називається алгебра КП = RКП, Б, де Б – булева сигнатура, що складається з ПО другого порядку диз’юнкції, кон’юнкції і заперечення, RКП – множина ПО, породжуване тотожними і константними ПО з R за допомогою сигнатури Б. Справедлива така теорема: рівняння F(X1, ..., Xn) = 1 алгебри КП (F RКП) розв’язується тоді і тільки тоді, коли виконується = 1, якщо рівняння розв’язується, то компоненти його загального розв’язку (X1, ..., Xn) виражаються через вільні параметри C1, C2, ..., Cn у виді

Pj = Pj(Cj, …, Cn) = Cj ~.

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

Алгебра підстановочних операцій являє собою алгебру предикатних операцій із сигнатурою, що складається з ПО другого порядку диз’юнкції і заперечення, а також операцій підстановок виду xj/a(F) = F(X1(x1, ..., xj-1, a, xj+1, ..., xm), ..., Xn(x1, ..., xj-1, a, xj+1, ..., xm)), де a U, F = F(X1, ..., Xn) – n-місцева ПО. Відомо, що кожна ПО може бути записана мовою алгебри підстановочних операцій, тому досить розглядати рівняння тільки цієї алгебри, яку будемо позначати символом АПО. Алгебра АПО могутніше алгебри КП, тому що при |U| > 1 їхні носії знаходяться у відношенні строгого включення RКП R. Це означає, що не будь-яке рівняння алгебри АПО є рівнянням алгебри КП. Однак, розв’язання будь-якого рівняння алгебри АПО можна звести до розв’язання рівняння алгебри КП (такі рівняння будемо називати рівносильними), спосіб розв’язання яких визначений сформульованою вище теоремою.

Установимо зв’язок між рівняннями алгебр АПО і КП. Розглянемо довільне рівняння алгебри АПО з одним невідомим F(P) = 1. Шуканий предикат P залежить від набору змінних (x1, ..., xm), що позначимо x. Рівняння при цьому можна переписати у вигляді

x F(P(x)) = 1. (3)

Умовимося через позначати деякий набір змінних з x, через x/ – набір змінних з x, що доповнює набір до x. У роботі показано, що для будь-якого предиката P(x) і будь-якого піднабору набору змінних x завжди існує таке розкладання

P(x) =, (4)

де k – кількість змінних у наборі , j() = – предикат дізнавання елемента aj з Uk, = x\, Pj()= /aj P(x), j = 1, ..., |Uk|. Тобто будь-який предикат можна розкласти в суму добутків предикатів з непересічними наборами змінних.

Якщо підставити розкладання (4) предиката P(x) у рівняння (3), то одержимо рівняння [ F()] = 1 чи

F*(P1(), P2(), …, ()) = 1, (5)

де

F*(P1(), P2(), …, P|I|()) = F(). (6)

Символом КП будемо позначати підалгебру КП, носій якої складається з тих ПО з RКП, у яких змінні, вхідні в набір , є фіктивними. У роботі доведена така теорема: для будь-якого рівняння (3) алгебри АПО завжди існує еквівалентне йому рівняння (5) алгебри КП, де – деякий піднабір набору змінних x; = x\ – доповнення набору до набору x. Зв’язок між предикатом P(x) і системою предикатів визначається формулою (4), предикатні операції F і F* зв’язані співвідношенням (6).

Під еквівалентністю рівнянь (3) і (5) розуміється наступне. Якщо ми вирішимо рівняння (5), то за формулами (4) ми зможемо записати загальне рішення рівняння (3). Вірно і зворотне, зворотний перехід здійснюється по формулах Pj() = /aj P(x), j = 1, ..., |Uk|. Будемо говорити, що набір змінних є вирішальний для рівняння (3), якщо рівняння (5) є рівнянням алгебри КП.

Чим менше буде змінних у вирішальному наборі , тим менше буде невідомих у рівнянні (5) і, як наслідок, менше буде потрібно обчислень при його розв’язанні. Питання про вибір оптимального вирішального набору, залишається відкритим. У дисертації доведена така теорема: складемо піднабір з тих змінних xj, j = 1, …, n , для яких у записі F зустрічається предикатна операція виду xj/a, aU, в область дії якої входить шуканий предикат P(x), тоді набір є вирішальним для рівняння (3). Отримана методика вирішення рівнянь алгебри АПО з одним невідомим за допомогою розв’язання рівнянь алгебри КП поширена на випадок рівнянь з декількома невідомими. Показано, що якщо відоме частинне розв’язання (P1*, ..., Pn*) рівняння F(P1, …, Pn) = 1 довільної алгебри предикатних операцій, то загальне розв’язання рівняння може бути записане у вигляді: Pj = Cj (C1, …, Cn) P1*F(C1, …, Cn), j = 1, …, n, де Cj – вільні предикатні параметри. Таким чином, загальне розв’язання будь-якого рівняння з n невідомими будь-якої алгебри предикатних операцій може бути записане за допомогою n вільних предикатних параметрів.

Проведено оцінку обчислювальної складності розробленого методу розв’язання рівнянь алгебри предикатних операцій з невідомими предикатами. Показано, що якщо рівняння F(P) = 1 з одним невідомим предикатом P має вирішальний набір змінних, що складається з k змінних, то новий метод дозволяє розв’язати рівняння за допомогою обчислень вихідної формули F, що скорочує обчислення в порівнянні з методом повного перебору в раз. Якщо вирішальний набір збігається з набором змінних, від яких залежить предикат P, то розроблений метод реалізує метод повного перебору.

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

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

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

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

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

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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