Debian Codegraph @

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

raw
1 <html>
2 <head>
3 <title>Z3Py Guide</title>
4 <link rel="StyleSheet" href="style.css" type="text/css">
5 </head>
6 <body>
7
8
9 <h1>Z3 API in Python</h1>
10 <p>Z3 is a high performance theorem prover developed at <a target="_blank" href="http://research.microsoft.com">Microsoft Research</a>.
11 Z3 is used in many applications such as: software/hardware verification and testing, constraint solving, analysis of hybrid systems,
12 security, biology (in silico analysis), and geometrical problems.</p>
13 <p>This tutorial demonstrates the main capabilities of Z3Py: the Z3 API in <a target="_blank" href="http://www.python.org">Python</a>.
14 No Python background is needed to read this tutorial. However, it is useful to learn Python (a fun language!) at some point, and
15 there are many excellent free resources for doing so (<a target="_blank" href="http://docs.python.org/tutorial/">Python Tutorial</a>).
16 </p>
17
18 <p>The Z3 distribution also contains the <b>C</b>, <b>.Net</b> and <b>OCaml</b> APIs. The source code of Z3Py is available in
19 the Z3 distribution, feel free to modify it to meet your needs. The source code also demonstrates how to use new features in Z3 4.0.
20 Other cool front-ends for Z3 include <a target="_blank" href="http://lara.epfl.ch/~psuter/ScalaZ3/">Scala^Z3</a> and <a target="_blank" href="http://hackage.haskell.org/package/sbv">SBV</a>.</p>
21
22 <p>
23 Be sure to follow along with the examples by clicking the <b>load in editor</b> link in the
24 corner. See what Z3Py says, try your own scripts, and experiment!
25 </p>
26
27 <p>
28 Please send feedback, comments and/or corrections to <a href="mailto:[email protected]">[email protected]</a>.
29 Your comments are very valuable.
30 </p>
31
32 <h2>Getting Started</h2>
33
34 <p>Let us start with the following simple example:</p>
35
36 <example pref="z3py.1"><html><body>
37 <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>
38 <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>
39 <span class="n">solve</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="n">y</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">,</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">7</span><span class="p">)</span>
40 </pre></div>
41 </body></html></example>
42
43 <p>The function <tt class="pre">Int('x')</tt> creates an integer variable in Z3 named <tt class="pre">x</tt>.
44 The <tt class="pre">solve</tt> function solves a system of constraints. The example above uses
45 two variables <tt class="pre">x</tt> and <tt class="pre">y</tt>, and three constraints.
46 Z3Py like Python uses <b class="pre">=</b> for assignment. The operators <tt class="pre">&lt;</tt>,
47 <tt class="pre">&lt;=</tt>,
48 <tt class="pre">&gt;</tt>,
49 <tt class="pre">&gt;=</tt>,
50 <tt class="pre">==</tt> and
51 <tt class="pre">!=</tt> for comparison.
52 In the example above, the expression <tt class="pre">x + 2*y == 7</tt> is a Z3 constraint.
53 Z3 can solve and crunch formulas.
54 </p>
55
56 <p>
57 The next examples show how to use the Z3 formula/expression simplifier.
58 </p>
59
60 <example pref="z3py.2"><html><body>
61 <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>
62 <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>
63 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span> <span class="o">+</span> <span class="mi">3</span><span class="p">)</span>
64 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">y</span> <span class="o">+</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span>
65 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&gt;=</span> <span class="mi">3</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</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">+</span> <span class="mi">2</span> <span class="o">&gt;=</span> <span class="mi">5</span><span class="p">))</span>
66 </pre></div>
67 </body></html></example>
68
69 <p>
70 By default, Z3Py (for the web) displays formulas and expressions using mathematical notation.
71 As usual, <tt>&#8743;</tt> is the logical and, <tt>&#8744;</tt> is the logical or, and so on.
72 The command <tt>set_option(html_mode=False)</tt> makes all formulas and expressions to be
73 displayed in Z3Py notation. This is also the default mode for the offline version of Z3Py that
74 comes with the Z3 distribution.
75 </p>
76
77 <example pref="printer"><html><body>
78 <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>
79 <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>
80 <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>
81 <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>
82 <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>
83 </pre></div>
84 </body></html></example>
85
86 <p>
87 Z3 provides functions for traversing expressions.
88 </p>
89
90 <example pref="z3py.3"><html><body>
91 <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>
92 <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>
93 <span class="n">n</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&gt;=</span> <span class="mi">3</span>
94 <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>
95 <span class="k">print</span> <span class="s">"children: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">children</span><span class="p">()</span>
96 <span class="k">print</span> <span class="s">"1st child:"</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="mi">0</span><span class="p">)</span>
97 <span class="k">print</span> <span class="s">"2nd child:"</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="mi">1</span><span class="p">)</span>
98 <span class="k">print</span> <span class="s">"operator: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span>
99 <span class="k">print</span> <span class="s">"op name: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span><span class="o">.</span><span class="n">name</span><span class="p">()</span>
100 </pre></div>
101 </body></html></example>
102
103 <p>
104 Z3 provides all basic mathematical operations. Z3Py uses the same operator precedence of the Python language.
105 Like Python, <tt>**</tt> is the power operator. Z3 can solve nonlinear <i>polynomial</i> constraints.
106 </p>
107
108 <example pref="z3py.4"><html><body>
109 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
110 <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>
111 <span class="n">solve</span><span class="p">(</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">3</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">3</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">5</span><span class="p">)</span>
112 </pre></div>
113 </body></html></example>
114
115 <p>
116 The procedure <tt>Real('x')</tt> creates the real variable <tt>x</tt>.
117 Z3Py can represent arbitrarily large integers, rational numbers (like in the example above),
118 and irrational algebraic numbers. An irrational algebraic number is a root of a polynomial with integer coefficients.
119 Internally, Z3 represents all these numbers precisely.
120 The irrational numbers are displayed in decimal notation for making it easy to read the results.
121 </p>
122
123 <example pref="z3py.5"><html><body>
124 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
125 <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>
126 <span class="n">solve</span><span class="p">(</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">==</span> <span class="mi">3</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">3</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
127
128 <span class="n">set_option</span><span class="p">(</span><span class="n">precision</span><span class="o">=</span><span class="mi">30</span><span class="p">)</span>
129 <span class="k">print</span> <span class="s">"Solving, and displaying result with 30 decimal places"</span>
130 <span class="n">solve</span><span class="p">(</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">==</span> <span class="mi">3</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">3</span> <span class="o">==</span> <span class="mi">2</span><span class="p">)</span>
131 </pre></div>
132 </body></html></example>
133
134 <p>
135 The procedure <tt>set_option</tt> is used to configure the Z3 environment. It is used to set global configuration options
136 such as how the result is displayed. The option <tt>set_option(precision=30)</tt> sets the number of decimal places used when displaying results.
137 The <tt>?</tt> mark in <tt>1.2599210498?</tt> indicates the output is truncated.
138 </p>
139
140 <p>
141 The following example demonstrates a common mistake. The expression <tt>3/2</tt> is a Python integer and not a Z3 rational number.
142 The example also shows different ways to create rational numbers in Z3Py. The procedure <tt>Q(num, den)</tt> creates a
143 Z3 rational where <tt>num</tt> is the numerator and <tt>den</tt> is the denominator. The <tt>RealVal(1)</tt> creates a Z3 real number
144 representing the number <tt>1</tt>.
145 </p>
146
147 <example pref="z3py.6"><html><body>
148 <div class="highlight"><pre><span class="k">print</span> <span class="mi">1</span><span class="o">/</span><span class="mi">3</span>
149 <span class="k">print</span> <span class="n">RealVal</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">3</span>
150 <span class="k">print</span> <span class="n">Q</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)</span>
151
152 <span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
153 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="o">/</span><span class="mi">3</span>
154 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="n">Q</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">)</span>
155 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="s">"1/3"</span>
156 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="mf">0.25</span>
157 </pre></div>
158 </body></html></example>
159
160 <p>
161 Rational numbers can also be displayed in decimal notation.
162 </p>
163
164 <example pref="z3py.6aa"><html><body>
165 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
166 <span class="n">solve</span><span class="p">(</span><span class="mi">3</span><span class="o">*</span><span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span>
167
168 <span class="n">set_option</span><span class="p">(</span><span class="n">rational_to_decimal</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
169 <span class="n">solve</span><span class="p">(</span><span class="mi">3</span><span class="o">*</span><span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span>
170
171 <span class="n">set_option</span><span class="p">(</span><span class="n">precision</span><span class="o">=</span><span class="mi">30</span><span class="p">)</span>
172 <span class="n">solve</span><span class="p">(</span><span class="mi">3</span><span class="o">*</span><span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span>
173 </pre></div>
174 </body></html></example>
175
176 <p>
177 A system of constraints may not have a solution. In this case, we say the system is <b>unsatisfiable</b>.
178 </p>
179
180 <example pref="z3py.6a"><html><body>
181 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
182 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">4</span><span class="p">,</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span>
183 </pre></div>
184 </body></html></example>
185
186 <p>
187 Like in Python, comments begin with the hash character <tt>#</tt> and are terminated by the end of line.
188 Z3Py does not support comments that span more than one line.
189 </p>
190
191 <example pref="comment"><html><body>
192 <div class="highlight"><pre><span class="c"># This is a comment</span>
193 <span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> <span class="c"># comment: creating x</span>
194 <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="mi">2</span><span class="o">*</span><span class="n">x</span> <span class="o">+</span> <span class="mi">2</span> <span class="c"># comment: printing polynomial</span>
195 </pre></div>
196 </body></html></example>
197
198 <h2>Boolean Logic</h2>
199
200 <p>
201 Z3 supports Boolean operators: <tt>And</tt>, <tt>Or</tt>, <tt>Not</tt>, <tt>Implies</tt> (implication),
202 <tt>If</tt> (if-then-else). Bi-implications are represented using equality <tt>==</tt>.
203 The following example shows how to solve a simple set of Boolean constraints.
204 </p>
205
206 <example pref="z3py.7"><html><body>
207 <div class="highlight"><pre><span class="n">p</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'p'</span><span class="p">)</span>
208 <span class="n">q</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'q'</span><span class="p">)</span>
209 <span class="n">r</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'r'</span><span class="p">)</span>
210 <span class="n">solve</span><span class="p">(</span><span class="n">Implies</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">q</span><span class="p">),</span> <span class="n">r</span> <span class="o">==</span> <span class="n">Not</span><span class="p">(</span><span class="n">q</span><span class="p">),</span> <span class="n">Or</span><span class="p">(</span><span class="n">Not</span><span class="p">(</span><span class="n">p</span><span class="p">),</span> <span class="n">r</span><span class="p">))</span>
211
212 </pre></div>
213 </body></html></example>
214
215 <p>
216 The Python Boolean constants <tt>True</tt> and <tt>False</tt> can be used to build Z3 Boolean expressions.
217 </p>
218
219 <example pref="z3py.8"><html><body>
220 <div class="highlight"><pre><span class="n">p</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'p'</span><span class="p">)</span>
221 <span class="n">q</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'q'</span><span class="p">)</span>
222 <span class="k">print</span> <span class="n">And</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">q</span><span class="p">,</span> <span class="bp">True</span><span class="p">)</span>
223 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">q</span><span class="p">,</span> <span class="bp">True</span><span class="p">))</span>
224 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="bp">False</span><span class="p">))</span>
225 </pre></div>
226 </body></html></example>
227
228 <p>The following example uses a combination of polynomial and Boolean constraints.
229 </p>
230
231 <example pref="z3py.9"><html><body>
232 <div class="highlight"><pre><span class="n">p</span> <span class="o">=</span> <span class="n">Bool</span><span class="p">(</span><span class="s">'p'</span><span class="p">)</span>
233 <span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
234 <span class="n">solve</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="mi">5</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">Or</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">==</span> <span class="mi">2</span><span class="p">),</span> <span class="n">Not</span><span class="p">(</span><span class="n">p</span><span class="p">))</span>
235 </pre></div>
236 </body></html></example>
237
238 <h2>Solvers</h2>
239
240 <p>Z3 provides different solvers. The command <tt>solve</tt>, used in the previous examples, is implemented using the Z3 solver API.
241 The implementation can be found in the file <tt>z3.py</tt> in the Z3 distribution.
242 The following example demonstrates the basic Solver API.
243 </p>
244
245 <example pref="z3py.10"><html><body>
246 <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>
247 <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>
248
249 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
250 <span class="k">print</span> <span class="n">s</span>
251
252 <span class="n">s</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">==</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span>
253 <span class="k">print</span> <span class="n">s</span>
254 <span class="k">print</span> <span class="s">"Solving constraints in the solver s ..."</span>
255 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
256
257 <span class="k">print</span> <span class="s">"Create a new scope..."</span>
258 <span class="n">s</span><span class="o">.</span><span class="n">push</span><span class="p">()</span>
259 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">y</span> <span class="o">&lt;</span> <span class="mi">11</span><span class="p">)</span>
260 <span class="k">print</span> <span class="n">s</span>
261 <span class="k">print</span> <span class="s">"Solving updated set of constraints..."</span>
262 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
263
264 <span class="k">print</span> <span class="s">"Restoring state..."</span>
265 <span class="n">s</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
266 <span class="k">print</span> <span class="n">s</span>
267 <span class="k">print</span> <span class="s">"Solving restored set of constraints..."</span>
268 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
269 </pre></div>
270 </body></html></example>
271
272 <p>
273 The command <tt>Solver()</tt> creates a general purpose solver. Constraints can be added using the method <tt>add</tt>.
274 We say the constraints have been <b>asserted</b> in the solver. The method <tt>check()</tt> solves the asserted constraints.
275 The result is <tt>sat</tt> (satisfiable) if a solution was found. The result is <tt>unsat</tt> (unsatisfiable) if
276 no solution exists. We may also say the system of asserted constraints is <b>infeasible</b>. Finally, a solver may fail
277 to solve a system of constraints and <tt>unknown</tt> is returned.
278 </p>
279
280 <p>
281 In some applications, we want to explore several similar problems that share several constraints.
282 We can use the commands <tt>push</tt> and <tt>pop</tt> for doing that.
283 Each solver maintains a stack of assertions. The command <tt>push</tt> creates a new scope by
284 saving the current stack size.
285 The command <tt>pop</tt> removes any assertion performed between it and the matching <tt>push</tt>.
286 The <tt>check</tt> method always operates on the content of solver assertion stack.
287 </p>
288
289 <p>
290 The following example shows an example that Z3 cannot solve. The solver returns <tt>unknown</tt> in this case.
291 Recall that Z3 can solve nonlinear polynomial constraints, but <tt>2**x</tt> is not a polynomial.
292 </p>
293
294 <example pref="z3py.11"><html><body>
295 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
296 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
297 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="mi">2</span><span class="o">**</span><span class="n">x</span> <span class="o">==</span> <span class="mi">3</span><span class="p">)</span>
298 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
299 </pre></div>
300 </body></html></example>
301
302 <p>
303 The following example shows how to traverse the constraints asserted into a solver, and how to collect performance statistics for
304 the <tt>check</tt> method.
305 </p>
306
307 <example pref="z3py.12"><html><body>
308 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
309 <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>
310 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
311 <span class="n">s</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">1</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">,</span> <span class="n">Or</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">3</span><span class="p">,</span> <span class="n">x</span> <span class="o">-</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">2</span><span class="p">))</span>
312 <span class="k">print</span> <span class="s">"asserted constraints..."</span>
313 <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">s</span><span class="o">.</span><span class="n">assertions</span><span class="p">():</span>
314 <span class="k">print</span> <span class="n">c</span>
315
316 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
317 <span class="k">print</span> <span class="s">"statistics for the last check method..."</span>
318 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">statistics</span><span class="p">()</span>
319 <span class="c"># Traversing statistics</span>
320 <span class="k">for</span> <span class="n">k</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">s</span><span class="o">.</span><span class="n">statistics</span><span class="p">():</span>
321 <span class="k">print</span> <span class="s">"</span><span class="si">%s</span><span class="s"> : </span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
322 </pre></div>
323 </body></html></example>
324
325 <p>
326 The command <tt>check</tt> returns <tt>sat</tt> when Z3 finds a solution for the set of asserted constraints.
327 We say Z3 <b>satisfied</b> the set of constraints. We say the solution is a <b>model</b> for the set of asserted
328 constraints. A model is an <b>interpretation</b> that makes each asserted constraint <b>true</b>.
329 The following example shows the basic methods for inspecting models.
330 </p>
331
332 <example pref="z3py.13"><html><body>
333 <div class="highlight"><pre><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">Reals</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
334 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
335 <span class="n">s</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">1</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">3</span><span class="p">,</span> <span class="n">z</span> <span class="o">-</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">)</span>
336 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
337
338 <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>
339 <span class="k">print</span> <span class="s">"x = </span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="n">m</span><span class="p">[</span><span class="n">x</span><span class="p">]</span>
340
341 <span class="k">print</span> <span class="s">"traversing model..."</span>
342 <span class="k">for</span> <span class="n">d</span> <span class="ow">in</span> <span class="n">m</span><span class="o">.</span><span class="n">decls</span><span class="p">():</span>
343 <span class="k">print</span> <span class="s">"</span><span class="si">%s</span><span class="s"> = </span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">d</span><span class="o">.</span><span class="n">name</span><span class="p">(),</span> <span class="n">m</span><span class="p">[</span><span class="n">d</span><span class="p">])</span>
344 </pre></div>
345 </body></html></example>
346
347 <p>In the example above, the function <tt>Reals('x y z')</tt> creates the variables. <tt>x</tt>, <tt>y</tt> and <tt>z</tt>.
348 It is shorthand for:
349 </p>
350
351 <pre>
352 x = Real('x')
353 y = Real('y')
354 z = Real('z')
355 </pre>
356
357 <p>
358 The expression <tt>m[x]</tt> returns the interpretation of <tt>x</tt> in the model <tt>m</tt>.
359 The expression <tt>"%s = %s" % (d.name(), m[d])</tt> returns a string where the first <tt>%s</tt> is replaced with
360 the name of <tt>d</tt> (i.e., <tt>d.name()</tt>), and the second <tt>%s</tt> with a textual representation of the
361 interpretation of <tt>d</tt> (i.e., <tt>m[d]</tt>). Z3Py automatically converts Z3 objects into a textual representation
362 when needed.
363 </p>
364
365 <h2>Arithmetic</h2>
366
367 <p>Z3 supports real and integer variables. They can be mixed in a single problem.
368 Like most programming languages, Z3Py will automatically add coercions converting integer expressions to real ones when needed.
369 The following example demonstrates different ways to declare integer and real variables.
370 </p>
371
372 <example pref="arith.1"><html><body>
373 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span>
374 <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>
375 <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">Reals</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span>
376 <span class="n">s</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'s r'</span><span class="p">)</span>
377 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">+</span> <span class="p">(</span><span class="n">a</span> <span class="o">+</span> <span class="n">s</span><span class="p">)</span>
378 <span class="k">print</span> <span class="n">ToReal</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="o">+</span> <span class="n">c</span>
379 </pre></div>
380 </body></html></example>
381
382 <p>The function <tt>ToReal</tt> casts an integer expression into a real expression.</p>
383
384 <p>Z3Py supports all basic arithmetic operations.</p>
385
386 <example pref="arith.2"><html><body>
387 <div class="highlight"><pre><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>
388 <span class="n">d</span><span class="p">,</span> <span class="n">e</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'d e'</span><span class="p">)</span>
389 <span class="n">solve</span><span class="p">(</span><span class="n">a</span> <span class="o">&gt;</span> <span class="n">b</span> <span class="o">+</span> <span class="mi">2</span><span class="p">,</span>
390 <span class="n">a</span> <span class="o">==</span> <span class="mi">2</span><span class="o">*</span><span class="n">c</span> <span class="o">+</span> <span class="mi">10</span><span class="p">,</span>
391 <span class="n">c</span> <span class="o">+</span> <span class="n">b</span> <span class="o">&lt;=</span> <span class="mi">1000</span><span class="p">,</span>
392 <span class="n">d</span> <span class="o">&gt;=</span> <span class="n">e</span><span class="p">)</span>
393 </pre></div>
394 </body></html></example>
395
396 <p>The command <tt>simplify</tt> applies simple transformations on Z3 expressions.</p>
397
398 <example pref="arith.3"><html><body>
399 <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">Reals</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
400 <span class="c"># Put expression in sum-of-monomials form</span>
401 <span class="n">t</span> <span class="o">=</span> <span class="n">simplify</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="mi">3</span><span class="p">,</span> <span class="n">som</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
402 <span class="k">print</span> <span class="n">t</span>
403 <span class="c"># Use power operator</span>
404 <span class="n">t</span> <span class="o">=</span> <span class="n">simplify</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">mul_to_power</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
405 <span class="k">print</span> <span class="n">t</span>
406 </pre></div>
407 </body></html></example>
408
409 <p>The command <tt>help_simplify()</tt> prints all available options.
410 Z3Py allows users to write option in two styles. The Z3 internal option names start with <tt>:</tt> and words are separated by <tt>-</tt>.
411 These options can be used in Z3Py. Z3Py also supports Python-like names,
412 where <tt>:</tt> is suppressed and <tt>-</tt> is replaced with <tt>_</tt>.
413 The following example demonstrates how to use both styles.
414 </p>
415
416 <example pref="arith.4"><html><body>
417 <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">Reals</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
418 <span class="c"># Using Z3 native option names</span>
419 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="p">,</span> <span class="s">':arith-lhs'</span><span class="p">,</span> <span class="bp">True</span><span class="p">)</span>
420 <span class="c"># Using Z3Py option names</span>
421 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="p">,</span> <span class="n">arith_lhs</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
422
423 <span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">All available options:"</span>
424 <span class="n">help_simplify</span><span class="p">()</span>
425 </pre></div>
426 </body></html></example>
427
428 <p>Z3Py supports arbitrarily large numbers. The following example demonstrates how to perform basic arithmetic using larger integer, rational and irrational numbers.
429 Z3Py only supports <a target="&#148;_blank&#148;" href="http://en.wikipedia.org/wiki/Algebraic_number">algebraic irrational numbers</a>. Algebraic irrational numbers are sufficient for presenting the solutions of systems of polynomial constraints.
430 Z3Py will always display irrational numbers in decimal notation since it is more convenient to read. The internal representation can be extracted using the method <tt>sexpr()</tt>.
431 It displays Z3 internal representation for mathematical formulas and expressions in <a target="_blank" href="http://en.wikipedia.org/wiki/S-expression">s-expression</a> (Lisp-like) notation.
432 </p>
433
434 <example pref="arith.5"><html><body>
435 <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">Reals</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
436 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">10000000000000000000000</span> <span class="o">==</span> <span class="n">y</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">20000000000000000</span><span class="p">)</span>
437
438 <span class="k">print</span> <span class="n">Sqrt</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">Sqrt</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span>
439 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Sqrt</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">Sqrt</span><span class="p">(</span><span class="mi">3</span><span class="p">))</span>
440 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Sqrt</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">Sqrt</span><span class="p">(</span><span class="mi">3</span><span class="p">))</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span>
441 <span class="c"># The sexpr() method is available for any Z3 expression</span>
442 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">Sqrt</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="o">*</span> <span class="mi">2</span><span class="p">)</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span>
443 </pre></div>
444 </body></html></example>
445
446 <h2>Machine Arithmetic</h2>
447
448 <p>
449 Modern CPUs and main-stream programming languages use
450 arithmetic over fixed-size bit-vectors.
451 Machine arithmetic is available in Z3Py as <i>Bit-Vectors</i>.
452 They implement the
453 precise semantics of unsigned and of
454 signed <a target="_blank" href="http://en.wikipedia.org/wiki/Two's_complement">two-complements arithmetic</a>.
455
456 </p>
457 <p>
458 The following example demonstrates how to create bit-vector variables and constants.
459 The function <tt>BitVec('x', 16)</tt> creates a bit-vector variable in Z3 named <tt>x</tt> with <tt>16</tt> bits.
460 For convenience, integer constants can be used to create bit-vector expressions in Z3Py.
461 The function <tt>BitVecVal(10, 32)</tt> creates a bit-vector of size <tt>32</tt> containing the value <tt>10</tt>.
462 </p>
463
464 <example pref="bitvec.1"><html><body>
465 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">BitVec</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
466 <span class="n">y</span> <span class="o">=</span> <span class="n">BitVec</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
467 <span class="k">print</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">2</span>
468 <span class="c"># Internal representation</span>
469 <span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span>
470
471 <span class="c"># -1 is equal to 65535 for 16-bit integers </span>
472 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
473
474 <span class="c"># Creating bit-vector constants</span>
475 <span class="n">a</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
476 <span class="n">b</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">65535</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
477 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span>
478
479 <span class="n">a</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
480 <span class="n">b</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">65535</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
481 <span class="c"># -1 is not equal to 65535 for 32-bit integers </span>
482 <span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">b</span><span class="p">)</span>
483 </pre></div>
484 </body></html></example>
485
486 <p>
487 In contrast to programming languages, such as C, C++, C#, Java,
488 there is no distinction between signed and unsigned bit-vectors
489 as numbers. Instead, Z3 provides special signed versions of arithmetical operations
490 where it makes a difference whether the bit-vector is treated as signed or unsigned.
491 In Z3Py, the operators
492 <tt class="pre">&lt;</tt>,
493 <tt class="pre">&lt;=</tt>,
494 <tt class="pre">&gt;</tt>,
495 <tt class="pre">&gt;=</tt>, <tt>/</tt>, <tt>%</tt> and <tt>&gt;&gt;</tt> correspond to the signed versions.
496 The corresponding unsigned operators are
497 <tt class="pre">ULT</tt>,
498 <tt class="pre">ULE</tt>,
499 <tt class="pre">UGT</tt>,
500 <tt class="pre">UGE</tt>, <tt>UDiv</tt>, <tt>URem</tt> and <tt>LShR</tt>.
501 </p>
502
503 <example pref="bitvec.2"><html><body>
504 <div class="highlight"><pre><span class="c"># Create to bit-vectors of size 32</span>
505 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">BitVecs</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
506
507 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">==</span> <span class="mi">2</span><span class="p">,</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
508
509 <span class="c"># Bit-wise operators</span>
510 <span class="c"># &amp; bit-wise and</span>
511 <span class="c"># | bit-wise or</span>
512 <span class="c"># ~ bit-wise not</span>
513 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&amp;</span> <span class="n">y</span> <span class="o">==</span> <span class="o">~</span><span class="n">y</span><span class="p">)</span>
514
515 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span>
516
517 <span class="c"># using unsigned version of &lt; </span>
518 <span class="n">solve</span><span class="p">(</span><span class="n">ULT</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="mi">0</span><span class="p">))</span>
519 </pre></div>
520 </body></html></example>
521
522 <p>
523 The operator <tt>&gt;&gt;</tt> is the arithmetic shift right, and
524 <tt>&lt;&lt;</tt> is the shift left. The logical shift right is the operator <tt>LShR</tt>.
525 </p>
526
527 <example pref="bitvec.3"><html><body>
528 <div class="highlight"><pre><span class="c"># Create to bit-vectors of size 32</span>
529 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">BitVecs</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
530
531 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">3</span><span class="p">)</span>
532
533 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">3</span><span class="p">)</span>
534
535 <span class="n">solve</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">24</span><span class="p">)</span>
536 </pre></div>
537 </body></html></example>
538
539 <h2>Functions</h2>
540
541 <p>
542 Unlike programming languages, where functions have side-effects, can throw exceptions,
543 or never return, functions in Z3 have no side-effects and are <b>total</b>.
544 That is, they are defined on all input values. This includes functions, such
545 as division. Z3 is based on <a target="_blank" href="http://en.wikipedia.org/wiki/First-order_logic">first-order logic</a>.
546 </p>
547
548 <p>
549 Given a constraints such as <tt>x + y &gt; 3</tt>, we have been saying that <tt>x</tt> and <tt>y</tt>
550 are variables. In many textbooks, <tt>x</tt> and <tt>y</tt> are called uninterpreted constants.
551 That is, they allow any interpretation that is consistent with the constraint <tt>x + y &gt; 3</tt>.
552 </p>
553
554 <p>
555 More precisely, function and constant symbols in pure first-order logic are <i>uninterpreted</i> or <i>free</i>,
556 which means that no a priori interpretation is attached.
557 This is in contrast to functions belonging to the signature of theories,
558 such as arithmetic where the function <tt>+</tt> has a fixed standard interpretation
559 (it adds two numbers). Uninterpreted functions and constants are maximally flexible;
560 they allow any interpretation that is consistent with the constraints over the function or constant.
561 </p>
562
563 <p>
564 To illustrate uninterpreted functions and constants let us the uninterpreted integer constants (aka variables)
565 <tt>x</tt>, <tt>y</tt>. Finally let <tt>f</tt> be an uninterpreted function that takes one argument of type (aka sort) integer
566 and results in an integer value.
567 The example illustrates how one can force an interpretation where <tt>f</tt>
568 applied twice to <tt>x</tt> results in <tt>x</tt> again, but <tt>f</tt> applied once to <tt>x</tt> is different from <tt>x</tt>.
569 </p>
570
571 <example pref="z3py.14"><html><body>
572 <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>
573 <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>
574 <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>
575 <span class="n">solve</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>
576 </pre></div>
577 </body></html></example>
578
579 <p>The solution (interpretation) for <tt>f</tt> should be read as <tt>f(0)</tt> is <tt>1</tt>, <tt>f(1)</tt> is <tt>0</tt>, and <tt>f(a)</tt>
580 is <tt>1</tt> for all <tt>a</tt> different from <tt>0</tt> and <tt>1</tt>.
581 </p>
582
583 <p>In Z3, we can also evaluate expressions in the model for a system of constraints. The following example shows how to
584 use the <tt>evaluate</tt> method.</p>
585
586 <example pref="z3py.15"><html><body>
587 <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>
588 <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>
589 <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>
590 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
591 <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>
592 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
593 <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>
594 <span class="k">print</span> <span class="s">"f(f(x)) ="</span><span class="p">,</span> <span class="n">m</span><span class="o">.</span><span class="n">evaluate</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>
595 <span class="k">print</span> <span class="s">"f(x) ="</span><span class="p">,</span> <span class="n">m</span><span class="o">.</span><span class="n">evaluate</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">))</span>
596 </pre></div>
597 </body></html></example>
598
599 <h2>Satisfiability and Validity</h2>
600
601 <p>A formula/constraint <tt>F</tt> is <b>valid</b> if <tt>F</tt> always evaluates to true for any assignment of appropriate values to its
602 uninterpreted symbols.
603 A formula/constraint <tt>F</tt> is <b>satisfiable</b> if there is some assignment of appropriate values
604 to its uninterpreted symbols under which <tt>F</tt> evaluates to true.
605 Validity is about finding a proof of a statement; satisfiability is about finding a solution to a set of constraints.
606 Consider a formula <tt>F</tt> containing <tt>a</tt> and <tt>b</tt>.
607 We can ask whether <tt>F</tt> is valid, that is whether it is always true for any combination of values for
608 <tt>a</tt> and <tt>b</tt>. If <tt>F</tt> is always
609 true, then <tt>Not(F)</tt> is always false, and then <tt>Not(F)</tt> will not have any satisfying assignment (i.e., solution); that is,
610 <tt>Not(F)</tt> is unsatisfiable. That is,
611 <tt>F</tt> is valid precisely when <tt>Not(F)</tt> is not satisfiable (is unsatisfiable).
612 Alternately,
613 <tt>F</tt> is satisfiable if and only if <tt>Not(F)</tt> is not valid (is invalid).
614 The following example proves the deMorgan's law.
615 </p>
616
617 <p>The following example redefines the Z3Py function <tt>prove</tt> that receives a formula as a parameter.
618 This function creates a solver, adds/asserts the negation of the formula, and check if the negation is unsatisfiable.
619 The implementation of this function is a simpler version of the Z3Py command <tt>prove</tt>.
620 </p>
621
622 <example pref="z3py.16"><html><body>
623 <div class="highlight"><pre><span class="n">p</span><span class="p">,</span> <span class="n">q</span> <span class="o">=</span> <span class="n">Bools</span><span class="p">(</span><span class="s">'p q'</span><span class="p">)</span>
624 <span class="n">demorgan</span> <span class="o">=</span> <span class="n">And</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">q</span><span class="p">)</span> <span class="o">==</span> <span class="n">Not</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">Not</span><span class="p">(</span><span class="n">p</span><span class="p">),</span> <span class="n">Not</span><span class="p">(</span><span class="n">q</span><span class="p">)))</span>
625 <span class="k">print</span> <span class="n">demorgan</span>
626
627 <span class="k">def</span> <span class="nf">prove</span><span class="p">(</span><span class="n">f</span><span class="p">):</span>
628 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
629 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Not</span><span class="p">(</span><span class="n">f</span><span class="p">))</span>
630 <span class="k">if</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> <span class="o">==</span> <span class="n">unsat</span><span class="p">:</span>
631 <span class="k">print</span> <span class="s">"proved"</span>
632 <span class="k">else</span><span class="p">:</span>
633 <span class="k">print</span> <span class="s">"failed to prove"</span>
634
635 <span class="k">print</span> <span class="s">"Proving demorgan..."</span>
636 <span class="n">prove</span><span class="p">(</span><span class="n">demorgan</span><span class="p">)</span>
637 </pre></div>
638 </body></html></example>
639
640 <h2>List Comprehensions</h2>
641
642 <p>
643 Python supports <a target="_blank" href="http://docs.python.org/tutorial/datastructures.html#list-comprehensions">list comprehensions</a>.
644 List comprehensions provide a concise way to create lists. They can be used to create Z3 expressions and problems in Z3Py.
645 The following example demonstrates how to use Python list comprehensions in Z3Py.
646 </p>
647
648 <example pref="list.1"><html><body>
649 <div class="highlight"><pre><span class="c"># Create list [1, ..., 5] </span>
650 <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="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">5</span><span class="p">)</span> <span class="p">]</span>
651
652 <span class="c"># Create two lists containing 5 integer variables</span>
653 <span class="n">X</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x</span><span class="si">%s</span><span class="s">'</span> <span class="o">%</span> <span class="n">i</span><span class="p">)</span> <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="mi">5</span><span class="p">)</span> <span class="p">]</span>
654 <span class="n">Y</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Int</span><span class="p">(</span><span class="s">'y</span><span class="si">%s</span><span class="s">'</span> <span class="o">%</span> <span class="n">i</span><span class="p">)</span> <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="mi">5</span><span class="p">)</span> <span class="p">]</span>
655 <span class="k">print</span> <span class="n">X</span>
656
657 <span class="c"># Create a list containing X[i]+Y[i]</span>
658 <span class="n">X_plus_Y</span> <span class="o">=</span> <span class="p">[</span> <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="n">Y</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <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="mi">5</span><span class="p">)</span> <span class="p">]</span>
659 <span class="k">print</span> <span class="n">X_plus_Y</span>
660
661 <span class="c"># Create a list containing X[i] &gt; Y[i]</span>
662 <span class="n">X_gt_Y</span> <span class="o">=</span> <span class="p">[</span> <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">Y</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <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="mi">5</span><span class="p">)</span> <span class="p">]</span>
663 <span class="k">print</span> <span class="n">X_gt_Y</span>
664
665 <span class="k">print</span> <span class="n">And</span><span class="p">(</span><span class="n">X_gt_Y</span><span class="p">)</span>
666
667 <span class="c"># Create a 3x3 "matrix" (list of lists) of integer variables</span>
668 <span class="n">X</span> <span class="o">=</span> <span class="p">[</span> <span class="p">[</span> <span class="n">Int</span><span class="p">(</span><span class="s">"x_</span><span class="si">%s</span><span class="s">_</span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="p">]</span>
669 <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="mi">3</span><span class="p">)</span> <span class="p">]</span>
670 <span class="n">pp</span><span class="p">(</span><span class="n">X</span><span class="p">)</span>
671 </pre></div>
672 </body></html></example>
673
674 <p>In the example above, the expression <tt>"x%s" % i</tt> returns a string where <tt>%s</tt> is replaced with the value of <tt>i</tt>.</p>
675
676 <p>The command <tt>pp</tt> is similar to <tt>print</tt>, but it uses Z3Py formatter for lists and tuples instead of Python's formatter.</p>
677
678 <p>Z3Py also provides functions for creating vectors of Boolean, Integer and Real variables. These functions
679 are implemented using list comprehensions.
680 </p>
681
682 <example pref="list.2"><html><body>
683 <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">5</span><span class="p">)</span>
684 <span class="n">Y</span> <span class="o">=</span> <span class="n">RealVector</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span> <span class="mi">5</span><span class="p">)</span>
685 <span class="n">P</span> <span class="o">=</span> <span class="n">BoolVector</span><span class="p">(</span><span class="s">'p'</span><span class="p">,</span> <span class="mi">5</span><span class="p">)</span>
686 <span class="k">print</span> <span class="n">X</span>
687 <span class="k">print</span> <span class="n">Y</span>
688 <span class="k">print</span> <span class="n">P</span>
689 <span class="k">print</span> <span class="p">[</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="k">for</span> <span class="n">y</span> <span class="ow">in</span> <span class="n">Y</span> <span class="p">]</span>
690 <span class="k">print</span> <span class="n">Sum</span><span class="p">([</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="k">for</span> <span class="n">y</span> <span class="ow">in</span> <span class="n">Y</span> <span class="p">])</span>
691 </pre></div>
692 </body></html></example>
693
694 <h2>Kinematic Equations</h2>
695
696 <p>
697 In high school, students learn the kinematic equations.
698 These equations describe the mathematical relationship between <b>displacement</b> (<tt>d</tt>),
699 <b>time</b> (<tt>t</tt>), <b>acceleration</b> (<tt>a</tt>), <b>initial velocity</b> (<tt>v_i</tt>) and <b>final velocity</b> (<tt>v_f</tt>).
700 In Z3Py notation, we can write these equations as:
701 </p>
702 <pre>
703 d == v_i * t + (a*t**2)/2,
704 v_f == v_i + a*t
705 </pre>
706
707 <h3>Problem 1</h3>
708
709 <p>
710 Ima Hurryin is approaching a stoplight moving with a velocity of <tt>30.0</tt> m/s.
711 The light turns yellow, and Ima applies the brakes and skids to a stop.
712 If Ima's acceleration is <tt>-8.00</tt> m/s<sup>2</sup>, then determine the displacement of the
713 car during the skidding process.
714 </p>
715
716 <example pref="k.1"><html><body>
717 <div class="highlight"><pre><span class="n">d</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">v_i</span><span class="p">,</span> <span class="n">v_f</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'d a t v__i v__f'</span><span class="p">)</span>
718
719 <span class="n">equations</span> <span class="o">=</span> <span class="p">[</span>
720 <span class="n">d</span> <span class="o">==</span> <span class="n">v_i</span> <span class="o">*</span> <span class="n">t</span> <span class="o">+</span> <span class="p">(</span><span class="n">a</span><span class="o">*</span><span class="n">t</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span>
721 <span class="n">v_f</span> <span class="o">==</span> <span class="n">v_i</span> <span class="o">+</span> <span class="n">a</span><span class="o">*</span><span class="n">t</span><span class="p">,</span>
722 <span class="p">]</span>
723 <span class="k">print</span> <span class="s">"Kinematic equations:"</span>
724 <span class="k">print</span> <span class="n">equations</span>
725
726 <span class="c"># Given v_i, v_f and a, find d</span>
727 <span class="n">problem</span> <span class="o">=</span> <span class="p">[</span>
728 <span class="n">v_i</span> <span class="o">==</span> <span class="mi">30</span><span class="p">,</span>
729 <span class="n">v_f</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span>
730 <span class="n">a</span> <span class="o">==</span> <span class="o">-</span><span class="mi">8</span>
731 <span class="p">]</span>
732 <span class="k">print</span> <span class="s">"Problem:"</span>
733 <span class="k">print</span> <span class="n">problem</span>
734
735 <span class="k">print</span> <span class="s">"Solution:"</span>
736 <span class="n">solve</span><span class="p">(</span><span class="n">equations</span> <span class="o">+</span> <span class="n">problem</span><span class="p">)</span>
737 </pre></div>
738 </body></html></example>
739
740
741 <h3>Problem 2</h3>
742
743 <p>
744 Ben Rushin is waiting at a stoplight. When it finally turns green, Ben accelerated from rest at a rate of
745 a <tt>6.00</tt> m/s<sup>2</sup> for a time of <tt>4.10</tt> seconds. Determine the displacement of Ben's car during this time period.
746 </p>
747
748 <example pref="k.2"><html><body>
749 <div class="highlight"><pre><span class="n">d</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">v_i</span><span class="p">,</span> <span class="n">v_f</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'d a t v__i v__f'</span><span class="p">)</span>
750
751 <span class="n">equations</span> <span class="o">=</span> <span class="p">[</span>
752 <span class="n">d</span> <span class="o">==</span> <span class="n">v_i</span> <span class="o">*</span> <span class="n">t</span> <span class="o">+</span> <span class="p">(</span><span class="n">a</span><span class="o">*</span><span class="n">t</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span>
753 <span class="n">v_f</span> <span class="o">==</span> <span class="n">v_i</span> <span class="o">+</span> <span class="n">a</span><span class="o">*</span><span class="n">t</span><span class="p">,</span>
754 <span class="p">]</span>
755
756 <span class="c"># Given v_i, t and a, find d</span>
757 <span class="n">problem</span> <span class="o">=</span> <span class="p">[</span>
758 <span class="n">v_i</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span>
759 <span class="n">t</span> <span class="o">==</span> <span class="mf">4.10</span><span class="p">,</span>
760 <span class="n">a</span> <span class="o">==</span> <span class="mi">6</span>
761 <span class="p">]</span>
762
763 <span class="n">solve</span><span class="p">(</span><span class="n">equations</span> <span class="o">+</span> <span class="n">problem</span><span class="p">)</span>
764
765 <span class="c"># Display rationals in decimal notation</span>
766 <span class="n">set_option</span><span class="p">(</span><span class="n">rational_to_decimal</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span>
767
768 <span class="n">solve</span><span class="p">(</span><span class="n">equations</span> <span class="o">+</span> <span class="n">problem</span><span class="p">)</span>
769 </pre></div>
770 </body></html></example>
771
772 <h2>Bit Tricks</h2>
773
774 <p>Some low level <a target="_blank" href="http://graphics.stanford.edu/~seander/bithacks.html">hacks</a> are very popular with C programmers.
775 We use some of these hacks in the Z3 implementation.
776 </p>
777
778 <h3>Power of two</h3>
779
780 <p>This hack is frequently used in C programs (Z3 included) to test whether a machine integer is a power of two.
781 We can use Z3 to prove it really works. The claim is that <tt>x != 0 &amp;&amp; !(x &amp; (x - 1))</tt> is true if and only if <tt>x</tt>
782 is a power of two.
783 </p>
784
785 <example pref="bit.1"><html><body>
786 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">BitVec</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
787 <span class="n">powers</span> <span class="o">=</span> <span class="p">[</span> <span class="mi">2</span><span class="o">**</span><span class="n">i</span> <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="mi">32</span><span class="p">)</span> <span class="p">]</span>
788 <span class="n">fast</span> <span class="o">=</span> <span class="n">And</span><span class="p">(</span><span class="n">x</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">&amp;</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="mi">0</span><span class="p">)</span>
789 <span class="n">slow</span> <span class="o">=</span> <span class="n">Or</span><span class="p">([</span> <span class="n">x</span> <span class="o">==</span> <span class="n">p</span> <span class="k">for</span> <span class="n">p</span> <span class="ow">in</span> <span class="n">powers</span> <span class="p">])</span>
790 <span class="k">print</span> <span class="n">fast</span>
791 <span class="n">prove</span><span class="p">(</span><span class="n">fast</span> <span class="o">==</span> <span class="n">slow</span><span class="p">)</span>
792
793 <span class="k">print</span> <span class="s">"trying to prove buggy version..."</span>
794 <span class="n">fast</span> <span class="o">=</span> <span class="n">x</span> <span class="o">&amp;</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="mi">0</span>
795 <span class="n">prove</span><span class="p">(</span><span class="n">fast</span> <span class="o">==</span> <span class="n">slow</span><span class="p">)</span>
796 </pre></div>
797 </body></html></example>
798
799 <h3>Opposite signs</h3>
800
801 <p>The following simple hack can be used to test whether two machine integers have opposite signs.</p>
802
803 <example pref="bit.2"><html><body>
804 <div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">BitVec</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
805 <span class="n">y</span> <span class="o">=</span> <span class="n">BitVec</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span> <span class="mi">32</span><span class="p">)</span>
806
807 <span class="c"># Claim: (x ^ y) &lt; 0 iff x and y have opposite signs</span>
808 <span class="n">trick</span> <span class="o">=</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">&lt;</span> <span class="mi">0</span>
809
810 <span class="c"># Naive way to check if x and y have opposite signs</span>
811 <span class="n">opposite</span> <span class="o">=</span> <span class="n">Or</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">),</span>
812 <span class="n">And</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">))</span>
813
814 <span class="n">prove</span><span class="p">(</span><span class="n">trick</span> <span class="o">==</span> <span class="n">opposite</span><span class="p">)</span>
815 </pre></div>
816 </body></html></example>
817
818 <h2>Puzzles</h2>
819
820 <h3>Dog, Cat and Mouse</h3>
821
822 <p>Consider the following puzzle. Spend exactly 100 dollars and buy exactly 100 animals.
823 Dogs cost 15 dollars, cats cost 1 dollar, and mice cost 25 cents each.
824 You have to buy at least one of each.
825 How many of each should you buy?
826 </p>
827
828 <example pref="puzzle.1"><html><body>
829 <div class="highlight"><pre><span class="c"># Create 3 integer variables</span>
830 <span class="n">dog</span><span class="p">,</span> <span class="n">cat</span><span class="p">,</span> <span class="n">mouse</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'dog cat mouse'</span><span class="p">)</span>
831 <span class="n">solve</span><span class="p">(</span><span class="n">dog</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">,</span> <span class="c"># at least one dog</span>
832 <span class="n">cat</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">,</span> <span class="c"># at least one cat</span>
833 <span class="n">mouse</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">,</span> <span class="c"># at least one mouse</span>
834 <span class="c"># we want to buy 100 animals</span>
835 <span class="n">dog</span> <span class="o">+</span> <span class="n">cat</span> <span class="o">+</span> <span class="n">mouse</span> <span class="o">==</span> <span class="mi">100</span><span class="p">,</span>
836 <span class="c"># We have 100 dollars (10000 cents):</span>
837 <span class="c"># dogs cost 15 dollars (1500 cents), </span>
838 <span class="c"># cats cost 1 dollar (100 cents), and </span>
839 <span class="c"># mice cost 25 cents </span>
840 <span class="mi">1500</span> <span class="o">*</span> <span class="n">dog</span> <span class="o">+</span> <span class="mi">100</span> <span class="o">*</span> <span class="n">cat</span> <span class="o">+</span> <span class="mi">25</span> <span class="o">*</span> <span class="n">mouse</span> <span class="o">==</span> <span class="mi">10000</span><span class="p">)</span>
841 </pre></div>
842 </body></html></example>
843
844 <h3>Sudoku</h3>
845
846 <p><a target="_blank" href="http://www.dailysudoku.com/sudoku/">Sudoku</a> is a very popular puzzle.
847 The goal is to insert the numbers in the boxes to satisfy only one condition: each row, column and
848 <tt>3x3</tt> box must contain the digits <tt>1</tt> through <tt>9</tt> exactly once.
849 </p>
850
851 <img style="width:213px;margin:20px;" src="examples/sudoku.png">
852
853 <p>
854 The following example encodes the sudoku problem in Z3. Different sudoku instances can be solved
855 by modifying the matrix <tt>instance</tt>. This example makes heavy use of
856 <a target="_blank" href="http://docs.python.org/tutorial/datastructures.html#list-comprehensions">list comprehensions</a>
857 available in the Python programming language.
858 </p>
859
860 <example pref="puzzle.2"><html><body>
861 <div class="highlight"><pre><span class="c"># 9x9 matrix of integer variables</span>
862 <span class="n">X</span> <span class="o">=</span> <span class="p">[</span> <span class="p">[</span> <span class="n">Int</span><span class="p">(</span><span class="s">"x_</span><span class="si">%s</span><span class="s">_</span><span class="si">%s</span><span class="s">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">))</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">9</span><span class="p">)</span> <span class="p">]</span>
863 <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="mi">9</span><span class="p">)</span> <span class="p">]</span>
864
865 <span class="c"># each cell contains a value in {1, ..., 9}</span>
866 <span class="n">cells_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">And</span><span class="p">(</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="mi">9</span><span class="p">)</span>
867 <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="mi">9</span><span class="p">)</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">9</span><span class="p">)</span> <span class="p">]</span>
868
869 <span class="c"># each row contains a digit at most once</span>
870 <span class="n">rows_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Distinct</span><span class="p">(</span><span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <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="mi">9</span><span class="p">)</span> <span class="p">]</span>
871
872 <span class="c"># each column contains a digit at most once</span>
873 <span class="n">cols_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Distinct</span><span class="p">([</span> <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <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="mi">9</span><span class="p">)</span> <span class="p">])</span>
874 <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">9</span><span class="p">)</span> <span class="p">]</span>
875
876 <span class="c"># each 3x3 square contains a digit at most once</span>
877 <span class="n">sq_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Distinct</span><span class="p">([</span> <span class="n">X</span><span class="p">[</span><span class="mi">3</span><span class="o">*</span><span class="n">i0</span> <span class="o">+</span> <span class="n">i</span><span class="p">][</span><span class="mi">3</span><span class="o">*</span><span class="n">j0</span> <span class="o">+</span> <span class="n">j</span><span class="p">]</span>
878 <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="mi">3</span><span class="p">)</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="p">])</span>
879 <span class="k">for</span> <span class="n">i0</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="k">for</span> <span class="n">j0</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> <span class="p">]</span>
880
881 <span class="n">sudoku_c</span> <span class="o">=</span> <span class="n">cells_c</span> <span class="o">+</span> <span class="n">rows_c</span> <span class="o">+</span> <span class="n">cols_c</span> <span class="o">+</span> <span class="n">sq_c</span>
882
883 <span class="c"># sudoku instance, we use '0' for empty cells</span>
884 <span class="n">instance</span> <span class="o">=</span> <span class="p">((</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">9</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">3</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
885 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">7</span><span class="p">),</span>
886 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
887 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">8</span><span class="p">),</span>
888 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">6</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
889 <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
890 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">7</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
891 <span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">6</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">),</span>
892 <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">9</span><span class="p">,</span><span class="mi">7</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="mi">0</span><span class="p">))</span>
893
894 <span class="n">instance_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">If</span><span class="p">(</span><span class="n">instance</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span>
895 <span class="bp">True</span><span class="p">,</span>
896 <span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="n">instance</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">])</span>
897 <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="mi">9</span><span class="p">)</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">9</span><span class="p">)</span> <span class="p">]</span>
898
899 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
900 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">sudoku_c</span> <span class="o">+</span> <span class="n">instance_c</span><span class="p">)</span>
901 <span class="k">if</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> <span class="o">==</span> <span class="n">sat</span><span class="p">:</span>
902 <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>
903 <span class="n">r</span> <span class="o">=</span> <span class="p">[</span> <span class="p">[</span> <span class="n">m</span><span class="o">.</span><span class="n">evaluate</span><span class="p">(</span><span class="n">X</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">])</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">9</span><span class="p">)</span> <span class="p">]</span>
904 <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="mi">9</span><span class="p">)</span> <span class="p">]</span>
905 <span class="n">print_matrix</span><span class="p">(</span><span class="n">r</span><span class="p">)</span>
906 <span class="k">else</span><span class="p">:</span>
907 <span class="k">print</span> <span class="s">"failed to solve"</span>
908 </pre></div>
909 </body></html></example>
910
911 <h3>Eight Queens</h3>
912
913 <p>
914 The eight queens puzzle is the problem of placing eight chess queens on an 8x8 chessboard so that no two queens attack each other.
915 Thus, a solution requires that no two queens share the same row, column, or diagonal.
916 </p>
917
918 <p> <img style="margin:20px;" src="examples/queens.png">
919 </p>
920
921 <example pref="puzzle.3"><html><body>
922 <div class="highlight"><pre><span class="c"># We know each queen must be in a different row.</span>
923 <span class="c"># So, we represent each queen by a single integer: the column position</span>
924 <span class="n">Q</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Int</span><span class="p">(</span><span class="s">'Q_</span><span class="si">%i</span><span class="s">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">))</span> <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="mi">8</span><span class="p">)</span> <span class="p">]</span>
925
926 <span class="c"># Each queen is in a column {1, ... 8 }</span>
927 <span class="n">val_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">And</span><span class="p">(</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="mi">8</span><span class="p">)</span> <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="mi">8</span><span class="p">)</span> <span class="p">]</span>
928
929 <span class="c"># At most one queen per column</span>
930 <span class="n">col_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Distinct</span><span class="p">(</span><span class="n">Q</span><span class="p">)</span> <span class="p">]</span>
931
932 <span class="c"># Diagonal constraint</span>
933 <span class="n">diag_c</span> <span class="o">=</span> <span class="p">[</span> <span class="n">If</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">j</span><span class="p">,</span>
934 <span class="bp">True</span><span class="p">,</span>
935 <span class="n">And</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="n">Q</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">i</span> <span class="o">-</span> <span class="n">j</span><span class="p">,</span> <span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="n">Q</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">!=</span> <span class="n">j</span> <span class="o">-</span> <span class="n">i</span><span class="p">))</span>
936 <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="mi">8</span><span class="p">)</span> <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> <span class="p">]</span>
937
938 <span class="n">solve</span><span class="p">(</span><span class="n">val_c</span> <span class="o">+</span> <span class="n">col_c</span> <span class="o">+</span> <span class="n">diag_c</span><span class="p">)</span>
939 </pre></div>
940 </body></html></example>
941
942 <h2>Application: Install Problem</h2>
943
944 <p>The <b>install problem</b> consists of determining whether a new set of packages can be installed in a system.
945 This application is based on the article
946 <a target="_blank" href="http://cseweb.ucsd.edu/~rjhala/papers/opium.pdf">OPIUM: Optimal Package Install/Uninstall Manager</a>.
947 Many packages depend on other packages to provide some functionality.
948 Each distribution contains a meta-data file that
949 explicates the requirements of each package of the distribution.
950 The meta-data contains details like the name, version, etc. More importantly, it contains
951 <b>depends</b> and <b>conflicts</b>
952 clauses that stipulate which other packages should be on the
953 system. The depends clauses stipulate which other packages must be present.
954 The conflicts clauses stipulate which other packages must not be present.
955 </p>
956
957 <p>The install problem can be easily solved using Z3. The idea is to define a Boolean variable for each
958 package. This variable is true if the package must be in the system. If package <tt>a</tt> depends on
959 packages <tt>b</tt>, <tt>c</tt> and <tt>z</tt>, we write:
960 </p>
961
962 <pre>
963 DependsOn(a, [b, c, z])
964 </pre>
965
966 <p><tt>DependsOn</tt> is a simple Python function that creates Z3 constraints that capture the
967 depends clause semantics.
968 </p>
969
970 <pre>
971 def DependsOn(pack, deps):
972 return And([ Implies(pack, dep) for dep in deps ])
973 </pre>
974
975 <p>
976 Thus, <tt>Depends(a, [b, c, z])</tt> generates the constraint
977 </p>
978
979 <pre>
980 And(Implies(a, b), Implies(a, c), Implies(a, z))
981 </pre>
982
983 <p>That is, if users install package <tt>a</tt>, they must also install packages
984 <tt>b</tt>, <tt>c</tt> and <tt>z</tt>.
985 </p>
986
987 <p>
988 If package <tt>d</tt> conflicts with package <tt>e</tt>, we write <tt>Conflict(d, e)</tt>.
989 <tt>Conflict</tt> is also a simple Python function.
990 </p>
991
992 <pre>
993 def Conflict(p1, p2):
994 return Or(Not(p1), Not(p2))
995 </pre>
996
997 <p><tt>Conflict(d, e)</tt> generates the constraint <tt>Or(Not(d), Not(e))</tt>.
998 With these two functions, we can easily encode the example in the
999 <a target="_blank" href="http://cseweb.ucsd.edu/~rjhala/papers/opium.pdf">Opium article</a> (Section 2) in Z3Py as:
1000 </p>
1001
1002 <example pref="install.1"><html><body>
1003 <div class="highlight"><pre><span class="k">def</span> <span class="nf">DependsOn</span><span class="p">(</span><span class="n">pack</span><span class="p">,</span> <span class="n">deps</span><span class="p">):</span>
1004 <span class="k">return</span> <span class="n">And</span><span class="p">([</span> <span class="n">Implies</span><span class="p">(</span><span class="n">pack</span><span class="p">,</span> <span class="n">dep</span><span class="p">)</span> <span class="k">for</span> <span class="n">dep</span> <span class="ow">in</span> <span class="n">deps</span> <span class="p">])</span>
1005
1006 <span class="k">def</span> <span class="nf">Conflict</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">):</span>
1007 <span class="k">return</span> <span class="n">Or</span><span class="p">(</span><span class="n">Not</span><span class="p">(</span><span class="n">p1</span><span class="p">),</span> <span class="n">Not</span><span class="p">(</span><span class="n">p2</span><span class="p">))</span>
1008
1009 <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="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">e</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">z</span> <span class="o">=</span> <span class="n">Bools</span><span class="p">(</span><span class="s">'a b c d e f g z'</span><span class="p">)</span>
1010
1011 <span class="n">solve</span><span class="p">(</span><span class="n">DependsOn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="p">[</span><span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">z</span><span class="p">]),</span>
1012 <span class="n">DependsOn</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="p">[</span><span class="n">d</span><span class="p">]),</span>
1013 <span class="n">DependsOn</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="p">[</span><span class="n">Or</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span> <span class="n">Or</span><span class="p">(</span><span class="n">f</span><span class="p">,</span> <span class="n">g</span><span class="p">)]),</span>
1014 <span class="n">Conflict</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span>
1015 <span class="n">a</span><span class="p">,</span> <span class="n">z</span><span class="p">)</span>
1016 </pre></div>
1017 </body></html></example>
1018
1019 <p>
1020 Note that the example contains the constraint
1021 </p>
1022
1023 <pre>
1024 DependsOn(c, [Or(d, e), Or(f, g)]),
1025 </pre>
1026
1027 <p>
1028 The meaning is: to install <tt>c</tt>, we must install <tt>d</tt> or <tt>e</tt>, and <tt>f</tt> or <tt>g</tt>
1029 </p>
1030
1031 <p>Now, we refine the previous example. First, we modify <tt>DependsOn</tt> to allow
1032 us to write <tt>DependsOn(b, d)</tt> instead of <tt>DependsOn(b, [d])</tt>. We also
1033 write a function <tt>install_check</tt> that returns a list of packages that must be installed
1034 in the system. The function <tt>Conflict</tt> is also modified. It can now receive multiple
1035 arguments.
1036 </p>
1037
1038 <example pref="install.2"><html><body>
1039 <div class="highlight"><pre><span class="k">def</span> <span class="nf">DependsOn</span><span class="p">(</span><span class="n">pack</span><span class="p">,</span> <span class="n">deps</span><span class="p">):</span>
1040 <span class="k">if</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">deps</span><span class="p">):</span>
1041 <span class="k">return</span> <span class="n">Implies</span><span class="p">(</span><span class="n">pack</span><span class="p">,</span> <span class="n">deps</span><span class="p">)</span>
1042 <span class="k">else</span><span class="p">:</span>
1043 <span class="k">return</span> <span class="n">And</span><span class="p">([</span> <span class="n">Implies</span><span class="p">(</span><span class="n">pack</span><span class="p">,</span> <span class="n">dep</span><span class="p">)</span> <span class="k">for</span> <span class="n">dep</span> <span class="ow">in</span> <span class="n">deps</span> <span class="p">])</span>
1044
1045 <span class="k">def</span> <span class="nf">Conflict</span><span class="p">(</span><span class="o">*</span><span class="n">packs</span><span class="p">):</span>
1046 <span class="k">return</span> <span class="n">Or</span><span class="p">([</span> <span class="n">Not</span><span class="p">(</span><span class="n">pack</span><span class="p">)</span> <span class="k">for</span> <span class="n">pack</span> <span class="ow">in</span> <span class="n">packs</span> <span class="p">])</span>
1047
1048 <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="p">,</span> <span class="n">d</span><span class="p">,</span> <span class="n">e</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">z</span> <span class="o">=</span> <span class="n">Bools</span><span class="p">(</span><span class="s">'a b c d e f g z'</span><span class="p">)</span>
1049
1050 <span class="k">def</span> <span class="nf">install_check</span><span class="p">(</span><span class="o">*</span><span class="n">problem</span><span class="p">):</span>
1051 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
1052 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="o">*</span><span class="n">problem</span><span class="p">)</span>
1053 <span class="k">if</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> <span class="o">==</span> <span class="n">sat</span><span class="p">:</span>
1054 <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>
1055 <span class="n">r</span> <span class="o">=</span> <span class="p">[]</span>
1056 <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">m</span><span class="p">:</span>
1057 <span class="k">if</span> <span class="n">is_true</span><span class="p">(</span><span class="n">m</span><span class="p">[</span><span class="n">x</span><span class="p">]):</span>
1058 <span class="c"># x is a Z3 declaration</span>
1059 <span class="c"># x() returns the Z3 expression</span>
1060 <span class="c"># x.name() returns a string</span>
1061 <span class="n">r</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">x</span><span class="p">())</span>
1062 <span class="k">print</span> <span class="n">r</span>
1063 <span class="k">else</span><span class="p">:</span>
1064 <span class="k">print</span> <span class="s">"invalid installation profile"</span>
1065
1066 <span class="k">print</span> <span class="s">"Check 1"</span>
1067 <span class="n">install_check</span><span class="p">(</span><span class="n">DependsOn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="p">[</span><span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">z</span><span class="p">]),</span>
1068 <span class="n">DependsOn</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">d</span><span class="p">),</span>
1069 <span class="n">DependsOn</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="p">[</span><span class="n">Or</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span> <span class="n">Or</span><span class="p">(</span><span class="n">f</span><span class="p">,</span> <span class="n">g</span><span class="p">)]),</span>
1070 <span class="n">Conflict</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span>
1071 <span class="n">Conflict</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">g</span><span class="p">),</span>
1072 <span class="n">a</span><span class="p">,</span> <span class="n">z</span><span class="p">)</span>
1073
1074 <span class="k">print</span> <span class="s">"Check 2"</span>
1075 <span class="n">install_check</span><span class="p">(</span><span class="n">DependsOn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="p">[</span><span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">z</span><span class="p">]),</span>
1076 <span class="n">DependsOn</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">d</span><span class="p">),</span>
1077 <span class="n">DependsOn</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="p">[</span><span class="n">Or</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span> <span class="n">Or</span><span class="p">(</span><span class="n">f</span><span class="p">,</span> <span class="n">g</span><span class="p">)]),</span>
1078 <span class="n">Conflict</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">e</span><span class="p">),</span>
1079 <span class="n">Conflict</span><span class="p">(</span><span class="n">d</span><span class="p">,</span> <span class="n">g</span><span class="p">),</span>
1080 <span class="n">a</span><span class="p">,</span> <span class="n">z</span><span class="p">,</span> <span class="n">g</span><span class="p">)</span>
1081 </pre></div>
1082 </body></html></example>
1083
1084 <h2>Using Z3Py Locally</h2>
1085
1086 <p>Z3Py is part of the Z3 distribution. It is located in the <tt>python</tt> subdirectory.
1087 To use it locally, you have to include the following command in your Python script.</p>
1088 <pre>
1089 from Z3 import *
1090 </pre>
1091 <p>
1092 The Z3 Python frontend directory must be in your <tt>PYTHONPATH</tt> environment variable.
1093 Z3Py will automatically search for the Z3 library (<tt>z3.dll</tt> (Windows), <tt>libz3.so</tt> (Linux), or <tt>libz3.dylib</tt> (OSX)).
1094 You may also initialize Z3Py manually using the command:
1095 </p>
1096 <pre>
1097 init("z3.dll")
1098 </pre>
1099
1100 </body>
1101 </html>