Яким чином ця властивість може нам допомогти? Якщо наші гіпотези послідовні, нам потрібно лише додати до них факти заперечення того, що ми хочемо довести, і аналіз видасть нам пусту фразу, якщо наші твердження випливають з гіпотез. Ми нвзиватимемо_пункти, які ми додаємо до гіпотез, цільоаими твердженнями. Зауважте, що цільовІ твердження нічим не відрізняються від гіпотез — це такі самі фрази. Отже, якщо ми маємо набІр.пунктівАУ,А2,..., An, I задачу показу, що вони непослідовні, тоді ми не шитим'емо, що мається на увазі: коли ~ A1 випливає з A2, АЗ, A4, ...An, чи коли~ A2 випливає з Al,A3, ...,An, чи коли ~A3 випливає з A l,A2, A4, ...,An I I. д. Важливо наголосити, яка фраза є цільовим твердженням, оскільки перед аналізом усі пункти рівні У прикладі про професора Івана, легко побачити, як можна отримати густу фразу, якщо ми додамо твердження:

Отже, аналіз довів, що Іван є професором.

Завершеність аналізу означає, що, якщо факти випливають з наших гіпотез, ми можемо довести їх вірність через використання аналізу. Коли ми говоримо, що аналіз зможе отримати пусту фразу, ми маємо на увазі, що існує послідовність дій (кожна з яких включає аксіоми чи фрази, виведені в попередніх діях), які закінчуються виведенням специфічної фрази. Хоча аналіз I дозволяє нам отримувати наслщки з двох фраз, але вж ніяк нєг вка-Іуг на те, де шукати наступні відповідності. Звичайно, якщо ми маємо 6a-, гато гіпотез, то^удеТбагатб варіантів. I кожна з виведених фраз збільшу-нагиме цю кількість. Більшість з варіантів будуть невірними, і якщо ми не будемо уважними, то витратимо безліч часу на обробку невірних варіан-Іііі. Можемо навіть просто не знайти вірного варіанта.

---

Було запропоновано чимало вдосконалень до процесу аналізу з даного приводу. Розглянемо деякі з них. Наприклад, удосконалення для випадку фраз Хорна. Нагадаємо, що фраза Хорна має не більше одного позитивного лггерала. Тобто можуть існувати два типи фраз Хорна: з одним позитивнимлІтералом або без жодного позитивноголперала. Ось їх приклади:Сиетнт Btyworo іятмипу. Cypom HLXl

малодий^спецюлкт (X):- ешщаосвіта Щ знання^Нюз^моши (X).

:■ мвлодой^спецЬлкт (X).

НаспраадІ, коли ми уявляємо множину фраз Хорна (включаючи цЩьові Цкрдження), то аоми вр1_е крйя однієї, мають бути повними. Будь^яка теорема, виражена через кормівсакї фрааи, може бути доведена лише тоді, копи вона містить тІЛьки одну негіЬвйу фразу. Оскільки ми самі вирішуємо, які фрази e метою, ми можемо вважати метою неповну фразу, а всі Інші ~ I Іпотезами. Це мае природну причину. Пр-перше, легко побачити, що має бути принаймні одна неповна фраза> щоб задача мала розв'язок. Це аипл*иас з того, що результатом аналізу двох повних хорнівських фраз завжди є повна фріза. По-друге, якщо Існує кЩька неповних фраз у наших аксіомах, то доведення аналізом отримання пустої фрази потребує лише однІєї з них.

Спробуємо сформулювати наведені вище міркування у формалІзованІ-шому •игляді.

ЗгЩно з (179]доведенням теореми називається отримання відповіді на запитання: чи випливає логічна формула В із заданого набору формул {F,, *.., FJ. Це еквівалентно доведенню загальнозначимості формули F,, ..., F_n В або суперечливості формули (P^ ,.., Fn) % в. 3 практичних міркувань зручніше доводити суперечливість формули (F,,..., F_H) ~ в, тобто йдеться no cyrl про доведення ||® супротивного".

4. Побудова теорП певної області знань.

Побудова теорІЇ певної області знань включає [ 172] дослідження структури цієї області і вибір позначень, що характеризують особливості даної структури. Потім будується множина вірно побудованих формул (ВПФ) для опису цієї структури. Множина ВПФ є теорією цієї області знань, в якій кожна ВПФ — аксіома.

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

ПЩфункцією розумітимемо відображення п елементів з області інтерпретації Ще л — арність функції) на один з елементів цієї області.

Нехай областю дослідження є службові стосунки між людьми у певній фірмі. Областю інтерпретації буде така множина людей:

(Іван; Ігор, підлеглий Івана; Петро, підлеглий Івана; Микола, друг Петра). На цій області можна виокремити унарну функцію "друг". Наприклад,

друг (Петра) —> Микола.

Відношенням називають відображення п елементів із області Інтерпретування на елемент множини (Істина, хибність). У нашому прикладі можна виокремити бінарне віДношення "підлеглий". Так, підлеглий (Івана, Ігор) матиме значення "істина", а підлеглий (Ігор, Микола) набуде значення "хибність". Якщо на певному конкретному наборі аргументів відношення буде істинним, тоді кажуть, що відношення справджується.

---

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

Свтшя шпушяп тпл»кіу С^иіНМ

області: констаит, функцій, відношень. іідмПимо, що функція сама no собі мє може матм значення — його може мати тільки конкретне використання функції. АкмогКмі можна смааатм I про відношення.

Проілюструємо це иа такому прикладі.

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

Значенням о буде /еон.

Значенням Ь буде підлеглий Івана Ігор.

Значенням c буде підлеглий Іоана Петро.

Функцію "друе" позначимо/, тоді семантика цієї функції визначиться: Значенням/(с) буде Микола.

Якщо позначимо через P введене нами відношення *ntoneeauQ*, тоді його семантика виражатиме:

Значенням P (о, Ь) буде Істина.

Значенням P (Ь, а) буде Істина.

Значенням P (c, а) буде Істина.

Значенням P (о, c) буде Істина.

Значенням P (Ь, c) буде хибнкть.

Значенням P (c, Ь) буде хибнкть.

Значенням P (b,f(c)) буде хибність.

Значенням P Ще), Ь) буде хибність.

Значенням P (a,f(c)) буде хибність.

Значенням P ff(c), d) буде хибність.

Значенням P (c, /(c)) буде хибність.

Значенням P СЦе), c) буде хибність.

3 даних атомарних формул маємо можливість будувати ВПФ.

Інтерпретація, яка робить ВПФ Істиною, називається моделлю цієї ВПФ. Аналогічно визначається і модель теорії. Про ВПФ, або теорію, яка набуває значення "істина" хоча б на одній інтерпретації, кажуть, що вона задовільна. Якщо ВПФ, або теорія, c хибною на всіх інтерпретаціях, тодІ її називають незадовільною або непослідовною.

Підведемо деякі підсумки побудови бази знань певної предметної області. Вони будуть сформульовані у вигляді такихдосить загальних принципів.

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

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

3. База знань описується як кон'юнкція деяких тверджень, якІ вважаються істинними; твердження може бути явним фактом або правилом виведення.

Систем* оітучного i*nueny. Сурова H.V1

4. Факти мдаюгься позитивним або негативним літералом, який не містить мммних.

5. Правила виведення задаються фразами Хорна; передумови імплікації задаються мегативниммлітералами, а наслідок — позитивними.

6. Квантори існування усуваються шляхом введення констант і функ-_г цій Сколема.

7. Після усунення кванторів існування механічно усуваються квантори узагальнення.

8. Після побудови формалізованої бази знань можна здійснювати логічне виведення на основі методу резолюцій.

---

Наведемо приклад. Нехай маємо такий неформальний опис: УсІ студенти люблять відвідувати лекції. Деякі студенти люблять морозиво. Іванов e студент, але нелюбить морозива.

Можна ааести, наприклад, такі предикати та предметні константи:

L (к у) ~ хлюбнть у,

S (x) — Jc e студентом.

А — предметна константа, яка означає "вЩаідування лекцій";

/ — предметна константа, яка відповідає Іванову;

Q — предметна константа, яка означає морозиво.

Отримуємо базу знань:

Vr(-JWv2(*4))

3rPM*Zfr0)

SU)

~L(t<n

Усунення кванторів I розподіл кон'юнкції приводитьдо такої бази знань:

-St*)vLte&

V -r:/v SM

l(c.Q)

S(i)

~Щ & Тут c — константа Сколема. '

5. ВідформальноїлогІкидологічного програмування

Як ми вже зазначали, в логіцІ предикатів існують методи доведення того, буде чи нІ конкретна ВПФ наслідкомдеякоїтеорії. Природно виникає бажання автоматизувати таке доведення за допомогою числення предикатів У більшості підходів до цієї проблеми використовується процедура спростування. Розглянемо її основні ідеї.

3 визначення тотожної істинності і непослідовності можна дійти висновку, що ВПФ буде тотожно Істинною тоді і тільки тоді, коли внесення в теорію заперечення даної ВПФ перетворить цю теорію на непослідовну.

Теорія буде непослідовною, якщо в ній можливо вивести протиріччя такого вигляду:^А * ~^А-

---

Для будь^кої системи логічного програмування характерною є та обставина, що для виконання програми (побудови виведення результату) використовується вмонтована система автоматичного пошуку. Як вже зазначалося, механізм пошуку логічного висновку бере свій початок від методу резолюцій Робінсона. Описане в п. 7.4 правило резолюци виведення логічного висновку можна уточнити таким чином. Дві фрази можуть резольву- вати між собою, якщо одне з ним має позитивний, в друга *~* негативний літерал і одним I тим самим позначенням предиката тв однаковою кількістю аргументів, і якщо аргументи обох літералів можуть бутн уніфіковані (погоджені).

Розглянемо дві фрази спеціального вигляду:

.P (о) ~~ заключення без умови I ~ P (aJ — умова без заключеиня. Нагадммо, що наявність цих двох фраз в одній теорії в протиріччям. Якщо вони резольаують між собою, тодІ отримана резольвента називається порожньою фразою

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

Розглянемо формальніше застосування принципу резолюції та уніфікації. Спочатку розглянемо варіант вживання правила резолюції для атомарних формул, які не мктять змінних, але можуть набувати значень "Істинність" або "хибнкть" (фактично ~ для висловлювань). Кажуть, що дві фрази містять контрарму пару атомарних формул (або просто коитрариу пару), якщо одна з них включає деяку атомарну формулу без заперечення, а інша — ту саму формулу пІд знаком заперечення

ДвІ фрази, що містять контрарну пару, можуть бути резольвовані

одна з Іншою, I результатом резолюції (резольвентою) є диз’юнкція лІтералІв, якІ залишаються в обох фразахпІсля викреслення контрарноі m пари.

Наприклад нехай ми маємо фрази:

~AvA/

PvL,

де M і L — диз'юнкцІЇ довільної кількості атомарних формул. Фрази є pe- зольвованими, і резольвента має виглядМуС

Це правило було запропоновано Девісом I Патнемом. Воно стає очевиднішим, якщо переписати його в термінах імплікацій (спробуйте зробити це самостійно).

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

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

Формальніше, результатом підстановки°"ІЇАи- -*A) до фрази М(записується мс)е фраза, утворена з M заміною змінних x, на терми t? Зверніть увагу: терми можна підставляти лише замість змінних (не замість константі).

---

Смотрите также файлы

• Рынок финансовых услуг (1).doc

• n9.doc

• ПЕРВЫЕ ДНИ ПОСЛЕ ОПЕРАЦИИ.doc

• ЛФК при заболеваниях сосудов.doc

• ЛФК при беременности.doc