具有错误定义的函数定义公理的意外未知数

Question

SMT 程序进一步以稍微迂回的方式对（定义不明确的）函数定义 ∀ s · wild(s) = 1 + wild(s) 进行编码（应用 Dafny 的 "limited functions" 递归函数编码），然后尝试证明 wild(emp) = 1 + wild(emp)。然而，Z3 4.6.0（以及最近的 4.7.0 nightly）意外地产生 unknown 而不是 unsat。

(set-option :auto_config false) ;; true -> no change in behaviour
(set-option :smt.mbqi false) ;; true -> no change in behaviour

(declare-sort Snap)      ;; In the full example, this is ...
(declare-const emp Snap) ;; ... declared using declare-datatypes

(declare-fun wild (Snap) Int)
(declare-fun wild%limited (Snap) Int)

(assert (forall ((s Snap)) (! ;; AX-1
  (= (wild%limited s) (wild s))
  :pattern ((wild s))
)))

(assert (forall ((s Snap)) (! ;; AX-2
  (=
    (wild s)
    (+ 1 (wild%limited emp)))
  :pattern ((wild s))
)))

(push) ;; Full examples uses incremental mode
(assert
  (not 
    (= 
      (wild emp)
      (+ 1 (wild emp)))))
(check-sat) ;; UNKNOWN --- but why?
(pop)

鉴于我对 Z3 和触发器的理解，我预计会发生以下证明步骤：

  ¬(wild(emp) = 1 + wild(emp))  // Source assertion
≡ ¬(1 + wild%limited(emp) = 1 + wild(emp))  // By AX-2
≡ ¬(1 + wild%limited(emp) = 1 + wild%limited(emp))  // By AX-1
≡ ¬(true)  // Done: UNSAT

但这似乎并没有发生。我的猜测是公理没有被实例化——事实上，get-info :all-statistics 报告没有量化的实例化。

任何人都可以阐明这一点吗？

Answer 1

最后一个断言简化为 "true"，因此不会出现触发量词实例化的 (wild emp)。

具有错误定义的函数定义公理的意外未知数

Unexpected unknown with ill-defined function definition axiom

z3