You need to enable JavaScript to run this app. Coq中构造返回sumbool的自定义归纳类型相等判定谓词问题
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.16 09:24:07