Z3 Forall mit Array

Question

Z3 bietet Unbekanntes für das einfache Problem:

(assert
(forall ((y (Array Int Int)))
   (= (select y 1) 0))
 )
(check-sat)

Ich habe festgestellt, dass es gesessen wird, wenn das negiert wird forall, aber dies scheint eine besonders einfache Sache zu sein, die man nicht lösen kann.

Dies verursacht Probleme, weil die Klasse von Problemen, die ich lösen möchte, eher wie folgt ist:

(declare-fun u () Int)
(assert
 (forall ((y (Array Int Int)) )
     (=> 
        (= u 0) (<= (select y 1) 0))
 )
)
(check-sat)

Wo das Negieren des Foralls allein nicht das gleiche Problem ist, kann das hier nicht gemacht werden. Gibt es eine Möglichkeit, Z3 diese Art von Problem zu stellen, um ein un / sat-Ergebnis zu erzielen?

Answer 1

Probleme mit Quantifizierern sind bei SMT-Lösern immer problematisch, insbesondere wenn es sich um Arrays und alternierende Quantifizierer handelt, wie in Ihrem Beispiel. Sie haben im Wesentlichen exits u. forall y. P(u, y). Z3 oder ein anderer SMT-Löser wird Schwierigkeiten haben, mit solchen Problemen umzugehen.

Wenn Sie eine quantifizierte Behauptung haben, wie Sie es tun, wenn Sie forallentweder auf der obersten Ebene oder verschachtelt sind exists, wird die Logik halbentscheidbar. Z3 verwendet MBQI (modellbasierte Quantifiziererinstanziierung), um solche Probleme heuristisch zu lösen, aber dies schlägt meistens fehl. Das Problem ist nicht nur, dass z3 nicht in der Lage ist: Es gibt kein Entscheidungsverfahren für solche Probleme, und z3 gibt sein Bestes.

Sie können versuchen, Quantifizierungsmuster für solche Probleme anzugeben, um z3 zu helfen, aber ich sehe keinen einfachen Weg, dies in Ihrem Problem anzuwenden. (Quantifizierermuster gelten, wenn Sie nicht interpretierte Funktionen und quantifizierte Axiome haben. Siehehttps://rise4fun.com/z3/tutorialcontent/guide#h28). Also denke ich nicht, dass es für dich funktionieren wird. Selbst wenn dies der Fall ist, sind Muster sehr schwierig zu programmieren und nicht robust gegenüber Änderungen in Ihrer Spezifikation, die ansonsten harmlos aussehen könnten.

Wenn Sie mit solchen Quantifizierern arbeiten, sind SMT-Löser wahrscheinlich einfach nicht gut geeignet. Schauen Sie sich halbautomatische Theorembeweiser wie Lean, Isabelle, Coq usw. an, die darauf ausgelegt sind, Quantifizierer viel disziplinierter zu behandeln. Natürlich verlieren Sie die vollständige Automatisierung, aber die meisten dieser Tools können einen SMT-Solver verwenden, um Teilziele zu entladen, die "einfach" genug sind. Auf diese Weise erledigen Sie das "schwere Heben" immer noch manuell, aber die meisten Unterziele werden automatisch von z3 behandelt. (Insbesondere bei Lean siehe hier:https://leanprover.github.io/)

Answer 2

Es gibt eine zusätzliche schließende (rechte) Klammer, die entfernt werden muss. Fügen Sie außerdem assert vor der forall-Anweisung hinzu.

(assert ( forall ( (y (Array Int Int) ) ) 
   (= (select y 1) 0) 
))
(check-sat)

Führen Sie den obigen Code aus und Sie sollten unsat als Antwort erhalten.

Für das zweite Programm kann die Antwort des Alias ​​für Sie hilfreich sein.