K-out-of-N restriction in Z3Py

Question

I use Python bindings to prove Theorem Z3 (Z3Py). I have N logical variables, x1, ..., xN. I want to express the restriction that exactly K of N of them must be true. How can I do this in Z3Py? Is there any built-in support for this? I checked the documentation online, but Z3Py docs does not mention any API for this.

For one-sided restrictions, I know that I can separately express that at least one is true (say Ili (x1, .., xN)) and that at least one is true (assert Not (And (xi, xj)) for all i, j). I also know other ways to manually express the limitations of 1-out-of-N and K-out-of-N. However, I got the impression that when the solver has built-in support for this restriction, it can sometimes be more effective than expressing it manually.

Answer 1

Yes, Z3Py has built-in support for this. There is an undocumented API for this that is not mentioned in the Z3Py documentation: use PbEq. In particular, the expression

PbEq(((x1,1),(x2,1),..,(xN,1)),K)

, K N true. , , .

1 N, K = 1 PbEq. K-out-of-N, PbLe. K-out-of-N, PbGe.

Python :

import z3

s = z3.Solver()
bvars = [z3.Bool("Var {0}".format(x)) for x in range(10)]
#Exactly 3 of the variables should be true
s.add( z3.PbEq([(x,1) for x in bvars], 3) )
s.check()
m = s.model()

s = z3.Solver()
bvars = [z3.Bool("Var {0}".format(x)) for x in range(10)]
#<=3 of the variables should be true
s.add( z3.PbLe([(x,1) for x in bvars], 3) )
s.check()
m = s.model()

s = z3.Solver()
bvars = [z3.Bool("Var {0}".format(x)) for x in range(10)]
#>=3 of the variables should be true
s.add( z3.PbGe([(x,1) for x in bvars], 3) )
s.check()
m = s.model()