Распространение рекурсивного свойства, если все предшественники ему удовлетворяют

Question

Я работаю над направленным ациклическим c графом, где узел может удовлетворять свойству. Я хочу рекурсивно распространить это свойство на другие узлы. Правило состоит в том, что узел удовлетворяет этому свойству тогда и только тогда, когда ему удовлетворяют все его прямые предшественники. Мне нужно, чтобы ВСЕ родители удовлетворяли его для распространения.

satisfies(node) :- isParent(parent, node), satisfies(parent).

То, что я пробовал:

• вместо этого написал правило doesNotSatisfy, которое будет работать, но сделав это, я столкнулся с той же проблемой в другом месте программы

• , отрицая это с помощью !, но это дало мне cycli c отрицания

Что помогло мне в прошлом с регистрацией данных, так это решить проблему естественным образом как человек на бумаге. Но здесь я не вижу другого пути, кроме как попытаться удовлетворить правило «для всех».

Это как-то возможно в журнале данных? И если да, то как?

Answer 1

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

1. forall p = ! exists ! p, которые, кажется, вы уже поняли
2. разделение базового свойства и производного свойства

Вот очень общий c пример, который вы можете легко адаптировать.

Вот простой график: узлы с + обладают свойством basi c (базовый случай). Те, у которых отмечены * - это те, для которых все преемники удовлетворяют этому свойству.

1 -- 2 -- 3 * --- 5 + *
     |\    \----- 6 + *
     | \-- 4 * -- 8 + *
     \---- 7

Сначала закодируйте граф.

transition(1,2).
transition(2,3).
transition(2,4).
transition(3,5).
transition(3,6).
transition(2,7).
transition(4,8).

Вспомогательный для перечисления всех узлов.

node(Node) :- transition(Node, _).
node(Node) :- transition(_, Node).

Отметьте базовый вариант (+ узлов).

property(5).
property(6).
property(8).

Найдите узлы, которые не имеют свойства.

notProperty(Node) :- node(Node), ! property(Node).

Теперь мы выясняем * узлов . Либо мы знаем это банально через property(Node). Или что мы можем перейти к узлу, где это свойство не выполняется.

propertyDerived(Node) :- property(Node).
propertyDerived(Node) :- transition(Node,Next), ! notProperty(Next).

Программа может избежать циклического отрицания, потому что я отделил propertyDerived от property, что в вашем примере сбит с толку.

Теперь, если вы запросите, вы получите то, что ожидаете!

?- propertyDerived(Node).
 3
 4
 5
 6
 8