『論理学をつくる』練習問題19(3)の証明

$\{\land, \underline{\lor}, \leftrightarrow\}$ が十全であることの証明を以下に示す.

1. 証明の方針（設計図）
   すでに $\{\neg, \land\}$ が十全（すべての真理関数を表現可能）であることは既知とします。
   したがって、今回の道具 $\{\land, \underline{\lor}, \leftrightarrow\}$ を使って、「否定（$\neg$）」さえ作ることができれば、この集合も十全であると言えます。
   さらに、「否定」を作るための定石として、以下の関係を利用します。
   $\neg P \equiv P \leftrightarrow \bot$ （$P$ が矛盾式と同値であるとき、それは $P$ の否定である）
   つまり、目標は 「$\{\land, \underline{\lor}, \leftrightarrow\}$ だけを使って、常に偽となる式（$\bot$）を作ること」 に定まります。
2. ステップ1：矛盾式（$\bot$）の作成
   まず、$A \underline{\lor} B$（排他的論理和）と $A \leftrightarrow B$（同値）の真理値を比較します。

この表から、任意の入力 $A, B$ に対して、$A \underline{\lor} B$ と $A \leftrightarrow B$ は常に一方が 0 で、もう一方が 1 であることがわかります。
論理積（$\land$）は、両方が 1 のときのみ 1 を返す演算ですから、この2つを $\land$ で結合すれば、どのような入力に対しても必ず 0 になります。
したがって、矛盾式 $\bot$ は次のように構成できます。
$$\bot \equiv (A \underline{\lor} B) \land (A \leftrightarrow B)$$
3. ステップ2：否定（$\neg$）の作成
ステップ1で作成した $\bot$ を利用して、任意の命題 $P$ に対する否定 $\neg P$ を作ります。
「$P$ が偽であること」と「$P$ と 偽($\bot$) が同値であること」は等価なので、
$$\neg P \equiv P \leftrightarrow \bot$$
これにステップ1の式を代入すると、
$$\neg P \equiv P \leftrightarrow ((A \underline{\lor} B) \land (A \leftrightarrow B))$$
となり、$\{\land, \underline{\lor}, \leftrightarrow\}$ のみで否定が表現できました。
4. ステップ3：シェーファーの棒（$A|B$）の作成
最後に、これらを組み合わせてシェーファーの棒（NAND）を構成します。
定義より $A|B \equiv \neg(A \land B)$ です。
ステップ2の式の $P$ の部分に $(A \land B)$ を代入すれば完了です。
$$A|B \equiv (A \land B) \leftrightarrow ((A \underline{\lor} B) \land (A \leftrightarrow B))$$
結論
$\{\land, \underline{\lor}, \leftrightarrow\}$ を用いて矛盾式 $\bot$ が構成できる。
$\bot$ と $\leftrightarrow$ を用いて否定 $\neg$ が構成できる。
$\neg$ と $\land$ が揃ったため、これを用いてシェーファーの棒 $A|B$ （および他のすべての真理関数）を構成できる。
よって、$\{\land, \underline{\lor}, \leftrightarrow\}$ は十全である。■
補足：なぜ解答はあんなに短かったのか
解答編の記述は、この「否定を作るために矛盾を作る」という思考の足場をすべて取り払い、完成した数式だけを提示したため、飛躍があるように見えました。数学の証明では「$\bot$ を定義する」という中継地点を省略して、一気に代入した形（ステップ4の式）を書くことが多いためです。