如何一步步检查 Coq 中更复杂的策略的作用?

2024-02-27

我试图经历那些著名的和精彩的软件基础书籍 https://softwarefoundations.cis.upenn.edu/lf-current/Basics.html#lab30但我举了一个例子simpl. and reflexivity.只是在幕后做太多事情,阻碍了我的学习和理解。

我正在经历以下定理:

Theorem plus_1_neq_0 : forall n : nat,
  beq_nat (n + 1) 0 = false. (* n+1 != 0 *)
Proof.
  intros n.
  destruct n as [| n'].
    -simpl. reflexivity.
    -simpl. reflexivity.
Qed.

我真正想要的是能让我一步步经历的东西simpl. and reflexivity.做过。有什么东西可以让我这样做吗?


Destruct 应该解决以下问题:

因为 beq_nat 的第一个参数(这只是not equal i.e. !=) 进行匹配,但第一个输入取决于未知变量 n ,对于+所以匹配不能做任何事情,所以做simpl.让我们陷入困境(出于某种原因)。

显然它必须解决这个问题,因为 Coq 后来接受了证明。但如果仔细看第二个目标是什么,似乎又再次引入了与上面相同的问题:

2 subgoals
______________________________________(1/2)
beq_nat (0 + 1) 0 = false
______________________________________(2/2)
beq_nat (S n' + 1) 0 = false

现在我们有n'作为两者的第一个参数beq_nat and +再次。不过对于我这样的新手来说simpl.这次由于某种神秘的原因奇迹般地起作用了。我显然读过simpl. 文档 https://coq.inria.fr/refman/proof-engine/tactics.html?highlight=simpl#coq:tacn.simpl但作为一个新手,我真的不知道自己在寻找什么,而且对我来说形成对它的理解太密集了,这很有帮助......

无论如何,为什么它在这里起作用?我问的原因是因为我从来没有想过在这个示例证明上使用 destruct,特别是因为重复发生n'一个未知的变量,似乎能够看到真正发生的事情或不同的事情会很有用。所以我认为检查这些类型的事情的逐步分解会很有用(而不是每隔一天发布一个新的问题)。


注意我确实看到了这个问题:

coq 中的逐步简化? https://stackoverflow.com/questions/39355817/step-by-step-simplification-in-coq

但我找不到一种方法让它对我有用,因为它是为该特定示例量身定制的。希望我的问题不会缩小到我的特定示例,尽管可能会这样,因为如果不知道如何进行逐步分解可能是不可能的simpl. (or reflexivity.)已经可以工作了(或者至少上述问题的上述答案给了我这样的印象)。


分解评估的一种方法是给出一个论据simpl,如建议的你链接的问题 https://stackoverflow.com/questions/39355817/step-by-step-simplification-in-coq. simpl f允许仅简化出现在调用下的子表达式f。在这种情况下,simpl Nat.add (or simpl plus or simpl "+")简化S n' + 1 into S (n' + 1). Then simpl beq_nat turns beq_nat (S (n' + 1)) 0 into false.

As for reflexivity,它可以得出比较的两个项在简化后是否相等的结论,这意味着,如果我没记错的话,你总是可以替换simpl; reflexivity仅仅通过reflexivity.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何一步步检查 Coq 中更复杂的策略的作用? 的相关文章

  • 如何阅读 ex_intro 的定义?

    我正在阅读Mike Nahas 的 Coq 入门教程 其中说 ex intro 的参数是 谓词 证人 与证人一起提出的谓词的证明 我在看定义 Inductive ex A Type P A gt Prop Prop ex intro for
  • Coq 中是否有一套最小完整的策略?

    我见过很多 Coq 策略 它们在功能上是相互重叠的 例如 当你在假设中得到确切的结论时 你可以使用assumption apply exact trivial 也许还有其他人 其他例子包括destruct and induction对于无感
  • 如何禁止简单策略展开算术表达式?

    The simpl策略展开诸如2 a 匹配树 这看起来一点也不简单 例如 Goal forall i Z fun x gt x i 3 i 3 simpl 导致 forall i Z match i with 0 gt 3 Z pos y
  • 当目标是类型时,为什么 Coq 不允许反转、析构等?

    When refine正在运行一个程序 我试图通过以下方式结束证明inversion on a False假设当目标是Type 这是我尝试做的证明的简化版本 Lemma strange1 forall T Type 0 gt 0 gt T
  • 如何证明 Coq 中的两个 Fibonacci 实现相等?

    我有两个斐波那契实现 如下所示 我想证明它们在功能上是等效的 我已经证明了自然数的性质 但是这个练习需要另一种我无法弄清楚的方法 我使用的教科书介绍了 Coq 的以下语法 因此应该可以使用这种表示法来证明相等性
  • Coq 中归纳集的归纳子集

    我有一个用三个构造函数构建的归纳集 Inductive MF Set D MF cn MF gt MF gt MF dn Z gt MF gt MF 我想以某种方式定义一个新的归纳集 B 使得 B 是 MF 的子集 仅包含从 D 和 dn
  • Coq Proof Assistant 中依赖类型的问题

    考虑以下简单的表达语言 Inductive Exp Set EConst nat gt Exp EVar nat gt Exp EFun nat gt list Exp gt Exp 及其格式良好的谓词 Definition Env lis
  • 对术语...进行抽象会导致术语...类型错误

    这是我想证明的 A Type i nat index f nat nat n nat ip n lt i partial index f nat option nat L partial index f index f n Some n V
  • 引入先前证明的定理作为假设

    假设我已经在coq中证明了某个定理 稍后我想将其作为假设引入到另一个定理的证明中 有没有一种简洁的方法来做到这一点 当我想做一些诸如案例证明之类的事情时 我通常会出现这种需要 我发现做到这一点的一种方法是assert陈述定理 然后立即证明它
  • 在 Coq 中,重写适用于 = 但不适用于 <-> (iff)

    我在证明期间有以下内容 我需要替换normal form step t with value t因为有一个已证明的定理存在等价 H1 t1 gt t1 normal form step t1 t2 tm H2 t2 gt t2 normal
  • 如何将假设中的具体变量更改为存在量化变量?

    假设我有一个这样的假设 FooProp a b 我想将假设改为这种形式 exists a FooProp a b 我怎样才能做到这一点 我知道我能做到assert exists a FooProp a b by eauto但我试图找到一个不
  • 如何在 Coq 简化过程中应用一次函数?

    据我了解 Coq 中的函数调用是不透明的 有时 我需要使用unfold应用它然后fold将函数定义 主体恢复为其名称 这通常很乏味 我的问题是 是否有更简单的方法来应用函数调用的特定实例 作为一个最小的例子 对于一个列表l 证明右附加 没有
  • 将假设中的 ~exists 转换为 forall

    我陷入了假设的境地 exists k k lt n 1 f k f n 2 并希望将其转换为等效的 我希望如此 假设forall k k lt n 1 gt f k lt gt f n 2 这是一个小例子 Require Import Co
  • 在 Coq 中证明可逆列表是回文

    这是我对回文的归纳定义 Inductive pal X Type list X gt Prop pal0 pal pal1 forall x X pal x pal2 forall x X l list X pal l gt pal x l
  • Coq 中的“错误:宇宙不一致”是什么意思?

    我正在努力通过软件基础 http www cis upenn edu bcpierce sf current 目前正在做教堂数字的练习 这是自然数的类型签名 Definition nat forall X Type X gt X gt X
  • 如何在构造微积分中提取Sigma的第二个元素?

    我尝试这样做 A gt B A gt gt t r gt x a gt B x gt r gt r gt t B t A x A gt y B x gt x x A gt y B x gt y 请注意 由于该函数返回的值取决于 sigma
  • 为什么较新的依赖类型语言没有采用 SSReflect 的方法?

    我在 Coq 的 SSReflect 扩展中发现了两个约定 它们似乎特别有用 但我还没有看到它们在较新的依赖类型语言 Lean Agda Idris 中得到广泛采用 首先 可能的谓词被表示为布尔返回函数而不是归纳定义的数据类型 默认情况下
  • 在 Coq 模块系统中导入 与包含

    确切的语义是什么Include M1在另一个模块中 比如 M 这与做有什么不同Import M1在模块 M 内 更准确地说 以下命令的语义是什么 Module Type M M1 lt M2 lt M3 总结这两个白话命令的语义 命令Inc
  • 标准库证明中定义的 Z.le 是否无关紧要?

    在 Coq 标准库中 有一个枚举类型称为comparison具有三个元素Eq Lt Gt 这用于定义小于或小于或等于运算符ZArith m lt n定义为m n Lt and m lt n定义为m n lt gt Gt 根据赫德伯格定理 U
  • Coq:承认断言

    有没有办法在 Coq 中承认断言 假设我有一个这样的定理 Theorem test forall m n nat m n n m Proof intros n m assert H1 m m n m S n Admitted Abort 上

随机推荐