Logic Homework 5

Problem 1

我们主要使用

另外，最后的式子 实际上定义了数学归纳法，下面我们利用数学归纳法考虑

需要满足的性质

首先，证明引理一（L1）

我们作归纳法，首先从

代入 即得

即

下面证明

这是因为

下面，我们证明引理二（L2）（记为）

同样用归纳法，首先

从 A1 知为 ， 也从 A1 知为

另一方面，若

则

因此对于 y 替换为 的情况也成立，综上可证出 L2

下面我们证目标结论

同样对 作归纳

时，

成立

而若

成立，则

综上，证毕

Problem 2

(a)

正确性性质即给定

与

要求

(b)

由

可知

则考虑

这时首先由于 ，根据 coincidence lemma

另一方面，由于

由 substitution lemma

因此

由

知

而由于 ，根据 coincidence lemma

因此

证毕

Problem 3

怎么有点没看懂这个题的意味 OwO

这个规则是不可推的。

若其可推即代表其恒真，则考虑构造一个解释

其中

易知

而

Problem 4

(a)

(b)

考虑

Problem 5

我们知道

首先

另一方面