Why this code returns Unsat (formula using ForAll & Implies)?

Question

Given 2 equations c == a + 4 and t == c + b, if a == -4, then t == b. I am trying to do the opposite, meaning given the above 2 equations, and t == b, I try to find value of a.

I have below code to do this with ForAll and Implies:

from z3 import *

a, b, c, t = BitVecs('a b c t', 32)

g = True
g = And(g, c == (a + 4))
g = And(g, t == (c + b))

s = Solver()
s.add(ForAll([c, t, b], Implies(g, t == b)))

if s.check() == sat:
    print s.model()[a]
else:
    print 'Unsat'

However, running the above code returns Unsat. I expect this returns -4 (or 0xfffffffc), so pretty confused.

Any idea where I am wrong?

Thanks!

Answer 1

The formulas you wrote don't correspond to the textual description of your problem. In particular, the implication you used does not ensure t == b must be true for the formulas to be satisfiable.

Based on the textual description of your problem, if t == b is true, then this means the only way t == c + b is true is if c == 0. Since c == 0, then the only way c == a + 4 is true is if a == -4 as desired. The assignments to t and b are arbitrary.

Here are two ways to encode this. In the first case, z3 assigns 0 to t and b both as they are implicitly existentially quantified. In the second case, I've used a universal quantifier over b and t to highlight that the assignment is arbitrary. The formulas cannot be satisfiable for an arbitrary choice of c based on the discussion just stated (since c == 0 must be true), so c should not be universally quantified. The following illustrates this (http://rise4fun.com/Z3Py/uGEV ):

a, b, c, t = BitVecs('a b c t', 32)

g = True
g = And(g, c == (a + 4))
g = And(g, t == (c + b))
g = And(g, t == b)

s = Solver()
s.add(g)
s.check()
print s.model()
ma = s.model()[a]
s = Solver()
s.add(Not(ma == 0xfffffffc))
print s.check() # unsat, proves ma is -4

solve(g) # alternatively, just solve the equations

# illustrate that the assignments to t and b are arbitrary
s = Solver()
g = True
g = And(g, c == (a + 4))
g = And(g, t == (c + b))
g = ForAll([t, b], Implies(t == b, g))
s.add(g)
s.check()
print s.model()
ma = s.model()[a]

Update Based on the comments, below, I hope this example will help to see why you need Implies(t == b, g) instead of Implies(g, t == b) (with z3py link: http://rise4fun.com/Z3Py/pl80I ):

p1, p2 = BitVecs('p1 p2', 4)

solve(Implies(p1 == 1, p2 == 2)) # gives p1 = 14, p2 = 13

solve(And(p1 == 0, Implies(p1 == 1, p2 == 2))) # gives p1 = 0, p2 unassigned

solve(And(p1 == 0, p1 == 1)) # no solution to illustrate that p1 can only be 0 or 1 in previous, but would be unsat is trying to assign both

solve(ForAll([p1], Implies(p1 == 1, p2 == 2))) # gives p2 == 2

solve(ForAll([p1], Implies(p2 == 2, p1 == 1))) # gives p2 = 0 and does not ensure p1 == 1 is true since the formula is satisfiable by picking p2 != 2