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

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

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

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

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

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

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

Харків 2003

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

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

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

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

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

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

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

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

Модель рівності являє собою пару P, U², де 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. Предикатна модель має вид P_S, U², предикат P_S визначається виразом

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

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

P_S(x, y) = P_L(x, y) p(x, y),(2)

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

Результатом логічної ідентифікації декартового добутку є модель вигляду P, U², де U - предметний універсум, предикат P визначається виразом x, yU (P(x, y) ~ A(x) B(y)). Дана модель має два параметри: предикати A і B. Співвідношення між A, B і P таке: ці предикати являють собою характеристичні функції множин A, B U і P U² таких, що 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, B³>, <S, B³>, <T, B²>. Предикати 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 - будь-які множини, 2^B - множина усіх підмножин B, C - система назв множин з 2^B. Між відношеннями на AB і відображеннями з A у 2^B існує взаємно-однозначна відповідність наступного вигляду. Нехай P - деяке відношення на AB, тоді йому відповідає відображення f:A2^B, таке, що f(x) = S_x= {y|P(x, y) = 1} для будь-якого xA. Відображення f формально задамо предикатом F(х, z) на АС, що зв'язує елемент хА з назвою zС множини S_x. Предикат 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)); z₁, z₂A (xA (F(x, z₁) ~ F(x, z₂)) D(z₁, z₂); xA zC F(x, z), де П - предикат належності на AC; D - предикат рівності на C.

Модель еквівалентності має вигляд <E, A²>, де 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.

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

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

Для будь-якого перетворення F позначимо: E_F = F(U) F(). Доведено таку теорему: рівняння F(P) = U має рішення тоді і тільки тоді, коли E_F = 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)) E_FC. Для будь-якого перетворення F і будь-якої множини C виконується F(F() F(U)C) = F(C~F(C)) = E_F. Рівняння 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 з 2^U назвемо нерухомою точкою перетворення F, якщо для неї виконується рівність P = F(P). Якщо перетворення F не має жодної нерухомої точки, то його будемо називати виродженим, у противному випадку - невиродженим. Областю значень перетворення F визначаємо множину = {F(P)|P2^U}. Доведено, що множина всіх нерухомих точок невиродженого перетворення збігається з його областю значень. Позначимо для будь-якого перетворення F множину H_F = {C ~ F(C)| C2^U}. Показано, якщо рівняння F(P) = U розв'язується, то пара H_F, є решіткою з нулем та одиницею, причому як нуль та одиниця виступають, відповідно, множиниF() і F(U).

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

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

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

F*(P₁(), P₂(), …, ()) = 1,(5)

F*(P₁(), P₂(), …, P_|I|()) = F().(6)

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