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

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

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

Логика событий — формализм для моделирования знаний в динамических интеллектуальных системах. Помимо обычных логических связок в этот формализм включены 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)} формально выражает вышеуказанное знание.