You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Coq中valid_path归纳证明的归纳假设(IH)格式问题求助

Coq归纳假设格式不符合需求的问题

在进行形式化证明时,证明path_equal引理遇到了归纳假设(IH)格式不正确的问题,具体情况如下:

问题说明

我需要证明从同一节点出发的有效路径是唯一的,但当前通过induction H0生成的归纳假设为:

IHvalid_path : valid_path ls xd (x :: p') → p'0 = x :: p'

而我实际需要的归纳假设形式应该是:

IHvalid_path : valid_path ls xd p'0 → valid_path ls xd p' → p'0 = p'

已经尝试过generalize方法,但仍无法解决问题,希望得到帮助。

相关代码

From stdpp Require Import mapset.

From stdpp Require Import gmap.
From stdpp Require Import options.
From stdpp Require Import proofmode.
From iris.heap_lang Require Export proofmode notation.

Definition Node : Type := nat.
Definition Children : Type := (loc * loc).
Definition Entry : Type := (Node * Children).

Definition ldd_state : Type := gmap loc (nat * (loc * loc)).

Definition ldd_zero : loc := Loc 0.
Definition ldd_one : loc := Loc 1.

(* Loc 0 and Loc 1 will never be present in the state.
   This is to prevent the true, false leaves having children and values. *)
Definition state_ok (ls : ldd_state) : Prop :=
  ls !! ldd_zero = None ∧ ls !! ldd_one = None.
    
Definition get_down (ls : ldd_state) (x : loc) : option loc := 
  ls !! x ≫= λ n, Some (snd n) ≫= λ n, Some (fst n).

Definition path := list loc.
Identity Coercion path_to_list : path >-> list.

Inductive valid_path (ls : ldd_state) (x : loc) : path → Prop :=
  | path_Et : x = ldd_one → valid_path ls x [ldd_one]
  | path_D  : ∀ (xd : loc) (p' : path),
      get_down ls x = Some xd → 
      valid_path ls xd p' → 
      valid_path ls x (x :: p').

Lemma path_equal : ∀ (ls : ldd_state) (x : loc) (p p' : path),
  state_ok ls → valid_path ls x p → valid_path ls x p' → p = p'.
intros. induction H0.
Proof.
- destruct H1.  + admit. (* easy case, this is contradiction *)
                + admit. (* again, easy contradiction *)
- destruct H1.  + admit. (* easy case, contradiction *)
                + (* Stuck here *)
 Admitted.

内容的提问来源于stack exchange,提问作者someStudentCS

相关产品推荐
方舟 Agent Plan

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

最近更新时间:2026.06.30 00:12:45