Z3 contains an extension called muZ with fixed-point constraints. This tutorial includes some examples that demonstrate features of this engine. The following papers μZ - An Efficient Engine for Fixed-Points with Constraints. (CAV 2011) and Generalized Property Directed Reachability (SAT 2012) describe some of the main features of the engine. Be sure to follow along with the examples by clicking the "edit" link in the corner. See what the tool says, try your own formulas, and experiment! Please send feedback, comments and/or corrections to firstname.lastname@example.org.
This tutorial covers some of the fixedpoint utilities available with Z3. The main features are a basic Datalog engine, an engine with relational algebra and an engine based on a generalization of the Property Directed Reachability algorithm, as well as the Duality engine.
The default fixed-point engine is a bottom-up Datalog engine. It works with finite relations and uses finite table representations as hash tables as the default way to represent finite relations.
(declare-rel a ()) (declare-rel b ()) (declare-rel c ()) (rule (=> b a)) (rule (=> c b)) (set-option :fixedpoint.engine datalog) (query a) (rule c) (query a :print-answer true)The example illustrates some of the basic constructs.
(declare-rel a ())declares a 0-ary relation a.
(rule (=> b a))Create the rule that a follows from b. In general you can create a rule with multiple premises and a name using the format
(rule (=> (and b c) a) name)The name is optional. It is used for tracking the rule in derivation proofs. Continuing with the example, a is false unless b is established.
(query r)Asks if relation a can be derived. The rules so far say that a follows if b is established and that b follows if c is established. But nothing establishes c and b is also not established, so a cannot be derived.
(rule c)Now it is the case that a can be derived.
Relations can take arguments. We illustrate relations with arguments using edges and paths in a graph.load in editor
(set-option :fixedpoint.engine datalog) (define-sort s () (_ BitVec 3)) (declare-rel edge (s s)) (declare-rel path (s s)) (declare-var a s) (declare-var b s) (declare-var c s) (rule (=> (edge a b) (path a b))) (rule (=> (and (path a b) (path b c)) (path a c))) (rule (edge #b001 #b010)) (rule (edge #b001 #b011)) (rule (edge #b010 #b100)) (declare-rel q1 ()) (declare-rel q2 ()) (declare-rel q3 (s)) (rule (=> (path #b001 #b100) q1)) (rule (=> (path #b011 #b100) q2)) (rule (=> (path #b001 b) (q3 b))) (query q1) (query q2) (query q3 :print-answer true)The example uses the declaration
(declare-var a s)to instrument the fixed-point engine that a should be treated as a variable appearing in rules.
McCarthy's 91 function illustrates a procedure that calls itself recursively twice. The Horn clauses below encode the recursive function:
mc(x) = if x > 100 then x - 10 else mc(mc(x+11))The general scheme for encoding recursive procedures is by creating a predicate for each procedure and adding an additional output variable to the predicate. Nested calls to procedures within a body can be encoded as a conjunction of relations. load in editor
(declare-rel mc (Int Int)) (declare-var n Int) (declare-var m Int) (declare-var p Int) (rule (=> (> m 100) (mc m (- m 10)))) (rule (=> (and (<= m 100) (mc (+ m 11) p) (mc p n)) (mc m n))) (declare-rel q1 (Int Int)) (rule (=> (and (mc m n) (< n 91)) (q1 m n))) (query q1 :print-certificate true) (declare-rel q2 (Int Int)) (rule (=> (and (mc m n) (not (= n 91)) (<= m 101)) (q2 m n))) (query q2 :print-certificate true) (declare-rel q3 (Int Int)) (rule (=> (and (mc m n) (< n 92)) (q3 m n))) (query q3 :print-certificate true)The first two queries are unsatisfiable. The PDR engine produces the same proof of unsatisfiability. The proof is an inductive invariant for each recursive predicate.
A self-contained example that exercises the .NET API over C# is provided as a separate download.
Three different text-based input formats are accepted.
Files with suffix .datalog are parsed using the BDDBDDB format. The format can be used for comparing benchmarks with the BDDBDDB tool.
We use an artificial program to illustrate the basic Datalog format that complies to the format used by BDDBDDB.
Z 64 P0(x: Z) input Gt0(x : Z, y : Z) input R(x : Z) printtuples S(x : Z) printtuples Gt(x : Z, y : Z) printtuples Gt(x,y) :- Gt0(x,y). Gt(x,y) :- Gt(x,z), Gt(z,y). R(x) :- Gt(x,_). S(x) :- Gt(x,x0), Gt0(x,y), Gt0(y,z), P0(z). Gt0("a","b"). Gt0("b","c"). Gt0("c","d"). Gt0("a1","b"). Gt0("b","a1"). Gt0("d","d1"). Gt0("d1","d"). P0("a1").
(set-logic HORN) (declare-fun mc (Int Int) Bool) (assert (forall ((m Int)) (=> (> m 100) (mc m (- m 10))))) (assert (forall ((m Int) (n Int) (p Int)) (=> (and (<= m 100) (mc (+ m 11) p) (mc p n)) (mc m n)))) (assert (forall ((m Int) (n Int)) (=> (and (mc m n) (<= m 101)) (= n 91)))) (check-sat) (get-model)Note the following:
You can interact with muZ over the programmatic API from Python, C, OCaml, Java, and .NET. The APIs support adding rules and posing queries.