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

Особенности реалізації експертних систем з урахуванням логічного моделі знаний.

1. Поняття логічного моделі знаний.

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

Формальная теорія задається завжди четвіркою символів P. S=, де.

В — кінцеве безліч базових символів, інакше — алфавіт теорії S;

F — підмножина висловів теорії P. S, званих формулами теорії. Зазвичай є ефективна процедура, що дає сукупність правил, дозволяють з елементів безлічі У будувати синтаксично правильні выражения.

А — виділений безліч правил, званих аксіомами теорії, т. е. безліч апріорно істинних формул.

R — кінцеве безліч відносин { r1, r2, …, rn } між формулами, званими правилами виведення. Для будь-якого ri існує ціле позитивне число j, таке, що кожного безлічі, що складається з j формул, для кожної формули F ефективно вирішується питання, містяться ці j-формулы щодо ri з формулою F. Якщо ri виконується, то F називають безпосереднім наслідком F-формул за правилом ri.

Следствием (висновком) формули теоретично P. S називається така послідовність правил, що нічого для будь-якого їх представлена формула явл-ся або аксіомою теорії P. S, або безпосереднім следствием.

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

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

Формальная теорія P. S зв. Непротиаворечивой, а то й існує такий формули Хіба й О, і не, А виведені у цій теории.

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

К гідностям логічного моделі относят:

— наявність стандартної типовий процедури логічного висновку (докази теорем). Але такий однаковість тягне у себе основний недолік моделі - складність використання їх у процесі логічного висновку эвристик, що відбивають специфіку ПО.

К іншим недоліків логічного моделі относят:

— «монотонность»;

— «комбинаторный взрыв»;

— слабкість структурованості описаний.

2. Характеристика мови предикатів першого порядку. Особливості уявлення знаний.

В основі мови предикатів першого порядку лежить поняття предикатів, тобто логічна функція від одній або кількох нелогических пременных. Функція може приймати значення істина (t) чи нахабна брехня (f). У межах логіки твердження вважається істинним, як і стосується нього припущення вважається істинним і висновок самого затвердження теж истина.

Синтаксис мови предикатів включає: предикативные символи, символи змінних, константи (?), і навіть роздільники (), [ ], «, ‘.

Предикативные символи йдуть на позначення відносин. Об'єкти відносин записуються в () після предикативного символу і наз-ся аргументами. Повна запис відносини наз-ся атомної чи атомарної формулой.

Атомарная формула:

Является (Іванов, спец.—поЭВМ) предикативный терм 1 терм 2.

символ Термы можуть представлятися констанатами і перемінними. Дозволено також як термов використовувати функції, к-рые обов’язково слід визначити у межах ПО. Проектувальник ЕС заранеее визначає, як інтерпретувати порядок термов в відношенні. Допустимі висловлювання на обчисленні предикатів, зокрема атомарні формули, наз-ся правильно побудованими функціями (ППФ). У мові предикатів кожної ППФ обов’язково визначається конкретна інтерпретація. Щойно для ППФ визначено інтерпретація, кажуть, що формула має значення «істина», якщо відповідне твердження ПО істинно, інакше ППФ має значення «ложь».

Из формул можна скласти речення з допомогою логічних зв’язок: й, диз’юнкція, імплікація, отрицание.

Конъюнкция (Ù) використовується для освіти складових фраз:

Учится (Іванов, эк.-университет) Ù розташовується (эк.-университет, Київ).

ППФ, побудовані з допомогою зв’язки зв’язок, наз-ся просто конъюнкциями.

Дизъюнкция (È) реалізує функцію не виключає «или».

Находятся (Іванов, аудит.-147) І перебуває (Іванов, бібліотека).

ППФ, побудовані з допомогою зв’язки диз’юнкція, наз-ся дизъюнкциями.

Связка імплікація (®) використовується до подання затвердження типу «якщо, то».

Владеть (Іванов, машина-1) ® марка (машина-1, «BMW»).

ППФ, побудована шляхом сполуки формул з допомогою зв’язки імплікація, наз-ся импликацией.

Левая сторона імплікації наз-ся антецедент, права — конциквент. Імплікація має значення «істина», якщо антецедент і конциквент мають значення «істина», або антецедент має значення «брехня» незалежно від конциквента. У інших випадках імплікація має значення «ложь».

ППФ зі знаком заперечення (~) перед ній наз-ся отрицанием.

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

Квантор — це операція, у якій беруть участь все значення перемінної одного предиката.

Квантор служить для вказівки заходи, як і екземпляри перемінної (?), тобто константи повинні бути істинними, щоб усе значення цілому були истинными.

Различают квантор спільності «і квантор сущестовования $. Якщо перед предикатом записано квантор «для якийсь перемінної, напр. «(x), це означає, що значення предиката буде істинним в тому разі, коли всі значення перемінної x будуть истинными.

" (x) (специалист-по-ЭВМ (x) ® програміст).

Если перед предикатом записано квантор $, напр. $(x), то тут для істинності предиката досить, аби тільки некотрые значення перемінної, по крайнього заходу одне, були истинными.

$(х) (специалист-по-ЭВМ (х) ® оптимист (х)).

В однієї предиката можна використовувати й кванторы спільності, і кванторы існування, але до різних переменных.

" (x) $(y) (службовець (x) ® керівник (y, х)).

Если некотрая змінна в ППФ проквантифицирована, вона називається пов’язаної. У протилежному разі змінна називається вільної. Будь-яке вираз, яке виходить шляхом квантифицирования правильної формули, є й ППФ.

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

3. Апарат логічного вывода.

В мові предикатів процедури логічного висновку виробляються над знаннями, представленими у внутрішній формі стосовно тим з описів, к-рые виконав проектувальник, відбиваючи специфіку ПО, т. про. проектувальник працює із зовнішньої формою уявлення знань, але процедуру логічного висновку — зі внутренней.

Перевод зовнішньої форми у внутрішнє виробляється у системах, що реалізують мову предикатів, автоматично з урахуванням таблиць істинності для обчислення окремих предикатів і логічних операцій, і навіть виходячи з цілого ряду еквівалентності (закони де Моргана, дистрибутивні закони, асоціативні закони). У процесі логічного висновку мови предикатів використовуються операції, к-рые застосовуються до існуючим ППФ з єдиною метою побудови нових ППФ.

«Modus ponens» — використовується до створення з ППФ виду, А ППФ виду У.

(А ë У). ë («турнікет») інтерпретується як «следовательно».

Операция спеціалізації. Суть — дозволяє довести, що й деякому класу об'єктів властиво к.-л. властивість, будь-який об'єкт даного класу володітиме цим властивістю. Всім об'єктів класу ісп. властивість А, следовательно.

" (x) W (x), A L*W (A) (?).

Операция — уніфікація. Использ-ся для док-ва теорії, містять квантиоризированные формули викликають відповідність певні подвыражения форми шляхом перебування подстановок.

Операция резолюція. Використовується для породження нових припущень. У основі методу резолюції лежить спростування гіпотези і доказ, що це не так. У процесі реалізації методу використовується операція винятку висловлювання, якщо це висловлення в даных припущеннях заперечуються, а вдругих — немає. Врезультате докази якщо спростування брехливо, формується порожня резольвента.

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

1 — виняток символів імплікації з формул і її області дії символу отрицания.

2 — поділ змінних, тобто. заміна однієї пов’язаної квантором перемінної, кіт. зустрічається у натуральному вираженні кілька разів — різними іменами.

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

4 — перетворення припущень в префиксную форму, тобто. в ППФ іншого кванторів існування. Кожен квантор спільності має власну зміну, тому все кванторы спільності можна перемістити на початок ППФ і слід вважати, що область дії кожного квантора включає всю ППФ.

5 — приведення матриці до коньюнктивной нормальної формі, тобто. коньюнкции кінцевого безлічі дизьюнкций.

6 — виняток кванторів спільності. Це можна, т.к. все перемінні, решта цьому етапі ставляться до квантору общности.

7 — виняток символів коньюнкции. Через війну матриця залишається тільки як дизьюнкций, з яких можливо проведення операцій резлюции.

4. Особливості машинної реалізації мови предикатів першого порядка.

Машинная реалізація мови предиката першого порядку має низку серйозні проблеми, які пов’язані з універсальністю апарату логічного висновку. 1-ша проблема — монотонність міркувань (у процесі логічного висновку не можна відмовитися від проміжного укладання, якщо стають відомими додаткові факти, які свідчать, що отримане з урахуванням цього висновку рішення не призводять до бажаному результату. 2-га проблема — комбинаторный вибух (у процесі логічного висновку неможливо застосовувати оціночні критерії для вибору чергового правила. Безсистемное застосування правив у рассчете на випадкове доказ призводить до того, що виникає багато зайвих ланцюжків ППФ, активних в момент часу. Це найчастіше призводить до переповненню робочої памяти.

В процесі досліджень з відшуканню ефективних процедур машинної реалізації мови предиката намітилося 2 основних подхода (кон. 60-х гг.):

1 — Відкидається принцип універсальності мови предиката і виробляється пошук конкретних процедур, ефективних для конкретної предметної області. У цьому вся разі БЗ вводилися великі знання предметної області. Найтиповіший представник — LISP.

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

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

Список литературы

Для підготовки даної роботи було використані матеріали із сайту internet.