如何在相互递归规则归纳中修复 "Illegal schematic variable(s)"?
How to fix "Illegal schematic variable(s)" in mutually recursive rule induction?
在 Isabelle 中,我正在尝试对相互递归归纳定义进行规则归纳。这是我能够创建的最简单的示例:
theory complex_exprs
imports Main
begin
datatype A = NumA int
| AB B
and B = NumB int
| BA A
inductive eval_a :: "A ⇒ int ⇒ bool" and eval_b :: "B ⇒ int ⇒ bool" where
eval_num_a: "eval_a (NumA i) i" |
eval_a_b: "eval_b b i ⟹ eval_a (AB b) i" |
eval_num_b: "eval_b (NumB i) i" |
eval_b_a: "eval_a a i ⟹ eval_b (BA a) i"
lemma foo:
assumes "eval_a a result"
shows "True"
using assms
proof (induction a)
case (NumA x)
show ?case by auto
case (AB x)
此时,伊莎贝尔停止 'Illegal schematic variable(s) in case "AB"'。实际上,当前目标是 ⋀x. ?P2.2 x ⟹ eval_a (AB x) result ⟹ True
,其中包含假设 ?P2.2 x
。 Isabelle 说的是 'schematic variable' 吗?它来自哪里,我该如何摆脱它?
如果我尝试对规则进行归纳,我会遇到同样的问题:
proof (induction)
case (eval_num_a i)
show ?case by auto
case (eval_a_b b i)
同样,目标是 ⋀b i. eval_b b i ⟹ ?P2.0 b i ⟹ True
,未知 ?P2.0 b i
,我无法继续。
作为一个相关问题:我尝试使用
进行归纳
proof (induction rule: eval_a_eval_b.induct)
但是伊莎贝尔不接受,说'Failed to apply initial proof method'。
如何完成这个入职培训? (在我的实际应用中,我确实需要归纳,因为目标比True
更复杂。)
关于相互递归定义的证明,无论是数据类型、函数还是归纳谓词,都必须是相互递归的。但是,在你的引理中,你只陈述了 eval_a
的归纳 属性,而不是 eval_b
。在 AB
的情况下,您显然想使用 eval_b
的归纳假设,但是由于引理没有说明 eval_b
的归纳假设 属性,伊莎贝尔不知道这是什么。所以它把它留作示意图变量 ?P2.0
.
所以,你必须陈述两个目标,比如说
lemma
shows "eval_a a result ==> True"
and "eval_b b result ==> True"
然后,induction a b
方法将计算出第一个语句对应于 A
,第二个语句对应于 B
。
归纳谓词的归纳规则失败,因为该规则消除了归纳谓词(对数据类型的归纳仅 "eliminates" 类型信息,但这不是 HOL 公式)并且它无法找到假设第二个归纳谓词。
可以在 src/HOL/Induct/Common_Patterns.thy
中找到更多关于相互递归对象归纳的例子。
在 Isabelle 中,我正在尝试对相互递归归纳定义进行规则归纳。这是我能够创建的最简单的示例:
theory complex_exprs
imports Main
begin
datatype A = NumA int
| AB B
and B = NumB int
| BA A
inductive eval_a :: "A ⇒ int ⇒ bool" and eval_b :: "B ⇒ int ⇒ bool" where
eval_num_a: "eval_a (NumA i) i" |
eval_a_b: "eval_b b i ⟹ eval_a (AB b) i" |
eval_num_b: "eval_b (NumB i) i" |
eval_b_a: "eval_a a i ⟹ eval_b (BA a) i"
lemma foo:
assumes "eval_a a result"
shows "True"
using assms
proof (induction a)
case (NumA x)
show ?case by auto
case (AB x)
此时,伊莎贝尔停止 'Illegal schematic variable(s) in case "AB"'。实际上,当前目标是 ⋀x. ?P2.2 x ⟹ eval_a (AB x) result ⟹ True
,其中包含假设 ?P2.2 x
。 Isabelle 说的是 'schematic variable' 吗?它来自哪里,我该如何摆脱它?
如果我尝试对规则进行归纳,我会遇到同样的问题:
proof (induction)
case (eval_num_a i)
show ?case by auto
case (eval_a_b b i)
同样,目标是 ⋀b i. eval_b b i ⟹ ?P2.0 b i ⟹ True
,未知 ?P2.0 b i
,我无法继续。
作为一个相关问题:我尝试使用
进行归纳proof (induction rule: eval_a_eval_b.induct)
但是伊莎贝尔不接受,说'Failed to apply initial proof method'。
如何完成这个入职培训? (在我的实际应用中,我确实需要归纳,因为目标比True
更复杂。)
关于相互递归定义的证明,无论是数据类型、函数还是归纳谓词,都必须是相互递归的。但是,在你的引理中,你只陈述了 eval_a
的归纳 属性,而不是 eval_b
。在 AB
的情况下,您显然想使用 eval_b
的归纳假设,但是由于引理没有说明 eval_b
的归纳假设 属性,伊莎贝尔不知道这是什么。所以它把它留作示意图变量 ?P2.0
.
所以,你必须陈述两个目标,比如说
lemma
shows "eval_a a result ==> True"
and "eval_b b result ==> True"
然后,induction a b
方法将计算出第一个语句对应于 A
,第二个语句对应于 B
。
归纳谓词的归纳规则失败,因为该规则消除了归纳谓词(对数据类型的归纳仅 "eliminates" 类型信息,但这不是 HOL 公式)并且它无法找到假设第二个归纳谓词。
可以在 src/HOL/Induct/Common_Patterns.thy
中找到更多关于相互递归对象归纳的例子。