Z3py: преобразовать формулу Z3 в предложения, используемые picosat
ССЫЛКИ:
Z3 доказатель теоремы
пикосат с привязками pyhton
Я использовал Z3 в качестве SAT-решателя. Для больших формул, похоже, есть проблемы с производительностью, поэтому я хотел проверить picosat, чтобы увидеть, является ли это более быстрой альтернативой. Мой существующий код Python генерирует пропозициональную формулу в синтаксисе z3:
from z3 import *
import pycosat
from pycosat import solve, itersolve
#
#1 2 3 4 5 6 7 8 (variable names in picosat are numbers!)
#
C, G, M, P, R, S, SN, B = Bools('C G M P R S SN B')
C = (And(*(S,Or(Not(S),P),Or(Not(P),S),Or(Not(P),B),Or(Not(C),P),Or(Not(G),P),Or(Not(M),P),Or(Not(R),P),Or(Not(SN),P),Or(Not(B),P),True,Not(False),Or(R,SN,B,G,M,C,True))))
# formula in Z3:
f = simplify(C)
print f
ВЫХОД / РЕЗУЛЬТАТ
And(S,
Or(Not(S), P),
Or(Not(P), S),
Or(Not(P), B),
Or(Not(C), P),
Or(Not(G), P),
Or(Not(M), P),
Or(Not(R), P),
Or(Not(SN), P),
Or(Not(B), P))
Однако Picosat использует списки / массивы чисел, как показано в следующем примере ("clauses1": 6 относится к переменной P, -6 означает "не P" и т. Д.):
import pycosat
from pycosat import solve, itersolve
#
# use pico sat
#
nvars = 8
clauses =[
[6],
[-6, 4], ## "Or(Not(S), P)" from OUPUT above
[-4, 6],
[-4, 8],
[-1, 4],
[-2, 4],
[-3, 4],
[-5, 4],
[-7, 4],
[-8, 4]]
#
# efficiently find all models of the formula
#
sols = list(itersolve(clauses, vars=nvars))
print "result:"
print sols
print "\n\n====\n"
Что вы порекомендуете в качестве простого решения для преобразования переменной Z3 (например, переменной "f" из примера кода), представляющей формулу в CNF, в вышеупомянутый формат, используемый picosat для представления формул в CNF? Я действительно пытался использовать Python API Z3, однако документации было недостаточно, чтобы решить проблему самостоятельно.
(Обратите внимание, что приведенный выше пример просто иллюстрирует концепцию. Формула, представленная переменной C, будет сгенерирована динамически и будет слишком сложной для эффективной обработки непосредственно z3)
1 ответ
Во-первых, мы должны преобразовать формулу Z3 в CNF. Следующий пост решает эту проблему
Чтобы преобразовать формулу Z3 CNF в Dimacs, мы можем просто написать функцию, которая обходит ее и генерирует список целых чисел. Следующие два поста описывают, как пройти формулы Z3
- Подстановка функциональных символов в формулах z3
- Есть ли способ запроса или доступа к структуре выражения Z3 через API
Наконец, если вам нужны карты из выражений в значения, вы можете использовать следующий подход