形式論理学についての解説の記事です。
トートロジー、真理関数、シェファーの棒記号について解説します。
トートロジー
トートロジー（tautology）とは、どのような命題の真偽値においても常に「真」である論理式を指します。命題論理におけるトートロジーは、すべての可能な真理値の組み合わせに対して命題が真になる場合に成立します。
例:
論理式「\(P \lor \neg P\)」はトートロジーです。
この論理式は、ある命題 \(P\) が真であろうと偽であろうと、必ず「真」になります。これは「排中律」とも呼ばれ、いかなる命題も「真」か「偽」のいずれかしか取らないことを表しています。
トートロジーを記号、\(\top\)で表すことがあります。
トートロジーの性質:
- トートロジーは、普遍的な真理を示しており、どんな文脈や状況においても真です。
- 論理式を評価する際に、論理式がすべての可能な真理値の割り当てにおいて真であれば、その論理式はトートロジーであるといえます。
トートロジーの否定を恒偽命題といいます。記号、\(\bot\)で表します。\(\neg \top \leftrightarrow \bot\)です。
重要なトートロジーの一覧
\(P \rightarrow P\) (同一律)
\(P \leftrightarrow P\) (同一律)
\(P \land P \leftrightarrow P\) (冪等律)
\(P \lor P \leftrightarrow P\) (冪等律)
\(\neg (\neg P) \leftrightarrow P\) (二重否定)
\(P \rightarrow Q \leftrightarrow \neg Q \rightarrow \neg P\) (対偶)
\(P \land Q \leftrightarrow Q \land P\) (交換律)
\(P \lor Q \leftrightarrow Q \lor P\) (交換律)
\((P \land Q) \land R \leftrightarrow P \land (Q \land R)\) (結合律)
\((P \lor Q) \lor R \leftrightarrow P \lor (Q \lor R)\) (結合律)
\(P \land (Q \lor R) \leftrightarrow (P \land Q) \lor (P \land R)\) (分配則)
\(P \lor (Q \land R) \leftrightarrow (P \lor Q) \land (P \lor R)\) (分配則)
\(P \land (P \lor Q) \leftrightarrow P\) (消去律)
\(P \lor (P \land Q) \leftrightarrow P\) (消去律)
\(\neg (P \land \neg P)\) (矛盾律)
\(P \lor \neg P\) (排中律)
\(\neg (P \land Q) \leftrightarrow \neg P \lor \neg Q\) (ド・モルガンの法則)
\(\neg (P \lor Q) \leftrightarrow \neg P \land \neg Q\) (ド・モルガンの法則)
\(P \rightarrow Q \leftrightarrow \neg P \lor Q\) (条件法)
\((P \leftrightarrow Q) \leftrightarrow (P \rightarrow Q) \land (Q \rightarrow P)\) (同値の定義)
\((P \rightarrow Q) \land P \rightarrow Q\) (前件肯定式)
\((P \rightarrow Q) \land \neg Q \rightarrow \neg P\) (後件否定式)
\((P \rightarrow Q) \land (Q \rightarrow R) \rightarrow (P \rightarrow R)\) (推移律)
トートロジーと恒偽命題を含む論理式
トートロジー\(\top\)と任意の命題\(P\)からなる命題を以下に示します。
\(\top \land P \leftrightarrow P\)
\(\top \lor P \leftrightarrow \top\)
\(\top \rightarrow P \leftrightarrow P\)
恒偽命題\(\bot\)と任意の命題\(P\)からなる命題を以下に示します。
\(\bot \land P \leftrightarrow \bot\)
\(\bot \lor P \leftrightarrow P\)
\(\bot \rightarrow P \leftrightarrow \top\)
ただし、\(\bot \rightarrow P\)は\(P\)の真偽に関わらず真となりますので、気をつけるべきです。
トートロジーを用いた複雑な命題の変形
トートロジーを用いて複雑な命題を簡単にすることができます。
\((P \rightarrow \neg Q) \land P\)を簡単にしてみます。
括弧の中をまず簡単にします。方針としては、含意\(\rightarrow\)を連言\(\land\)や選言\(\lor\)で書き換えることを優先するとよいでしょう。
\(A \rightarrow B \leftrightarrow \neg A \lor B\)を利用できます。
\(P \rightarrow \neg Q \leftrightarrow \neg P \lor \neg Q\)
これに\(\land P\)を作用させます。
\((P \rightarrow \neg Q) \land P \leftrightarrow (\neg P \lor \neg Q) \land P\)
括弧の中が選言で、連言がかかっているので、分配法則を利用します。
\((\neg P \lor \neg Q) \land P \leftrightarrow (\neg P \land P) \lor (\neg Q \land P)\)
\(\neg P \land P\)は矛盾律の否定であり、恒偽命題です。
\(\bot \lor (\neg Q \land P)\)
\(\bot \lor A \leftrightarrow A\)ですから、結果的には以下のようになります。
\((P \rightarrow \neg Q) \land P \leftrightarrow \neg Q \land P\)
※実は上式は前件肯定式と関連しています。
真理関数
真理関数（truth function）は、真理値を引数として受け取り、その結果として真理値（「真」または「偽」）を出力する関数です。つまり、真理関数は入力される真理値を真理値に変換する関数です。
命題\(P\)、\(Q\)の真理値を\(〚P〛, 〚Q〛\)と表すと、\(P\)、\(Q\)からなる命題\(X\)の真理値は、真理関数\(f_X(〚P〛,〚Q〛)\)で表せます。
命題\(X\)の真理値が以下の表のように表される場合に、\(X\)が\(P, Q\)でどう表されるかを考えてみましょう。
| \(P\) | \(Q\) | \(X\) |
| \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(0\) |
| \(0\) | \(0\) | \(1\) |
\(X\)は、\(P\)が真・\(Q\)が偽のとき、\(P\)が偽・\(Q\)が偽のときに真です。
それゆえ、\(X\)は\((P \land \neg Q) \lor (\neg P \land \neg Q)\)と表せます。
この論理式はもっと簡単にすることができます。
\(X \leftrightarrow (P \land \neg Q) \lor (\neg P \land \neg Q)\)
\(\leftrightarrow (P \lor \neg P) \land \neg Q\) (分配律)
\(\leftrightarrow \top \land \neg Q\) (排中律)
\(\leftrightarrow \neg Q\) (トートロジーの性質)
論理演算
論理演算（logical operations）は、真理値を引数として取り、論理的な結果を計算するものです。代表的な論理演算には、「NOT」「AND」「OR」「XOR」などがあります。これらの演算は通常、\(0\)（偽）と\(1\)（真）という二値の真理値を入力として、その組み合わせに基づいて真理値を出力します。
例えば、次のような論理演算があります：
NOT（論理否定）: 真理値の反転を行い、\(1\)（真）なら\(0\)（偽）、\(0\)（偽）なら\(1\)（真）を出力します。
\(\overline{1}=0\) 入力: 1 → 出力: 0
\(\overline{0}=1\) 入力: 0 → 出力: 1
AND（論理積）: 2つの入力が両方とも1（真）である場合に1を出力します。それ以外は0（偽）を出力します。
\(1 \cdot 1 = 1\) 入力: 1 AND 1 → 出力: 1
\(1 \cdot 0 = 0\) 入力: 1 AND 0 → 出力: 0
\(0 \cdot 0 = 0\) 入力: 0 AND 0 → 出力: 0
OR（論理和）: 少なくとも1つの入力が1（真）であれば1を出力し、両方が0（偽）なら0を出力します。
\(1 + 1 = 1\) 入力: 1 OR 1 → 出力: 1
\(1 + 0 = 1\) 入力: 1 OR 0 → 出力: 1
\(0 + 0 = 0\) 入力: 0 OR 0 → 出力: 0
XOR（排他的論理和）: 1つの入力が1（真）であれば1を出力し、両方が1 （真）か0（偽）なら0を出力します。
\(1 \oplus 1 = 0\) 入力: 1 XOR 1 → 出力: 0
\(1 \oplus 0 = 1\) 入力: 1 XOR 0 → 出力: 1
\(0 \oplus 0 = 0\) 入力: 0 XOR 0 → 出力: 0
これらの演算は真理関数の一種であり、二値論理における基本的な操作です。そのため、真理値（0または1）を引数として扱い、それをもとにした出力（0または1）を返す場合、それは論理演算とみなされます。
例題
\((1 + 0) \cdot (1 \oplus 0)\)
括弧の中から計算します。
\((1 + 0) \cdot (1 \oplus 0)\)
\(=1 \cdot 1\)
\(=1\)
シェファーの棒記号
シェファーの棒記号（Sheffer stroke）は、論理積や論理和、否定などの基本的な論理演算をすべて表現できる単一の演算子です。この記号は「NAND」（否定論理積）を表します。すなわち、シェファーの棒記号「\(|\)」で表される論理式 \(P | Q\) は、命題 \(P\) と \(Q\) の論理積の否定を意味します。
NAND の定義:
- \(P | Q\) は、\(P \land Q\) の否定、つまり「\(P \land Q\) が偽であるときに真」となります。
シェファーの棒記号は、命題論理における他の論理演算（論理積、論理和、否定など）を表現することができるため、非常に強力です。事実、この記号を用いれば、すべての命題論理の演算を表すことができるため、論理演算の最小基底（functionally complete）であると言えます。
例えば、次のようにして基本的な論理演算を表現できます：
- 否定：\(\neg P = P | P\)
- 論理積：\(P \land Q = \neg (P | Q) = (P | Q) | (P | Q)\)
論理演算では、以下のように表されます。
\(\overline{1 \cdot 1} = 0\)
\(\overline{1 \cdot 0} = 1\)
\(\overline{0 \cdot 0} = 1\)
参考文献
参考文献を紹介します．
以下はアフィリエイト広告です．
野矢茂樹著，『論理学』
長岡亮介著，『論理学で学ぶ数学』
