Logic Homework 2

Problem 1

S - strcuture 的不确定性来自 a，亦即 R, f, c 的映射结果，下面对每个符号的映射种类记为 ，则 1.

综上，由于 有限，设 分别有 个，则 S-structure 的个数至多为

Problem 2

这是做不到的，证明如下： 注意到 本身是一个公式 ，分类讨论：

1. 若建立的 ，则 ， 为真， 也为真，故 成立，即
2. 若 ，即 为假，这时由于 为假，故 亦为真 综上，不可能

Problem 3

It depends，比如考察

则

则直接出现了一条从 到 的路

另一方面，若考察

基于 的定义，可见 的情况如下

显然不存在从 到 的有向路径。