(A -> B) /\ (B -> C) -> (A -> C) 在 Coq 中？

Question

我正在通过软件基础这本书学习 Coq，但无法证明以下引理（我需要用它来证明其他定理。）

Lemma if_trans : 
  forall (P Q R: Prop),
    (P -> Q) /\ (Q -> R) -> (P ->R).
Proof.
  intros P Q R [E1 E2]. 
Admitted.

这就是我卡住的地方。我不能对命题进行破坏，虽然我可以 apply E2 in E1，但它会生成两个子目标（我不明白为什么），并且第二个子目标在逻辑上无法证明。请帮忙。另外我只知道以下战术：

简单、自反性、对称性、破坏、归纳、应用、替换、.. in、exfalso、区分、注入、拆分、左、右、介绍、展开、断言、重写。

Q2：另一个问题有点类似。我需要使用上面证明的引理来证明其他定理。所以假设我有两个假设 H1: P -> Q 和 H2: Q -> R，目标是 P -> R。在这种情况下，我如何使用上述引理来证明目标，即如何将 H1 和 H2 组合成一个假设 H : (P ->Q ) /\ (Q -> R)?

Answer 1

您正在尝试证明以下内容：

Lemma if_trans :
  forall (P Q R : Prop),
    (P -> Q) /\ (Q -> R) -> (P -> R).

但是你只介绍了P, Q, RP -> Q的证明和Q -> R的证明所以它让你去证明P -> R。同理你可以用intro p得到p : P作为额外假设然后证明R.

总结一下你有

P, Q, R : Prop
E1 : P -> Q
E2 : Q -> R
p : P
===============
R

战术后

intros P Q R [E1 E2] p.

（注意额外的 p）。

也许到那时，如何证明它会显得更清楚。

当你使用 apply E2 in E1 时，它基本上看到 E1 在 P 成立的假设下证明了 Q，因此它将 E2 : Q -> R 应用于获取 R 并要求您为 P.

提供证据

对于你的第二个问题，如果你应用你的引理，它会要求 (P -> Q) /\ (Q -> P)，你可以用 split 证明，然后 assumption。你不应该尝试将 P -> Q 和 Q -> R 组合成 (P -> Q) /\ (Q -> P)，但如果你真的必须，你可以使用 pose proof (conj H1 H2) as H.

(A -> B) /\ (B -> C) -> (A -> C) 在 Coq 中？

(A -> B) /\ (B -> C) -> (A -> C) in Coq?

coq

coq-tactic