ЛОГІЧНІ МОДЕЛІ(ЛМ) ПОДАННЯ ЗНАНЬ

Для подання знань у ЛМ використовується формальна система ZL

ZL=(A, P1,P2, Z)

де А – множина базових елементів або алфавіт;

Р1 – множина синтаксичних правил побудови правильних формул з елементів А;

Р2 – множина правильно побудованих формул – аксіом;

Z – знання про предметну галузь (ПГ) із правил подання, що із множини Р2 дозволяють одержувати множину нових правильно побудованих формул-теорем.

Вираз у вигляді висловлення або складеного висловлення називається правильно побудованою формулою (ППФ), якщо містить допущені елементи, з’єднані з правилами Р1.

До ЛМ відносять логіку висловлювань (ЛВ) та логіку предикатів (ЛП).

ЛОГІКА ВИСЛОВЛЮВАНЬ

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

Позначення	Опис		Таблиця істинності
Унарні		A	B	~A	А B	А B	А B
~, НІ, ‾, ┐	Операція заперечення або інверсії		I	І	П	І	І	І
Бінарні		П	І	І	І	П	І
+, , АБО	Логічне підсумовування або диз’юнкція		I	П	П	І	П	П
, &, I, ·	Логічне множення або кон’юнкція		П	П	І	П	П	І
, , ЯКЩО-ТО	Імплікація, висновок або стрілка Пірса
	Рівнозначність, „тоді і тільки тоді”

Результати виконання деяких операції над висловленнями можуть мати тільки одне значення: І – істина, П- помилка. Операції мають старшинство: дії в дужках, заперечення, множення, імплікація, додавання. В логічних формулах спочатку записують наслідки – висновки, а потім умови – посилання (вчиться(студент, коледж) –– студент вчиться в коледжі; *(+(А,В),-(С,D) –– (А+В)*(С-D)).

Нехай G – задана формула, а B₁, B₂, …, B_n, - її атомарні формули. Інтерпретація формули G – це таке приписування значень атомарним формулам B₁, B₂, …, B_n, при якому кожній формулі В приписане значення істина або помилка, але не обидва разом.

Тавтологія (загальнозначуща формула, ■) – формула істина в усіх можливих її інтерпретаціях.

Суперечлива формула(□) – помилкова при всіх її інтерпретаціях, є нездійсненною.

Формули еквівалентні (А=B), якщо їх істині значення збігаються при кожній інтерпретації.

Внормальній формінемає заперечень над декількома елементами формули. До нормальної форми можна перейти за допомогою еквівалентних перетворень.

	дистрибутивні закони	закони де Моргана
закон суперечливості □	закон виключення третього	закон подвійного заперечення
P □=P	P □=□	P ■=■	P ■=P

ЛОГІКА ПРЕДИКАТІВ(ЛП)

Для побудови атомарних формул в ЛП використовують такі типи символів:

- індивідуальні символи (імена об’єктів) або константи а, b, с, …

- символи предметних змінних х,y,z,..., конкретні значення яких є предметними сталими (константами)

- функціональні символи (f, g,h, ... або змістовні слова з цих літер)

- предикатні символи (P, Q, D, … або змістовні слова з цих літер)

Функція або предикатний символ складається з термів – клас логічних понять, утворених константами або предметними змінними. Якщо f – n–місцевий функціональний символ, а t₁,…t_n – терми, то f(t₁,…t_n) –терм. Предикат – пропозиційна функція предметних змінних, заміна яких на сталі перетворює цю функцію на осмислене висловлювання. Предикат P(t₁,…t_n) – де P – n–місцевий предикатний символ, а t₁,…t_n –терми, є атомарною формулою ЛП першого порядку.

Квантори ( (загальності), (існування)) – спеціальні символи, що для характеристики змінних. Діють на формулу, до якої застосовуються. - відповідає за істинність формули для всіх об’єктів, - хоча б для одного об’єкта. Входження змінної х у формулу є зв’язаним, якщо х є змінною квантора, що входить в цю формулу або діє на такий квантор. Інакше входження є вільним. Змінні є вільними, якщо існують їх вільні входження в формулу і зв’язаними, якщо існують зв’язані входження.
(P(x,y)→ x P(x) перше входження х вільне, друге і третє зв’язані, у – вільна змінна)

Формула ЛП P(x) є вільною для змінної y, якщо в P відсутні вільні входження х, які підпадають під дію кванторів y або y. Підставити змінну у замість х у предикатну форму Р – значить замінити кожне вільне входження змінної х у Р входженням у. (Якщо P(x) має вигляд H(x,z)→ y Q(y), то Р є вільною для у, якщо – H(x,z) y Q(x,y)), то Р не є вільною для у).

Вираз, який будується на основі атомарних формул, логічних відношень і кванторів, є ППФ ЛП.

Фразова форма – форма ЛП, де кожна фраза, це множина позитивних або негативних атомарних формул, поєднаних знаком . С початку розміщують позитивні фрази, потім негативні:

I₁ I₂ … I_n П₁ П₂ П_k = I₁ I₂ … I_n ~(I_n+1 I_n+2 … I_n+k) = I_n+1 I_n+2 … I_n+k→ I₁ I₂ … I_n

Позитивні фрази є альтернативними висновками, негативні – необхідними умовами.

Квантори та ставлять перед формулою, якщо вона є істиною для якої-небудь змінної чи іншого об’єкта (Для кожного х існує хоча б одне значення у в х y [Q(x,y) P(x)], якщо вираз у [] істинний).

Нормальною формою у ЛП є попередньо нормальна форма (ПНФ). Формула, записана в ПНФ, має вигляд , де – префікс у вигляді або , а М –формула без кванторів.

Основні правила ЛП:

1. Правило узагальнення. Нехай Q-формула, що містить вільні входження змінної x і P(x) –формула. Тоді, якщо Q → P(x) є вивідною формулою (такою, що можна вивести з попередніх формул), то і Q → x P(x) є вивідною .

2. Правило зв’язування фактором існування. Нехай Q-формула, що не містить вільних входжень змінної x і P(x) –формула. Тоді, якщо P(x) → Q є вивідною формулою, то і x P(x)→ Q є вивідною .

3. Правило універсальної конкретизації. Нехай P(x) формула вільна для у. Тоді з x P(x) можна вивести P(y) підстановкою у P(x) замість змінної x змінної y.

4. Правило спеціалізації.Якщо деякому класу притаманна якась властивість, то будь-який об’єкт цього класу буде її мати: x P(x), а P(а).

5. Правило конкретизації для квантора існування. Нехай a – такий певний елемент, що коли формула x P(x) є істиною, то формула P(а) також буде істинною. Тоді x P(x), а P(а).

ПРАВИЛО РЕЗОЛЮЦІЇ

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

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

Правило резолюції: якщо в будь-яких двох диз’юнктах А₁ і А₂ існує контрактна пара літер (L і ~L), то викресливши ці літери, можна побудувати диз’юнкцію з тих частин диз’юнктів А₁ і А₂, що залишаться.

Якщо аргументами виступають змінні (х, y), то вони уніфікуються з будь-якими константами.

Приклади:

Контрольні запитання.

1. Сформулюйте задачу автоматичного доведення теорем.

2. Дайте визначення логічної моделі.

3. Дайте визначення предиката.

4. Які основні елементи використовуються в численні предикатів?

5. Що таке квантори узагальнення та існування?

6. Дайте визначення атомарної формули.

7. Дайте визначення диз'юнкта.

8. Що таке фраза Хорна?

9. Поясніть зв'язок фраз Хорна з імплікаціями.

10. Дайте визначення пренексної нормальної форми.

11 Яким чином можна усунути квантори узагальнення та існування?

12. Що таке константи і функції Сколема?

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

14. Сформулюйте правило резолюцій. Наведіть власні приклади застосу­вання цього правила.

15. Що означає виведення пустого диз'юнкта? Яким чином він може бути отриманий?

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

17. Що означає поняття повноти для методу резолюцій?

18. З чим пов'язана необхідність модифікації загального методу резолюцій?

19. Охарактеризуйте лінійну і вхідну резолюції. Покажіть, що вони не усу­вають бектрекінгового перебору.

20. Чи є вхідна резолюція повною? Наведіть клас диз'юнктів, для яких вона є повною.

21. Охарактеризуйте поняття логічного програмування.

22. Назвіть найпоширенішу мову логічного програмування.

23. Поясніть взаємозв'язок прологівських фактів і правил з фразами Хорна.

Література.

1. Глибовець М.М., Олецький О.В. Штучний інтелект. –К.: КМ Академія, 2002. –с. 66-93.

2. Ходаков В.Є., Пилипенко М.В., Соколова Н.А. Вступ до комп’ютерних наук. –К.: Центр навчальної літератури, 2005. –496с.

3. Попов Э.В. Экспертные системы. М.: Наука, 1987.

4. Хейес-Рот Ф., Уотерман Д., Ленат Д. Построение экспертных си­стем. М.: Мир, 1987.

5. Стефанюк В.Л. Некоторые аспекты теории экспертных систем// Известия АН СССР. Техническая кибернетика, 1987. №2. С. 85-91.

6. Поспелов Д.А. Ситуационное управление: Теория и практика. М.: Наука, 1986.

7. Элти Дж., Кумбс Н. Экспертные системы: концепция и примеры. М.: Финансы и статистика, 1987.

8. Искусственный интеллект: Справочник. В 3-х томах. М.: Радио и связь, 1990.

Тема: Нечітка модель подання знань. Подання знань у штучній нейромережі. Стратегії та методи виведення знань.

Мета:ознайомлення з нечіткими моделями подання знань та штучними нейронними мережами.

Поиск по сайту: