| 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">></span> <span class="mi">2</span><span class="p">,</span> <span class="n">y</span> <span class="o"><</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"><</tt>, |
| 47 |
<tt class="pre"><=</tt>, |
| 48 |
<tt class="pre">></tt>, |
| 49 |
<tt class="pre">>=</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"><</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">>=</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">>=</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>∧</tt> is the logical and, <tt>∨</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">>=</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">>=</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">>=</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">></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"><</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">></span> <span class="mi">4</span><span class="p">,</span> <span class="n">x</span> <span class="o"><</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"><</span> <span class="mi">5</span><span class="p">,</span> <span class="n">x</span> <span class="o">></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">></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"><</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">></span> <span class="mi">1</span><span class="p">,</span> <span class="n">y</span> <span class="o">></span> <span class="mi">1</span><span class="p">,</span> <span class="n">Or</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">3</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> |
| 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">></span> <span class="mi">1</span><span class="p">,</span> <span class="n">y</span> <span class="o">></span> <span class="mi">1</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">></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"><</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">></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"><=</span> <span class="mi">1000</span><span class="p">,</span> |
| 392 |
<span class="n">d</span> <span class="o">>=</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="”_blank”" 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">></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"><</tt>, |
| 493 |
<tt class="pre"><=</tt>, |
| 494 |
<tt class="pre">></tt>, |
| 495 |
<tt class="pre">>=</tt>, <tt>/</tt>, <tt>%</tt> and <tt>>></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">></span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">></span> <span class="mi">0</span><span class="p">)</span> |
| 508 |
|
| 509 |
<span class="c"># Bit-wise operators</span> |
| 510 |
<span class="c"># & 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">&</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"><</span> <span class="mi">0</span><span class="p">)</span> |
| 516 |
|
| 517 |
<span class="c"># using unsigned version of < </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>>></tt> is the arithmetic shift right, and |
| 524 |
<tt><<</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">>></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"><<</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"><<</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 > 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 > 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] > 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">></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 && !(x & (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">&</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">&</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) < 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"><</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"><</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">>=</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">>=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o"><</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">>=</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">>=</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">>=</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"><=</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"><=</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"><=</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"><=</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> |