Debian Codegraph @

examples/python/tutorial/html/advanced-examples.htm

raw
1 <html>
2 <head>
3 <title>Z3Py Advanced</title>
4 <link rel="StyleSheet" href="style.css" type="text/css">
5 </head>
6 <body>
7
8 <h1>Advanced Topics</h1>
9
10 <p>
11 Please send feedback, comments and/or corrections to <a href="mailto:[email protected]">[email protected]</a>.
12 Your comments are very valuable.
13 </p>
14
15 <h2>Expressions, Sorts and Declarations</h2>
16
17 <p>In Z3, expressions, sorts and declarations are called <i>ASTs</i>.
18 ASTs are directed acyclic graphs. Every expression has a sort (aka type).
19 The method <tt>sort()</tt> retrieves the sort of an expression.
20 </p>
21
22 <example pref="expr.1"><html><body>
23 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
24 <span class="n">y</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'y'</span><span class="p">)</span>
25 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
26 <span class="k">print</span> <span class="p">(</span><span class="n">y</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
27 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">&gt;=</span> <span class="mi">2</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
28 </pre></div>
29 </body></html></example>
30
31 <p>The function <tt>eq(n1, n2)</tt> returns <tt>True</tt> if <tt>n1</tt>
32 and <tt>n2</tt> are the same AST. This is a structural test.
33 </p>
34
35 <example pref="expr.2"><html><body>
36 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
37 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span>
38 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">,</span> <span class="n">y</span> <span class="o">+</span> <span class="n">x</span><span class="p">)</span>
39 <span class="n">n</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span>
40 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span>
41 <span class="c"># x2 is eq to x</span>
42 <span class="n">x2</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
43 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x2</span><span class="p">)</span>
44 <span class="c"># the integer variable x is not equal to </span>
45 <span class="c"># the real variable x</span>
46 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">),</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">))</span>
47 </pre></div>
48 </body></html></example>
49
50 <p>The method <tt>hash()</tt> returns a hashcode for an AST node.
51 If <tt>eq(n1, n2)</tt> returns <tt>True</tt>, then <tt>n1.hash()</tt>
52 is equal to <tt>n2.hash()</tt>.
53 </p>
54
55 <example pref="expr.3"><html><body>
56 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
57 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span>
58 <span class="k">print</span> <span class="p">(</span><span class="mi">1</span> <span class="o">+</span> <span class="n">x</span><span class="p">)</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span>
59 <span class="k">print</span> <span class="n">x</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span>
60 </pre></div>
61 </body></html></example>
62
63 <p>Z3 expressions can be divided in three basic groups: <b>applications</b>,
64 <b>quantifiers</b> and <b>bounded/free variables</b>.
65 Applications are all you need if your problems do not contain
66 universal/existential quantifiers. Although we say <tt>Int('x')</tt> is an
67 integer "variable", it is technically an integer constant, and internally
68 is represented as a function application with <tt>0</tt> arguments.
69 Every application is associated with a <b>declaration</b> and contains
70 <tt>0</tt> or more arguments. The method <tt>decl()</tt> returns
71 the declaration associated with an application. The method <tt>num_args()</tt>
72 returns the number of arguments of an application, and <tt>arg(i)</tt> one of the arguments.
73 The function <tt>is_expr(n)</tt> returns <tt>True</tt>
74 if <tt>n</tt> is an expression. Similarly <tt>is_app(n)</tt> (<tt>is_func_decl(n)</tt>)
75 returns <tt>True</tt> if <tt>n</tt> is an application (declaration).
76 </p>
77
78 <example pref="expr.4"><html><body>
79 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
80 <span class="k">print</span> <span class="s">"is expression: "</span><span class="p">,</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
81 <span class="n">n</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">1</span>
82 <span class="k">print</span> <span class="s">"is application:"</span><span class="p">,</span> <span class="n">is_app</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
83 <span class="k">print</span> <span class="s">"decl: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span>
84 <span class="k">print</span> <span class="s">"num args: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">num_args</span><span class="p">()</span>
85 <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="o">.</span><span class="n">num_args</span><span class="p">()):</span>
86 <span class="k">print</span> <span class="s">"arg("</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="s">") -&gt;"</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
87 </pre></div>
88 </body></html></example>
89
90 <p>Declarations have names, they are retrieved using the method <tt>name()</tt>.
91 A (function) declaration has an arity, a domain and range sorts.
92 </p>
93
94 <example pref="expr.5"><html><body>
95 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
96 <span class="n">x_d</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span>
97 <span class="k">print</span> <span class="s">"is_expr(x_d): "</span><span class="p">,</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">x_d</span><span class="p">)</span>
98 <span class="k">print</span> <span class="s">"is_func_decl(x_d):"</span><span class="p">,</span> <span class="n">is_func_decl</span><span class="p">(</span><span class="n">x_d</span><span class="p">)</span>
99 <span class="k">print</span> <span class="s">"x_d.name(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">name</span><span class="p">()</span>
100 <span class="k">print</span> <span class="s">"x_d.range(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
101 <span class="k">print</span> <span class="s">"x_d.arity(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">arity</span><span class="p">()</span>
102 <span class="c"># x_d() creates an application with 0 arguments using x_d.</span>
103 <span class="k">print</span> <span class="s">"eq(x_d(), x): "</span><span class="p">,</span> <span class="n">eq</span><span class="p">(</span><span class="n">x_d</span><span class="p">(),</span> <span class="n">x</span><span class="p">)</span>
104 <span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span>
105 <span class="c"># f is a function from (Int, Real) to Bool</span>
106 <span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">RealSort</span><span class="p">(),</span> <span class="n">BoolSort</span><span class="p">())</span>
107 <span class="k">print</span> <span class="s">"f.name(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">name</span><span class="p">()</span>
108 <span class="k">print</span> <span class="s">"f.range(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">range</span><span class="p">()</span>
109 <span class="k">print</span> <span class="s">"f.arity(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">arity</span><span class="p">()</span>
110 <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">f</span><span class="o">.</span><span class="n">arity</span><span class="p">()):</span>
111 <span class="k">print</span> <span class="s">"domain("</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="s">"): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">domain</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
112 <span class="c"># f(x, x) creates an application with 2 arguments using f.</span>
113 <span class="k">print</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>
114 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">f</span><span class="p">)</span>
115 </pre></div>
116 </body></html></example>
117
118 <p>
119 The built-in declarations are identified using their <b>kind</b>. The kind
120 is retrieved using the method <tt>kind()</tt>. The complete list of built-in declarations
121 can be found in the file <tt>z3consts.py</tt> (<tt>z3_api.h</tt>) in the Z3 distribution.
122 </p>
123
124 <example pref="expr.6"><html><body>
125 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
126 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span><span class="o">.</span><span class="n">kind</span><span class="p">()</span> <span class="o">==</span> <span class="n">Z3_OP_ADD</span>
127 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span><span class="o">.</span><span class="n">kind</span><span class="p">()</span> <span class="o">==</span> <span class="n">Z3_OP_SUB</span>
128 </pre></div>
129 </body></html></example>
130
131 <p>
132 The following example demonstrates how to substitute sub-expressions in Z3 expressions.
133 </p>
134
135 <example pref="expr.7"><html><body>
136 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
137 <span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
138 <span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
139 <span class="n">n</span> <span class="o">=</span> <span class="n">f</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))),</span> <span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">y</span><span class="p">)))</span>
140 <span class="k">print</span> <span class="n">n</span>
141 <span class="c"># substitute g(g(x)) with y and g(y) with x + 1</span>
142 <span class="k">print</span> <span class="n">substitute</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">)),</span> <span class="n">y</span><span class="p">),</span> <span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">))</span>
143 </pre></div>
144 </body></html></example>
145
146 <p>
147 The function <tt>Const(name, sort)</tt> declares a constant (aka variable) of the given sort.
148 For example, the functions <tt>Int(name)</tt> and <tt>Real(name)</tt> are shorthands for
149 <tt>Const(name, IntSort())</tt> and <tt>Const(name, RealSort())</tt>.
150 </p>
151
152 <example pref="expr.8"><html><body>
153 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">())</span>
154 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">))</span>
155
156 <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a b'</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span>
157 <span class="k">print</span> <span class="n">And</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
158 </pre></div>
159 </body></html></example>
160
161 <h2>Arrays</h2>
162
163 <p>As part of formulating a programme of a mathematical theory of computation
164 McCarthy proposed a <i>basic</i> theory of arrays as characterized by
165 the select-store axioms. The expression <tt>Select(a, i)</tt> returns
166 the value stored at position <tt>i</tt> of the array <tt>a</tt>;
167 and <tt>Store(a, i, v)</tt> returns a new array identical to <tt>a</tt>,
168 but on position <tt>i</tt> it contains the value <tt>v</tt>.
169 In Z3Py, we can also write <tt>Select(a, i)</tt> as <tt>a[i]</tt>.
170 </p>
171
172 <example pref="array.1"><html><body>
173 <div class="highlight"><pre><span class="c"># Use I as an alias for IntSort()</span>
174 <span class="n">I</span> <span class="o">=</span> <span class="n">IntSort</span><span class="p">()</span>
175 <span class="c"># A is an array from integer to integer</span>
176 <span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">I</span><span class="p">)</span>
177 <span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
178 <span class="k">print</span> <span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span>
179 <span class="k">print</span> <span class="n">Select</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>
180 <span class="k">print</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span>
181 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Select</span><span class="p">(</span><span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="n">x</span><span class="o">+</span><span class="mi">1</span><span class="p">),</span> <span class="mi">2</span><span class="p">))</span>
182 </pre></div>
183 </body></html></example>
184
185 <p>
186 By default, Z3 assumes that arrays are extensional over select.
187 In other words, Z3 also enforces that if two arrays agree on all positions,
188 then the arrays are equal.
189 </p>
190
191 <p>
192 Z3 also contains various extensions
193 for operations on arrays that remain decidable and amenable
194 to efficient saturation procedures (here efficient means,
195 with an NP-complete satisfiability complexity).
196 We describe these extensions in the following using a collection of examples.
197 Additional background on these extensions is available in the
198 paper <a href="http://research.microsoft.com/en-us/um/people/leonardo/fmcad09.pdf" target="_blank">Generalized and Efficient Array Decision Procedures</a>.
199 </p>
200
201 <p>
202 Arrays in Z3 are used to model unbounded or very large arrays.
203 Arrays should not be used to model small finite collections of values.
204 It is usually much more efficient to create different variables using list comprehensions.
205 </p>
206
207 <example pref="array.2"><html><body>
208 <div class="highlight"><pre><span class="c"># We want an array with 3 elements.</span>
209 <span class="c"># 1. Bad solution</span>
210 <span class="n">X</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
211 <span class="c"># Example using the array</span>
212 <span class="k">print</span> <span class="n">X</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">&gt;=</span><span class="mi">0</span>
213
214 <span class="c"># 2. More efficient solution</span>
215 <span class="n">X</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span>
216 <span class="k">print</span> <span class="n">X</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="mi">0</span>
217 <span class="k">print</span> <span class="n">Sum</span><span class="p">(</span><span class="n">X</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="mi">0</span>
218 </pre></div>
219 </body></html></example>
220
221 <h3>Select and Store</h3>
222
223
224 <p>Let us first check a basic property of arrays.
225 Suppose <tt>A</tt> is an array of integers, then the constraints
226 <tt>A[x] == x, Store(A, x, y) == A</tt>
227 are satisfiable for an array that contains an index <tt>x</tt> that maps to <tt>x</tt>,
228 and when <tt>x == y</tt>.
229 We can solve these constraints.
230 </p>
231
232 <example pref="array.3"><html><body>
233 <div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
234 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
235 <span class="n">solve</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="n">A</span><span class="p">)</span>
236 </pre></div>
237 </body></html></example>
238
239 <p>The interpretation/solution for array variables is very similar to the one used for functions.</p>
240
241 <p>The problem becomes unsatisfiable/infeasible if we add the constraint <tt>x != y</tt>.
242
243 </p>
244 <example pref="array.4"><html><body>
245 <div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
246 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
247 <span class="n">solve</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="n">A</span><span class="p">,</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">y</span><span class="p">)</span>
248 </pre></div>
249 </body></html></example>
250
251 <h3>Constant arrays</h3>
252
253 <p>
254 The array that maps all indices to some fixed value can be specified in Z3Py using the
255 <tt>K(s, v)</tt> construct where <tt>s</tt> is a sort/type and <tt>v</tt> is an expression.
256 <tt>K(s, v)</tt> returns a array that maps any value of <tt>s</tt> into <tt>v</tt>.
257 The following example defines a constant array containing only ones.
258 </p>
259
260 <example pref="array.5"><html><body>
261 <div class="highlight"><pre><span class="n">AllOne</span> <span class="o">=</span> <span class="n">K</span><span class="p">(</span><span class="n">IntSort</span><span class="p">(),</span> <span class="mi">1</span><span class="p">)</span>
262 <span class="n">a</span><span class="p">,</span> <span class="n">i</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a i'</span><span class="p">)</span>
263 <span class="n">solve</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">AllOne</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
264 <span class="c"># The following constraints do not have a solution</span>
265 <span class="n">solve</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">AllOne</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">)</span>
266 </pre></div>
267 </body></html></example>
268
269 <h2>Datatypes</h2>
270
271 <p>Algebraic datatypes, known from programming languages such as ML,
272 offer a convenient way for specifying common data structures. Records
273 and tuples are special cases of algebraic datatypes, and so are
274 scalars (enumeration types). But algebraic datatypes are more
275 general. They can be used to specify finite lists, trees and other
276 recursive structures.</p>
277
278 <p>
279 The following example demonstrates how to declare a List in Z3Py. It is
280 more verbose than using the SMT 2.0 front-end, but much simpler than using
281 the Z3 C API. It consists of two phases.
282 First, we have to declare the new datatype, its constructors and accessors.
283 The function <tt>Datatype('List')</tt> declares a "placeholder" that will
284 contain the constructors and accessors declarations. The method
285 <tt>declare(cname, (aname, sort)+)</tt> declares a constructor named
286 <tt>cname</tt> with the given accessors. Each accessor has an associated <tt>sort</tt>
287 or a reference to the datatypes being declared.
288 For example, <tt>declare('cons', ('car', IntSort()), ('cdr', List))</tt>
289 declares the constructor named <tt>cons</tt> that builds a new <tt>List</tt>
290 using an integer and a <tt>List</tt>. It also declares the accessors <tt>car</tt> and
291 <tt>cdr</tt>. The accessor <tt>car</tt> extracts the integer of a <tt>cons</tt>
292 cell, and <tt>cdr</tt> the list of a <tt>cons</tt> cell.
293 After all constructors were declared, we use the method <tt>create()</tt> to
294 create the actual datatype in Z3. Z3Py makes the new Z3 declarations and constants
295 available as slots of the new object.
296 </p>
297
298 <example pref="datatype.1"><html><body>
299 <div class="highlight"><pre><span class="c"># Declare a List of integers</span>
300 <span class="n">List</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'List'</span><span class="p">)</span>
301 <span class="c"># Constructor cons: (Int, List) -&gt; List</span>
302 <span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">List</span><span class="p">))</span>
303 <span class="c"># Constructor nil: List</span>
304 <span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span>
305 <span class="c"># Create the datatype</span>
306 <span class="n">List</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">create</span><span class="p">()</span>
307 <span class="k">print</span> <span class="n">is_sort</span><span class="p">(</span><span class="n">List</span><span class="p">)</span>
308 <span class="n">cons</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">cons</span>
309 <span class="n">car</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">car</span>
310 <span class="n">cdr</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">cdr</span>
311 <span class="n">nil</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">nil</span>
312 <span class="c"># cons, car and cdr are function declarations, and nil a constant</span>
313 <span class="k">print</span> <span class="n">is_func_decl</span><span class="p">(</span><span class="n">cons</span><span class="p">)</span>
314 <span class="k">print</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">nil</span><span class="p">)</span>
315
316 <span class="n">l1</span> <span class="o">=</span> <span class="n">cons</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="n">cons</span><span class="p">(</span><span class="mi">20</span><span class="p">,</span> <span class="n">nil</span><span class="p">))</span>
317 <span class="k">print</span> <span class="n">l1</span>
318 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">cdr</span><span class="p">(</span><span class="n">l1</span><span class="p">))</span>
319 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">car</span><span class="p">(</span><span class="n">l1</span><span class="p">))</span>
320 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">l1</span> <span class="o">==</span> <span class="n">nil</span><span class="p">)</span>
321 </pre></div>
322 </body></html></example>
323
324 <p>
325 The following example demonstrates how to define a Python function that
326 given a sort creates a list of the given sort.
327 </p>
328
329 <example pref="datatype.2"><html><body>
330 <div class="highlight"><pre><span class="k">def</span> <span class="nf">DeclareList</span><span class="p">(</span><span class="n">sort</span><span class="p">):</span>
331 <span class="n">List</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'List_of_</span><span class="si">%s</span><span class="s">'</span> <span class="o">%</span> <span class="n">sort</span><span class="o">.</span><span class="n">name</span><span class="p">())</span>
332 <span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">sort</span><span class="p">),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">List</span><span class="p">))</span>
333 <span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span>
334 <span class="k">return</span> <span class="n">List</span><span class="o">.</span><span class="n">create</span><span class="p">()</span>
335
336 <span class="n">IntList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">IntSort</span><span class="p">())</span>
337 <span class="n">RealList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">RealSort</span><span class="p">())</span>
338 <span class="n">IntListList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">IntList</span><span class="p">)</span>
339
340 <span class="n">l1</span> <span class="o">=</span> <span class="n">IntList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="n">IntList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span>
341 <span class="k">print</span> <span class="n">l1</span>
342 <span class="k">print</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">l1</span><span class="p">,</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">l1</span><span class="p">,</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">nil</span><span class="p">))</span>
343 <span class="k">print</span> <span class="n">RealList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="s">"1/3"</span><span class="p">,</span> <span class="n">RealList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span>
344
345 <span class="k">print</span> <span class="n">l1</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
346 </pre></div>
347 </body></html></example>
348
349 <p>The example above demonstrates that Z3 supports operator overloading.
350 There are several functions named <tt>cons</tt>, but they are different since they receive and/or
351 return values of different sorts.
352 Note that it is not necessary to use a different sort name for each instance of the sort
353 list. That is, the expression <tt>'List_of_%s' % sort.name()</tt> is not necessary, we
354 use it just to provide more meaningful names.
355 </p>
356
357 <p>
358 As described above enumeration types are a special case of algebraic datatypes.
359 The following example declares an enumeration type consisting of three values:
360 <tt>red</tt>, <tt>green</tt> and <tt>blue</tt>.
361 </p>
362
363 <example pref="datatype.3"><html><body>
364 <div class="highlight"><pre><span class="n">Color</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'Color'</span><span class="p">)</span>
365 <span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'red'</span><span class="p">)</span>
366 <span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'green'</span><span class="p">)</span>
367 <span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'blue'</span><span class="p">)</span>
368 <span class="n">Color</span> <span class="o">=</span> <span class="n">Color</span><span class="o">.</span><span class="n">create</span><span class="p">()</span>
369
370 <span class="k">print</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">Color</span><span class="o">.</span><span class="n">green</span><span class="p">)</span>
371 <span class="k">print</span> <span class="n">Color</span><span class="o">.</span><span class="n">green</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span>
372 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Color</span><span class="o">.</span><span class="n">green</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span><span class="p">)</span>
373
374 <span class="c"># Let c be a constant of sort Color</span>
375 <span class="n">c</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'c'</span><span class="p">,</span> <span class="n">Color</span><span class="p">)</span>
376 <span class="c"># Then, c must be red, green or blue</span>
377 <span class="n">prove</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">green</span><span class="p">,</span>
378 <span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span><span class="p">,</span>
379 <span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">red</span><span class="p">))</span>
380 </pre></div>
381 </body></html></example>
382
383 <p>
384 Z3Py also provides the following shorthand for declaring enumeration sorts.
385 </p>
386
387 <example pref="datatype.4"><html><body>
388 <div class="highlight"><pre><span class="n">Color</span><span class="p">,</span> <span class="p">(</span><span class="n">red</span><span class="p">,</span> <span class="n">green</span><span class="p">,</span> <span class="n">blue</span><span class="p">)</span> <span class="o">=</span> <span class="n">EnumSort</span><span class="p">(</span><span class="s">'Color'</span><span class="p">,</span> <span class="p">(</span><span class="s">'red'</span><span class="p">,</span> <span class="s">'green'</span><span class="p">,</span> <span class="s">'blue'</span><span class="p">))</span>
389
390 <span class="k">print</span> <span class="n">green</span> <span class="o">==</span> <span class="n">blue</span>
391 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">green</span> <span class="o">==</span> <span class="n">blue</span><span class="p">)</span>
392
393 <span class="n">c</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'c'</span><span class="p">,</span> <span class="n">Color</span><span class="p">)</span>
394 <span class="n">solve</span><span class="p">(</span><span class="n">c</span> <span class="o">!=</span> <span class="n">green</span><span class="p">,</span> <span class="n">c</span> <span class="o">!=</span> <span class="n">blue</span><span class="p">)</span>
395 </pre></div>
396 </body></html></example>
397
398 <p>
399 Mutually recursive datatypes can also be declared. The only difference is that we use
400 the function <tt>CreateDatatypes</tt> instead of the method <tt>create()</tt> to create
401 the mutually recursive datatypes.
402 </p>
403
404 <example pref="datatype.5"><html><body>
405 <div class="highlight"><pre><span class="n">TreeList</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'TreeList'</span><span class="p">)</span>
406 <span class="n">Tree</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'Tree'</span><span class="p">)</span>
407 <span class="n">Tree</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'leaf'</span><span class="p">,</span> <span class="p">(</span><span class="s">'val'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()))</span>
408 <span class="n">Tree</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'node'</span><span class="p">,</span> <span class="p">(</span><span class="s">'left'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">),</span> <span class="p">(</span><span class="s">'right'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">))</span>
409 <span class="n">TreeList</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span>
410 <span class="n">TreeList</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">Tree</span><span class="p">),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">))</span>
411
412 <span class="n">Tree</span><span class="p">,</span> <span class="n">TreeList</span> <span class="o">=</span> <span class="n">CreateDatatypes</span><span class="p">(</span><span class="n">Tree</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">)</span>
413
414 <span class="n">t1</span> <span class="o">=</span> <span class="n">Tree</span><span class="o">.</span><span class="n">leaf</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span>
415 <span class="n">tl1</span> <span class="o">=</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span>
416 <span class="n">t2</span> <span class="o">=</span> <span class="n">Tree</span><span class="o">.</span><span class="n">node</span><span class="p">(</span><span class="n">tl1</span><span class="p">,</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span>
417 <span class="k">print</span> <span class="n">t2</span>
418 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Tree</span><span class="o">.</span><span class="n">val</span><span class="p">(</span><span class="n">t1</span><span class="p">))</span>
419
420 <span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">,</span> <span class="n">t3</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'t1 t2 t3'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">)</span>
421
422 <span class="n">solve</span><span class="p">(</span><span class="n">Distinct</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">,</span> <span class="n">t3</span><span class="p">))</span>
423 </pre></div>
424 </body></html></example>
425
426 <h2>Uninterpreted Sorts</h2>
427
428 <p>
429 Function and constant symbols in pure first-order logic are uninterpreted or free,
430 which means that no a priori interpretation is attached.
431 This is in contrast to arithmetic operators such as <tt>+</tt> and <tt>-</tt>
432 that have a fixed standard interpretation.
433 Uninterpreted functions and constants are maximally flexible;
434 they allow any interpretation that is consistent with the constraints over the function or constant.
435 </p>
436
437 <p>
438 To illustrate uninterpreted functions and constants let us introduce an (uninterpreted) sort <tt>A</tt>,
439 and the constants <tt>x</tt>, <tt>y</tt> ranging over <tt>A</tt>.
440 Finally let <tt>f</tt> be an uninterpreted function that takes one
441 argument of sort <tt>A</tt> and results in a value of sort <tt>A</tt>.
442 The example illustrates how one can force an interpretation where <tt>f</tt> applied twice to <tt>x</tt> results in <tt>x</tt> again,
443 but <tt>f</tt> applied once to <tt>x</tt> is different from <tt>x</tt>.
444 </p>
445
446 <example pref="uninterp.1"><html><body>
447 <div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span>
448 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
449 <span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
450
451 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
452 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="n">y</span><span class="p">,</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">y</span><span class="p">)</span>
453
454 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
455 <span class="n">m</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
456 <span class="k">print</span> <span class="n">m</span>
457 <span class="k">print</span> <span class="s">"interpretation assigned to A:"</span>
458 <span class="k">print</span> <span class="n">m</span><span class="p">[</span><span class="n">A</span><span class="p">]</span>
459 </pre></div>
460 </body></html></example>
461
462 <p>
463 The resulting model introduces abstract values for the elements in <tt>A</tt>,
464 because the sort <tt>A</tt> is uninterpreted. The interpretation for <tt>f</tt> in the
465 model toggles between the two values for <tt>x</tt> and <tt>y</tt>, which are different.
466 The expression <tt>m[A]</tt> returns the interpretation (universe) for the uninterpreted sort <tt>A</tt>
467 in the model <tt>m</tt>.
468 </p>
469
470 <h2>Quantifiers</h2>
471
472 <p>
473 Z3 is can solve quantifier-free problems containing arithmetic, bit-vector, Booleans,
474 arrays, functions and datatypes. Z3 also accepts and can work with formulas
475 that use quantifiers. It is no longer a decision procedure for
476 such formulas in general (and for good reasons, as there can be
477 no decision procedure for first-order logic).
478 </p>
479
480 <example pref="quant.1"><html><body>
481 <div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
482 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
483 <span class="k">print</span> <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
484 <span class="k">print</span> <span class="n">Exists</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span>
485
486 <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b'</span><span class="p">)</span>
487 <span class="n">solve</span><span class="p">(</span><span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">),</span> <span class="n">f</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span>
488 </pre></div>
489 </body></html></example>
490
491 <p>
492 Nevertheless, Z3 is often able to handle formulas involving
493 quantifiers. It uses several approaches to handle quantifiers.
494 The most prolific approach is using <i>pattern-based</i> quantifier
495 instantiation. This approach allows instantiating quantified formulas
496 with ground terms that appear in the current search context based
497 on <i>pattern annotations</i> on quantifiers.
498 Z3 also contains a model-based quantifier instantiation
499 component that uses a model construction to find good terms to instantiate
500 quantifiers with; and Z3 also handles many decidable fragments.
501 </p>
502
503 <p>Note that in the previous example the constants <tt>x</tt>
504 and <tt>y</tt> were used to create quantified formulas.
505 This is a "trick" for simplifying the construction of quantified
506 formulas in Z3Py. Internally, these constants are replaced by
507 bounded variables. The next example demonstrates that. The method
508 <tt>body()</tt> retrieves the quantified expression.
509 In the resultant formula the bounded variables are free.
510 The function <tt>Var(index, sort)</tt> creates a bounded/free variable
511 with the given index and sort.
512 </p>
513
514 <example pref="quant.2"><html><body>
515 <div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
516 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
517 <span class="n">f</span> <span class="o">=</span> <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
518 <span class="k">print</span> <span class="n">f</span><span class="o">.</span><span class="n">body</span><span class="p">()</span>
519 <span class="n">v1</span> <span class="o">=</span> <span class="n">f</span><span class="o">.</span><span class="n">body</span><span class="p">()</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
520 <span class="k">print</span> <span class="n">v1</span>
521 <span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">Var</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()))</span>
522 </pre></div>
523 </body></html></example>
524
525 <h3>Modeling with Quantifiers</h3>
526
527 <p>
528 Suppose we want to model an object oriented type system with single inheritance.
529 We would need a predicate for sub-typing. Sub-typing should be a partial order,
530 and respect single inheritance. For some built-in type constructors,
531 such as for <tt>array_of</tt>, sub-typing should be monotone.
532 </p>
533
534 <example pref="quant.3"><html><body>
535 <div class="highlight"><pre><span class="n">Type</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'Type'</span><span class="p">)</span>
536 <span class="n">subtype</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'subtype'</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span>
537 <span class="n">array_of</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'array_of'</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span>
538 <span class="n">root</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'root'</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span>
539
540 <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span>
541
542 <span class="n">axioms</span> <span class="o">=</span> <span class="p">[</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)),</span>
543 <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">)),</span>
544 <span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">z</span><span class="p">))),</span>
545 <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">x</span><span class="p">)),</span>
546 <span class="n">x</span> <span class="o">==</span> <span class="n">y</span><span class="p">)),</span>
547 <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">z</span><span class="p">)),</span>
548 <span class="n">Or</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">z</span><span class="p">,</span> <span class="n">y</span><span class="p">)))),</span>
549 <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span>
550 <span class="n">subtype</span><span class="p">(</span><span class="n">array_of</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">array_of</span><span class="p">(</span><span class="n">y</span><span class="p">)))),</span>
551
552 <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">subtype</span><span class="p">(</span><span class="n">root</span><span class="p">,</span> <span class="n">x</span><span class="p">))</span>
553 <span class="p">]</span>
554 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
555 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">axioms</span><span class="p">)</span>
556 <span class="k">print</span> <span class="n">s</span>
557 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
558 <span class="k">print</span> <span class="s">"Interpretation for Type:"</span>
559 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()[</span><span class="n">Type</span><span class="p">]</span>
560 <span class="k">print</span> <span class="s">"Model:"</span>
561 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
562 </pre></div>
563 </body></html></example>
564
565 <h3>Patterns</h3>
566
567 <p>
568 The Stanford Pascal verifier and the subsequent Simplify theorem prover pioneered
569 the use of pattern-based quantifier instantiation.
570 The basic idea behind pattern-based quantifier instantiation is in a sense straight-forward:
571 Annotate a quantified formula using a pattern that contains all the bound variables.
572 So a pattern is an expression (that does not contain binding operations, such as quantifiers)
573 that contains variables bound by a quantifier. Then instantiate the quantifier whenever a term
574 that matches the pattern is created during search. This is a conceptually easy starting point,
575 but there are several subtleties that are important.
576 </p>
577
578 <p>
579 In the following example, the first two options make sure that Model-based quantifier instantiation engine is disabled.
580 We also annotate the quantified formula with the pattern <tt>f(g(x))</tt>.
581 Since there is no ground instance of this pattern, the quantifier is not instantiated, and
582 Z3 fails to show that the formula is unsatisfiable.
583 </p>
584
585 <example pref="quant.4"><html><body>
586 <div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
587 <span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
588 <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span>
589 <span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
590
591 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
592 <span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span>
593
594 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))]),</span>
595 <span class="n">g</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span>
596 <span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span>
597 <span class="n">a</span> <span class="o">!=</span> <span class="n">b</span> <span class="p">)</span>
598
599 <span class="c"># Display solver state using internal format</span>
600 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span>
601 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
602 </pre></div>
603 </body></html></example>
604
605 <p>When the more permissive pattern <tt>g(x)</tt> is used. Z3 proves the formula
606 to be unsatisfiable. More restrictive patterns minimize the number of
607 instantiations (and potentially improve performance), but they may
608 also make Z3 "less complete".
609 </p>
610
611 <example pref="quant.5"><html><body>
612 <div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
613 <span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
614 <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span>
615 <span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
616
617 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
618 <span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span>
619
620 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">)]),</span>
621 <span class="n">g</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span>
622 <span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span>
623 <span class="n">a</span> <span class="o">!=</span> <span class="n">b</span> <span class="p">)</span>
624
625 <span class="c"># Display solver state using internal format</span>
626 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span>
627 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
628 </pre></div>
629 </body></html></example>
630
631 <p>
632 Some patterns may also create long instantiation chains. Consider the following assertion.
633 </p>
634
635 <pre>
636 ForAll([x, y], Implies(subtype(x, y),
637 subtype(array_of(x), array_of(y))),
638 patterns=[subtype(x, y)])
639 </pre>
640
641 <p>
642 The axiom gets instantiated whenever there is some ground term of the
643 form <tt>subtype(s, t)</tt>. The instantiation causes a fresh ground term
644 <tt>subtype(array_of(s), array_of(t))</tt>, which enables a new
645 instantiation. This undesirable situation is called a matching
646 loop. Z3 uses many heuristics to break matching loops.
647 </p>
648
649 <p>
650 Before elaborating on the subtleties, we should address an important
651 first question. What defines the terms that are created during search?
652 In the context of most SMT solvers, and of the Simplify theorem
653 prover, terms exist as part of the input formula, they are of course
654 also created by instantiating quantifiers, but terms are also
655 implicitly created when equalities are asserted. The last point means
656 that terms are considered up to congruence and pattern matching takes
657 place modulo ground equalities. We call the matching problem
658 <b>E-matching</b>. For example, if we have the following equalities:
659 </p>
660
661 <example pref="quant.6"><html><body>
662 <div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
663 <span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span>
664 <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span>
665 <span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
666
667 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
668 <span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span>
669
670 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))]),</span>
671 <span class="n">a</span> <span class="o">==</span> <span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">),</span>
672 <span class="n">b</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span>
673 <span class="n">f</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">!=</span> <span class="n">c</span> <span class="p">)</span>
674
675 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
676 </pre></div>
677 </body></html></example>
678
679 <p>
680 The terms <tt>f(a)</tt> and <tt>f(g(b))</tt> are equal modulo the
681 equalities. The pattern <tt>f(g(x))</tt> can be matched and <tt>x</tt> bound to <tt>b</tt>
682 and the equality <tt>f(g(b)) == b</tt> is deduced.
683 </p>
684
685 <p>
686 While E-matching is an NP-complete problem, the main sources of overhead in larger verification
687 problems comes from matching thousands of patterns in the context of an evolving set of terms and
688 equalities. Z3 integrates an efficient E-matching engine using term indexing techniques.
689 </p>
690
691 <h3>Multi-patterns</h3>
692
693 <p>
694 In some cases, there is no pattern that contains all bound variables
695 and does not contain interpreted symbols. In these cases, we use
696 multi-patterns. In the following example, the quantified formula
697 states that <tt>f</tt> is injective. This quantified formula is annotated with
698 the multi-pattern <tt>MultiPattern(f(x), f(y))</tt>.
699 </p>
700
701 <example pref="quant.7"><html><body>
702 <div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span>
703 <span class="n">B</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'B'</span><span class="p">)</span>
704 <span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span>
705 <span class="n">a1</span><span class="p">,</span> <span class="n">a2</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a1 a2'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
706 <span class="n">b</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span>
707 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
708
709 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
710 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">a1</span> <span class="o">!=</span> <span class="n">a2</span><span class="p">,</span>
711 <span class="n">f</span><span class="p">(</span><span class="n">a1</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span>
712 <span class="n">f</span><span class="p">(</span><span class="n">a2</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span>
713 <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="n">f</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">x</span> <span class="o">==</span> <span class="n">y</span><span class="p">),</span>
714 <span class="n">patterns</span><span class="o">=</span><span class="p">[</span><span class="n">MultiPattern</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">f</span><span class="p">(</span><span class="n">y</span><span class="p">))])</span>
715 <span class="p">)</span>
716 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
717 </pre></div>
718 </body></html></example>
719
720 <p>
721 The quantified formula is instantiated for every pair of occurrences
722 of <tt>f</tt>. A simple trick allows formulating injectivity of <tt>f</tt> in such a way
723 that only a linear number of instantiations is required. The trick is
724 to realize that <tt>f</tt> is injective if and only if it has a partial
725 inverse.
726 </p>
727
728 <example pref="quant.8"><html><body>
729 <div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span>
730 <span class="n">B</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'B'</span><span class="p">)</span>
731 <span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span>
732 <span class="n">finv</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'finv'</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
733 <span class="n">a1</span><span class="p">,</span> <span class="n">a2</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a1 a2'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
734 <span class="n">b</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span>
735 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span>
736
737 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
738 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">a1</span> <span class="o">!=</span> <span class="n">a2</span><span class="p">,</span>
739 <span class="n">f</span><span class="p">(</span><span class="n">a1</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span>
740 <span class="n">f</span><span class="p">(</span><span class="n">a2</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span>
741 <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">finv</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span>
742 <span class="p">)</span>
743 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
744 </pre></div>
745 </body></html></example>
746
747 <h3>Other attributes</h3>
748
749 <p>
750 In Z3Py, the following additional attributes are supported: <b>qid</b> (quantifier identifier
751 for debugging), <b>weight</b> (hint to the quantifier instantiation module: "more weight equals less instances"),
752 <b>no_patterns</b> (expressions that should not be used as patterns, <b>skid</b> (identifier
753 prefix used to create skolem constants/functions.
754 </p>
755
756 <h2>Multiple Solvers</h2>
757
758 <p>In Z3Py and Z3 4.0 multiple solvers can be simultaneously used.
759 It is also very easy to copy assertions/formulas from one solver to another.
760 </p>
761
762 <example pref="msolver.1"><html><body>
763 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
764 <span class="n">s1</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
765 <span class="n">s1</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">10</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">10</span><span class="p">)</span>
766 <span class="n">s2</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
767 <span class="c"># solver s2 is empty</span>
768 <span class="k">print</span> <span class="n">s2</span>
769 <span class="c"># copy assertions from s1 to s2</span>
770 <span class="n">s2</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">s1</span><span class="o">.</span><span class="n">assertions</span><span class="p">())</span>
771 <span class="k">print</span> <span class="n">s2</span>
772 </pre></div>
773 </body></html></example>
774
775 <h2>Unsat Cores and Soft Constraints</h2>
776
777 <p>Z3Py also supports <i>unsat core extraction</i>. The basic idea is to use
778 <i>assumptions</i>, that is, auxiliary propositional variables that we want to track.
779 Assumptions are also available in the Z3 SMT 2.0 frontend, and in other Z3 front-ends.
780 They are used to extract unsatisfiable cores. They may be also used to "retract"
781 constraints. Note that, assumptions are not really <i>soft constraints</i>, but they can be used to implement them.
782 </p>
783
784 <example pref="unsatcore.1"><html><body>
785 <div class="highlight"><pre><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">,</span> <span class="n">p3</span> <span class="o">=</span> <span class="n">Bools</span><span class="p">(</span><span class="s">'p1 p2 p3'</span><span class="p">)</span>
786 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
787 <span class="c"># We assert Implies(p, C) to track constraint C using p</span>
788 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
789 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Implies</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">10</span><span class="p">),</span>
790 <span class="n">Implies</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="n">x</span><span class="p">),</span>
791 <span class="n">Implies</span><span class="p">(</span><span class="n">p2</span><span class="p">,</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">5</span><span class="p">),</span>
792 <span class="n">Implies</span><span class="p">(</span><span class="n">p3</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">))</span>
793 <span class="k">print</span> <span class="n">s</span>
794 <span class="c"># Check satisfiability assuming p1, p2, p3 are true</span>
795 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">,</span> <span class="n">p3</span><span class="p">)</span>
796 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">unsat_core</span><span class="p">()</span>
797
798 <span class="c"># Try again retracting p2</span>
799 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p3</span><span class="p">)</span>
800 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
801 </pre></div>
802 </body></html></example>
803
804 <p>The example above also shows that a Boolean variable (<tt>p1</tt>) can be used to track
805 more than one constraint. Note that Z3 does not guarantee that the unsat cores are minimal.
806 </p>
807
808 <h2>Formatter</h2>
809
810 <p>
811 Z3Py uses a formatter (aka pretty printer) for displaying formulas, expressions, solvers, and other
812 Z3 objects. The formatter supports many configuration options.
813 The command <tt>set_option(html_mode=False)</tt> makes all formulas and expressions to be
814 displayed in Z3Py notation.
815 </p>
816
817 <example pref="printer"><html><body>
818 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
819 <span class="n">y</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'y'</span><span class="p">)</span>
820 <span class="k">print</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="o">&gt;=</span> <span class="mi">1</span>
821 <span class="n">set_option</span><span class="p">(</span><span class="n">html_mode</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span>
822 <span class="k">print</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="o">&gt;=</span> <span class="mi">1</span>
823 </pre></div>
824 </body></html></example>
825
826 <p>By default, Z3Py will truncate the output if the object being displayed is too big.
827 Z3Py uses &#8230; to denote the output is truncated.
828 The following configuration options can be set to control the behavior of Z3Py's formatter:
829 </p>
830
831 <ul>
832 <li> <tt>max_depth</tt> Maximal expression depth. Deep expressions are replaced with &#8230;. </li>
833 <li> <tt>max_args</tt> Maximal number of arguments to display per node. </li>
834 <li> <tt>rational_to_decimal</tt> Display rationals as decimals if True. </li>
835 <li> <tt>precision</tt> Maximal number of decimal places for numbers being displayed in decimal notation. </li>
836 <li> <tt>max_lines</tt> Maximal number of lines to be displayed. </li>
837 <li> <tt>max_width</tt> Maximal line width (this is a suggestion to Z3Py). </li>
838 <li> <tt>max_indent</tt> Maximal indentation.</li>
839 </ul>
840
841 <example pref="format"><html><body>
842 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span>
843 <span class="n">y</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span>
844 <span class="n">f</span> <span class="o">=</span> <span class="n">And</span><span class="p">(</span><span class="n">Sum</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">Sum</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span>
845
846 <span class="n">set_option</span><span class="p">(</span><span class="n">max_args</span><span class="o">=</span><span class="mi">5</span><span class="p">)</span>
847 <span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 1:"</span>
848 <span class="k">print</span> <span class="n">f</span>
849
850 <span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 2:"</span>
851 <span class="n">set_option</span><span class="p">(</span><span class="n">max_args</span><span class="o">=</span><span class="mi">100</span><span class="p">,</span> <span class="n">max_lines</span><span class="o">=</span><span class="mi">10</span><span class="p">)</span>
852 <span class="k">print</span> <span class="n">f</span>
853
854 <span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 3:"</span>
855 <span class="n">set_option</span><span class="p">(</span><span class="n">max_width</span><span class="o">=</span><span class="mi">300</span><span class="p">)</span>
856 <span class="k">print</span> <span class="n">f</span>
857 </pre></div>
858 </body></html></example>
859
860 </body>
861 </html>