問題一：https://blog.yexca.net/archives/198
問題二：この文章
問題三：https://blog.yexca.net/archives/200
問題四：https://blog.yexca.net/archives/202
問題五：https://blog.yexca.net/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$ が恒真（トートロジー）であるか否か答えよ。
c）命題 $\varphi$ が充足可能であるか否か答えよ。
解答
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
b
$\varphi=0$ の場合が存在するため、恒真命題ではない
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 }$ が矛盾するか無矛盾であるかを答え、その理由を述べよ。
解答
题目给出的几个符号如果能够了解的话，这题还是比较容易做出来前两问的
$\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$ 变成 $A$
a
- ア: $p_1 \wedge p_2$
- イ: $p_1 \wedge p_2$
- ウ: $p_2$
- エ: $p_3$
- オ: $p_2 \wedge p_3$
b
- ア: $p_1 \wedge p_2$
- イ: $p_1 \wedge p_2$
- ウ: $p_1 \to (p_2 \to p_3)$
- エ: $p_2 \to p_3$
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）以下の論理式のモデルは存在するか。存在するならば、モデルのユニバースの濃度の最小値を答えよ。存在しないならば、その理由を述べよ。
\[\exists x \exists y \exists z \space \neg(x=y) \wedge \neg(y=z) \wedge \neg(z=x)\]b）以下の論理式のモデルは存在するか。存在するならば、そのモデルを1つ挙げよ。存在しなければ、その理由を述べよ。
\[\exists x \forall y(x=y)\]解答
a
この論理式のモデルは存在する。モデルのユニバースの濃度の最小値は3である。
b
この論理式のモデルは存在する。例えば、ユニバース $U={a}$ を設定する。この場合、$U$ のすべての要素が $x$ と等しいため、論理式が成り立つ。
4
一階述語論理の自然演繹について考える。以下が成り立つか否か答え、その理由を述べよ。ただし、$P$ はアリティ2の述語記号とする。
\[\vdash (\forall x \exists y P(x,y)) \to \exists x \forall y P(x,y)\]解答
これは成り立たない。反例は以下のように構成する。
ユニバースを ${ 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)$ は成り立たない。