AskOverflow.Dev

AskOverflow.Dev Logo AskOverflow.Dev Logo

AskOverflow.Dev Navigation

  • 主页
  • 系统&网络
  • Ubuntu
  • Unix
  • DBA
  • Computer
  • Coding
  • LangChain

Mobile menu

Close
  • 主页
  • 系统&网络
    • 最新
    • 热门
    • 标签
  • Ubuntu
    • 最新
    • 热门
    • 标签
  • Unix
    • 最新
    • 标签
  • DBA
    • 最新
    • 标签
  • Computer
    • 最新
    • 标签
  • Coding
    • 最新
    • 标签
主页 / coding / 问题 / 79573232
Accepted
balllerz21
balllerz21
Asked: 2025-04-14 21:11:20 +0800 CST2025-04-14 21:11:20 +0800 CST 2025-04-14 21:11:20 +0800 CST

当 Coq 无法将我的目标与 IH 统一时,我该如何重写或使用 IH?

  • 772

我正在尝试证明一个插入基于列表的优先级队列的正确性定理。以下是插入函数、归纳性质以及我正在使用的证明:

Fixpoint insert (x : nat) (l : list nat) : list nat :=
  match l with
  | [] => [x]
  | h :: t => if x <=? h then x :: h :: t else h :: insert x t
  end.

Inductive list_PQ_property : list nat -> Prop :=
| sorted_empty : list_PQ_property []
| sorted_one : forall x, list_PQ_property [x]
| sorted_add : forall x y l,
    x <= y ->
    list_PQ_property (y :: l) ->
    list_PQ_property (x :: y :: l).

Theorem insert_correctness :
  forall (pq : PQ) (x : el),
    list_PQ_property pq ->
    list_PQ_property (insert x pq).
Proof.
  intros pq x H.
  induction H as [ | y | a b l Hab IHl].
  - simpl. apply sorted_one.
  - simpl. destruct (x <=? y) eqn:E.
    + apply Nat.leb_le in E. apply sorted_add.
      * apply E.
      * apply sorted_one.
    + apply Nat.leb_gt in E.
      apply Nat.lt_le_incl in E.
      apply sorted_add.
      * apply E.
      * apply sorted_one.
  - simpl. destruct (x <=? a) eqn:E.
    + apply Nat.leb_le in E.
      apply sorted_add.
      * apply E.
      * apply sorted_add.
        -- apply Hab.
        -- apply IHl.
  + destruct (x <=? b) eqn:E'.
      * apply Nat.leb_le in E'.
      apply sorted_add.
      apply Nat.lt_le_incl.
      apply Nat.leb_gt in E. apply E.
      apply sorted_add.
        ++ apply E'.
        ++ apply IHl.
       * apply Nat.leb_gt in E'.
        apply sorted_add.
        -- apply Hab.
Admitted.

当我开始证明的时候,一切都很简单,直到我遇到第三个情况。一开始我卡在了

apply sorted_add.
        ++ apply E'.
        ++ apply IHl.

我的目标是 ,b <= x但我对 E' 的假设是 ,x <= b直到我通过应用 Coq 中的一堆 Nat 函数绕过了传递性。现在我卡在了 ,我的 IHIHl 假设如下所示: IHIHl : list_PQ_property (insert x (b :: l)) ,但我的目标是: list_PQ_property (b :: insert x l)。

我不知道如何解决这个问题,或者我是否正确地证明了这一点。

任何指导都将不胜感激。

欲了解更多信息,到目前为止我的完整目标是这样的:

1 goal
x : el
a, b : nat
l : list nat
Hab : a <= b
IHl : list_PQ_property (b :: l)
IHIHl : list_PQ_property (insert x (b :: l))
E : (x <=? a) = false
E' : b < x
______________________________________(1/1)
list_PQ_property (b :: insert x l)

我试过用 IHIHl,但没用。我有点迷茫,我猜这就是我建立证明的方法。

coq
  • 1 1 个回答
  • 33 Views

1 个回答

  • Voted
  1. Best Answer
    Tragicus
    2025-04-14T21:46:04+08:002025-04-14T21:46:04+08:00

    insert x (b :: l)简化为if x <=? b then x :: b :: l else b :: insert x l,而不是b :: insert x l。您可以简化以使后一项出现,得到从 的IHIHl证明,并将此证明重写为 ,以使该项进一步简化。x <=? b = falseE' : b < xIHIHl

    • 3

相关问题

  • 展开策略中 Delta 减少后的 Beta 减少

  • Coq:在模块内使用参数化类型

  • 如何在 CoqIDE 中证明这一点

  • Coq 中的高效记录构建:直接证明包含可能吗?

  • 为什么“专门化”在证明中不是无效策略?

Sidebar

Stats

  • 问题 205573
  • 回答 270741
  • 最佳答案 135370
  • 用户 68524
  • 热门
  • 回答
  • Marko Smith

    重新格式化数字,在固定位置插入分隔符

    • 6 个回答
  • Marko Smith

    为什么 C++20 概念会导致循环约束错误,而老式的 SFINAE 不会?

    • 2 个回答
  • Marko Smith

    VScode 自动卸载扩展的问题(Material 主题)

    • 2 个回答
  • Marko Smith

    Vue 3:创建时出错“预期标识符但发现‘导入’”[重复]

    • 1 个回答
  • Marko Smith

    具有指定基础类型但没有枚举器的“枚举类”的用途是什么?

    • 1 个回答
  • Marko Smith

    如何修复未手动导入的模块的 MODULE_NOT_FOUND 错误?

    • 6 个回答
  • Marko Smith

    `(表达式,左值) = 右值` 在 C 或 C++ 中是有效的赋值吗?为什么有些编译器会接受/拒绝它?

    • 3 个回答
  • Marko Smith

    在 C++ 中,一个不执行任何操作的空程序需要 204KB 的堆,但在 C 中则不需要

    • 1 个回答
  • Marko Smith

    PowerBI 目前与 BigQuery 不兼容:Simba 驱动程序与 Windows 更新有关

    • 2 个回答
  • Marko Smith

    AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String”

    • 1 个回答
  • Martin Hope
    Fantastic Mr Fox msvc std::vector 实现中仅不接受可复制类型 2025-04-23 06:40:49 +0800 CST
  • Martin Hope
    Howard Hinnant 使用 chrono 查找下一个工作日 2025-04-21 08:30:25 +0800 CST
  • Martin Hope
    Fedor 构造函数的成员初始化程序可以包含另一个成员的初始化吗? 2025-04-15 01:01:44 +0800 CST
  • Martin Hope
    Petr Filipský 为什么 C++20 概念会导致循环约束错误,而老式的 SFINAE 不会? 2025-03-23 21:39:40 +0800 CST
  • Martin Hope
    Catskul C++20 是否进行了更改,允许从已知绑定数组“type(&)[N]”转换为未知绑定数组“type(&)[]”? 2025-03-04 06:57:53 +0800 CST
  • Martin Hope
    Stefan Pochmann 为什么 {2,3,10} 和 {x,3,10} (x=2) 的顺序不同? 2025-01-13 23:24:07 +0800 CST
  • Martin Hope
    Chad Feller 在 5.2 版中,bash 条件语句中的 [[ .. ]] 中的分号现在是可选的吗? 2024-10-21 05:50:33 +0800 CST
  • Martin Hope
    Wrench 为什么双破折号 (--) 会导致此 MariaDB 子句评估为 true? 2024-05-05 13:37:20 +0800 CST
  • Martin Hope
    Waket Zheng 为什么 `dict(id=1, **{'id': 2})` 有时会引发 `KeyError: 'id'` 而不是 TypeError? 2024-05-04 14:19:19 +0800 CST
  • Martin Hope
    user924 AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String” 2024-03-20 03:12:31 +0800 CST

热门标签

python javascript c++ c# java typescript sql reactjs html

Explore

  • 主页
  • 问题
    • 最新
    • 热门
  • 标签
  • 帮助

Footer

AskOverflow.Dev

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

Language

  • Pt
  • Server
  • Unix

© 2023 AskOverflow.DEV All Rights Reserve