LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Формалізоване проектування природно-мовних діалогових комп'ютерних систем

називаються змінними типу "статус задачі" чи просто S–змінними та змінні P1, P2, …, Pn, …, які називаються змінними типу "стан задачі" чи просто P–змінними.

Атомарним виразом (чи А-виразом) будемо називати вираз виду (u, v), де

u– чи s–змінна, чи одна з констант n, un;

v- чи р–змінна, чи одна з констант t, i, f.


Комплексним виразом (чи С-виразом) будемо називати вираз виду (A1, …, An), де A1, …, An - атомарні вирази.

Наприклад, С-виразами є вирази: ((s1, p1)), ((s1, p1), (n, p2), (un, f)).

Тепер введемо поняття передформул опціональної логіки. Передформули визначаються рекурсивно такими правилами:

  • А-вираз є передформулою;

  • Заміна р-змінної в будь-якій передформулі на С-вираз також є передформулою.

Наприклад, передформулами є вирази (s1, p1), (s1, ((s2, p2), (s3, p3))), (s1, ((s2, ((s4, p4), (s5, p5), (s3, p3)).

Введемо поняття формули опціональної логіки. Формула опціональної логіки визначається рекурсивно такими правилами:

Вираз виду t F,

де t - спеціальний символ, який називається оператором стану, а F – передформула, є формулою. Нехай формула F містить рядок: t ( (u1, E1), …, (un, En) ), де ui, i = 1, …, n– чи s–змінна, чи одна з констант n, un, а Ei, i = 1, …, u– чи p–змінна, чи передформули, тоді заміна в формулі F наведеного вище виразу на вираз: t ( t(u1, E1), t(u2, E2), …, t(un, En) ) також є формулою опціональної логіки.

Константи t, i, f є формулами.

Вирази виду: V1 l1 V2l2 … lk-1 Vk, де V1, ..., Vk – константи t, i, f, чи р – змінна, а l1, …, lk-1 – чи символ Щ, чи символ Ъ, є формулами.

Наприклад, формулами опціональної логіки є вирази: t ( s1, ((s2,p2), (s3, p3)) ), t ( s1, t ((s2,p2), (s3, p3)) ), t ( s1, t (t (s2,p2), t (s3, p3)) ), p1 Щ t Щ p2 Ъ f Ъ i Ъ pn.

Введемо поняття еквівалентних формул опціональної логіки. Еквівалентність формул F1 і F2 будемо позначати F1 = F2. Постулюємо еквівалентність деяких формул.

Аксіома 10.


t(s, i) = i; t(s, f) = f; t(s, t) = t;

t(n, i) = i; t(n, f) = f; t(n, t) = t;

t(un, i) = i; t(un, f) = f; t(n, t) = t;

Аксіома 11.

Нехай в формулу F входить вираз виду t( (u1, E1), …, (un, En) ).

Замінимо в формулі F цей вираз на виразt( t (u1, E1), …, t (u1, En) ).

Отриману формулу F1 будемо вважати еквівалентною формулі F.

Аксіома 12.

t( t (n, u1), …, t (n, uk) ) = u1 Щ … Щ uk, де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 13.

t( t (un, u1), …, t (un, uk) ) = u1 Ъ … Ъ uk, де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 14.

t( t (u, u1), …, t (n, um), t (un, um+1), …, t (un, uk) ) = t(u1) Щ … Щ t(um), де ui, i = 1, …, k чи одна з констант t, i, f, чи р-змінна.

Аксіома 15.

Нехай в формули F і F1 входять одні й тіж s-змінні та р-змінні. Замінимо кожну s-змінну в F і F1 на одну й ту ж константу з множини {n, un}, а кожну р-змінну на одну й ту ж константу з множини {t, i, f}. Отримані таким чином формули позначимо через та .

Якщо виявиться, що і чи і чи і то будемо вважати, що формули і еквівалентні.

Аксіома 16.

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

Дамо, нарешті, визначення опціональної логіки.

Визначення.

Кортеж < F, = >, де F - множина формул, а = - відношення еквівалентності формул. будемо називати опціональною логікою, якщо виконуються аксіоми 10 - 17.

Мають місце такі теореми:


Теорема 2.

Якщо формула опціональної логіки не містить s-змінних і р-змінних, то вона еквівалентна одній з формул:

t, i, f.


Теорема 3.

Система аксіом опціональной логіки 10 - 16 несуперечлива.


Нехай В – цільова структура. Поставимо у відповідність усякій задачі хi цільової структури змінну рi опціональної логіки. Нехай ця відповідність встановлюється оператором l, тобто для будь-якої задачі х, р = l(х).

Нехай В - цільова структура.

Тоді будь-якій задачі х О Х можна поставити у відповідність формулу опціональної логіки F, яка містить тільки змінні асоційовані з тривіальними задачами цільової структури.

При цьому, якщо t (х) = С, де С О {t, i, f}, то формула F еквівалентно логіці еквівалентна С.

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

Аналізуючи логічну структуру, діалоговий engine (DE) задає питання користувачу, аналізує його, змінює зовнішній світ і повідомляє інформацію про його стан.

Мета діалогу – розв'язання деякої задачі.

Саме в процесі розв'язання задачі і виникає діалог із користувачем.

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

Логічна структура - це дерево підзадач. Кожна підзадача зображається вершиною (вузлом) у цьому дереві. Ці вершини (підзадачі) позначаються

символом n (necessary – обов'язкова вершина) або символом un (unnecessary – необов'язкова вершина)

Позначка n означає, що підзадача є необхідною для материнської задачі. Іншими словами її розв'язання є обов'язковим для розв'язання материнської задачі.

Позначка un означає, що підзадача не є необхідною для материнської задачі. Тобто її розв'язання не є обов'язковим для розв'язання материнської задачі.

Відзначимо відразу, що будь-яка вершина дерева (підзадача) у кожний момент часу може знаходитися в одному із трьох станів:

t (true) - задача розв'язана позитивно;

f (false) - задача розв'язана негативно;

i (indefinite) - невизначений стан, тобто підзадача ще не розв'язувалася.


В четвертому розділі наведено