Дедуктивне виведення. Виведення в семантичних мережах. Виведення в мережах фреймів. Виведення в логічних системах

V. ДЕДУКТИВНЕ ВИВЕДЕННЯ

3. Виведення в семантичних мережах(СМ)

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

Пошук оформлюється у вигляді запитів двох видів:

-  запит на існування, коли можливі відповіді “так” чи “ні”;

-  запит на перелік, коли відшукуються всі можливі вкладення.

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

4. Виведення в мережах фреймів (МФ)

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

Існують інтелектуальні системи, в яких використовується семантичні мережі на фреймах, де вершинам відповідають класи об’єктів-сутностей (подані у вигляді фреймів зі слотами атрибутами сутностей), а дуги – це бінарні зв’язки між сутностями. Корінь графового прототипу (виділена для деякого класу об’єктів підмножина його примірників) визначає клас. Фрагмент мережі (зв’язки кореня з іншими класами об’єктів) використовується для визначення положення класу серед інших.

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

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

5. Виведення в логічних системах (ЛС)

Основні правила виведень в ЛС

Логічне правило полягає в утворенні з деякої сукупності початкових даних правильно побудованих формул (ППФ) нових формул, які є тавтологіями. Ця задача розв’язується за допомогою правил виведення з використанням наступних правил: Modus ponens (B→D), BD (- означає виводимість); Modus tollens (B→D), ~D~B; подвійного заперечення ~(~B) →B; силогізму (B→D)(D→P)(B→P).

Формула Q є вивідною, якщо вона може бути виведена з кінцевої сукупності початкових формул
P₁, P₂,... ,P_n шляхом кінцевої кількості кроків застосування правил виведення P₁→(P₂→(...(P_n→Q)...)).

Для скорочення багаторазового використання основних правил застосовуються спеціальні правила.

 Нехай задано формули P₁, P₂,... ,P_n та формулу Q. Кажуть, що Q є логічним наслідком формул
P₁, P₂,... ,P_n (позначається (P₁, P₂,... ,P_nQ)) тоді і тільки тоді, коли для будь-якої інтерпретації, в якій формули P₁, P₂,... ,P_n є істинними, Q також істинна формула. Тут P₁, P₂,... ,P_n називаються аксіомами (постулатами, посиланнями) формули Q.

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

У логіці висловлювань доведено дві теореми, на яких ґрунтується коротший і простіший спосіб виведення.

Теореми дедукції: Нехай задано формули P₁, P₂,... ,P_n і формулу Q. Тоді Q є логічним наслідком P₁, P₂,... ,P_n тоді і тільки тоді, коли (P₁, P₂,... ,P_n)→Q є вивідною формулою.

Теорема про суперечливість: Нехай задано формули P₁, P₂,... ,P_n і формулу Q. Тоді Q є логічним наслідком P₁, P₂,... ,P_n тоді і тільки тоді, коли (P₁P₂...P_n)~Q є суперечливою формулою.

6. Метод резолюції

Ідея цього методу полягає в перевірці наявності в множині формул пустого (помилкового) диз’юнкта □. Якщо множина містить диз’юнкт □, то вона не виконувана, якщо не містить, то виводяться нові диз’юнкти, доки не буде знайдений диз’юнкт □.

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