使用 SML 和 HOL 推理规则从第一原理证明定理

Question

我正在尝试使用带有 HOL 推理规则的 SML 来证明定理 [] |- p /\ q <=> q /\ p :thm。这是 SML 代码：

val thm1 = ASSUME ``p:bool /\ q:bool``;
val thm2 = ASSUME ``p:bool``;
val thm3 = ASSUME ``q:bool``;
val thm4 = CONJ thm2 thm3;
val thm5 = CONJ thm3 thm2;
val thm6 = DISCH ``(q:bool/\p:bool)`` thm4;
val thm7 = DISCH ``(p:bool/\q:bool)`` thm5;
val thm8 = IMP_ANTISYM_RULE thm6 thm7;

以上代码的结果产生：

val thm8 =  [(p :bool), (q :bool)] |- (q :bool) /\ (p :bool) <=> p /\ q: thm

我做错了什么？

Answer 1

你的最终定理的问题是你仍然有 p 和 q 作为假设，通过 thm2 和 thm3 引入，而你可以而且应该得到他们来自 thm1.

您需要的第一个定理类似于 p /\ q ==> p。我通过浏览 description（第 2.3.24 节）找到了适当的规则。它被称为CONJUNCT1。

利用它，我们可以从thm1:

得到一个定理p

val thmp = CONJUNCT1 thm1;

同样的想法可以从 thm1 得到 q 作为定理：

val thmq = CONJUNCT2 thm1;

然后你可以将你的想法应用到 thm5:

val thm5 = CONJ thmq thmp;

这里重要的事情是我们不使用从p导出的p（thm2) 和 q 来自 q (thm3) 而 p 来自 p /\ q和q源自p /\ q（设置show_assumes := true;可能有助于更清楚地看到这一点）。

最后，我们将您的想法应用到 thm7:

val thm7 = DISCH ``p /\ q`` thm5;

获得预期结果的前半部分，但没有多余的假设。

后半部分同理得到：

val thm9 = ASSUME (``q /\ p``); val thmp2 = CONJUNCT2 thm9; val thmq2 = CONJUNCT1 thm9; val thm6 = DISCH ``q /\ p`` (CONJ thmp2 thmq2);

那么你对 thm8 的想法就完美了：

val thm8 = IMP_ANTISYM_RULE thm7 thm6;

使用 SML 和 HOL 推理规则从第一原理证明定理

Theorem proving from first principles using SML with HOL inference rules

sml

theorem-proving

hol