Satisfiability and SMT Solving — SAT Solvers and Z3

In this tutorial, you'll learn about Satisfiability and SMT Solving. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

SAT and SMT solvers determine whether logical formulas have satisfying assignments, forming the backbone of bounded Model Checking, test generation, and program verification.

Learning Path

flowchart LR
  A["Propositional Logic"] --> B["SAT & SMT Solving
SAT Solvers & Z3"]
  B --> C["Bounded Model Checking"]
  B --> D["Z3 Solver Deep Dive"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Propositional logic and CNF. Basic Python programming.

What Is SAT Solving?

SAT asks: given a propositional formula in CNF, is there an assignment of variables to true/false that makes it true? Modern SAT solvers handle formulas with millions of clauses using conflict-driven clause learning (CDCL).

Step-by-Step: DPLL Algorithm

Step 1: Unit Propagation

If a clause has a single literal, assign it to true.

def unit_propagate(clauses, assignment):
    changed = True
    while changed:
        changed = False
        for clause in clauses:
            unassigned = [l for l in clause if abs(l) not in assignment]
            if len(unassigned) == 1:
                lit = unassigned[0]
                val = lit > 0
                assignment[abs(lit)] = val
                changed = True
    return clauses, assignment

clauses = [[1], [-1, 2], [-2, 3]]
assignment = {}
result, assign = unit_propagate(clauses, assignment)
print(f"Assignment: {assign}")

Expected output:

Assignment: {1: True, 2: True, 3: True}

Step 2: Pure Literal Elimination

If a variable appears only positively or only negatively, set it accordingly.

def pure_literal_assign(clauses):
    pos = set()
    neg = set()
    for c in clauses:
        for l in c:
            if l > 0:
                pos.add(l)
            else:
                neg.add(abs(l))
    pure_pos = pos - neg
    pure_neg = neg - pos
    assign = {v: True for v in pure_pos}
    assign.update({v: False for v in pure_neg})
    return assign

clauses = [[1, 2], [-2, 3], [1, -3]]
result = pure_literal_assign(clauses)
print(f"Pure literals: {result}")

Expected output:

Pure literals: {1: True}

Step-by-Step: Using Z3

Z3 is an SMT Solver from Microsoft that handles arithmetic, arrays, bit vectors, and quantifiers.

Step 1: Install and Import

# pip install z3-solver
from z3 import *

Step 2: Create Variables and Formulas

from z3 import Int, And, Or, Not, Solver, sat

x = Int("x")
y = Int("y")
formula = And(x + y > 5, x > 0, y > 0)

solver = Solver()
solver.add(formula)
result = solver.check()
if result == sat:
    model = solver.model()
    print(f"x = {model[x]}, y = {model[y]}")

Expected output:

x = 1, y = 5

Step 3: Verify Program Correctness

from z3 import *

def verify_abs():
    x = Int("x")
    result = Int("result")
    # result = abs(x) implemented as: if x >= 0 then result = x else result = -x
    spec = And(
        Implies(x >= 0, result == x),
        Implies(x < 0, result == -x),
        result >= 0
    )
    solver = Solver()
    solver.add(Not(spec))  # Try to disprove
    if solver.check() == unsat:
        print("abs() is correct for all inputs")
    else:
        print("Counterexample found")

verify_abs()

Expected output:

abs() is correct for all inputs

Common Errors

1. Using Int for Bit-Precise Reasoning

SMT solvers treat Int as mathematical integers (unbounded). For hardware or low-level code, use BitVec.

2. Forgetting to Check Solver Result

Always check solver.check() == sat before accessing solver.model(). Accessing the model on unsatisfiable formulas raises an exception.

3. Slow Quantifier Reasoning

Quantifiers in SMT are heuristically instantiated. Overuse of quantifiers causes slowdowns or non-termination.

4. Assuming Real-World Arithmetic

Z3's Int and Real use exact arithmetic. Floats require the Float theory.

5. Not Using Incremental Solving

For multiple related queries, use solver.push() and solver.pop() to reuse learned clauses.

Practice Questions

Q1: What is the difference between SAT and SMT?

SAT handles only propositional logic. SMT extends SAT with background theories (arithmetic, arrays, bit vectors, strings).

Q2: What does CDCL stand for?

Conflict-Driven Clause Learning — the algorithm modern SAT solvers use, which learns new clauses from conflicts to prune the search space.

Q3: How does Z3 verify program correctness?

Z3 takes the specification as a formula and checks if its negation is satisfiable. If unsatisfiable, the program is correct.

Q4: What is a theory solver in SMT?

A dedicated solver for a specific theory (e.g., linear arithmetic) that communicates with the SAT core via an equality interface.

Q5: Can SMT solvers handle floating-point arithmetic?

Yes, via the floating-point theory (FPA). However, it is slower than integer or bit-vector reasoning.

Challenge

Write a Python function that finds all pairs (x, y) of integers between 0 and 10 that satisfy x^2 + y^2 = z^2 for some integer z. Then use Z3 to verify that no other pairs exist in that range.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.