Метод аналитических таблиц для логики событий

Размещено на http://www.allbest.ru/

Метод аналитических таблиц для логики событий

Г.С. Плесневич

Рассматривается язык представления знаний о событиях, которые можно соединять с помощью обычных булевых связок и темпоральных связок Аллена. Предлагается основанный на методе аналитических таблиц полный алгоритм, выясняющий отношение логического следствия в этом языке. Работа выполнена при поддержке Российского фонда фундаментальных исследований.

1. СИНТАКСИС И СЕМАНТИКА ЯЗЫКА СОБЫТИЙ

Логика событий - формализм для моделирования знаний в динамических интеллектуальных системах. Помимо обычных логических связок в этот формализм включены 7 связок Аллена, выражающих временные (темпоральные) отношения между событиями. (Под событием мы понимаем объект, существующий в некотором интервале времени.

Классический подход Дж.Аллена [1] предполагает, что все моделируемые события свершились и что нас интересуют лишь логические следствия новых качественных соотношений (т.е. соотношений типа "раньше", "в течение", "начиная" и т.п.) из заданных. В логике событий мы можем, однако, делать и выводить условные или альтернативные утверждения о событиях (напр., такие, как "если произошло событие A, то оно совершалось в течение события B или раньше события C").

З а м е ч а н и е. Одно из направлений развития подхода Аллена заключалось в расширения базиса отношений между событиями. В частности, вводились так называемые метрические отношения, т.е. отношения, выразимые в терминах длин интервалов событий (напр., "событие A длилось по меньшей мере 8 минут"),[2,3].

Исходными символами языка событий служат:

переменные, обозначающие события;

логические связки: ~ (отрицание), & (конъюнкция), (дизъюнкция) и -> (импликация);

связки Аллена: b (before - раньше), m (meets - встречает), o (overlaps - перекрывает), s (starts - начинает), e (is equal - равно, точнее, синхронно с), f (finishes - заканчивает);

левая и правая скобки: ( и ).

Элементарными формулами являются:

переменные, обозначающие события;

выражения вида X @ Y, где X, Y - переменные и @ - любая из связок Аллена.

Произвольные формулы языка событий получаются по следующим правилам: элементарные формулы суть формулы;

если f и g - формулы, то формулами также являются: ~f, (f & g), (fg), (f -> g).

Пусть VAR - множество переменных, используемых в данном контексте представления знаний. Интерпретация VAR - это пара I = (u,v) такая, что:

v - функция, назначающая каждой переменной X из VAR истинностное значение v(X) = O или v(X) = 1;

u - частичная функция, назначающая некоторым переменным X из VAR интервал, т.е. пару (t1,t2) моментов времени c условием t1 < t2;

значение u(X) определено тогда и только тогда, когда v(X) = 1.

З а м е ч а н и я: 1. Моменты времени - это элементы типа данных TIME, на котором задано отношение линейного порядка < . В качестве TIME можно взять тип данных INTEGER, REAL или DATE. 2. Мы рассматриваем здесь только события, не могущие быть мгновенными (т.е. ни для какой интерпретации и ни для какого события X не может быть t1 = t2). Это допущение может быть снято, но ценой некоторого утяжеления изложения; 3. Соотношение v(X) = 1 означает, что событие X произошло (при данной интерпретации I), и тогда X наблюдается в интервале u(X).

С каждой переменной X мы ассоциируем два имени X' и X", обозначающие, соответственно, начало и конец интервала события X (если оно произошло). Мы обозначаем через u(X') и u(X") эти моменты времени. Таким образом, u(X) = (u(X'),u(X")).

Функция v(X) называется оценкой переменной X в интерпретации I. Оценка v распространяется по следующим правилам на все формулы вида X @ Y, причем такие, что v(X) = v(Y) = 1.

v(X b Y) = 1 <==> u(X") < u(Y'); v(X m Y) = 1 <==> u(X") = u(Y'); v(X o Y) = 1 <==> u(X') < u(Y') < u(X") < u(Y"); v(X s Y) = 1 <==> u(X') = u(Y') и u(X") < u(Y"); u(X d Y) = 1 <==> u(X') > u(Y') и u(X") < u(Y"); u(X e Y) = 1 <==> u(X') = u(Y') и u(X") = u(Y"); u(X f Y) = 1 <==> u(Y') < u(X') и u(X") = u(Y").

Оценка v на X @ Y считается не определенной, если значения u(X) или u(Y) не определены. Оценку v мы затем распространяем по обычным правилам пропозициональной логики на произвольные формулы:

v(~f) = ~v(f), v(f & g) = v(f) & v(g) и т.д., если значения v(f) и f(g) определены. Таким образом, каждая оценка v является частичной функцией, заданной на множестве всех формул, причем оценка данной формулы не определена тогда и только тогда, когда эта формула содержит хотя бы одну переменную X такую, что u(X) не определено.

Отношение логического следование в логике событий определяется обычным образом: f1, f2,..., fN |== f, если для любой интерпретации I имеет место v(f)= 1 всякий раз, когда все v(fj)= 1 (другими словами, если не существует интерпретации I такой, что все v(fj) = 1, но v(f)= 0 или значение v(f) не определено).

П р и м е р. Запишем в языке логики событий следующее знание: "Если Петр приехал на работу раньше Ивана, то либо Петр ехал на машине, а Иван ехал в метро, причем оба они вышли из дома одновременно, либо Петр вышел из дома раньше Ивана и оба они ехали на машине или оба в метро. Введем события:

A - "Петр ехал на машине", B - "Иван ехал на машине",

С - "Петр ехал в метро", D - "Иван ехал в метро",

E - "Петр вышел из дома", F - "Иван вышел из дома",

G - "Петр приехал на работу", H - "Иван приехал на работу".

Тогда имеем:

(1) A E s A (Если имело место событие "Петр ехал на машине", то событие "Петр вышел из дому" начинает событие "Петр ехал на машине".);

(2) B F s B ;

(3) C E s C ;

(4) D F s D ;

(5) A G f A (Если имело место событие "Петр ехал на машине", то событие "Петр приехал на работу" заканчивает событие "Петр ехал на машине".);

(6) B H f B ;

(7) G b H C & D & (E e F) (E b F) & (A & B C & D).

Таким образом, совокупность формул {(1)-(7)} формально выражает вышеуказанное знание.

2. МЕТОД АНАЛИТИЧЕСКИХ ТАБЛИЦ

Метод аналитических таблиц - один из основных методов логической дедукции [4], приобретший в последнее время значительную популярность у исследователей искусственного интеллекта. Мы применим метод аналитических таблиц (с соответствующей его модификацией) к логике событий.

Правила вывода по методу аналитических таблиц определим для означенных формул. Означенная формула - это формула логики событий, снабженная знаком плюс или знаком минус, т.е. +f или -f, где f - формула логики событий.

Для пропозициональных связок правила вывода задаются так же, как и при обычном применении метода аналитических таблиц (см. табл. 1). Доказательство логического следования f1, f2,...,fN |== f включает построение дерева (называемого аналитической таблицей), вершинам которого приписаны означенные формулы. Процесс построения начинается с дерева, состоящего из одной ветви с формулами +f1, +f2,..., +fN, -g. Дерево последовательно расширяется при каждом применении правила вывода. Например, если текущее дерево имеет вершину a с приписанной формулой вида +g & h, то при применении третьего правила из табл.1 в вершине a к каждой вершине b, являющейся концом ветви, проходящей через вершину a , достраивается два ребра (b,c) и (c,d) и вершинам c и d приписываются формулы +f и +g, соответственно. (Здесь c и d свои вершины для каждой из вершин b.). Если же вершине a была приписана формула вида -f & g, то к каждой вершине b достраивается вилка", т.е . два ребра (b,c) и (b,d) с приписанными к c и d формулам -f и -g. В процессе построения дерева его ветви тестируются на свойство быть замкнутыми. При стандартном использовании метода аналитических таблиц ветвь считается замкнутой, если она содержит контрарную пару формул, т.е. формулы +f и -f. Но для его использования в языке логики событий необходимо расширить понятие замкнутой ветви.

Ветвь называется замкнутой, если выполняется хотя бы одно из следующих свойств:

(а) ветвь содержит контрарную пару формул +f, -f;

(б) ветвь содержит пару формул -A, +f или -A, -f, где A - событие, а f - элементарная формула со связкой Аллена, содержащая A (т.е. формула вида A @ X или вида X @ A);

(в) ветвь содержит невыполнимое множество элементарных формул со связками Аллена.

Свойства (a) и (б) могут быть проверены непосредственно. Проверка свойства (в) труднее и осуществляется специальным алгоритмом. Суть метода аналитических таблиц применительно к логике событий легко уяснить из следующего примера.

П р и м е р. Доказывая логическое следствие A o D, AB o A, B m C, C m D |== A C d A, мы строим следующее дерево:

Мы видим, что левая ветвь этого дерева замкнута в силу свойства (а), так как она содержит явно противоречивую пару формул +A и -A. Вторая ветвь также замкнута, так как содержит невыполнимое множество формул Ф = {+A o d, +B m C, +C m D, -C d A, +B o A}. Невыполнимость множества Ф устанавливается алгоритмом, который применяется к последовательности его формул, упорядоченной так, чтобы отрицательная формула стояла в конце. Он начинает работу с построения графа Г(0), вершинами которого служат все имена X' и X", где X - любое из событий, входящих в формулы из Ф. Дугами графа Г(0) служат все пары X'X". Дальнейшие шаги алгоритма заключаются в последовательном применения к формулам из Ф. Каждое применение правила к положительной элементарной формуле из Ф состоит в присоединении дуг и/или к стягиванию пар вершин; если же элементарная формула отрицательна, то применение к ней правила состоит в копировании текущего графа Г(i) (столько раз, сколько имеется альтернатив в этом правиле вывода) и в добавление дуг и/или стягивании некоторых пар вершин. Так, результатом применения правила 3 к формуле +A o D служит граф Г(1), полученный из Г(1) присоединением трех дуг A'D', D'A", A"D", а результатом применения правила 2 к формуле +B m C служит граф Г(2), полученный стягиванием вершин B" и C'. После применения правил к четырем формулам (со знаком +) из Ф мы получим граф Г(4) со следующими множествами вершин и дуг: {A',A",B',B", C",D"} и {A'A",A'B',A'C",B'B",B"A",B"C",C"A",C"D"}.

Применение правила 12 к формуле -C d A дает граф Г(5), состоящий из четырех компонент связности Г1, Г2, Г3 и Г4. Эти компоненты получаются, соответственно: (1) стягиванием C' и A'; (2) присоединением дуги C'A'; (3) стягиванием C" и A"; (4) присоединением дуги C"A'. Легко обнаружить, что каждая из этих компонент содержит цикл. (Напр., компонента Г1 имеет цикл A',B',A".) Это означает, что множество формул Ф невыполнимо.

Л е м м а. Пусть Ф - произвольное (конечное) множество означенных элементарных формул, каждая из которых содержит связку Аллена. Пусть Г1, Г2,...,ГN - графы, построенные алгоритмом при его применении к Ф. Тогда множество формул Ф невыполнимо в том и только том случае, если каждый граф Гi содержит цикл.

Т е о р е м а. Метод аналитических таблиц для логики событий является полным методом вывода.

Таблица 1

Таблица 2

аналитическая таблица логический событие

ЛИТЕРАТУРА

1. J.F.Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, vol.26, pp. 832-843, 1983

2.R.Dechter, I.Meiri, and J.Pearl. Temporal constraint networks. Artificial Intelligence, vol.49, pp.353-366, 1991

3. I.Meeri. Combining qualitative and quantitative constraints in temporal reasoning. Techn. rep., Cognitive Systems Laboratory, Comp. Sci. Dept., University of California (USA), 1-50, 1995

4. R.Smullyan. First-Order Logic. Springer-Verlag, 1968

Размещено на Allbest.ru