Coq中构造返回sumbool的自定义归纳类型相等判定谓词问题
原因
你使用普通if语法对sumbool类型的eq_nat_dec结果分支时,默认不会将分支对应的判定假设(如a1 = a2、a1 <> a2)引入子目标上下文,因此无法完成后续证明。
解决方案
方案1:显式为match添加return子句传递假设
手动编写带as绑定和return子句的match表达式,将判定结果对应的等式带入分支上下文:
Definition state_eq2 : forall (s1 s2 : state_type), {s1 = s2} + {s1 <> s2}. refine (fun (s1 s2 : state_type) => match s1, s2 with State a1 b1, State a2 b2 => match eq_nat_dec a1 a2 as a_res return (a_res = eq_nat_dec a1 a2 -> {State a1 b1 = State a2 b2} + {State a1 b1 <> State a2 b2}) with | left H_a => fun _ => match eq_nat_dec b1 b2 as b_res return (b_res = eq_nat_dec b1 b2 -> {State a1 b1 = State a2 b2} + {State a1 b1 <> State a2 b2}) with | left H_b => fun _ => left _ (f_equal2 State H_a H_b) | right H_b => fun _ => right _ (fun H => injection H as _ _ H'; apply H_b in H'; contradiction) end eq_refl | right H_a => fun _ => right _ (fun H => injection H as _ H' _; apply H_a in H'; contradiction) end eq_refl end). Defined.
方案2:使用Program扩展自动管理假设
引入Program扩展后可以直接按直觉写分支逻辑,Program会自动保留分支假设,生成的子目标直接用原有的congruence战术即可证明:
Require Import Program. Program Definition state_eq3 (s1 s2 : state_type) : {s1 = s2} + {s1 <> s2} := match s1, s2 with State a1 b1, State a2 b2 => if eq_nat_dec a1 a2 then if eq_nat_dec b1 b2 then left _ _ else right _ _ else right _ _ end. Next Obligation. congruence. Qed. Next Obligation. congruence. Qed. Next Obligation. congruence. Qed.
方案3:使用标准库战术自动生成
对于这种简单的代数数据类型,直接使用标准库的decide equality战术即可一键生成符合要求的相等判定谓词,不需要手动编写匹配逻辑:
Definition state_eq4 : forall (s1 s2 : state_type), {s1 = s2} + {s1 <> s2}. decide equality. all: apply eq_nat_dec. Defined.
内容的提问来源于stack exchange,提问作者Felipe
相关产品推荐
相关产品推荐

