論理 1

Lean による定理証明は，証明したいステートメントを論理式に落としてプログラミングするわけだが，それには数理論理に関する知識が必要になる．そこで「はじめての数理論理学」山田俊行著，森北出版．2018．を使って数理論理を勉強することにした．

ナルホドと思った演習問題に関して，ここに備忘録を残す．

演習問題 1.1 論理同値性の判定

(5) $A \Rightarrow (B \Rightarrow C)$ と $(A \Rightarrow B) \Rightarrow C$ は論理同値か？

演習問題は真理値表を使って判定することになっているが，式変形で判定する．
まず $A \Rightarrow (B \Rightarrow C)$ について
$$
\begin{aligned}
& \ A \Rightarrow (B \Rightarrow C) \\
\Leftrightarrow & \ \lnot A \lor (\lnot B \lor C) \\
\Leftrightarrow & \ \lnot A \lor \lnot B \lor C \\
\end{aligned}
$$
一方，
$$
\begin{aligned}
& \ (A \Rightarrow B) \Rightarrow C \\
\Leftrightarrow & \ \lnot (A \Rightarrow B) \lor C \\
\Leftrightarrow & \ \lnot (\lnot A \lor B) \lor C \\
\Leftrightarrow & \ A \land \lnot B \lor C \\
\end{aligned}
$$
となるので，論理同値ではない．
含意では結合則が成り立たないことがよくわかりました．

(6) $A \Rightarrow (B \Rightarrow C)$ と $A \land B \Rightarrow C$ は論理同値か？

先と同様に式変形にて判定する．$A \land B \Rightarrow C$ について
$$
\begin{aligned}
& \ A \land B \Rightarrow C \\
\Leftrightarrow & \ \lnot (A \land B) \lor C \\
\Leftrightarrow & \ \lnot A \lor \lnot B \lor C \\
\end{aligned}
$$
これは (5) で示した $A \Rightarrow (B \Rightarrow C)$ と同じなので，論理同値である．

演習問題 1.2 恒真性の判定

(3) $A \land B \Rightarrow A \lor B$ は恒真か？
ヴェン図で考えると $A \land B$ は $A \lor B$ の部分集合だから真だろうなと思ったが，式変形にて判定する．
$$
\begin{aligned}
& \ A \land B \Rightarrow A \lor B \\
\Leftrightarrow & \ \lnot (A \land B) \lor A \lor B \\
\Leftrightarrow & \ (\lnot A \lor \lnot B) \lor A \lor B \\
\Leftrightarrow & \ \lnot A \lor \lnot B \lor A \lor B \\
\Leftrightarrow & \ \lnot A \lor A \lor \lnot B \lor B \\
\Leftrightarrow & \ \top \lor \top \\
\Leftrightarrow & \ \top \\
\end{aligned}
$$
よって恒真である．

(7) $(A \land B) \land C \Rightarrow A \land (B \land C)$ は恒真か？
論理積は結合則が成り立つ（と思う）ので恒真な気もするが，式変形して確認する．
$$
\begin{aligned}
& \ (A \land B) \land C \Rightarrow A \land (B \land C) \\
\Leftrightarrow & \ \lnot ((A \land B) \land C) \lor A \land (B \land C) \\
\Leftrightarrow & \ \lnot (A \land B) \lor \lnot C \lor A \land (B \land C) \\
\Leftrightarrow & \ (\lnot A \lor \lnot B) \lor \lnot C \lor A \land (B \land C) \\
\Leftrightarrow & \ (\lnot A \lor \lnot B \lor \lnot C) \lor (A \land B \land C) \\
\end{aligned}
$$
$\lnot A \lor \lnot B \lor \lnot C$ が唯一偽になるときは $A \land B \land C$ が真になるので，この論理式は恒真である．

演習問題 1.3 主張の論理式による表現

変数のドメイン $x \in \mathbb{Z}$ などは省いて記述する．
(7) ある整数は，すべての正整数の約数である．
$$
\exists x \forall y \ y > 0 \Rightarrow x \mid y
$$
上記は教科書の解答例だが，ドメインを指定して書くなら
$$
\exists x \in \mathbb{Z}, \forall y \in \mathbb{Z}^+ \ x \mid y
$$
でもいいのかな？

(8) $x$ は，2つの整数 $y$ と $z$ の最大公約数である．
$$
x \mid y \land x \mid z \land \forall w \ (w \mid y \land w \mid z \Rightarrow w \le x)
$$
最大を表すのに補助変数 $w$ を導入するのが興味深い．

(9) 最大の偶数は存在しない．
$$
\lnot \exists x \left( 2 \mid x \land \forall y \left( 2 \mid y \Rightarrow y \le x \right)\right)
$$