Differences

This shows you the differences between two versions of the page.

--- sav08:fixed-width_bitvectors [2008/03/12 22:12]
vkuncak
+++ sav08:fixed-width_bitvectors [2015/04/21 17:30] (current)
@@ Line 14: / Line 14: @@
   * finding counterexamples for formulas over unbounded integers
+===== Expressing Linear Arithmetic with Given Bounds =====
+Consider formulas in our linear arithmetic language:
+   T ::= K | V | (T + T) | (T - T) | (K * T) | (T / K) | (T % K)
+   F ::= (T=T) | (T < T) | (T > T) | (~F) | (F & F) | (F|F)
+   V ::= x | y | z | ...
+   K ::= 0 | 1 | 2 | ...
+Suppose we are given bounds for all integer variables and that they belong to $[0,2^B-1]$.
+We present translation from $F$ to equisatisfiable $prop(F)$ in propositional logic.  That is,
+\begin{equation*}
+   \exists x_1,\ldots,x_n.\ F
+\end{equation*}
+is equivalent to
+\begin{equation*}
+   \exists p_1,\ldots,p_m.\ prop(F)
+\end{equation*}
+Where $FV(F)=\{x_1,\ldots,x_n\}$ and $FV(prop(F)) = \{p_1,\ldots,p_m\}$.
+For each bounded integer variable $x \in [0,2^B-1]$ we introduce propositional variables corresponding to its binary representation.
+The constructions for operations correspond to implementing these operations in hardware circuits:
+  * adder for +
+  * shift for *
+  * comparator for <, =
+Example: propositional formula expressing $x + y = z$ when $x,y,z \in [0,2^B-1]$.
+Note that subtraction can be expressed using addition, similarly for / and %.
+++How to express inverse operations for nested terms?|Flat form of formulas.++
+Additional pre-processing is useful.  Much more on such encodings we will see later, and can also be found here:
   * [[http://www.springerlink.com/content/t57g3616p4756140/|Bitvectors and Arrays]]
+  * [[http://www.decision-procedures.org/]]
+Later we will see how to prove that linear arithmetic holds for //all// bounds and not just given one.