如何为不能成立的归纳谓词定义引理

Question

最近学习了Isabelle的归纳谓词even和自反及物clousre。看起来我们可以很容易地推导出谓词成立的情况，但是当我们需要证明一些归纳谓词不成立的情况时，它就不太容易工作了。

而我也做过像下面这样的一个案例，用一个LTS系统来accept list，终于可以到了。 notJoinLTSlemma 引理对我来说很难证明。任何帮助将不胜感激。

type_synonym ('q,'a) LTS = "('q * 'a set * 'q) set"

inductive LTS_is_reachable :: "(('q, 'a) LTS * ('q * 'q) set) ⇒ 'q ⇒ 'a list ⇒ 'q ⇒ bool" where
   LTS_Empty[intro!]:"LTS_is_reachable Δ q [] q"|
   LTS_Step1[intro!]:"(∃q''. (q, q'') ∈ snd Δ ∧ LTS_is_reachable Δ q'' l q') ⟹ LTS_is_reachable Δ q l q'" |
   LTS_Step2[intro!]:"(∃q'' σ. a ∈ σ ∧ (q, σ, q'') ∈ fst Δ ∧ LTS_is_reachable Δ q'' w q') ⟹ LTS_is_reachable Δ q (a # w) q'"

lemma joinLTSlemma:"LTS_is_reachable l q x p ⟹  LTS_is_reachable l p y q''⟹ LTS_is_reachable l q (x@y) q''"
  proof (induction rule: LTS_is_reachable.induct)
    case (LTS_Empty Δ q)
    then show ?case by auto
  next
    case (LTS_Step1 q Δ l q')
    then show ?case by auto
  next
    case (LTS_Step2 a q Δ w q')
    then show ?case by auto
  qed

lemma notJoinLTSlemma:"LTS_is_reachable l q x p ⟹  ¬ LTS_is_reachable l p y q''⟹ ¬ LTS_is_reachable l q (x@y) q''"
  nitpick

Answer 1

您的引理 notJoinLTSlemma 不成立，正如 nitpick 已经指出的那样。直觉上，原因是你说“对于 some p，如果 p 可以从 q 通过 x 到达，并且 q'' 无法从 p 通过 y 到达，那么 q'' 无法从 q 通过 x@y 到达”，这显然不是是的，因为 LTS 中可能有另一条路径从 q 通过 x@y 到达 q''。为了看到这一点，您可以检查 nitpick 给出的 counter-example。因此，正确的说法是“For all p, ...”，即：

lemma notJoinLTSlemma:"∀p. LTS_is_reachable l q x p ∧ ¬ LTS_is_reachable l p y q'' ⟹ ¬ LTS_is_reachable l q (x@y) q''"

希望这对您有所帮助。

如何为不能成立的归纳谓词定义引理

How to define a lemma towards inductive predicate that can not hold

isabelle