是否存在不可解释函数的理论（同余分析）？

Question

我有一组符号变量：

int a, b, c, d, e;

一组未知函数，受许多公理约束：

f1(a, b) = f2(c, b)
f1(d, e) = f1(e, d)
f3(b, c, e) = f1(b, e)
c = f1(a, b)
b = d

此处函数 f1、f2、f3 未知，但已修复。所以不是uninterpreted functions.

的理论

我想证明以下断言的有效性：

c = f2(f1(a, b), b)
f3(d, f2(c, b), e) = f1(e, b)

使用基于上述公理等式的替换。

对于这样的定理，是否有一种理论只会使用提供的等式来尝试组合答案，而不是对函数进行解释？

如果是这样，该理论的名称是什么，支持它的 SMT 求解器是什么？

它可以与其他理论混合使用，例如线性算术吗？

Answer 1

这仍然是未解释函数，因为如果存在满足您的公理的函数，那么这将属于未解释函数理论。同样，如果不存在这样的功能，那么这在未解释的功能中是不满意的。所以当且仅当未解释函数中的问题是可满足的时，你所描绘的是可满足的，所以这两个理论是同构的，即相同。

鉴于您正试图根据您的公理证明某些定理是有效的，求解器如何表示 可满足的 结果应该无关紧要，因为 sat 结果对应无效模型。要使用 SMT 求解器证明您的定理，您应该声明您的公理，声明定理的否定，然后寻找不可满足的结果。有关可满足性和有效性之间联系的更详细说明，请参阅。

为了使用 Z3 证明你的第一个定理，SMT-LIB 2 中满足以下条件：

(declare-fun a () Int)
(declare-fun b () Int)
(declare-fun c () Int)

(declare-fun f1 (Int Int) Int)
(declare-fun f2 (Int Int) Int)

(assert (= (f1 a b) (f2 c b)))
(assert (= c (f1 a b)))
(assert (not (= c (f2 (f1 a b) b))))

(check-sat)

是否存在不可解释函数的理论（同余分析）？

Is there a theory for uninterpretable functions (congruence analysis)?

verification

stp

smt

z3

alt-ergo