在 z3 smt2 中使用整数除法时未知

Question

我正在尝试为函数 penta(n) = (n * (3n -1)) / 2 找到一个解决方案，其中 penta (z) = penta (a) + penta(b) 对于所有数字优点。这一直有效，直到整数 division (div) 成为定义的一部分，但是当它被添加到定义中时，我得到了 timeout 或未知。我希望得到 8 、 7 、 4 。知道我做错了什么吗？

(declare-const a Int)
(declare-const b Int)
(declare-const z Int)

(define-fun penta ((n Int)) Int (div (* (- (* 3 n ) 1) n) 2) )  

(assert (= (penta z) (+ (penta a) (penta b))  ))
(assert (> a 1))
(assert (> b 1))
(assert (> z 1))

(check-sat)
(get-model)

我正在使用 http://rise4fun.com/Z3 网站上的版本和版本 4.1 (x64)。

Answer 1

主要问题是该问题使用了两个非数字参数之间的整数乘法。一般丢番图问题没有决策程序，因此 Z3 尽最大努力，这不利于模型枚举。

当您不使用整数 division 时，Z3 将尝试基于将问题转换为有限域位向量以找到模型。它调用通过对公式执行句法检查来验证这种启发式方法。使用运算符 (div .. 2) 时语法检查失败。您可以对 (div x 2) 进行编码，以便启发式方法找出问题所在通过引入新变量并限制它们：

(declare-const penta_z Int)
(declare-const penta_a Int)
(declare-const penta_b Int)
(assert (or (= (* 2 penta_z) (penta z)) (= (+ 1 (* 2 penta_z)) (penta z))))
(assert (or (= (* 2 penta_a) (penta a)) (= (+ 1 (* 2 penta_a)) (penta a))))
(assert (or (= (* 2 penta_b) (penta b)) (= (+ 1 (* 2 penta_b)) (penta b))))
(assert (= penta_z (+ penta_a penta_b)  ))
(assert (> a 1))
(assert (> b 1))
(assert (> z 1))
(assert (>= penta_z 0))
(assert (<= penta_z 100))

您也可以使用位向量直接编码您的问题，尽管这开始变得容易出错，因为您必须处理如何处理溢出。

在 z3 smt2 中使用整数除法时未知

unknown when using a integer division in z3 smt2

z3