30

[我不确定这是否适合堆栈溢出,但这里还有许多其他 Coq 问题,所以也许有人可以提供帮助。]

我正在从http://www.cis.upenn.edu/~bcpierce/sf/Basics.html#lab28完成以下工作(就在介绍案例的下方)。请注意,我在这方面是一个完整的初学者,并且正在家里工作——我不是学生。

Theorem andb_true_elim1 : forall b c : bool,
  andb b c = true -> b = true.
Proof.
  intros b c H.
  destruct b.
  Case "b = true".
    reflexivity.
  Case "b = false".
    rewrite <- H. reflexivity.
Qed.

我正在研究重写的作用:

  Case := "b = false" : String.string
  c : bool
  H : andb false c = true
  ============================
   false = true

然后rewrite <- H.应用:

  Case := "b = false" : String.string
  c : bool
  H : andb false c = true
  ============================
   false = andb false c

并且很清楚证明将如何成功。

我可以看到如何以机械方式操纵符号来获得证明。没关系。但我对“意义”感到不安。特别是,我怎么能false = true在一个证明中间?

似乎我在提出某种矛盾的论点,但我不确定是什么。我觉得我一直在盲目地遵守规则,不知怎的已经到了我在胡说八道的地步。

我在上面做什么

我希望这个问题很清楚。

4

4 回答 4

24

通常,当您在定理证明器中进行案例分析时,很多案例归结为“不可能发生”。例如,如果您要证明有关整数的某些事实,您可能需要对整数i是正数、零还是负数进行案例分析。但是在您的上下文中可能还有其他假设,或者您的目标的某些部分,这与其中一种情况相矛盾。例如,您可能从先前的断言中知道,它i永远不会是否定的。

然而 Coq 并不那么聪明。所以你仍然必须通过实际证明两个相互矛盾的假设可以粘合在一起来证明荒谬性并因此证明你的定理的机制。

像在计算机程序中一样思考它:

switch (k) {
  case X:
    /* do stuff */
    break;
  case Y:
    /* do other stuff */
    break;
  default:
    assert(false, "can't ever happen");
}

目标是“false = true永远不会发生”。但是你不能只在 Coq 中断言你的出路。你实际上必须写下一个证明项。

所以上面,你必须证明这个荒谬的目标false = true。而你唯一需要处理的就是假设H: andb false c = true。片刻的思考会告诉你,这实际上是一个荒谬的假设(因为andb false y任何东西都归结为假y,因此不可能是真的)。所以你用你唯一可以支配的东西(即H)来实现目标,而你的新目标是false = andb false c

所以你应用一个荒谬的假设来试图实现一个荒谬的目标。你瞧,你最终得到了一些你可以通过反身性实际展示的东西。Qed。

更新 正式地,这就是发生的事情。

回想一下,Coq 中的每个归纳定义都带有一个归纳原则。以下是等式和False命题的归纳原则的类型(与false类型的术语相反bool):

Check eq_ind.
eq_ind
  : forall (A : Type) (x : A) (P : A -> Prop),
    P x -> forall y : A, x = y -> P y
Check False_ind.
False_ind
 : forall P : Prop, False -> P

那个归纳原理False说,如果你给我一个证明False,我可以给你一个任何命题的证明P

的归纳原理eq比较复杂。让我们认为它仅限于bool. 并专门针对false. 它说:

Check eq_ind false.
eq_ind false
 : forall P : bool -> Prop, P false -> forall y : bool, false = y -> P y

因此,如果您从某个P(b)依赖于布尔值的命题开始b,并且您有 的证明P(false),那么对于任何其他y等于 的布尔值false,您都有 的证明P(y)

这听起来不是很令人兴奋,但我们可以将它应用于P我们想要的任何命题。我们想要一个特别讨厌的。

Check eq_ind false (fun b : bool => if b then False else True).
eq_ind false (fun b : bool => if b then False else True)
 : (fun b : bool => if b then False else True) false ->
   forall y : bool,
   false = y -> (fun b : bool => if b then False else True) y

稍微简化一下,这就是说True -> forall y : bool, false = y -> (if y then False else True)

所以这需要一个证明,True然后y是我们可以选择的一些布尔值。所以让我们这样做。

Check eq_ind false (fun b : bool => if b then False else True) I true.
eq_ind false (fun b : bool => if b then False else True) I true
 : false = true -> (fun b : bool => if b then False else True) true

我们在这里:false = true -> False

结合我们对 的归纳原理的了解False,我们有:如果你给我一个 的证明false = true,我可以证明任何命题。

所以回到andb_true_elim1. 我们有一个假设Hfalse = true。我们想证明某种目标。正如我在上面所展示的,存在一个证明术语,可以将证明false = true变成任何你想要的证明。所以特别H是 的证明false = true,所以你现在可以证明你想要的任何目标。

这些策略基本上是构建证明项的机器。

于 2011-11-01T14:21:36.450 回答
8

true = false是一个等同于两个不同布尔值的语句。由于这些值不同,这个陈述显然是不可证明的(在空的上下文中)。

考虑到你的证明:你到达了目标的阶段false = true,所以很明显你将无法证明它......但问题是你的上下文(假设)也是矛盾的。例如,当您进行案例分析并且其中一个案例与您的其他假设相矛盾时,通常会发生这种情况。

于 2011-11-01T14:35:15.937 回答
2

我意识到这是旧的,但我想澄清 Lambdageek 答案背后的一些直觉(以防有人发现这个)

我注意到关键点似乎是我们F:bool->Prop在每个点定义了一个具有不同值的函数(即true => Truefalse => False)。然而,从相等的归纳原理可以很容易地证明eq_ind直观的想法(这实际上是定义相等的“莱布尼茨”方式):

forall P:bool -> Prop, forall x,y:bool, (x = y) -> (P x) -> (P y),

但这意味着从true=falseand I:True,我们可以得出结论False

我们在这里使用的另一个基本属性是定义 的能力F,这是由 bool 的递归原理给出的bool_rect

forall P:bool -> Type, P true -> P false -> (forall b:bool, P b)

通过选择P := (fun b:bool => Prop),我们得到

(bool_rect P) : Prop -> Prop -> (bool -> Prop),

我们在哪里输入TrueFalse获得我们的功能F

如果我们把这一切放在一起,我们会得到

(eq_ind true (bool_rect (fun b => Prop) True False) I false) : true = false -> False

还值得指出的是,Coq 采用归纳/递归原则,例如eq_ind或作为定义身份和布尔类型的bool_rect公理。

于 2017-12-22T06:24:45.737 回答
0

证明这一点的正常的、人类的方法是说,由于在这种情况下假设不匹配,我们不需要证明续集。在 Coq 中,有一种表达方式。这是通过一种名为inversion.

这是一个例子:

Theorem absurd_implies_absurd : 
  true = false -> 1 = 2.
Proof.
  intros H.
  inversion H.
  Qed.

第一步H是假设true = false,因此要证明的目标是1 = 2

inversion H步骤将自动证明目标!正是我们想要的,魔法!

为了理解这种魔力,我们转向文档的inversion含义。

对于初学者(比如我)来说,反演的官方文档读起来简洁而晦涩,这里有一个更好的解释。在页面上搜索关键字inversion,你会发现:

如果cd是不同的构造子,那么假设H是矛盾的。也就是说,一个错误的假设已经潜入上下文,这意味着任何目标都是可以证明的!在这种情况下,反转 H 将当前目标标记为已完成并将其从目标堆栈中弹出。

这正是我们想要的。唯一的问题是这超出了本书的计划。当然,重写truefalse起作用。问题不在于它不起作用,问题在于它不是我们想要的。

于 2021-08-21T22:54:28.167 回答