1. Поняття логічної моделі знань.
В основі лот. моделі знань лежить поняття формальної теорії та відносини, які існують між одиницями знань можна описувати тільки за допомогою синтаксичних правил, допустимих в рамках цієї теорії.
Формальна теорія задається завжди четвіркою символів S = <B, F, A, R>, де
В - кінцеве безліч базових символів, інакше - алфавіт теорії S;
F - підмножина виразів теорії S, званих формулами теорії. Зазвичай є ефективна процедура, яка представляє собою сукупність правил, які дозволяють з елементів множини У будувати синтаксично правильні вирази.
А - виділене безліч правил, які називаються аксіомами теорії, тобто безліч апріорно істинних формул.
R - кінцеве безліч відносин {r1, r2, ... , Rn} між формулами, званими правилами виводу. Для будь-якого ri існує ціле позитивне число j, таке, що для кожного безлічі, що складається з j формул, і для кожної формули F ефективно вирішується питання про те, чи знаходяться ці j-формули щодо ri з формулою F. Якщо ri виконується, то F називають безпосереднім наслідком F-формул за правилом ri.
Наслідком (висновком) формули в теорії S називається така послідовність правил, що для будь-якого з них представлена формула явл-ся або аксіомою теорії S, або безпосереднім наслідком.
Правила виводу, які розробляються проектувальниками, позволдяют розширити безліч формул, які явл-ся аксіомами теорії.
Формальна теорія зв. розв'язною, якщо існує ефективна процедура, що дозволяє дізнатися для будь-якої заданої формули, чи існує її висновок в теорії S.
Формальна теорія S зв. Непротіаворечівой, якщо не існує такої формули А, що і А, і не А виведені в цій теорії.
Найбільш поширеною формальною теорією, що використовується в системах штучного інтелекту явл-ся числення предикатів, тобто функцій, які можуть приймати тільки 2 значення.
До достоїнств логічної моделі відносять:
- Наявність стандартної типової процедури логічного висновку (докази теорем). Проте така уніфікація тягне за собою основний недолік моделі - складність використання в процесі логічного виведення евристик, що відбивають специфіку ПЗ.
До інших недоліків логічної моделі відносять:
- "Монотонність";
- "Комбінаторний вибух";
- Слабкість структурованості описів.
2. Характеристика мови предикатів першого порядку. Особливості подання знань.
В основі мови предикатів першого порядку лежить поняття предикатів, тобто логічна функція від однієї або декількох нелогічних мінно. Функція може приймати значення істина (t) або брехня (f). У рамках логіки твердження вважається істинним, якщо і що відноситься до нього припущення вважається дійсним і висновок самого твердження теж істина.
Синтаксис мови предикатів включає: предикативні символи, символи змінних, константи (?), А також роздільники (), [], ", '.
Предикативні символи використовуються для позначення відносин. Об'єкти відносин записуються в () після предикативного символу і наз-ся аргументами. Повна запис відносини наз-ся атомної або атомарної формулою.
Атомарна формула:
Є (Іванов, спец.-поЕВМ)
предикативний терм 1 терм 2
символ
Терми можуть представлятися констанатамі і змінними. Дозволено також як термів використовувати функції, к-які обов'язково повинні бути визначені в рамках ПЗ. Проектувальник ЕС заранеее визначає, як інтерпретувати порядок термів у відношенні. Допустимі вирази в численні предикатів, зокрема атомарні формули, наз-ся правильно побудованими функціями (ППФ). У мові предикатів для кожної ППФ обов'язково визначається конкретна інтерпретація. Як тільки для ППФ визначена інтерпретація, кажуть, що формула має значення "істина", якщо відповідне твердження ПО істинно, інакше ППФ має значення "брехня".
З формул можна скласти пропозицію за допомогою логічних зв'язок: кон'юнкція, диз'юнкція, імплікація, заперечення.
Кон'юнкція ( ) використовується для утворення складових фраз:
Вчиться (Іванов, ек.-університет) розташовується (ек.-університет, Київ)
ППФ, побудовані за допомогою зв'язки кон'юнкція, наз-ся просто кон'юнкції.
Диз'юнкція () реалізує функцію не виключає "або".
Знаходяться (Іванов, аудіт.-147) І знаходиться (Іванов, бібліотека).
ППФ, побудовані за допомогою зв'язки диз'юнкція, наз-ся диз'юнкції.
Зв'язка імплікація () використовується для представлення затвердження типу "якщо, то".
Володіти (Іванов, машина-1) марка (машина-1, "BMW").
ППФ, побудована шляхом з'єднання формул з допомогою зв'язки імплікація, наз-ся імплікацією.
Ліва сторона імплікації наз-ся антецедент, права - конціквент. Імплікація має значення "істина", якщо антецедент і конціквент мають значення "істина", або антецедент має значення "брехня" незалежно від конціквента. В інших випадках імплікація має значення "брехня".
ППФ зі знаком заперечення (~) перед нею наз-ся запереченням.
У мові предикатів атомна формула може приймати тільки істинні значення, тільки помилкові значення, а також у залежності від значень змінних, які до неї входять, або ітсіна, або брехня. Для того, щоб при обчисленні предикатів можна було маніпулювати значеннями змінних, треба було ввести поняття "квантор".
Квантор - це операція, в якій беруть участь всі значення змінної одного предиката.
Квантор служить для вказівки заходи, в якій екземпляри змінної (?), Тобто константи повинні бути істинними, щоб всі значення в цілому були істинними.
Розрізняють квантор спільності і квантор сущестовованія . Якщо перед предикатом записаний квантор для якоїсь змінної, напр. (х), то це означає, що значення предиката буде істинним тільки в тому випадку, якщо всі значення змінної х будуть істинними.
(х) (фахівець-по-ЕОМ (х) програміст)
Якщо перед предикатом записаний квантор , напр. (х), то для істинності предиката досить, щоб тільки некотрое значення змінної, принаймні одне, були істинними.
(х) (фахівець-по-ЕОМ (х) оптиміст (х))
У рамках одного предиката можна використовувати і квантори спільності, і квантори існування, але для різних змінних.
(х) (y) (службовець (х) керівник (y, х))
Якщо некотрая змінна в ППФ проквантіфіцірована, то вона називається зв'язаною. В іншому випадку змінна називається вільною. Будь-яке вираження, яке виходить шляхом квантіфіцірованія правильної формули, є також ППФ.
Предикатами першого порядку наз-ся предикати, в яких не допускається квантифікація по предикативним або функціональним символів, а можна квантифікувати тільки змінні.
3. Апарат логічного висновку.
У мові предикатів процедури логічного висновку виробляються над знаннями, представленими у внутрішній формі по відношенню до тих описів, к-які виконав проектувальник, відображаючи специфіку ПЗ, т. о. проектувальник працює з зовнішньою формою подання знань, а процедури логічного висновку - з внутрішньої.
Переклад зовнішньої форми у внутрішню виробляється в системах, які реалізують мову предикатів, автоматично на основі таблиць істинності для обчислення окремих предикатів і логічних операцій, а також на підставі цілого ряду еквівалентності (закони де Моргана, дистрибутивні закони, асоціативні закони). У процесі логічного висновку мови предикатів використовуються операції, к-які застосовуються до існуючих ППФ з метою побудови нових ППФ.
"Modus ponens" - використовується для створення з ППФ виду А ППФ виду В
(А В). ("турнікет") інтерпретується як "отже".
Операція спеціалізації. Суть - дозволяє довести, що якщо певного класу об'єктів притаманне к.-л. властивість, то будь-який об'єкт даного класу буде володіти цією властивістю. Для всіх об'єктів класу ісп. властивість А, отже
x) W (x), AL * W (A) (?)
Операція - уніфікація. Викорис-ся для док-ва теорії, що містять квантіорізірованние формули приводять у відповідність певні подвираженія форми шляхом знаходження підстановок.
Операція резолюція. Використовується для породження нових припущень. В основі методу резолюції лежить спростування гіпотези і доказ, що це невірно. У процесі реалізації методу використовується операція виключення висловлювання, якщо ці висловлювання в даних припущеннях заперечуються, а вдругих - немає. Врезультате докази якщо спростування брехливо, формується порожня резольвента.
Для застосування резолюції ППФ повинні бути переведені в клаузальную форму шляхом спрощення, а потім представлене у формі диз'юнкції. Процес перетворення зводиться до следующ. основними етапами:
1 - виключення символів імплікації з формул і обмеження області дії символу заперечення
2 - поділ змінних, тобто заміна однієї пов'язаної квантором змінної, кіт. зустрічається у виразі кілька разів - різними іменами
3 - виняток кванторів існування шляхом їх заміни функціями, аргументами яких є змінні, пов'язані квантором спільності, область дії кіт. включає область дії виключеного квантора існування.
4 - перетворення припущень в префіксной форму, тобто в ППФ не залишається кванторів існування. Кожен квантор спільності має свою змінну, тому всі квантори спільності можна перемістити в початок ППФ і вважати, що область дії кожного квантора включає всю ППФ.
5 - приведення матриці до коньюнктівной нормальній формі, тобто кон'юнкції кінцевого безлічі диз'юнкція.
6 - виняток кванторів спільності. Це можливо, тому що всі змінні, що залишилися на цьому етапі ставляться до квантор спільності.
7 - виключення символів кон'юнкції. У результаті матриця залишається тільки у вигляді диз'юнкції, над якими можливе проведення операцій резлюціі.
4. Особливості машинної реалізації мови предикатів першого порядку.
Машинна реалізація мови предиката першого порядку має ряд серйозних проблем, які пов'язані з універсальністю апарату логічного висновку. 1-а проблема - монотонність міркувань (у процесі логічного виведення не можна відмовитися від проміжного висновку, якщо стають відомими додаткові факти, які свідчать про те, що отримані на основі цього висновку рішення не призводять до бажаного результату. 2-а проблема - комбінаторний вибух ( в процесі логічного висновку неможливо застосовувати оціночні критерії для вибору чергового правила. Безсістемное застосування правил у розрахунку на випадкове доказ приводить до того, що виникає багато зайвих ланцюжків ППФ, активних у певний момент часу. Це найчастіше приводить до переповнення робочої пам'яті.
У процесі досліджень з відшукання ефективних процедур машинної реалізації мови предиката намітилося 2 основних підходи (кін. 60-х рр..):
1 - Відкидається принцип універсальності мови предиката і проводиться пошук конкретних процедур, ефективних для конкретної предметної області. У цьому випадку в БЗ вводилися великі знання предметної області. Найбільш типовий представник - LISP
2 - розвивався в рамках традиційної логіки і був спрямований на збереження універсальності, властивої мови-предикату шляхом розробки ефективних процедур логічного висновку універсальних за своїм характером, але дозволяють нейтралізувати монотонність і комбінаторний вибух.
Найбільш ефективною розробкою цього підходу явл. мова PROLOG. У ньому прийнята зворотна стратегія виведення. Повністю реалізовані всі засоби опису знань мови-предиката, в т.ч. і кванторами для породження нових висловлювань використовується операція резолюціі.В якості процедури пошуку рішення, що дозволяє усунути монотонність і комбінаторний вибух використовують пошук в ієрархічно упорядкованому просторі станів.