CODEWITHSUNDEEP
smthorn
howareyouimfinethanks
howareyouimfinethanks

Reputation: 11

what's the meaning of "at-most" keyword in SMT-LIB language (extended version of Z3 FixedPoint)

like in this file the "at-most" keyword in the rule:

horn1.smt2(from the Z3 github repository examples/python/data)

(declare-rel Goal (Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool))
(declare-rel Invariant (Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool Bool))
(declare-var A Bool)
(declare-var B Bool)
(declare-var C Bool)
(declare-var D Bool)
(declare-var E Bool)
(declare-var F Bool)
(declare-var G Bool)
(declare-var H Bool)
(declare-var I Bool)
(declare-var J Bool)
(declare-var K Bool)
(declare-var L Bool)
(declare-var M Bool)
(declare-var N Bool)
(declare-var O Bool)
(declare-var P Bool)
(declare-var Q Bool)
(declare-var R Bool)
(declare-var S Bool)
(declare-var T Bool)
(declare-var U Bool)
(declare-var V Bool)
(declare-var W Bool)
(declare-var X Bool)
(rule (=> (not (or L K J I H G F E D C B A)) (Invariant L K J I H G F E D C B A)))
(rule (let ((a!1 (and (Invariant X W V U T S R Q P O N M)
                (=> (not (and true)) (not F))
                (=> (not (and true)) (not E))
                (=> (not (and W)) (not D))
                (=> (not (and W)) (not C))
                (=> (not (and U)) (not B))
                (=> (not (and U)) (not A))
                (= L (xor F X))
                (= K (xor E W))
                (= J (xor D V))
                (= I (xor C U))
                (= H (xor B T))
                (= G (xor A S))
                (=> D (not E))
                (=> C (not E))
                (=> B (not C))
                (=> A (not C))
                ((_ at-most 5) L K J I H G))))
  (=> a!1 (Invariant L K J I H G F E D C B A))))
(rule (=> (and (Invariant L K J I H G F E D C B A) L (not K) J (not I) H G)
    (Goal L K J I H G F E D C B A)))
(query Goal)

It seems like the meaning of the keyword "at-most" is that only five literal of the six literal (L K J I H G) can be true simultaneously, or it means anything else, I can't figure it out. I really appreciate it if there's any nice guy could help me out.

Upvotes: 0

Views: 325

Answers (1)

alias
alias

Reputation: 30525

These are pseudo-boolean functions, see this answer for details: K-out-of-N constraint in Z3Py

Basically:

  • at-most: At most this many are true
  • at-least: At least this many are true
  • pble: At most this many, weighted
  • pbge: At least this many, weighted
  • pbeq: Exactly this many, weighted

The weighted versions are essentially multipliers on the boolean, and take a constant list of integers.

Note that these are z3 specific, and not actually defined in SMTLib. There might be other solvers that support it too, of course.

Upvotes: 1

Related Questions