我如何用 coq 证明荒谬？

Question

我正在阅读软件基础系列中的逻辑基础，我看到 plus_id_example 即：

Theorem plus_id_example : forall n m:nat,
  n = m ->
  n + n = m + m.

Proof.
  intros n m.
  intros H.
  rewrite H.
  reflexivity.  Qed.

我能理解解决方案，所以我尝试使用 absurd 来解决它，我想做的是：

让我们荒谬地考虑，n+n <> m+m，所以我们有2n <> 2m，n <> m，这是一个矛盾，因为我们有n=m作为我们的假设。

我如何使用 Coq 策略编写此代码？

Answer 1

您可以在 Coq 中使用许多 contraposition-based 引理之一：您可以通过使用 Coq 中的 Search "contra". 来查看它们。

使用ssreflect tactic语言，可以得到基于这个思路的证明如下（相信一定有更短的证明）：

Theorem plus_id_example : forall n m:nat,
  n = m ->
  n + n = m + m.
Proof.
  move=> n m.
  apply: contra_eq.
  have twice : forall p, p + p = p * 2.
    move=> p.
    by rewrite -iter_addn_0 /= addn0.
  by rewrite !twice eqn_mul2r.
Qed.

我如何用 coq 证明荒谬？

How can i proof by absurd with coq?

coq