Алгебро-логічний підхід до аналізу та обробки текстової інформації
Пропонується формальна модель системи аналізу та обробки текстової інформації на основі алгебри множин і відношень та простої логічної мови. Описані алгебро-логічний підхід до аналізу природномовного тексту та алгебраїчна система спискових структур, орієнтована на обробку текстової інформації. The f...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/14629 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Алгебро-логічний підхід до аналізу та обробки текстової інформації / О.В. Палагін, С.Л. Кривий, М.Г. Петренко, Д.C. Бібіков// Пробл. програмув. — 2010. — № 2-3. — С. 318-329. — Бібліогр.: 14 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859857685306933248 |
|---|---|
| author | Палагін, О.В. Кривий, С.Л. Петренко, М.Г. Бібіков, Д.C. |
| author_facet | Палагін, О.В. Кривий, С.Л. Петренко, М.Г. Бібіков, Д.C. |
| citation_txt | Алгебро-логічний підхід до аналізу та обробки текстової інформації / О.В. Палагін, С.Л. Кривий, М.Г. Петренко, Д.C. Бібіков// Пробл. програмув. — 2010. — № 2-3. — С. 318-329. — Бібліогр.: 14 назв. — укр. |
| collection | DSpace DC |
| description | Пропонується формальна модель системи аналізу та обробки текстової інформації на основі алгебри множин і відношень та простої логічної мови. Описані алгебро-логічний підхід до аналізу природномовного тексту та алгебраїчна система спискових структур, орієнтована на обробку текстової інформації.
The formal model of system of the analysis and processing of the text information on the basis of algebra of sets and relations and simple logic language is offered. Are described algebro-logical the approach to the analysis of naturally-language text and the algebraic system of list structures focused on processing of the text information.
|
| first_indexed | 2025-12-07T15:44:25Z |
| format | Article |
| fulltext |
Формальні методи програмування
© О.В. Палагін, С.Л. Кривий, М.Г. Петренко, Д.C. Бібіков, 2010
318 ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск
УДК 51.681.3
АЛГЕБРО-ЛОГІЧНИЙ ПІДХІД ДО АНАЛІЗУ ТА ОБРОБКИ
ТЕКСТОВОЇ ІНФОРМАЦІЇ
О.В. Палагін, С.Л. Кривий, М.Г. Петренко, Д.C. Бібіков
Інститут кібернетики імені В.М. Глушкова НАН України,
03680, МСП, Київ-187, проспект Академика Глушкова, 40,
e-mail: palagin_a@ukr.net, факс: +38044 5263348
Київський національний університет імені Тараса Шевченка,
01601, МСП, Київ-01вул. Володимирівська, 64,
e-mail: krivoi@i.com.ua, факс: +38044 2590439
Пропонується формальна модель системи аналізу та обробки текстової інформації на основі алгебри множин і відношень та простої
логічної мови. Описані алгебро-логічний підхід до аналізу природномовного тексту та алгебраїчна система спискових структур,
орієнтована на обробку текстової інформації.
The formal model of system of the analysis and processing of the text information on the basis of algebra of sets and relations and simple
logic language is offered. Are described algebro-logical the approach to the analysis of naturally-language text and the algebraic system of
list structures focused on processing of the text information.
Вступ
Бурхливий розвиток науки і техніки протягом останніх десятиліть 20-го та початку 21-го століть призвів
до величезного росту інформації, яку одній людині (навіть висококваліфікованому спеціалісту в галузі науки і
техніки) не під силу освоїти, зрозуміти і скористатися нею з метою проведення наукових досліджень. В зв’язку
з такою ситуацією виникає необхідність в автоматизації процесів пошуку та обробки потрібної інформації для її
подальшого ефективного використання. При цьому виникає декілька проблем.
Першою проблемою і однією з основних є проблема аналізу природномовної текстової інформації
(морфологічний, синтаксичний, семантичний та логічний аналіз) з метою добування знань [1].
Другою проблемою є проблема проектування системи пошуку та добування знань, побудова її
архітектури та розробка інструментарію для користувача [1, 2].
Третя проблема – це інтеграція знань із декількох (зокрема двох) предметних областей для забезпечення
ефективності проведення досліджень міждисциплінарного характеру, використання вже існуючих алгоритмів,
фактів, теоретичних положень та практичних розв’язань [1].
В даній роботі пропонується деяка формалізація методів аналізу природномовних текстів (ПМТ), пошуку
логічних наслідків з даних фактів та перевірка суперечності в цій формалізації, формальна мова, названа
алгебраїчною системою спискових структур (АССС), яка орієнтована на обробку текстової інформації. Ця
АССС розглядається як алгоритмічна мова високого рівня.
1. Короткий огляд методів дослідження природномовних текстів
Формалізація природної мови з метою автоматизації аналізу природномовних текстів була започаткована
ще на початку тридцятих років 20-го століття в роботах А. Тарського та його учнів, хоча про таку необхідність
говорили ще Арістотель, Лейбніц і Ейлер. Зокрема, Арістотель виділив чотири типи висловлювань:
А – «все Х є У»; Е – «все Х не є У»; І – «деякі Х є У»; О – «деякі Х не є У».
Ці типи висловлювань були названі силогізмами, а сам підхід Арістотеля – силогістикою. Пізніше
Ейлер в популярній формі виклав своє розуміння силогістики Арістотеля, скориставшись геометричною
інтерпретацією силогістики у вигляді кругів (цю інтерпретацію стали називати кругами Ейлера). Ідеї Ейлера
далі були розвинуті в роботах французького математика і астронома Ж.Д. Жергона, який ввів типи відношень й
інтерпретацію силогістики Арістотеля в термінах цих відношень. Основні типи відношень, введених Жергоном,
є такими:
G
1
– «збігається або рівнозначно»; G
2
– «лівостороннє включення »; G
3
– «окремий випадок збігання»;
G
4
– «правостороннє включення»; G
5
– «несумісність».
Жергон показав, що кожний тип силогізму Арістотеля можна виразити у вигляді певної множини
можливих варіантів таких відношень. Зокрема, А:{G
1
,G
2
}, E:{G
5
}, I:{G
1
,G
2
,G
3
,G
4
}, O:{G
3
,G
4
,G
5
}. Наприклад,
висловлювання типу І означає, що деяка непуста підмножина множини, чи клас Х включається в У. Головна
трудність у використанні жергонових відношень полягає в тому, що практично всі типи цих відношень при
складному реченні вимагають перевірки великої кількості варіантів. Тому більш підходящим виявився підхід на
основі використання формальної математичної логіки.
mailto:palagin_a@ukr.net
mailto:krivoi@i.com.ua
Формальні методи програмування
319
Якщо Арістотель, Лейбніц та Ейлер лише говорили про необхідність формалізації і робили лише перші
кроки на цьому шляху, то більш серйозні спроби такої формалізації були зроблені логіком А. Тарським [3, 4],
результатом яких стала поява поняття виконуваності (сатисфакції) формул – більш загального ніж поняття
істинності. Це поняття Тарський застосував до відкритих і замкнутих формул (під замкнутою формулою
стосовно речень природної мови розуміють фразу), що дало змогу сформулювати поняття істинності природно-
мовного речення і накласти на кожну відкриту атомарну формулу, яка складається з примітивного предиката
(тобто предметної константи) і стількох змінних, стільки відповідає арності предиката. Оскільки таких формул
існує лише скінченна множина, то такий підхід стає конструктивним.
Наступна спроба вдосконалення формалізації А. Тарського була зроблена Д. Девідсоном [5]. Він
запропонував додати до понять виконуваності та істини рекурсивне означення істини. Тоді теорія Т, яка
включає рекурсивне означення істини, пояснює яким чином значення фраз залежить від значення (сенсу) слів
цих фраз. Але, оскільки слово «значення» не є синонімом слова «істина», то означення істини не завжди буде
означенням значення (сенсу). Отже, теза Девідсона не зовсім очевидна, зате її легко обґрунтувати. Звідси
випливає, що необхідно співставляти змістові значення розповідних речень з умовами їх істинності.
Якщо приймається рівняння «значення розповідного речення = умова істинності цього речення», то
потрібно накласти умову: якщо в означенні говориться про те, яким чином умови істинності складного речення
залежать від умов істинності його складових простих речень, то в цьому означенні повинно говоритися про те,
як значення складного речення залежить від значень його складових простих речень.
Монтегю теж вірив у те, що методи формальної семантики можна застосувати до дослідження семантики
природної мови. Але він, на відміну від Девідсона, відмовився від застосування логіки предикатів першого
порядку, віддавши перевагу категоріальним граматикам. Ці граматики включають в себе ті категорії, які
спеціалісти в області граматик традиційно використовують при означенні природної мови, наприклад, такі
категорії, як підмет чи присудок. Цей підхід протилежний до підходу Девідсона. Це дало змогу Монтегю
замінити поняття абсолютної істини на поняття відносної істини в моделі, тому що в одній моделі одне і теж
речення може бути істинним, а в другій – хибним. Таке розширення дало змогу визначити поняття логічної
істинності і логічного наслідку для більш широкого фрагмента природної мови [6]. Таким чином Монтегю
виділив два елементи: інтенцію (сенс) і екстенцію (денотат) й застосував їх до підметів, присудків та фраз.
Існують й інші підходи до аналізу природномовних текстів, які ґрунтуються на поняттях семантичної мережі,
фрейма тощо.
Якщо коротко характеризувати ідеї, які домінували останні десятиліття 20-го століття, то вони зводяться
до таких положень.
Починаючи з 70-х років в дослідженнях природних і штучних (формальних) мов домінували намагання
побудувати теорію, яка б охвачувала як природні, так і штучні мови.
Синтаксис викликає інтерес тільки в зв’язку з семантикою.
Метою семантики є пояснення понять істини та логічного наслідування.
Метою синтаксису є характеристика синтаксичних категорій, з яких побудовані висловлювання.
Ці ідеї привели до того, що виробилися нові погляди на такі поняття як граматика та значення виразів. А
саме:
а) граматика – це інтерпретоване числення виразів мови (генеративна лінгвістика);
б) значення виразів обчислюються інтерпретатором (інтерпретаціонізм);
в) композиційність категорій синтаксису, семантики і прагматики (категоріальні граматики).
В даній роботі розглядається підхід, який поєднує в собі алгебраїчні аспекти аналізу природної мови та
логічні аспекти такого аналізу. Нижченаведений текст структурований таким чином.
Формулюється формальна постановка задачі добування знань з ПМТ. З цього формулювання випливає
структуралізація текстів при накладанні на текст певних обмежень. В якості прикладів такого типу обмежень
розглядається силогістика Арістотеля та тексти бібліографічного характеру. Зокрема для силогістики
Арістотеля будується її теоретико-множинна інтерпретація з розширеною системою правил виведення та
аналізом можливих ситуацій, які можуть виникати в процесі застосування цієї системи правил.
Для маніпуляції, аналізу та трансформації текстів вводиться поняття алгебраїчної системи спискових
структур, за допомогою якої виконується оброблення текстів на рівні фізичного представлення.
На завершення розглядається алгебро-логічний підхід до дослідження семантичних властивостей
природномовних текстів, наводиться проста логічна мова для дослідження властивостей природомовного
тексту.
2. Формальна постановка задачі добування знань з ПМТ
Перш ніж перейти до розгляду системи оброблення та добування знань, що містяться в ПМТ, визначимо
поняття добування знань з ПМТ. З цією метою скористаємося поняттями, які використовуються
в програмуванні з обмеженнями.
Нехай дана множина D, на якій визначена деяка скінченна сукупність n-арних відношень R на D, тобто
,n
iR D де iR R D , i = 1,…, k. Мовою обмежень L на D називається деяка непуста множина
L R D . Проблема виконуваності обмежень формулюється таким чином.
Формальні методи програмування
320
Для довільної множини D і довільної мови обмежень L на D проблемою виконуваності обмежень CSP(L)
є розв’язання такої комбінаторної проблеми:
Дано: трійка P = (V, D, C), де – V – скінченна множина змінних; – C – деяка множина обмежень
{ 1,..., qC C };
– кожне обмеження iC C – це пара ( , )i is R , де is - n-ка, яка називається областю обмеження, iR L
– in -арне обмеження на D, яке називається відношенням обмеження.
Знайти: функцію :V D таку, що ( , )s R C , де 1 2( , ,..., )ns v v v , n-ка
1 2( ( ), ( ),..., ( )nv v v R або переконатися в тому, що такої функції не існує.
Множина D в цьому випадку називається областю проблеми, а множина всіх розв’язків CSP вигляду
P=(V,D,C) позначається Sol(P).
У випадку аналізу ПМТ з метою добування знань множина D інтерпретується як вхідний текст T,
в якому задані («'закодовані'») відношення 1 2( , )i i iR R R , де 1iR – синтаксичні обмеження,
а 2iR – семантичні обмеження, V= 1 2( , ,..., )nv v v – лексико-граматичні розряди (іменники, дієслова,
прикметники тощо).
Проблема добування знань з ПМТ полягає в пошуку інтерпретації :V T і явній побудові
відношення 2iR при умові істинності відношення 1iR , тобто необхідно знайти відображення таке, що
(V) = 2 1 1 2( ( )) * ( )V V , де * означає суперпозицію відображень. Відображення 1 і 2 означають
відповідно синтаксичну та семантичну правильність речення чи тексту в цілому.
Це означення досить загальне і потребує уточнення. Розглянемо деякі конкретизації цього означення.
Уточнення можна виконувати в різних напрямках.
Одне із можливих уточнень є уточнення відображення 1 . Це відображення, в свою чергу, теж можна
розглядати як суперпозицію двох відображень, які реалізують морфологічний та синтаксичний аналіз речень
ПМТ і разом з відображенням 2 утворюють цілісну систему класичного типу, схема якої показана
на рис. 1 [7].
Морфологічні
структури речень
Морфологічний аналіз Синтаксичний аналіз Семантичний аналіз
База знань морфології
Морфологічний
словник
Вихідний ПМТ
База знань синтаксису
Комбінаторний
словник
Синтаксичні
структури речень
Семантичні структури
речень
База знань поверхневої
семантики
Семантичний
словник
Рис. 1. Схема лінгвістичного аналізу класичного типу
Для перевірки коректності виконаного аналізу передбачається зворотний синтез речення до його запису
в звичному орфографічному вигляді. Така перевірка може виконуватися в діалоговому режимі роботи системи з
користувачем. Можлива структура словників, які використовуються в наведеній системі, та певне її
обгрунтування описані в роботах [8–10].
З вищенаведеної формалізованої постановки проблеми аналізу ПМТ випливає, що однією з основних
задач є задача побудови предметної моделі А. Ця задача є найбільш складною в зв’язку з тим, що предметна
модель по суті є базою знань (побудова такої бази полягає в тому, щоб визначитися з об’єктами, які
добуваються з тексту, з формальною логічною мовою, правилами виведення, аксіоматикою тощо).
3. Логічне слідування. Загальнозначущі та спеціальні відношення
При формалізації знань певної предметної області будемо розрізняти два типи відношень між поняттями
цієї предметної області – загальнозначущі відношення та спеціальні. Перший тип відношень означає, що вони
притаманні більшості або кожній предметній області (мають категоріальний характер), а другі – тільки певній
конкретній предметній області. Наприклад, до першого типу відношень відносяться відношення «частина–
ціле», «тип–підтип», «рід–вид», «розділ – параграф» тощо. Класичними типами загальнозначущих відношень є
відношення часткового порядку та еквівалентності для подання існуючої ієрархії та синонімії в тексті: що
аналізується. А до відношень другого типу відносяться специфічні, притаманні лише даній предметній області
відношення. Наприклад, якщо предметна область відноситься до теорії автоматів, то специфічними
відношеннями між поняттями цієї предметної області є відношення типу «скінченні автомати над скінченними
Формальні методи програмування
321
словами – регулярні мови, акцептовані цими автоматами», «автомати Б’юхі – регулярні надмови, акцептовані
цими автоматами», «відношення еквівалентності на множині – розбиття цієї множини на класи
еквівалентності» і т. п. Цей поділ є природним і його необхідність продиктована тим, що одна справа
аналізувати текст на предмет існування в ньому необхідної нам інформації, а друга справа отримувати логічні
наслідки з фактів, що знаходяться в такому тексті. Опишемо методи аналізу, які опираються на перший тип
відношень, тобто на загальнозначущих відношеннях.
Арістотелева силогістика та її теоретико-множинна інтерпретація. Якщо детально проаналізувати
типи загальнозначущих відношень, то можна помітити, що вони асоціюються перш за все з відношенням
часткового порядку. А такого типу відношення складають дистрибутивну гратку, яка має корисні властивості і
ці властивості можна використати для генерації наслідків, тобто для пошуку (генерації) нових знань. Більше
того, неважко помітити, що силогізми Арістотеля інтерпретуються в алгебрі множин і відношень. А з алгебри
множин і відношень відомо, що відносно операцій об’єднання, перетину та доповнення ці алгебри є булевими
кільцями, носії яких є частково упорядкованими множинами відносно теоретико-множинного включення.
Закони цієї алгебри і властивості частково упорядкованих множин можна застосувати як правила виведення в
такій формальній системі. Більш детально ці можливості розглянуто в [7]. Зокрема, це є закони алгебри множин
і відношень (комутативності, асоціативності, дистрибутивності. ідемпотентності, поглинання і закони де
Моргана), три основні властивості відношення включення (транзитивність, контрапозиція та асиметричність) та
закон подвійного доповнення. При цьому останні дві можливості відіграють роль правил виведення. Нижче
проілюструємо їх на прикладах.
Приклад 1. Нехай задані такі факти (взяті з книги Л. Керола «Історія з вузликами»):
«Всі малі діти нерозумні»;
«Всі, хто приборкує змій, заслуговують на повагу»;
«Всі нерозумні люди не заслуговують на повагу».
Вияснимо, які наслідки випливають з цих фактів. Зазначимо, що такого типу факти в логіці часом
називаються полісилогізмами або сорітами . А силогізмом називається система, яка має лише дві посилки.
Визначимо основні терміни, з яких складається система фактів, введемо для них позначення і виберемо
універсум U. В даному прикладі основними термінами є такі: «малі діти» (С), «розумні люди» (Р), «ті, хто
приборкує змій» (Т), «ті, хто заслуговує на повагу» (П). Ясно, що ці терміни представляють якісь множини в
універсумі «люди». Їх запереченнями будуть відповідно такі терміни: «не малі діти» (С), «нерозумні люди»
(Р), «ті, хто не приборкує змій» (Т), «ті, хто не заслуговує на повагу» (П). Тепер наші факти
приймають вигляд:
С Р, Т П, Р П.
Таким чином, визначилася гратка (як універсальна множина), яка складається з елементів ( , U, Р, Т, П,
С,Р,Т, П), де U – універсум. Отже, першими наслідками даних фактів є наступні наслідки на підставі
правила контрапозиції (правило контрапозиції в даній інтерпретації має вигляд «з А В випливає B A,
де знак означає доповнення множини):
(С 1 ): Р С, (С 2 ): П Т, (С 3 ): П Р.
Якщо перевести отримані наслідки на природну мову, то вони відповідно означатимуть такі факти: «всі
розумні люди не є малими дітьми», «ті, хто не заслуговує на повагу, не приборкують змій», «заслуговує на
повагу той, хто розумна людина».
Користуючись правилом транзитивності, отримуємо такі наслідки:
(С 4 ): С П, (С 5 ): Т Р, (С 6 ): Р Т, (С 7 ): П С.
З цих наслідків за тим же правилом транзитивності отримуємо ще два наслідки:
(С 8 ): С Т, (С 9 ): Т С.
Якщо перевести на природну мову останні наслідки, то вони звучатимуть так:«всі малі діти не є
приборкувачами змій», «всі, хто приборкує змій, не є малими дітьми». (цей знак означає кінець приклада).
Таким чином, розв’язання поставленої задачі в наведеному прикладі отримано, але методи генерації
наслідків є досить складними процедурами і хотілося б мати які-небудь засоби спрощення процесу пошуку
висновків. Якщо в вищенаведених позначеннях для формул замість знака включення використовувати знак
імплікації , то одержуємо мову, подібну до мови математичної логіки (на жаль в цій логіці не працює
правило modus ponens), а в такому випадку одним із засобів покращення ситуації в процесі генерації висновків
є використання концептуальних графів і семантичних мереж. При такому способі представлення фактів, пошук
і генерація наслідків зводиться до проблеми досяжності вершин в графі чи семантичній мережі. Розглянемо
детальніше процес пошуку наслідків.
Введемо деякі означення і нотацію, якою користуються в математичній логіці. Будемо вважати, що
кожному терміну відповідає деяка множина або її доповнення, якщо термін вживається разом із запереченням.
Означення 1. Літералом називається термін або його заперечення, а множину всіх літералів деякої
множини термінів називатимемо базовими літералами.
Формальні методи програмування
322
Висловлюванням називається відношення включення, що виражене за допомогою базових літералів, в
лівій частині якого находиться єдиний базовий літерал, а в правій частині – перетин множин, що
представлені базовими літералами.
Множину висловлювань, яка зображує деяку множину силогізмів, називатимемо базовою множиною
формул.
Означення 2. Силогістичною структурою називається множина літералів, відношення між якими
визначаються множиною висловлювань, які називатимемо посилками.
Отже, формалізація фактів, наведених в прикладі 1, виглядає так: сукупність літералів L = {С, Т, Р, П,
С, Р, Т, П} з посилками С Р, Т П, Р П. Крім того, з цього прикладу випливає, що
проблема пошуку наслідків зводиться до проблеми побудови контрапозиційно-транзитивно-асиметричного
(КТА) замикання деякої базової множини формул. При транзитивному замиканні можуть виникнути такі
ситуації:
К1) отримана формула вигляду A A або A A ;
К2) в процесі побудови транзитивного замикання одержано принаймні один цикл.
Вияснимо, що означають ці ситуації в нашому випадку. Перша формула у випадку К1) відповідає
ситуації 'A A . З властивості перетину множини та її доповнення маємо 'A A , а тому таке включення
вірне лише тоді, коли А є пустою множиною. Друга формула у випадку К1) означає, що доповнення А’
множини А повинно бути універсальною множиною. З точки зору алгебри множин такі ситуації не можна
назвати суперечними, але в нашому випадку ця ситуація означає, що деякий об’єкт мусить існувати і в той же
час не існувати. Така ситуація цікава принаймні з двох причин. Перша причина полягає в тому, що ситуація є
катастрофічною, а друга причина дає можливість виключити з розгляду певні терміни, які призводять до появи
суперечності. Проаналізуємо ці випадки детальніше. Першою причиною виникнення суперечності типу
A A є поява в множині наслідків формул вигляду A B і A B . Другою причиною появи
суперечності A A є поява двох формул A B і A B .
Приклад 1. (продовження). Якщо до фактів з прикладу 1 додати формулу P T («всі розумні люди
не приборкують змій»). Такого типу висловлювання не здається дивним з точки зору здорового глузду, але
воно приводить до появи катастрофічних наслідків. Якщо побудувати КТА-замикання отриманої множини
фактів, то в цьому замиканні з’явиться формула T T . Якщо приймається, що задана множина фактів
правильна, то приходимо до висновку, що людей, котрі приборкують змій, не існує.
Зауважимо, що наявність суперечності типу A A не завжди веде до катастрофічних наслідків.
Часом поява такої суперечності дає можливість розпізнати факти, які приводять до суперечності і вилучити
суперечності. Продемонструємо це на прикладі.
Приклад 2. Візьмемо такі факти (з книги Д. Свіфта «Подорожі Леймлюеля Гулівера»):
А: «всі члени парламенту мають здоровий глузд»;
В: «всі, хто носить титул пера, не розбиває яйце з тупого кінця»;
С: «всі члени палати лордів мають титул пера»;
D: «члени палати лордів є членами парламенту».
Наслідками з цих фактів, зокрема, будуть такі висновки:
«всі, хто не в здоровому глузді, не є членами палати лордів» і «всі, хто розбиває яйце з тупого кінця, не є
членами парламенту».
Якщо хто-небудь (а це на думку Д. Свіфта повинні бути лікар і аптекар) вирішив перевірити розумові
здібності членів парламенту і отримав результат: «всі члени палати лордів не мають здорового глузду». Коли
отриманий факт додати до фактів А, В, С, D, то отримуємо суперечність типу: «всі, хто не в здоровому глузді,
мають здоровий глузд». Така суперечність, як про це було сказано вище, може бути у випадку пустоти
множини А. Для нашого прикладу це означає, що в парламенті немає членів, які не в здоровому глузді. Цей
висновок дає можливість вилучити з розгляду термін «ті, хто не мають здорового глузду».
Ситуація у випадку К2) означає (на підставі правила антисиметричності ПА), що всі об’єкти, які
знаходяться в ланцюжку виведення, еквівалентні між собою. Звідси випливає, що в ієрархії об’єктів, які
складають дану інформаційну систему, діють два загальнозначущі фундаментальні відношення – відношення
часткового порядку і відношення еквівалентності. Відношення еквівалентності дає змогу, в разі необхідності,
факторизувати об’єкти в такій інформаційній системі і цим досягати більшої компактності в представленні її
об’єктів.
З розглянутих прикладів ситуацій для К1) і К2) випливає ще один надзвичайно важливий момент.
Суперечності типу К1), К2) носять формальний характер, оскільки вони появляються тільки в результаті
логічного аналізу заданої множини фактів, але існує іще один тип суперечності, який суттєво відрізняється від
суперечностей К1) і К2). Припустимо, що в результаті побудови КТА-замикання з добре обґрунтованих і
перевірених фактів, що не є суперечними, наприклад, відомих і обґрунтованих теорій, одержані суперечні
наслідки, тобто наслідки, які суперечать фактам початкових теорій. Це говорить про те, що між початковими
теоріями існують суперечності, а це і є ознакою появи нового знання або, принаймні стимулом для пошуку
розв’язання отриманої суперечності. Все вищесказане дає право ввести таке означення.
Формальні методи програмування
323
Означення 3. Інформаційна система називається коректною, якщо в ній не виникають суперечності типу
К1) чи К2).
Відомо, що в процесі побудови КТА-замикання, виходячи з різних початкових множин фактів, можна
отримати одну і ту саму множину наслідків. Це дає можливість ввести таке відношення еквівалентності на
множинах фактів: дві множини фактів Ф і Ф’ називаються еквівалентними, якщо КТА(Ф) = КТА(Ф’). На
підставі цього відношення можна спрощувати (шляхом елімінації) структуру інформаційної системи, а також
початкові множини фактів.
Розширення множини правил виведення силогістичної структури. Вищенаведені правила виведення
в силогістичній структурі можна розширити шляхом використання інших властивостей відношення включення
і законів алгебри множин і відношень. Розглянемо деякі з них.
(ЗПД) Закон подвійного доповнення (подвійного заперечення): (А) = А;
(ЗО) Закон об’єднання для включення (закон диз’юнкції): якщо А С і В Р, то А В С Р,
зокрема якщо А С і ВС, то А В С;
(ЗП) Закон перетину для включення (закон кон’юнкції): якщо А С і В Р, то А В С Р і А В
С, А В Р;
А коли до результатів застосування цих правил застосувати правило контрапозиції, то приходимо до
необхідності використання законів де Моргана:
ЗДМ1) Якщо А В С Р , то (С Р)= С Р (A В) А В;
ЗДМ2) Якщо А В С Р , то (С Р)= С Р (А В) A B.
Ці правила дають можливість розширити вищенаведене поняття висловлювання та силогістичної
структури шляхом використання правил ЗПД, ЗО, ЗП, ЗМД1 і ЗМД2. Застосовуючи ці правила до базової
множини формул з прикладу 1, можна отримати висловлювання типу Т Р = і СТ = , які говорять про
те, що «серед приборкувачів змій немає нерозумних людей», а «серед малих дітей немає приборкувачів змій».
Розширена таким чином множина правил виведення дає змогу конструювати дескриптори, які
включають кон’юнкції та диз’юнкції (подібна можливість описується й в інших системах [8]). Слід зауважити,
що при застосуванні правил ЗО і ЗП, як і ЗМД1 і ЗМД2 необхідно слідкувати за певними обставинами
збереження сенсу. Це пов’язано з тим, що при застосуванні правила ЗП необхідна узгодженість, яка полягає в
тому щоб з’єднувалися родове і конкретне коректним чином в лексичному і семантичному значенні. Звідси
випливає, що необхідно вказувати відмінності в різних моделях, в лексичних функціях, в полях стійких
словосполучень і т. п. Як правило, в реальних комп’ютерних системах приймаються обмеження типу: слово
представляється не більше ніж k словоформами, де k – стала величина для даної комп’ютерної системи [9, 10].
Чи є розширена таким чином силогістична структура булевою алгеброю і чи є додана множина правил
такою, яка насправді розширює потужність силогістичної структури, потребує додаткового дослідження.
Що стосується спеціальних відношень, то на закінчення даного підрозділу зазначимо, що оскільки
спеціальні відношення залежать від конкретної предметної області, то сформулювати їх в загальному вигляді
неможливо. Формулювання цієї множини відношень цілком лежить на відповідальності експерта в даній
предметній області, який ці відношення декларує і вносить в систему.
Перейдемо тепер до розгляду питання про засоби маніпуляції з текстовою інформацією. Представимо
формальну алгебро-логічну мову, орієнтовану на обробку такого типу інформації.
4. Алгебраїчна система спискових структур
Побудова та опис такої мови виконується в два етапи. На першому описується алгебра спискових
структур, а на другому – доповнення цієї алгебри до алгебраїчної системи спискових структур.
Алгебра спискових структур. Нехай F(X) – вільна напівгрупа з одиницею над деяким скінченним
алфавітом X = {х1, х2,..., хn}. Роль одиниці відіграє пусте слово e. Нагадаємо, що словом в алфавіті X називається
довільна скінченна послідовність символів цього алфавіту. Довільне слово р = у1у2 … уm із F(X) будемо
називати списком елементів у1у2 … ут, а самі елементи уі X, і = 1, 2,..., т, – складовими цього списку. При
цьому елемент у1 називається початком, а елемент ут – кінцем списку. Якщо р F(X), то число складових
списку р називається його довжиною і позначається через l(р). Якщо p, q – два списки, то список (слово) q
називається початком (кінцем) списку (слова) р, коли існує таке слово р', що р = qp' (р = p'q). Два списки р =
s1s2...sk і q = t1t2...tl рівні між собою, якщо l = k і si = ti, і = 1, 2,..., k.
З теорії відомо, що F(X) є алгеброю з однією бінарною операцією конкатенації (сопc) і однією нульарною
операцією (пусте слово e). Введемо в розгляд ще декілька функцій і операцій над списками, тобто над
елементами множини F(X) [7].
Нехай N – множина натуральних чисел і р = у1у2 … ут – довільне слово із F(X), тоді
head(p) = y1(head: F(X) F(X)). (1)
Іншими словами, функція head(p) дає перший символ слова р. Безпосередньо з визначення цієї
функції випливають такі її властивості:
head(e) = e, head(y) = y, якщо y = X, head(head(p)) = head(p),
tail(p) = y2…ym (tail: F(X) F(X)). (2)
Формальні методи програмування
324
Очевидно, що tail (e) = e, tail (y) = e, якщо y = X.
Зміст наведених нижче функцій випливає з їх визначення.
add(p, i, x) = y1…yi xyi+1…ym, 0 i l(p). (3)
sub(p, i) = y1…yi–1yi+1…ym, 1 i l(p). (4)
dist(p, i) = (р1, р2), (5)
дe р1 = у1…уі, р2 = уі+1 …ут, 0 і l(р)
hl(p, i) = y1…yi, 0 i l(p). (6)
tr(p, i) = yi+1 … ym, 0 i l(p). (7)
push(p, x) = px = add(p, l(p), x). (8)
pop(p) = y1…ym−1 = sub(p, l(p)). (9)
Виявляється, що базовими операціями, тобто такими, через які виражаються всі останні із
перелічених функцій, є операції e, сопc, head, tail, рекурсії та суперпозиції. Іншими словами має місце таке
просте твердження.
Теорема 2. Усі функції (3)–(9) представляються у вигляді термів за допомогою операцій e, сопc, head, tail
і операторів рекурсії та суперпозиції.
Доведення. Розглянемо послідовно випадки:
add(p, i, x) = hl(p, i) xtr (p, i); sub(p, i) = hl(p, i – 1) tr (p, i); dist(p, i) = (hl(p, i), tr(p, i));
, якщо 0,
, , якщо 1,
, 1 , якщо 1.
e i
hl p i head p i
head p hl tail p i i
;
, якщо 0,
, , якщо 1,
, 1 , якщо 1.
p i
tr p i tail p i
tr tail p i i
З представлення функцій hl і tr випливає представлення функцій add, sub і dist, a, отже, і представлення
функцій push і pop.
Слід зазначити, що функції head і tail (push i pop) дійсно є операціями, у той час як решта функцій (3)–(7)
операціями не являються. Це дозволяє ввести таке
Означення 4. Універсальна алгебра G = (F(X), = {conc, head, tail, e}) розширена операторами рекурсії та
суперпозиції називається алгеброю спискових структур (АСС).
У цій алгебрі легко встановити справедливість таких тотожностей.
(a) sub(p,1) = tail(p) = tr(p,1); (б) sub(add(p,i,x),i+1) = р; (в) hl(p,l(p)) = р; (г) tr(p,l(p)) = e; (д) pop(push(p,x)) = p.
Має місце і ряд інших співвідношень у цій алгебрі.
Інколи разом з множинами функцій (3)–(9) розглядаються й інші корисні функції, такі як:
substr(p, i, j) = xi…xi+j–1, (10)
тобто це підслово слова р, яке починається з i-го символу і має довжину j;
conv(p) = xmxm–1…х2х1, (11)
тобто це перестановка символів, які складають список р у зворотному порядку. Очевидно, що conv(e) = e i
conv(y) = y, якщо y X, а представлення функцій substr і conv у вигляді термів алгебри спискових структур
має вигляд substr(p,i,j) = hl(tr(p,i),j) і, conv(p) = conv(tail(p))head(p).
Тепер, користуючись операціями і функціями (1)–(11), можна вводити й інші функції. Розглянемо деякі
з таких функцій.
Нехай задано деякий алфавіт X = {х1, х2, …, хn}. Множина F(X), як було зазначено вище, є повністю
впорядкованою відносно лексикографічного порядку, мінімальним елементом якої є пусте слово e.
Користуючись цим порядком, визначимо за індукцією такі функції:
а) l(p) : F(X) N – функція довжини слова, означення якої було дане вище. Індуктивне означення цієї
функції є таким:
0, коли
;
1 , інакше
p e
l p
l tail p
б) subword(p, q) : F(X) F(X) {0, 1}. Ця функція дорівнює 1, якщо слово q є підсловом слова р,
і дорівнює 0 – у протилежному випадку. Індуктивне означення цієї функції таке: для довільних слів p, q = F(X)
0, якщо ( ) ( ),
, 1, якщо , ,
, , інакше.
l p l q
subword p q hl p l q q
subword tail p q
Безпосередньо з означення цієї функції випливають такі її прості властивості: оскільки пусте слово є
підсловом довільного слова і довільне непусте слово є підсловом самого себе, то
, 1, , 1;subword p e subword p p
Формальні методи програмування
325
в) substit(p, q, r) : F(X) F(X) F(X) F(X). Результатом цієї операції є підстановка слова r замість
першого входження слова q в слово р. Визначення цієї функції таке: для довільних слів р, q, r = F(X)
, якщо ,
, , , , якщо ( , ( )) ,
, , , інакше.
e p e
substit p q r r tr p l q hl p l q q
head p substit tail p q r
Безпосередньо з означення випливають такі очевидні властивості:
substit(p, e, r) = rp, substit(p, q, q) = p.
Приклад 3. Знайти
а) subword(abbcda, cd); б) subword(abbc, ax); в) substit(abbcda, cd, a); г) substit(abcd, xa, da).
Розв’язок:
a) subword(abbcda,cd) subword(bbcda,cd) subword(bcda,cd) subword(cda,cd) 1.
б) subword(abbc,ax) subword(bbc,ax) subword(bc,ax) subword(c,ax) subword(e,ax) 0.
в) substit(abbcda,cd,a) asubstit(bbcda,cd,a) absubstit(bcda,cd,a) abbsubstit(cda,cd,a) abbasubstit(a,cd,a) =
=abbaаsubstit(е,cd,a) = abbaа.
г) substit(abcd,xa,da) asubstit(bcd,xa,da) absubstit(cd,xa,da) abcsubstit(d,xa,da) abcdsubstit(e,xa,da) abсd.
Алгебраїчна система спискових структур. Розширимо АСС предикатом рівності та умовним
оператором. Розширену таким чином АСС будемо називати алгебраїчною системою спискових структур
(АССС). Для цієї алгебраїчної системи має місце
Теорема 3. АССС є алгоритмічно повною системою, тобто системою, в якій можна обчислити
довільну частково рекурсивну функцію.
Доведення. Для доведення необхідно показати, що довільний нормальний алгорифм Маркова можна
представити і обчислити його значення в цій системі. Нехай Ф – деякий нормальний алгорифм Маркова,
заданий системою формул підстановки R в алфавіті X:
1 1
2 2
[.]
[.]
... ... ...
[.]m m
p q
p q
p q
1 1
2 2
... ... ...
m m
p q
p q
p q
де . ,i iq q якщо формула підстановки заключна і ,i iq q якщо формула підстановки проста. Далі, нехай
рF(X) і G – АССС над алфавітом X' X {.}. Тоді, використовуючи операції і предикати АССС,
а також функції subword, substit і функцію довжини, можемо записати для довільного рF(X):
Ф(р) якщо subword(p, p1) 1 то
якщо head( 1q ) «.» то substit(p, p1, tail( 1q ))
інакше Ф(substit(p, p1, 1q )
інакше якщо subword(p, p2) 1 то
якщо head( 2q ) «.» то substit(p, p2, tail( 2q ))
інакше Ф(substit(p, p2, 2q )
інакше ……..
інакше якщо subword(p, pm) 1 то
якщо head( mq ) «.» то substit(p, pm, tail( mq ))
інакше Ф(substit(p, pm, mq )
інакше р.
Покажемо індукцією за числом п застосованих підстановок до слова р, що функція f (p), яка
отримана за допомогою системи R, і функція f'(p), яка отримана за допомогою системи Ф(р), збігаються.
При п 0 маємо f (p) р, оскільки жодна із підстановок системи R не застосовна до слова р. Із системи
Ф(р) випливає, що f'(p) р, оскільки всі умови вигляду subword(p, pi) 0. Отже, у цьому випадку f (p) f' (p).
Припустимо, що рівність виконується для всіх т < п і нехай n-ою формулою підстановки є формула рі
iq . Можливі такі випадки: формула рі iq – заключна і формула рі iq не заключна.
Нехай у першому випадку т п – 1 і після виконання т-ї підстановки одержано слово р'. За
припущенням індукції f(p') f'(p'). З того, що рі iq застосовна до р' випливає, що жодна з підстановок, які їй
передують у системі R, не застосовні до р', або що те саме, що всі умови вигляду subword(p', pj) 0, де j < і, а
умова subword(p', pi) 1 і head( iq ) «.». що f(p') substit(p', pi, tail( iq )) substit(p', pi, qi) f ' (p').
Другий випадок аналогічний першому, з тією лише різницею, що в першому випадку обчислення
закінчуються, а в другому – продовжуються.
Формальні методи програмування
326
5. Алгебро-логічний підхід до аналізу природномовного тексту
Формалізовану мову для аналізу природномовного тексту будемо нарощувати поступово, розширюючи
синтаксис і семантику цієї мови. Почнемо з означення синтаксису та семантики мови висловлювань, які
відрізняються від традиційних синтаксису і семантики числення висловлювань [5].
Синтаксис і семантика мови висловлювань. Розглянемо мову висловлювань, в якій висловлювання
подаються у вигляді константних предикатів. Нехай L
0
означає цю мову. Кожне висловлювання мови L
0
представляється предикатом, аргументи якого приймають значення в множині предметних констант. Це
означає, що L
0
не включає ні змінних, ні функціональних констант, відмінних від предметних констант. Крім
того, висловлювання вже не є атомами мови L
0
на відміну від класичної мови висловлювань, оскільки воно
будується за допомогою предикатних та предметних констант, які стають новими атомами мови L
0
. Це
нововведення дає змогу ввести семантичне поняття виконуваності для формул як узагальнення поняття
істини. Для пояснення сказаного розглянемо приклад.
Приклад 4. Нехай множину предметних констант складають співробітники деякого відділу та статті,
авторами яких вони є. Висловлюваннями виступають відношення між авторами і написаними ними статтями.
Нехай ic , i=1,2,…,n, означають предметні константи, s( ic ) – семантичне значення предметної константи.
Для нашого прикладу розглянемо такі предметні константи:
КОНСТАНТИ СЕМАНТИЧНЕ ЗНАЧЕННЯ
автор1 s(автор1) = Палагін
автор2 s(автор2) = Яковлєв
автор3 s(автор3) = Кривий
автор4 s(автор4) = Петренко
автор5 s(автор5) = Опанасенко
автор6 s(автор6) = Кургаєв
Предметні константи складають алфавіт об’єктної мови, а семантичні значення – інтерпретацію
предметних констант або їх сутність. Мова L
0
включає предикатні константи (відношення) jP , j = 1,2,…,m,
семантичні значення яких є множинами. Семантичне значення предикатної константи jP позначатимемо через
s( jP ). Для нашого прикладу визначимо такі предикати:
ПРЕДИКАТНА КОНСТАНТА СЕМАНТИЧНЕ ЗНАЧЕННЯ
авP s( авP ) = множина авторів
стP s( стP ) = множина статей
асP s( асP ) = множина пар (х,у), де х – автор,
у – стаття, автором якої є х
арсP s( арсP ) = множина трійок (а,р,с), де
а – автор, р – рецензент, с – стаття
чсP s( чсP ) = множина пар (х,у), де х – читач, у – стаття.
Синтаксис і семантика мови L
0
. Нехай Х – алфавіт, символами якого є предметні та предикатні
константи, тобто Х = { 1 2 1, ,..., , ,...,n mc c c P P }.
Синтаксис мови L
0
визначається так:
довільний предикат є формулою мови L
0
;
якщо А, В – формули мови L
0
, то А, А В, А В, А В, А В теж формули мови L
0
;
ніякі інші вирази не є формулами мови L
0
.
Семантичні значення предикатних і предметних констант дають можливість обчислити семантичні
значення висловлювань, а отже, на їх підставі і значення формул.
Означення семантики мови L
0
, як випливає з означення синтаксису і того, що говорилося вище про
висловлювання, повинно включати традиційні для мови висловлювань кроки і специфічні кроки для
предикатних і предметних констант.
Семантика мови L
0
визначається так:
довільна формула з L
0
інтерпретується як істинна або хибна;
якщо А L
0
, то А істинна тоді і тільки тоді, коли А хибна;
якщо А, В L
0
, то А В істинна тоді і тільки тоді, коли А або В істинна;
А В істинна тоді і тільки тоді, коли А і В істинні;
А В істинна тоді і тільки тоді, коли А істинна, а В хибна;
А В істинна тоді і тільки тоді, коли А і В або обидві хибні, або обидві істинні;
якщо jP – предикатна константа арності k і 1 2, ,..., kc c c – предметні константи, то формула jP ( 1 2, ,..., kc c c )
істинна тоді і тільки тоді, коли ( 1 2( ), ( ),..., ( )) ( )k js c s c s c s P .
Формальні методи програмування
327
6. Означення моделі та істини
Коли мова заходить про семантичне значення речень природної мови, то це значення може залишатися
сталим, а може змінюватися в залежності від інтерпретації в тій чи іншій моделі. В зв’язку з такою можливістю
розрізнятимемо абсолютну і відносну істинність простого речення. В теорії моделей формули логічної мови
інтерпретуються в універсумі суджень, який будемо позначати через Ũ.
Під моделлю для мови будемо розуміти деякий стан світу, яка включає в себе непусту множину Ũ
(універсум) і функції інтерпретації V: X Ũ B(Ũ) B(Ũ Ũ) …, яка ставить у відповідність кожній
предметній чи предикатній константі мови L
0
відповідний об’єкт з Ũ B(Ũ) B(Ũ Ũ) …, де B(А)
означає булеан множини А.
Приклад 5. Для універсума з введених вище констант, предметних констант та їх семантичних значень
маємо:
Ũ = {Палагін, Яковлєв, Кривий, Петренко, Опанасенко, Кургаєв, сПЯ, сПО, сКр, сПП, сКуО, сПКП};
Функція інтерпретації визначається таким чином:
V(автор1) = s(автор1) = Палагін,
V (автор2) = s(автор2) = Яковлєв,
V (автор3) = s(автор3) = Кривий,
V (автор4) = s(автор4) = Петренко,
V (автор5) = s(автор5) = Опанасенко,
V (автор6) = s(автор6) = Кургаєв.
V( авP ) = s( авP ) = {Палагін, Яковлєв, Кривий, Петренко, Опанасенко, Кургаєв},
V ( стP ) = s( стP ) = {сПЯ, сПО, сКр, сПП, сКуО, сПКП},
V(P ас ) = s(P ас ) = {(Палагін, сПЯ), (Яковлєв, сПЯ), (Кривий, сКр), (Палагін, сПП),
(Петренко,сПП), (Палагін, сПКП), (Кривий, сПКП), (Петренко, сПКП),
(Палагін, сПО), (Опанасенко, сПО), (Кургаєв, сКуО), (Опанасенко, сКуО)};
V(P арс ) = s(P арс ) = {(Кривий, Палагін, сКр), (Кургаєв, Яковлєв, сПЯ), (Яковлєв, Опанасенко, сПЯ)};
V(P чс ) = s(P чс ) = (Кривий, сПО), (Петренко, сПЯ), (Кургаєв, сКр), (Петренко, сКуО), ( Кривий, сПЯ)}.
Формальне означення моделі для мови L
0
має вигляд:
Означення 3. Моделлю мови L 0 називається пара М = (Ũ, V), де Ũ – деякий універсум суджень, а
V: X Ũ B(Ũ) B(Ũ Ũ) …, причому
а) V(c i ) Ũ для всіх c i X;
б) V(P i ) Ũ
n
для всіх n-арних предикатних констант P i .
Тепер семантичне значення предметної і предикатної константи визначається відносно моделі М. Якщо
c i , P j Х, то ( ), ( )M i M js c s P буде означати значення констант c i і P j в моделі М. Отже, поняття моделі дає
можливість замінити поняття істини на поняття істини в моделі. Оскільки функція інтерпретації V може
приписувати формулам мови L 0 різні значення істинності відносно вибраної моделі М = (Ũ, V), то формула
може виявитися істинною в одній моделі і хибною в іншій.
Ця обставина дає можливість на формальному рівні розв’язати проблеми омонімії та синонімії шляхом
використання поняття моделі й відношення еквівалентності на розширенні одноелементної множини значень
предметних констант. Дійсно, для розв’язання проблеми омонімії необхідно перевірити істинність даного
висловлювання в різних моделях і вирішити яке з них має сенс.
Означення 4. Формула мови L
0
називається загальнозначущою, якщо вона істинна в довільній моделі
мови L
0
, і називається хибною, якщо вона хибна у всіх моделях цієї мови.
Дві формули мови L
0
називаються логічно еквівалентними, якщо вони одночасно істинні в одних і тих
же моделях. Формула А називається логічним наслідком множини формул Г тоді і тільки тоді, коли формула А
істинна в кожній моделі, в якій істинні всі формули з множини формул Г.
Аналіз природномовних текстів з метою добування знань (необхідної інформації) зводиться до
виявлення таких властивостей як істинність в моделі та логічного слідування.
7. Збагачення мови L
0
– мова L1
Розглянемо розширення мови L
0
шляхом додавання до L
0
предметних змінних і кванторів. Отриману
таким чином мову позначатимемо L
1
.
Алфавіт мови L
1
складається з множини Х = { 1 1 1,..., , ,..., , ,...,n k mc c x x P P }, де предметні константи і
змінні називаються термами.
Символи алфавіту Х називаються нелогічними константами або атомами.
Означення 5. Формальне означення синтаксису мови L
1
має вигляд:
1) довільний атом є формулою мови L
1
;
Формальні методи програмування
328
2) якщо А і В – формули мови L
1
і х – предметна змінна, то А, А В, А В, А В, А В, xA і
xA теж є формулами мови L
1
;
3) інших формул в мові L
1
, крім означених в пунктах 1), 2), немає.
Семантика мови L
1
. Означення семантики мови L
1
виконується за допомогою функції інтерпретації.
Інтерпретація мови L1 визначається так само як і у випадку мови L
0
. А саме, задається універсум Ũ, який
складається з об’єктів (індивідів), і функція інтерпретації V для констант. В зв’язку з появою предметних
змінних появляється функція g, яка присвоює значення змінним в множині Ũ, тобто g: { 1,..., nx x } Ũ.
Приклад 6. Якщо мова L
0
така як в вищенаведених прикладах, то синтаксис мови L
1
породжується
формулами вигляду P ас ( 1 2,x x ), де 1 2,x x – предметні змінні (на відміну від мови L
0
, яка породжувалась тільки
фразами вигляду P ас ( 1 2,c c )), семантичне значення якої можна обчислити як значення функції семантичних
значень констант P ас , 1 2,c c . А тому необхідно мати процедуру, яка присвоює значення істинності формулам
типу P ас ( 1 2,x x ). Ця формула повинна бути істинна тоді і тільки тоді, коли стаття 2x написана автором 1x .
Отже, виникає необхідність присвоювання семантичних значень істинності предикатам, які мають вільні
входження змінних, а отже, самим вільним змінним.
Таким чином, необхідно до правил семантики, які були описані вище, додати функцію, що присвоює
кожній змінній x, мови L 1 , деяке значення з універсума Ũ. Ось для цієї мети і служить функція
g: { 1,..., nx x } Ũ.
Визначимо спочатку поняття формули, істинної в моделі відносно функції присвоювання g,
використовуючи рекурсію. Слід зазначити, що функція g не приймає участі в інтерпретації предметних і
предикатних констант даної мови, а тому g не є частиною моделі М.
Нехай g – яка-небудь функція присвоювання значень предметним змінним мови L 1 . Назвемо x-вибором
функцію g’, яка збігається з функцією g на всіх значеннях змінних x, крім змінної x. Символом ,M gs (t)
позначимо семантичне значення виразу t в моделі М з функцією присвоювання g.
Означення семантики мови L
1
. Означення семантики мови L
1
виконується індуктивно в кілька кроків,
Означення 5. а) інтерпретація термів:
- якщо x – предметна змінна із L
1
, то ,M gs (x) = g(x);
- якщо с – предметна чи предикатна константа із L
1
, то ,M gs (с) = V(c), де V – функція інтерпретації
моделі М = (Ũ, V);
б) інтерпретація термів:
- якщо 1 2,t t - терми із L
1
, то ,M gs ( 1 2t t ) істинна тоді і тільки тоді, коли ,M gs ( 1t ) = ,M gs ( 2t );
- якщо 1,..., nt t - терми і Р - n-арна предикатна константа із L 1 , то ,M gs (P( 1,..., nt t )) істинна тоді і
тільки тоді, коли ( ,M gs ( 1t ),…, ,M gs ( nt )) ,M gs (P);
в) інтерпретація формул:
- якщо А і В – формули із L 1 , то А, А В, А В, А В, А В стандартним способом так, як це
визначалося вище в означенні 4.
- якщо А – формула і х – змінна мови L
1
, то ,M gs ( xA ) істинна тоді і тільки тоді, коли ,M gs ( A )
істинна для всіх х-виборів g’ функції g;
- якщо А – формула і х – змінна мови L
1
, то ,M gs ( xA ) істинна тоді і тільки тоді, коли ,M gs ( A )
істинна хоча б для одного х-вибору g’ функції g.
Користуючись цим означенням семантики для мови L
1
, можемо формально означити поняття формули,
істинної в моделі й загальнозначущої формули.
Означення 6. Формула А називається істинною в моделі М, якщо ,M gs (А) істинна для довільної функції
присвоювання g.
Формула А називається загальнозначущою, якщо ,M gs (А) істинна в довільній моделі М і для довільної
функції присвоювання g.
Зазначимо, що поняття виконуваності формул відносно деякої функції присвоювання g, в точності
збігається з поняттям істинності формули відносно деякої функції присвоювання g. Ці поняття зустрічаються і
у Монтегю і теж збігаються.
Формальні методи програмування
329
8. Підхід до реалізації
Проблема представлення, пошуку та обробки природномовних текстів є однією з найбільш інтригуючих
та складних проблем. Складність цієї проблеми полягає в тому, що вона погано формалізується і в наслідок
цього погано піддається автоматизації. Використання формальних методів перевірки несуперечності чи
виконуваності множини формул в системах гільбертовського типу (тобто, систем в яких доведення будуються
формальним способом з аксіом шляхом застосування правил виведення) не мають якого-небудь задовільного
розв’язання. Справа в тому, що системи гільбертовського типу не є структурованими, а це означає, що для
збору необхідної інформації по одному єдиному об’єкту необхідно переглянути всю множину логічних
формул, яка знаходиться в системі (як правило такою системою є база даних). На жаль, цим недоліком
страждають всі формальні логічні системи гільбертовського типу. З метою ліквідації цього недоліку було
запропоновано графічне представлення формул і їх аргументів, яке служить глобалізації й структурованості
інформації. Основою графічного представлення є концептуальні графи (КГ) та їх родові структури –
семантичні мережі (СМ). Таке представлення дає можливість візуалізувати модель природномовної картини
світу, до якої відноситься проблема, що розглядається. Крім того, ця візуалізація дозволяє отримувати, в разі
необхідності, весь процес доведення.
Подання семантичної моделі ПМО в залежності від типів задач, що потребують розв’язання (і
відповідних КГ) може мати різний ступінь деталізації. При цьому розрізняють дві задачі формально-логічного
подання ПМО в процесі комп’ютерного аналізу та інтерпретації. Перша з них відноситься до внутрішньомовної
обробки, при якій результат семантичного аналізу представляється найбільш повними логічними виразами у
відповідному логічному базисі. Їх формування виконується паралельно з процедурою зняття лексичної
неоднозначності, яка потребує деталізації КГ і експліцитного представлення відповідних контекстних
залежностей. Друга задача відноситься до позамовної обробки, до етапу побудови бази знань предметної
області, а точніше – до побудови бази правил логічного виведення. Така база знань повинна мати короткі
правила, які дають можливість реалізувати ефективне виведення (з точки зору швидкодії та пам’яті).
Зі сказаного вище випливає, що для першої задачі слід використовувати деталізовані КГ, а для другої –
максимально спрощені КГ і відповідні їм СМ.
Висновки
У роботі запропоновано формальну постановку задачі добування знань з природномовних об'єктів, з якої
випливає структуралізація текстів при накладанні на них певних обмежень. Наведено приклади такого типу
обмежень, такі як силогістика Арістотеля та тексти бібліографічного характеру. Для силогістики Арістотеля
побудована її теоретико-множинна інтерпретація з розширеною системою правил виведення та аналізом
можливих ситуацій, які можуть виникати в процесі застосування цієї системи правил. Для маніпуляції, аналізу
та трансформації текстів введено поняття алгебраїчної системи спискових структур, за допомогою якої
виконується оброблення текстів на рівні фізичного представлення. Розроблено алгебро-логічний підхід та
просту логічну мову до дослідження семантичних властивостей ПМО.
Зрозуміло, що розроблені формальні засади комп'ютерного опрацювання ПМО далеко не вичерпують
всіх теоретичних засад обробки природної мови, зокрема засад семантичного аналізу. Запропонована
формалізація семантики та підхід, що її реалізує, потребують об'ємних спеціалізованих словників для різних
етапів лінгвістичного аналізу ПМО. Іншим недоліком системи, що пропонується, є суттєве обмеження на стиль
природномовних текстів.
Наступним кроком вдосконалення та розширення формально-логічних засад та підходу до оброблення
ПМО повинен бути перехід до обробки неструктурованих текстів, тобто таких, стиль яких не вичерпується
силогізмами Арістотеля та бібліографічним характером. Крім того, для природномовної обробки слід
розглянути доцільність переходу від множини різного роду граматичних словників до єдиної, системно-
онтологічної, природномовної бази знань, або мовно-онтологічної картини світу.
1. Палагин А.В., Крывый С.Л., Петренко Н.Г. Знание-ориентированные информационные системы с обработкой естественно-
языковых объектов: основы методологии и архитектурно-структурная организация // УСиМ. – 2009. – № 3. – С. 42–55.
2. Палагин А.В., Петренко Н.Г. Системно-онтологический анализ предметной области // УСиМ. – 2009. – № 4. – С. 3–14.
3. Tarski A. The semantic conception of truth. Philosophy and phenomenological Research. – v.4. – 1944. – P. 241–375.
4. Tarski A. Logique, Semantique and Metamathematique (1923-1944). Colin. – Paris. – 1972.
5. Devidson D. Proceedings of Philosofical Logic. – Reidel. – Dordrecht. – 1969.
6. Montague R. Universal grammars. Theoria. Formal Phylisophy: Selected Papers of R. Montague. – Yale University Press. -1974. – vol. 36. –
P. 222–246.
7. Кривий С.Л. Дискретна математика: вибрані питання. Київ: Видавничий дім «Києво-Могилянська академія». – 2007. – 570 с.
8. Тейз А,, Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. От классической логики к логическому
программированию. – М.: Мир. – 1990. – 429 с.
9. Тейз А,, Грибомон П., Юлен Г. и др. Логический подход к искусственному интеллекту. От модальной логики к логике баз данных. –
М.: Мир. – 1998. – 494 с.
10. Леонтьева Н.Н., Семенова С.Ю. Семантический словарь РУСЛАН как инструментарий компьютерного понимания. – М.: МГГИИ.
– 2003. – С. 41–46.
11. Леонтьева Н.Н. К теории автоматического понимания естественных текстов. Часть 1. Моделирование системы "мягкого
понимания" текста: информационно-лингвистическая модель. – М., МГУ, 2000. – 43 с.
12. Леонтьева Н.Н. К теории автоматического понимания естественных текстов. Часть 2. Семантические словари: состав, структура,
методика создания. – М., МГУ, 2001. – 41 с.
13. Апресян Ю.Д. Лингвистический процессор для сложных информационных систем. М.: Наука. –1992. – 324 с.
14. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. – 1979. – 535 с.
|
| id | nasplib_isofts_kiev_ua-123456789-14629 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:44:25Z |
| publishDate | 2010 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Палагін, О.В. Кривий, С.Л. Петренко, М.Г. Бібіков, Д.C. 2010-12-27T13:43:55Z 2010-12-27T13:43:55Z 2010 Алгебро-логічний підхід до аналізу та обробки текстової інформації / О.В. Палагін, С.Л. Кривий, М.Г. Петренко, Д.C. Бібіков// Пробл. програмув. — 2010. — № 2-3. — С. 318-329. — Бібліогр.: 14 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14629 51.681.3 Пропонується формальна модель системи аналізу та обробки текстової інформації на основі алгебри множин і відношень та простої логічної мови. Описані алгебро-логічний підхід до аналізу природномовного тексту та алгебраїчна система спискових структур, орієнтована на обробку текстової інформації. The formal model of system of the analysis and processing of the text information on the basis of algebra of sets and relations and simple logic language is offered. Are described algebro-logical the approach to the analysis of naturally-language text and the algebraic system of list structures focused on processing of the text information. uk Інститут програмних систем НАН України Формальні методи програмування Алгебро-логічний підхід до аналізу та обробки текстової інформації The algebro-logical approach to the analysis and processing of the text information Article published earlier |
| spellingShingle | Алгебро-логічний підхід до аналізу та обробки текстової інформації Палагін, О.В. Кривий, С.Л. Петренко, М.Г. Бібіков, Д.C. Формальні методи програмування |
| title | Алгебро-логічний підхід до аналізу та обробки текстової інформації |
| title_alt | The algebro-logical approach to the analysis and processing of the text information |
| title_full | Алгебро-логічний підхід до аналізу та обробки текстової інформації |
| title_fullStr | Алгебро-логічний підхід до аналізу та обробки текстової інформації |
| title_full_unstemmed | Алгебро-логічний підхід до аналізу та обробки текстової інформації |
| title_short | Алгебро-логічний підхід до аналізу та обробки текстової інформації |
| title_sort | алгебро-логічний підхід до аналізу та обробки текстової інформації |
| topic | Формальні методи програмування |
| topic_facet | Формальні методи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/14629 |
| work_keys_str_mv | AT palagínov algebrologíčniipídhíddoanalízutaobrobkitekstovoíínformacíí AT kriviisl algebrologíčniipídhíddoanalízutaobrobkitekstovoíínformacíí AT petrenkomg algebrologíčniipídhíddoanalízutaobrobkitekstovoíínformacíí AT bíbíkovdc algebrologíčniipídhíddoanalízutaobrobkitekstovoíínformacíí AT palagínov thealgebrologicalapproachtotheanalysisandprocessingofthetextinformation AT kriviisl thealgebrologicalapproachtotheanalysisandprocessingofthetextinformation AT petrenkomg thealgebrologicalapproachtotheanalysisandprocessingofthetextinformation AT bíbíkovdc thealgebrologicalapproachtotheanalysisandprocessingofthetextinformation |