DemonScript: Пространственные отношения

Введение

Рассмотрим четыре отношения, которые составляют основу описания относительного расположения объектов в пространстве:

• X in Y - объект X находится где-то в объекте Y. При этом Y полностью окружает своей оболочкой объект Х (Х не "выглядывает" наружу). Если X in Y, то при перемещении объекта Y в пространстве, вместе с ним переместится и объект Х. Для этого отношения выполняется свойство транзитивности, т.е. подразумевается возможность вложения объектов подобно матрёшкам (если ключ в шкатулке, а шкатулка в сундуке, то ключ и в сундуке).
• X ins Y - объект Х находится непосредственно внутри объекта Y (если мы заглянем в Y, то увидим Х). Это отношение похоже на in, но не обладает свойством транзитивности (в примере выше ключ ins сундук будет ложным).
• X above Y - все части объекта Х находятся выше всех частей объекта Y. Выше понимается в обыденном смысле — выше по вертикали против направления силы гравитации.
• X оn Y - объект Х находится на горизонтальной поверхности объекта Y, имея с ней контакт, внутри которого нет других объектов.

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

Примеры

Ниже приведен пример для отношений in и ins (a внутри b, b внутри c и d вне всех остальных). Справа от рисунка записаны пары объектов для которых отношения истинны (первая колонка) и для которых они ложны (вторая колонка). Ложное отношение, как обычно, помечается восклицательным знаком "!":

Например, (a in c) истинно (транзитивность). В тоже время (a ins c) ложно (a находится не непосредственно внутри c, а через вложение в b). Аналогичны примеры для отношений above, on:

Объекты выше изображены прямоугольниками, символизирующими некоторые ящики. Это может быть реальный ящик (коробка, сундук) или воображаемый параллелепипед, полностью окружающий объект. Подчеркнём, что эти отношения применяются к закрытым ящикам. В частности, для истинного отношения X ins Y, объект X не может выглядывать за Y. Если один ящик ставится на другой (X on Y), то он не "проваливается вниз" (есть крышка у Y). Наконец, отношение X above Y будет ложным, если хотя-бы часть объекта Х не выше объекта Y.

Для закрытых ящиков возможны вполне корректные (и многочисленные) модели в которых данное отношение ложно (ниже первые три примера). Однако, можно нарисовать картинки, которые запрещены в принципе (последние два примера):

Для двух ящиков Х и Y существует 9 вариантов из расположения (X непосредственно внутри Y, X вложен в Y и т.д.):

На второй картинке ящик Х окружён пунктиром. Это подчеркивает, что в общем случае между ним и ящиком Y могут быть другие ящики, вложенные друг в друга. Аналогично для Y на четвёртой картинке. Мы не ограничиваем относительных размеров ящиков (за исключением возможности их вложения ins, in). Поэтому в последнем примере, при ложности отношения выше X above Y и Y above Х, не принципиально кто из ящиков больше или "чуть выше" (они нарисованы одинаковыми и на одном уровне).

True, False и Undef

Задание отношений не всегда однозначно фиксирует модель. Это означает, что данному множеству отношений может удовлетворять несколько различных "картинок" (= моделей). Например, пусть известно, что Y непосредственно находится внутри Z, а X - выше Y. Этой информации удовлетворяет пять моделей:

Ящик Х, находящийся выше Y, может быть как внутри Z, так и не вне его (но выше Y). Отношения, приведенные справа от рисунков, в одних моделях истинные, а в других ложные. Поэтому в вероятностной логике для них используется значение "возможно"= Undef. Истинность такого отношения не доказуема, но не доказуема и его ложность.

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

Аксиоматика отношения in

Отношение in образует строгий древесный порядок. Ниже на рисунке приведена система вложенных друг в друга ящиков. Если нарисовать отношение непосредственного вложения ins, то получится древесный граф. С учётом транзитивности, в графе отношения in добавляются ещё рёбра A-E и B-E (последний рисунок):

Графы выше приведены в традиционном для математики виде (указаны только истинные рёбра). Первый граф фактически является диаграммой порядка для отношения in (не рисуются рёбра транзитивности), а второй - графом отношения in на котором указаны все True рёбра отношения.

Напомним, что в трёхзначной логике (True, False, Undef) мы придерживаемся, вообще говоря, иного соглашения. Если значение отношения известно (True или False) ребро рисуется явным образом (и для False помечается восклицательным знаком). Если же ребра нет, это означает Undef (не известно, но не запрещено, ни значение True, ни значение False).

Для полного описания строго древесного порядка in необходимы три аксиомы:

• (1) in антирефлексивно: сам в себя не находится;
• (2) in транзитивно: если истинно, что Х в Z, и Z в Y, то истинно, что Х в Y;
• (3) in древесно: если Z находится в Х и Y, то, либо Х в Y, либо Y в Х, либо Х и Y один ящик.

В DemonScript аксиомы отношения in записываются следующим образом:

edges in, ins, on, above, below;                  // декларируем отношения

var X,Y,Z                                         // переменные для аксиом
Mind.add(                                    
   !(X in X),                                     // (1) антирефлексивно    
    (X in Z) & (Z in Y) -> (X in Y),              // (2) транзитивно
    (Z in X) & (Z in Y) -> (X in Y) | (Y in X) | (X==Y)   // (3) дерево
)

Заметим, что из первой и второй аксиомы следует свойство асимметричности: (Y in X) -> !(X in Y) (если Y в X, то X не в Y). Действительно, положив X=Y в аксиоме транзитивности (2) и записав её в КНФ, имеем:

   !(X in Z) | !(Z in X) | (X in X)    =>    !(X in Z) | !(Z in X)   =>   (X in Z) -> !(Z in X),

Аксиоматика отношения ins

Добавим отношение непосредственного вложения ins, которое в языковых конструкциях будем обозначать предлогом "внутри", в отличии от предлога "в" для отношения in. Отношение ins антирефлексивно и асимметрично однако не обладает транзитивностью (далее опускаем Mind.add(...)):

   !(X ins X),                                     // (4) антирефлексивно
    (Y ins X) -> !(X ins Y)                        // (5) асимметрично

Справедлива ещё одна "аксиома единственности": если истинно, что Х находится внутри Z, то он не может находится внутри другого Y, который не есть Z:

    (X ins Z) & (Z!=Y) -> !(X ins Y)               // (6) единственность

Свяжем теперь отношение ins с отношением in. Очевидно, что, если Х непосредственно (ins) внутри Y, то оно находится и где-то в (in) Y (но не наоборот!):

    (X ins Y) -> (X in Y),                         // (7) если "внутри", то "в"

Должны также выполняться две аксиомы, примеры для которых приведены на рисунках выше:

    (X in Z) &  (Z in Y) -> !(X ins Y),            // (8)
    (X in Z) & !(Y in Z) & (Y != Z) -> !(X ins Y)  // (9)

Тестируем in и ins

Решим следующую задачу. Пусть известно, что ящик "a" находится где-то в ящике "c", ящик "b" не находится в "c". Какие выводы из этой информации можно сделать? Понятно, что возможны две модели. В одной ящик "b" находится вне ящика "c", а в другой ящик "c" находится в "b" (и "b", соответственно, в "c" также не находится). Эти модели приведены на рисунках справа.

Получим решение при помощи DemonScript:

var G = GRAPH("G")                                // создаём пустой граф
GRAPH = G                                         // делаем его текущим
nodes a,b,c                                       // добавляем в него три узла

a  in c;                                          // а находится в c
b !in c;                                          // b не находится в c

out G                                             // выводим исходный граф
Mind.set_graph(G)                                 // запускаем логический вывод             
out G                                             // выводим финальный граф

   G { 
      a {  in: [c]  },
      b {  in: [!c] },
      c {}          }

   G {
      a{ in: [c,!a],      ins: [!a,!b],    },
      b{ in: [!c,!b,!a],  ins: [!b,!c,!a], },
      c{ in: [!c,!a],     ins: [!c,!a],    } }

Например, !a in a или a in a == False (это сработала аксиома антирефлексивности). Более нетривиальный вывод !a ins b, т.е. ящик "a" не может находиться непосредственно внутри "b" (т.к. b не находится в "c", где находится "a"). Ещё один важный вывод: !b in a ("b" не может находиться в "a").

При этом a ins c, в отличии от a in c, имеет неопределённое значение ("c" отсутствует в массиве a { ins: [...] }). Это связано с тем, что информация a in c; означает, что "a" находится где-то в "c", т.е. не обязательно непосредственно внутри "c"). Если мир не замкнут (могут существовать другие ящики), то между "a" и "c" может оказаться ящик (а может и не оказаться). Именно поэтому отношение a ins c имеет неопределённое значение.

Аналогично стоит проанализировать остальные результаты вывода.

Для аналогичной задачи с отношениями ins результат другой. В этом случае условиям соответствует уже три модели.

G.clear_edges()                                   // очищаем рёбра
a  ins c;                                         // а находится непосредственно внутри c
b !ins c;                                         // b не находится непосредственно внутри c

G { 
   a{  in: [!a,c],  ins: [c,!a,!b], },
   b{  in: [!b],    ins: [!c,!b],   },
   c{  in: [!c,!a], ins: [!c,!a],   } }

Аксиоматика отношения above

Отношения above, как и in, образует строгий частичный порядок, но древесного ограничения для него нет. Оно антирефлесивно, транзитивно (и, следовательно, асимметрично):

   !(X above X),                                  // (10) антирефлексивно
    (X above Z) & (Z above Y) -> (X above Y)      // (11) транзитивно

    (X in Y) -> !(X above Y),                     // (12)
    (Y in X) -> !(X above Y),                     // (13)

    (X in Z)    & (Z above Y) -> (X above Y),     // (14)
    (X above Z) & (Y in Z)    -> (X above Y)      // (15)

Аксиоматика отношения on

Отношение on антирефлексивно и асимметрично, но, как и ins, транзитивностью не обладает:

  !(X on X),                                      // (16) антирефлексивно
   (Y on X) -> !(X on Y),                         // (17) асимметрично

   (X on Y) -> (X above Y),                       // (18)

Если между Х и Y "вклинивается" третий объект Z, то отношение X on Y запрещено:

   (X above Z) & (Z above Y) -> !(X on Y),        // (19)
    
   (X in Z) & !(Y in Z) & (Y != Z) -> !(X on Y),  // (20)
  !(X in Z) &  (Y in Z) & (X != Z) -> !(X on Y)   // (21)

Ещё два правила выглядят понятнее, если их записать не как запрещающие для on, а как разрешающие для ins:

   (X on Z) & (Z ins Y)  ->  (X ins Y),           // (22)
   (Z on X) & (Z ins Y)  ->  (X ins Y)            // (23)

На этом аксиоматика отношений in, ins, above и on окончена.

Аксиоматика отношения below

Для полноты картины добавим также аксиомы для отношения below:

    (Y above X) -> (X below Y),                   // (24)
    (Y below X) -> (X above Y)                    // (25)

Тест для всех отношений

G.clear_edges()                                   // очищаем рёбра
nodes d                                           // добавляем ещё один узел

a ins c;
b on  c;
d below c;

Mind.set_graph(G)
out G

   a{ in: [!a,c,!d],  ins: [c,!a,!b,!d],   on: [!a,!c,!b,!d],  above: [!a,!c,d],    below: [!a,!c,!d]},
   b{ in: [!b,!a,!d], ins: [!b,!a,!c,!d],  on: [c,!b,!a],      above: [!b],         below: [!b],   },
   c{ in: [!c,!a,!d], ins: [!c,!a,!b,!d],  on: [!c,!b,!a],     above: [!c,!a,d],    below: [!c,!a,!d]},
   d{ in: [!d,!c,!a], ins: [!d,!c,!a],     on: [!d,!a],        above: [!d,!a,!c],   below: [c,!d,a] }

Открытый и закрытый мир

Построенная выше аксиоматика пространственных отношений основывается на модели открытого мира. В такой модели могут существовать объекты, которые не упомянуты в исходной информации. В ряде случаев это может оказаться не удобным. Например, если дополнительно утверждается, что существуют только ящики a,b,c и других нет, то эту информацию также необходимо уметь использовать. Подобная модель называется закрытой. В модели закрытого мира с двумя ящиками "a" и "b" противоречивыми являются факты a in b; a !ins b. В открытой модели они непротиворечивы и означают существование такого "c", что: a in c; c in b.

Чуть более сложный пример. Пусть известно, что

[a, b] ins c; 
d !ins c; d in c;

Закрытый мир реализуется при помощи построения всех возможных, полностью определённых моделей. Для этого в Mind существует метод .get_models. Впрочем часть сгенерённых им моделей, при наличии нескольких отношений, по-прежнему будут "открытыми".

Заключительные замечания

      A & B -> C    <=>     !С & B -> ! A       <=>     A & !C -> В.