問題一： https://blog.yexca.net/ja/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は偽を表す。

b）命題 $\varphi$ が恒真（トートロジー）であるか否か答えよ。

c）命題 $\varphi$ が充足可能であるか否か答えよ。

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} $$

これより

ゆえに、ア：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$ を $A$ に変換する。

2-a

• ア: $p_1 \wedge p_2$
• イ: $p_1 \wedge p_2$
• ウ: $p_2$
• エ: $p_3$
• オ: $p_2 \wedge p_3$

$$ \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2)\wedge p_3}{p_1 \wedge p_2}\wedge E_L }{p_1}\wedge E_L \quad \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2) \wedge p_3}{p_1 \wedge p_2}\wedge E_L }{p_2}\wedge E_R \quad \cfrac{(p_1 \wedge p_2) \wedge p_3}{p_3}\wedge E_R }{p_2 \wedge p_3}\wedge I }{p_1 \wedge (p_2 \wedge p_3)}\wedge I $$

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$

$$ \cfrac{ \cfrac{p_1 \wedge p_2}{p_2}\wedge E_R \quad \cfrac{ \cfrac{p_1 \wedge p_2}{p_1}\wedge E_L \quad p_1 \to (p_2 \to p_3) }{p_2 \to p_3}\to E }{p_3}\to E $$

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=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) $$

3-a

この論理式のモデルは存在する。モデルのユニバースの濃度の最小値は3である。

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) $$

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)$ は成り立たない。

Reference

自然演繹

命題論理

演繹定理

充足可能性問題