Для імплікації і тотожності справедливі твердження:

a>b дорівнює (~a)b

a-b дорівнює (a&b)(~a & ~b)

a-b дорівнює (a>b) & (b>a)

З кожним предикатом може бути пов'язаний квантор - елемент, який визначає, за яких умов предикат може перетворюватися на істинне висловлювання.

Розрізняють квантор узагальнення () і квантор існування ().

Якщо u - змінна, r - твердження, то запис

“ u r” означає „r справджується для всіх u” (узагальнення, для будь-якого u, all);

“ u r” означає „існує u, для якого r справджується” (існування, існує хоча б одне u для якого ..., exists);

Приклад: All (Х, чоловік(Х) > людина (Х))

Елементарним об'єктом, який має значення „істина”, є атомарна формула (літерал):

P(t1, t2, …, tn), де Р - предикат, t - терми, n - арність предикату.

Хибна формула: „?”.

Тавтології (тотожньо істинні формули): ~~A-A.

Позитивний літерал не стоїть під знаком заперечення, а негативний - під знаком заперечення.

Диз'юнктом (фразою теорії) називається диз'юнкція деякої кількості атомарних формул.

Часто використовують фрази спеціального типу - фрази Хорна (хорнівські диз'юнкти) - диз'юнкція довільної кількості атомарних формул, з яких позитивною є не більше ніж одна (~A ~B ~C D).

Фрази Хорна по суті є імплікаціями, оскільки за правилами Моргана

(~A ~B ~C D) еквівалентне (A B C ) > D.

Для практичного застосування у логічних виразах потрібно позбутися кванторів узагальнення та існування (пренексна нормальна форма).

Для усунення кванторів існування використовують константи і функції Сколема. Наприклад:

Маємо формулу x: P(x) вкажемо предметну константу С (константу Сколема), для якої твердження P(C) є істинним; таким чином перейдемо від x: P(x) до P(C).

Маємо формулу y x: P(x,y), вкажемо деякий елемент С, для якого твердження P(|C,y) є істинним, тому можна перейти від формули y x: P(x,y) до формули y P(h(y), y), де h(y) - функція Сколема.

Квантори узагальнення просто видаляються (вважається, що якщо фраза залежить від деяких змінних, то всі вони зв'язані оператором узагальнення); формула xyz P(x,y,z) замінюється на P(x,y,z).

Для спрощення логічних формул використовують рівності

~(а&b) означає (~а) (~b);

~Exists(u,r) означає All(u,~r);

~All(u,r) означає Exists(u,~r).

В результаті перетворень отримуються хорнівські фрази, наприклад (~A  ~B  ~C  D), яка еквівалентна D<(A B C ), а в мовах логічного програмування записується у вигляді D:- A, B, C.

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

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

Визначаються предметні змінні.

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

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

Правила виведення задаються фразами Хорна.

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

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

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

Наприклад:

Маємо неформальний опис: „Всі студенти люблять відвідувати лекції. Деякі студенти люблять морозиво. Іванов є студент, але не любить морозива”

Введемо такі предикати і предметні константи:

L(x,y) - x любить y.

S(x) - x є студентом.

A - предметна константа „відвідування лекцій”.

I - предметна константа „Іванов”

Q - предметна константа „Морозиво”.

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

x: (~S(x) L(x,A))

x: (S(x) & L(x,Q))

S(I)

~L(I,Q)

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

S(x) L(x,Q)

S(c)

L(c,Q)

S(I)

~L(I,Q),

де С - константа Сколема.

В логічному програмуванні для автоматичного доведення певного твердження (ВПФ) використовується метод від супротивного: береться інверсія ВПФ і додається до бази знань; якщо при цьому виникає протиріччя (A & ~A) , то ВПФ вважається вірною.

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

Наприклад, фрази (~PM) і (PL) утворюють контрарну пару, результатом якої (резольвентою) є фраза (ML).

Приклад застосування методу резолюцій.

Дано набір фраз:

„вовк їсть м'ясо”

„тварини, які їдять м'ясо, є хижаками”

Потрібно довести, що „вовк є хижаком”

Введемо предикати

G(x,y) => „х їсть у”

Q(x) => „х є хижак”

13. Продукційні моделі

Продукційною називається модель знань, в якій база знань складається із сукупності продукцій, тобто правил „Якщо А, тоді В”.

Термін „продукція” введений американським математиком Е.Постом. Як і логічні, продукційні моделі базуються на дедуктивному виведенні, але є менш формалізованими і простими.

Приклади продукцій для зоологічного парку:

„Якщо тварина є птахом, вона не літає, вона плаває, має чорно-білий колір - то це пінгвін”

Такі продукції описують імплікації (з істиності А випливає істинність В).

Приклад для системи керування технологічним процесом:

„Якщо температура перевищує 200 градусів, то ввімкнути систему охолодження”

Такі продукції задають умовні операції (якщо справедлива умова А, то виконати дію В).

Продукційна система - це база знань разом з механізмом керування продукціями.

Продукційна модель - подання знань у вигляді сукупності продукцій. Продукція визначається виразом:

(і) Q; P; A B ; N ,

де (і) - ім'я продукції, Q - сфера застосування продукції (предметна область), P - умова застосування продукції, AB ядро продукції, N - постумова продукції, постулює виконання дій після реалізації ядра.

Приклад:

„(БС-29) Банківська сфера; клієнт має рахунок у банку на достатню суму; якщо клієнт бажає зняти певну суму грошей, то він повинен написати ордер; внести зміни до бази даних”.

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

Переваги продукцій них моделей:

Більшість людських знань можна описати у вигляді продукцій.

Більшість продукцій є взаємно незалежними.

Продукційні моделі можуть реалізувати будь-які алгоритми.

Продукції можуть працювати паралельно.

Основний недолік продукцій - складність перевірки правильності функціонування.

Системи продукцій можна зображати у вигляді графів - мереж виведення.

Мережі виведення будуть так. Вершини графу відповідають умовам і діям, що входять до лівих і правих частин продукцій. Якщо є продукція А>В, то від вершини А до вершини В йде орієнтована дуга. Якщо є продукція А, В>С, до дуги (АС) та (ВС) зв'язані відношенням „І” (кон'юнкції).

Для продукційної системи

А>С

В>С

В, F>L

F>Q

D, C>G

мережа виведення

Мережа виведення забезпечує поділ задачі на підзадачі і є структурою, близькою до І-АБО-графів.

Схема роботи експертної системи на базі продукцій

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

Наприклад, продукції А>В і В>С виконуються, якщо стає відомо про істинність А.

Пряме виведення на основі правил передбачає аналіз:

усіх наслідків з фактів;

наслідків з наслідків і т.д.

Процес продовжується, поки не буде встановлено істинність або хибність запиту користувача.

Нехай є продукція А>В та В>С; користувач оголосив про істинність факту А і спитав про істинність факту С. Ланцюг прямого виведення матиме вигляд: з А виводиться В, з В виводиться С, отже С- істинне.

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

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

В нашому випадку ланцюжок зворотного розповсюдження матиме вигляд: „С виводиться з В, В виводиться з А, А істинне, отже і С істинне”.

Зворотне виведення, як і пряме, є стратегією перебору (вимагає повторень у випадку невдалої спроби). В загальному для зворотного виведення потрібно виконати менше продукцій, ніж для прямого. Зворотне виведення тісно пов'язане з прологівським механізмом виконання програм. Продукції поділяються на детерміновані й не детерміновані.

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

У не детермінованих продукціях права частина при виконанні лівої виконується з певною ймовірністю.

Є два режими керування виконанням продукцій:

1. режим негайного виконання (виконується перша вірна продукція);

2. режим формування конфліктного набору або „фронту готових продукцій” (списку продукцій, готових до виконання). Далі відбувається вибір однієї продукції зі списку.

При виконанні конфліктних наборів є певні проблеми.

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

А>В

А>С,

й А - істинне.

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

Якщо ж ядра продукцій є процедурами, то в результаті виконання однієї продукції може змінитися стан іншої продукції.

Наприклад, після виконання першої продукції А може перестати бути істинними, відповідно продукція 2 не виконається. Якщо ж першою виконається продукція 2, то результат може бути зовсім інший.

Існують різноманітні стратегії вирішення конфліктів, централізоване і децентралізоване керування продукціями (наприклад, механізм „класної дошки”). Класна дошка - спільна область пам'яті для всіх продукцій, на якій кожна продукція може знайти інформацію про свій запуск.

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

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

1. Принцип „стосу книг”. Ґрунтується на ідеї, що найкориснішою є та продукція, яка використовується найчастіше (у стосі книг зверху звичайно опиняються книги, що користуються найбільшим попитом). Стратегія є ефективною, якщо продукції відносно незалежні між собою.

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

Наприклад, з двох продукцій:

Якщо А - птах, то А - літає;

Якщо А птах і А- пінгвін, то А не літає.

за принципом найдовшої умови вибирається 2. Принцип найдовшої умови ефективний при аналізі винятків.

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

4. Принцип „класної дошки”. Конфлікти вирішуються на основі обміну інформацією з використанням класної дошки.

5. Принцип вибору за пріоритетом (важливістю). Пріоритети продукцій можуть бути різними для різних ситуацій, тобто статичними і динамічними.

Страницы: 1, 2