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

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

Рубрика Математика
Вид автореферат
Язык украинский
Дата добавления 12.07.2014
Размер файла 93,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

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

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

Харків 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).


Подобные документы

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

    дипломная работа [328,4 K], добавлен 21.07.2008

  • Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.

    лекция [2,5 M], добавлен 28.10.2014

  • Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.

    курсовая работа [239,3 K], добавлен 10.06.2007

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

    конспект урока [263,1 K], добавлен 28.06.2012

  • Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.

    задача [112,0 K], добавлен 23.06.2010

  • Історія виникнення математичних рядів. Монотонна послідовність, сума ряду і властивості гармонійного ряду. Поняття числа "e", властивості рядів Фур'є і Діріхле. Приклади розгортання і збіжності рядів Фур'є. Індивідуальна побудова математичних рядів.

    контрольная работа [502,5 K], добавлен 08.10.2014

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

    курсовая работа [1,6 M], добавлен 02.03.2014

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

    дипломная работа [239,7 K], добавлен 15.03.2013

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

    контрольная работа [116,4 K], добавлен 29.08.2011

  • Розв'язання задач з теорії множин та математичної логіки. Визначення основних характеристик графа г (Х,W). Розклад функцій дискретного аргументу в ряди по базисним функціям. Побудова та доведення діаграми Ейлера-Вена. Побудова матриці інцидентності графа.

    курсовая работа [988,5 K], добавлен 20.04.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.