伊德里斯：证明一些矛盾的情况

Question

总的来说，我是 Idris 和 Proofs 的新手，但我正在通过移植到 Idris 的软件基础取得进展。我正在做练习

namespace Booleans

  data Bool = True | False

  andb : Booleans.Bool -> Booleans.Bool  -> Booleans.Bool
  andb True b = b
  andb False _ = False

  orb : Booleans.Bool -> Booleans.Bool -> Booleans.Bool
  orb True _ = True
  orb False b = b

  (&&) : Booleans.Bool -> Booleans.Bool  -> Booleans.Bool
  (&&) = andb

  (||) : Booleans.Bool -> Booleans.Bool  -> Booleans.Bool
  (||) = orb

  andb_eq_orb : (b, c : Booleans.Bool) -> (b && c = b || c) -> b = c

显然有四种情况，其中两种适用于自反性。

  andb_eq_orb True True _ = Refl
  andb_eq_orb True False prf = ?rhs1
  andb_eq_orb False True prf = ?rhs2
  andb_eq_orb False False _ = Refl

检查漏洞后发现

Main.Booleans.rhs1
    prf : True && False = True || False
---------------------------------
Main.Booleans.rhs1 : True = False

Main.Booleans.rhs2
    prf : False && True = False || True
---------------------------------
Main.Booleans.rhs2 : False = True

我不明白虽然断言显然不合逻辑，但我需要为这两个步骤证明这一点。我看不到我可以做的任何重写步骤。更多但抽象地说，我不理解在语言（Idris）中逻辑上或明确地解决这个问题的方法或模式。

通过为类型签名实现 Uninhabbited 接口，我能够使这两种方法都起作用：

Uninhabited (Booleans.True && Booleans.False = Booleans.True || Booleans.False) where
    uninhabited Refl impossible

Answer 1

我不确定你是如何定义 && 和 || 的，为什么它们不为你减少，所以让我展示一下这对 stdlib Bool 是如何工作的:

如果你这样写：

andb_eq_orb : (b, c : Bool) -> (b && c = b || c) -> b = c
andb_eq_orb True  True  _   = Refl
andb_eq_orb True  False prf = ?rhs1
andb_eq_orb False True  prf = ?rhs2
andb_eq_orb False False _   = Refl

然后

> :t rhs1
prf : False = True
--------------------------------------
rhs1 : True = False
Holes: Booleans.rhs2, Booleans.rhs1

 > :t rhs2
prf : False = True
--------------------------------------
rhs2 : False = True

您可以通过简单地通过这些简化的证明来填充它的一种方法，在必要时交换边：

andb_eq_orb : (b, c : Bool) -> (b && c = b || c) -> b = c
andb_eq_orb True  True  _   = Refl
andb_eq_orb True  False prf = sym prf
andb_eq_orb False True  prf = prf
andb_eq_orb False False _   = Refl

另一个正确的方法是使用 the Uninhabited interface, which gives you a proof of Void given a contradictory premise. You can then use a void : Void -> a function (aka the principle of explosion)，或者一个方便的同义词 absurd = void . uninhabited:

andb_eq_orb : (b, c : Bool) -> (b && c = b || c) -> b = c
andb_eq_orb True  True  _   = Refl
andb_eq_orb True  False prf = absurd prf
andb_eq_orb False True  prf = absurd prf
andb_eq_orb False False _   = Refl

伊德里斯：证明一些矛盾的情况

Idris: Proving some contradiction cases

proof

idris