問題一：
https://blog.yexca.net/zh-tw/archives/198
問題二：本文
問題三：
https://blog.yexca.net/zh-tw/archives/200
問題四：
https://blog.yexca.net/zh-tw/archives/202
問題五：
https://blog.yexca.net/zh-tw/archives/203
引言
這一大題剛看的時候還以為屬於形式語言（與自動機理論）呢，實際上動手做題後發現是數理邏輯的內容 (兩者都沒學過，也都一樣)
總體的難度並非特別高 (可能是因為做過東大試卷吧，看這裡的題目都不太難) 但還是需要掌握較多的理論基礎才能解出。
題目版權屬於東京科學大學所有，僅為了方便閱讀而引用，無營利行為。
1
考慮命題邏輯。命題 $\varphi$ 為 $(\neg p_0 \to \neg p_1) \wedge (\neg p_1 \to p_0)$。其中，$p_0, p_1$ 為命題記號。
a）請回答填入下表（ア）～（エ）的值，使之成為 $\varphi$ 的真值表。其中，1 代表真，0 代表偽。
| $p_0$ | $p_1$ | $\varphi$ |
|---|---|---|
| 0 | 0 | （ア） |
| 0 | 1 | （イ） |
| 1 | 0 | （ウ） |
| 1 | 1 | （エ） |
b）回答命題 $\varphi$ 是否為恆真式（Tautology）。
c）回答命題 $\varphi$ 是否為可滿足的（Satisfiable）。
1-a
首先，整理命題 $\varphi$：
$$ \begin{align} \varphi &= (\neg p_0 \to \neg p_1) \wedge (\neg p_1 \to p_0) \\ &= (p_0 \vee \neg p_1) \wedge (p_1 \vee p_0) \end{align} $$由此得：
| $p_0$ | $p_1$ | $\varphi$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
因此，（ア）：0、（イ）：0、（ウ）：1、（エ）：1。
1-b
由於存在 $\varphi=0$ 的情況，因此並非恆真命題。
1-c
由於存在 $\varphi=1$ 的情況，因此是可滿足的。
2
考慮命題邏輯的自然演繹。$p_1, p_2, p_3$ 為命題記號，$\wedge I$ 為連言導入規則，$\wedge E_L$ 為連言除去規則（左），$\wedge E_R$ 為連言除去規則（右），$\to E$ 為蘊涵除去規則。
a）假設為 $(p_1 \wedge p_2) \wedge p_3$，結論為 $p_1 \wedge (p_2 \wedge p_3)$，欲完成下方的自然演繹導出（證明圖）。請回答填入（ア）～（オ）的命題。
$$ \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2)\wedge p_3}{(ア)}\wedge E_L }{p_1}\wedge E_L \quad \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2) \wedge p_3}{(イ)}\wedge E_L }{(ウ)}\wedge E_R \quad \cfrac{(p_1 \wedge p_2) \wedge p_3}{(エ)}\wedge E_R }{(オ)}\wedge I }{p_1 \wedge (p_2 \wedge p_3)}\wedge I $$b）假設為 $p_1 \wedge p_2$ 與 $p_1 \to (p_2 \to p_3)$，結論為 $p_3$，欲完成下方的自然演繹導出（證明圖）。請回答填入（ア）～（エ）的命題。
$$ \cfrac{ \cfrac{(ア)}{p_2}\wedge E_R \quad \cfrac{ \cfrac{(イ)}{p_1}\wedge E_L \quad (ウ) }{(エ)}\to E }{p_3}\to E $$c）回答命題集合 $\{ \neg p_0 \to \neg p_1, \neg p_1 \to p_0 \}$ 是矛盾還是無矛盾（一致），並說明理由。
2-解答
如果能理解題目給出的幾個符號，前兩小題其實相當容易。
$\wedge I$ 是連言導入規則，即將 $A$ 和 $B$ 變為 $A \wedge B$。
$\wedge E_L$ 是連言除去規則，保留左側，即將 $A \wedge B$ 變為 $A$。
$\wedge E_R$ 是連言除去規則，保留右側，即將 $A \wedge B$ 變為 $B$。
$\to E$ 是蘊涵除去規則，即將 $A$ 和 $A \to B$ 變為 $B$。
2-a
- ア: $p_1 \wedge p_2$
- イ: $p_1 \wedge p_2$
- ウ: $p_2$
- エ: $p_3$
- オ: $p_2 \wedge p_3$
2-b
- ア: $p_1 \wedge p_2$
- イ: $p_1 \wedge p_2$
- ウ: $p_1 \to (p_2 \to p_3)$
- エ: $p_2 \to p_3$
2-c
是無矛盾的。整理命題：
$$ \neg p_0 \to \neg p_1 \equiv p_0 \vee \neg p_1 \\ \neg p_1 \to p_0 \equiv p_1 \vee p_0 $$建立真值表：
| $p_0$ | $p_1$ | $\neg p_0 \to \neg p_1$ | $\neg p_1 \to p_0$ |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
當 $p_0=1, p_1=0$ 或 $p_0=1, p_1=1$ 時，兩個命題皆成立。
由於至少存在一種真值分配使得命題集合成立，因此命題集合 $\{ \neg p_0 \to \neg p_1, \neg p_1 \to p_0 \}$ 是無矛盾的。
3
考慮一階述詞邏輯。
a）以下論理式的模型是否存在？若存在，請回答該模型宇集（Universe）基數的最小值。若不存在，請說明理由。
$$ \exists x \exists y \exists z \space \neg(x=y) \wedge \neg(y=z) \wedge \neg(z=x) $$b）以下論理式的模型是否存在？若存在，請列舉一個模型。若不存在，請說明理由。
$$ \exists x \forall y(x=y) $$3-a
此論理式的模型存在。其模型宇集基數的最小值為 3。
3-b
此論理式的模型存在。例如，設定宇集 $U=\{a\}$。在此情況下，由於 $U$ 的所有元素都與 $x$ 相等，因此論理式成立。
4
考慮一階述詞邏輯的自然演繹。請回答以下式子是否成立，並說明理由。其中，$P$ 為二元述詞符號。
$$ \vdash (\forall x \exists y P(x,y)) \to \exists x \forall y P(x,y) $$4-解答
此式不成立。反例如下：
定義宇集為 $\{ m,n,a,b \}$。此時，給予述詞 $P(x,y)$ 的解釋如下：
$$ P(m,a) = 真 \quad P(a,m) = 偽 \\ P(n,b) = 真 \quad P(b,n) = 偽 $$由此，$\forall x \exists y P(x,y)$ 成立。然而，$\exists x \forall y P(x,y)$ 並不成立。