Проблемы с функцией TransitiveClosure в Z3Py

Я пытаюсь смоделировать графическое соединение с Z3. В частности, я разбиваю граф и хочу, чтобы подграфы оставались связанными. Однако TransitiveClosure работает не так, как я ожидал. Я моделирую кромки буквой F

Вот MWE:

s = Solver()
N = DeclareSort('N')
a,b,c = Consts('a b c', N)
F = Function(N,N,BoolSort())
s.add(F(A,B) == True)
s.add(F(B,A) == True)

s.add(F(B,C) == False)
s.add(F(C,B) == False)
s.add(F(A,C) == False)
s.add(F(C,A) == False)

s.add(A != B, B != C, C != A)

FX = TransitiveClosure(F)
s.add(FX(A,C))

Очевидно, это SAT, что для меня не имеет особого смысла. Если я изменю s.add(FX(A,C)) на s.add(Not(FX(A,C))).

Почему это? C не должен быть членом FX. Я как-то выставляю FX(A,C) == True), добавляя в модель? Почему это не противоречит определению FX.

Линии вывода / подключения модели трудно понять, поэтому я не совсем уверен, что происходит.


person Pangurbon    schedule 28.01.2021    source источник
comment
Я не уверен, что TransitiveClosure должен работать с произвольными / бесконечными доменами, такими как IntSort(). Я подозреваю, что это может сработать только в том случае, если основной сортировкой является новое объявление сортировки. Однако в документации по этому поводу нет ясности, поэтому вы можете спросить на странице github.com/Z3Prover/z3 / issues, чтобы получить более точный ответ. Если вы это сделаете, опубликуйте обновление!   -  person alias    schedule 28.01.2021
comment
Хорошо, это имеет смысл. Я переключил его на неинтерпретируемую сортировку с одной константой на вершину. Если я сделаю то же самое с этим новым сортом, я все равно получу SAT, хотя не должен. Если я установил для всех других функций края значение false, почему я должен был утверждать, что существует транзитивное замыкание двух разъединенных? Я обновлю приведенный выше код, когда вернусь домой.   -  person Pangurbon    schedule 28.01.2021


Ответы (1)


Я также работаю с tclosures и считаю это полезным: https://theory.stanford.edu/%7Enikolaj/programmingz3.html#sec-transitive-closure

Может быть, есть ответ и на твой второй вопрос.

person Vladi    schedule 11.02.2021