向 Coq 添加断言及其否定

Question

我想证明下面的定理：

Theorem T1 : forall s x,
  Ps s x -> PPs s x /\ ~IPs s x \/ ~PPs s x /\ IPs s x.

其中Ps是原语，PPs和IPs定义如下（F也是原语）：

Definition PPs x y := Ps x y /\ ~ F y x.
Definition IPs x y := Ps x y /\ F y x.

所以我想要一个定理来说明如果 Ps s x 那么我们有 PPs s x xor IPs s x （我不知道如何写异或运算符在 Coq 中，所以我分解了它）。

现在，我想在我关于命题 F x s 的证明中引入一个假设。我想要它和它的否定（不是同时），这样我就可以很容易地证明我的定理。但是，我不知道该怎么做。所以我的问题是如何证明假设一个新命题的东西，然后它的否定？

（如有必要，请随时更改标题。我不知道。）

Answer 1

如果我没理解错的话，你是在找排中律。因此，您想假设 F x s \/ ~ F x s 并在每种情况下进行不同的推理。

如果您知道 F x s 是可判定的，例如如果 F x s : bool，则析取是可证明的，您可以通过以下方式将其放入上下文中。

Lemma name : ... .
Proof.
  ...
  destruct (F x s) eqn:eF.
  - (* assume F x s = true *)  admit.
  - (* assume F x s = false *) admit.

如果你不知道 F x s 是可判定的，这是标准的 if F x s : Prop 并且你没有其他假设，那么你可以通过假设排中律来凑合。这不是 Coq 基础理论的一部分，但可以接受：

Require Import Classical.
Check classic.
(* classic : forall P : Prop, P \/ ~ P *)

因此您的开发可能如下所示：

Require Import Classical.

Lemma name : ... .
Proof.
  ...
  destruct (classic (F x s)) as [yesF|notF].
  - (* assume F x s *) admit.
  - (* assume ~ F x s *) admit.

向 Coq 添加断言及其否定

Add an assertion and its negation to Coq

coq