Solving predicate calculus problems with Z3 SMT

Question

I'd like to use Z3 to solve problems that are most naturally expressed in terms of atoms (symbols), sets, predicates, and first order logic. For example (in pseudocode):

A = {a1, a2, a3, ...} # A is a set
B = {b1, b2, b3...}
C  = {c1, c2, c3...}

def p = (a:A, b:B, c:C) -> Bool # p is unspecified predicate
def q = (a:A, b:B, c:C) -> Bool

# Predicates can be defined in terms of other predicates:
def teaches = (a:A, b:B) -> there_exists c:C 
                            such_that [ p(a, b, c) OR q(a, b, c)  ]

constraint1 = forall b:B there_exists a:A
                         such_that teaches(a, b)

solve(constraint1)

What are good ways to express atoms, sets, predicates, relations, and first order quantifiers in Z3 (or other SMTs)?

Is there a standard idiom for this? Must it be done manually? Is there perhaps a translation library (not necessarily specific to Z3) that can convert them?

I believe Alloy uses SMT to implement predicate logic and relations, but Alloy seems designed more for interactive use to explore consistency of models, rather than to find specific solutions for problems.

Answer 1

"Alloy seems designed more for interactive use to explore consistency of models, rather than to find specific solutions for problems."

IMHO, Alloy shines when it comes to validate your own way of thinking. You model something and through the visualization of several instances you can sometime come to realize that what you modeled is not exactly what you'd have hoped for. In that sense, I agree with you.

Yet, Alloy can also be used to find specific solutions to problems. You can overload a model with constraints so that only one instance can be found (i.e. your solution). It works also quite well when your domain space remains relatively small.

Here's your model translated in Alloy :

sig A,B,C{}

pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}

// I'm a bit rusted, so .. that's my unelegant take on defining an "undefined predicate"
one sig REL {
q: A->B ->C,
p: A->B->C
}

fact constraint1 {
all b:B | some a:A | teaches[a,b]
}

run{} 

If you want to define the atoms in sets A,B,C yourself and refer to them in predicates you could always over-constraint this model as follows:

abstract sig A,B,C{}

one sig A1,A2 extends A{}
one sig B1 extends B{}
one sig C1,C2,C3 extends C{}


pred teaches(a:A,b:B) {
some c:C | a->b->c in REL.q or a->b->c in REL.p}

one sig REL {
q: A->B ->C,
p: A->B->C
}{
// here you could for example define the content of p and q yourself
q= A1->B1->C2 + A2 ->B1->C3
p= A1->B1->C3 + A1 ->B1->C2
 }

fact constraint1 {
all b:B | some a:A | teaches[a,b]
}

run{} 

Answer 2

Modeling predicate logic in SMTLib is indeed possible; though it might be a bit cumbersome compared to a regular theorem prover like Isabelle/HOL etc. And interpreting the results can require a fair amount of squinting.

Having said that, here's a direct encoding of your sample problem using SMTLib:

(declare-sort A)
(declare-sort B)
(declare-sort C)

(declare-fun q (A B C) Bool)
(declare-fun p (A B C) Bool)

(assert (forall ((b B))
  (exists ((a A))
    (exists ((c C)) (or (p a b c) (q a b c))))))

(check-sat)
(get-model)

A few notes:

• declare-sort creates an uninterpreted sort. It's essentially a non-empty set of values. (Can be infinite as well, there are no cardinality assumptions made, aside from the fact that it's not empty.) For your specific problem, it doesn't seem to matter what this sort actually is since you didn't use any of its elements directly. If you do so, you might also want to try a "declared" sort, i.e., a data-type declaration. This can be an enumeration, or something even more complicated; depending on the problem. For the current question as posed, an uninterpreted sort works just fine.

• declare-fun tells the solver that there's an uninterpreted function with that name and the signature. But otherwise it neither defines it, nor constrains it in any way. You can add "axioms" about them to be more specific on how they behave.

• Quantifiers are supported, as you see with forall and exists in how your constraint1 is encoded. Note that SMTLib isn't that suitable for code-reuse, and one usually programs in a higher-level binding. (Bindings from C/C++/Java/Python/Scala/O'Caml/Haskell etc. are provided, with similar but varying degrees of support and features.) Otherwise, it should be easy to read.

• We finally issue check-sat and get-model, to ask the solver to create a universe where all the asserted constraints are satisfied. If so, it'll print sat and will have a model. Otherwise, it'll print unsat if there's no such universe; or it can also print unknown (or loop forever!) if it cannot decide. Use of quantifiers are difficult for SMT solvers to deal with, and heavy use of quantifiers will no doubt lead to unknown as the answer. This is an inherent limitation of the semi-decidability of first-order predicate calculus.

When I run this specification through z3, I get:

sat
(
  ;; universe for A:
  ;;   A!val!1 A!val!0
  ;; -----------
  ;; definitions for universe elements:
  (declare-fun A!val!1 () A)
  (declare-fun A!val!0 () A)
  ;; cardinality constraint:
  (forall ((x A)) (or (= x A!val!1) (= x A!val!0)))
  ;; -----------
  ;; universe for B:
  ;;   B!val!0
  ;; -----------
  ;; definitions for universe elements:
  (declare-fun B!val!0 () B)
  ;; cardinality constraint:
  (forall ((x B)) (= x B!val!0))
  ;; -----------
  ;; universe for C:
  ;;   C!val!0 C!val!1
  ;; -----------
  ;; definitions for universe elements:
  (declare-fun C!val!0 () C)
  (declare-fun C!val!1 () C)
  ;; cardinality constraint:
  (forall ((x C)) (or (= x C!val!0) (= x C!val!1)))
  ;; -----------
  (define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
    (and (= x!0 A!val!0) (= x!2 C!val!0)))
  (define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
    false)
)

This takes a bit of squinting to understand fully. The first set of values tell you how the solver constructed a model for the uninterpreted sorts A, B, and C; with witness elements and cardinality constraints. You can ignore this part for the most part, though it does contain useful information. For instance, it tells us that A is a set with two elements (named A!val!0 and A!val!1), so is C, and B only has one element. Depending on your constraints, you'll get different sets of elements.

For p, we see:

  (define-fun p ((x!0 A) (x!1 B) (x!2 C)) Bool
    false)

This means p always is False; i.e., it's the empty set, regardless of what the arguments passed to it are.

For q we get:

 (define-fun q ((x!0 A) (x!1 B) (x!2 C)) Bool
    (and (= x!0 A!val!0) (= x!2 C!val!0)))

Let's rewrite this a little more simply:

 q (a, b, c) = a == A0 && c == C0

where A0 and C0 are the members of the sorts A and C respectively; see the sort declarations above. So, it says q is True whenever a is A0, c is C0, and it doesn't matter what b is.

You can convince yourself that this model does indeed satisfy the constraint you wanted.

To sum up; modeling these problems in z3 is indeed possible, though a bit clumsy and heavy use of quantifiers can make the solver loop-forever or return unknown. Interpreting the output can be a bit cumbersome, though you'll realize that the models will follow a similar schema: First the uninterpreted sorts, and then the the definitions for the predicates.

Side note

As I mentioned, programming z3 in SMTLib is cumbersome and error-prone. Here's the same program done using the Python interface:

from z3 import *

A = DeclareSort('A')
B = DeclareSort('B')
C = DeclareSort('C')

p = Function('p', A, B, C, BoolSort())
q = Function('q', A, B, C, BoolSort())

dummyA = Const('dummyA', A)
dummyB = Const('dummyB', B)
dummyC = Const('dummyC', C)

def teaches(a, b):
    return Exists([dummyC], Or(p(a, b, dummyC), q(a, b, dummyC)))

constraint1 = ForAll([dummyB], Exists([dummyA], teaches(dummyA, dummyB)))

s = Solver()
s.add(constraint1)
print(s.check())
print(s.model())

This has some of its idiosyncrasies as well, though hopefully it'll provide a starting point for your explorations should you choose to program z3 in Python. Here's the output:

sat
[p = [else -> And(Var(0) == A!val!0, Var(2) == C!val!0)],
 q = [else -> False]]

Which has the exact same info as the SMTLib output, though written slightly differently.

Function definition style

Note that we defined teaches as a regular Python function. This is the usual style in z3py programming, as the expression it produces gets substituted as calls are made. You can also create a z3-function as well, like this:

teaches = Function('teaches', A, B, BoolSort())
s.add(ForAll([dummyA, dummyB],
       teaches(dummyA, dummyB) == Exists([dummyC], Or(p(dummyA, dummyB, dummyC), q(dummyA, dummyB, dummyC)))))

Note that this style of definition will rely on quantifier instantiation internally, instead of the general function-definition facilities of SMTLib. So, you should prefer the python function style in general as it translates to "simpler" internal constructs. It is also much easier to define and use in general.

One case where you need the z3 function definition style is if the function you're defining is recursive and its termination relies on a symbolic argument. For a discussion of this, see: https://stackoverflow.com/a/68457868/936310