0.はじめに
本記事では「情報科学における論理」の第1章2節から5節までの内容をまとめています。
※筆者なりのアレンジ・付け足しがあります。ご容赦ください。
1.命題とは何か
命題（proposition） は、真（True）または偽（False）のいずれかの真理値を持つ文のことです。
命題の例
- 「2 + 2 = 4」 → 真
- 「今日は雨が降っている」 → 天候によって真偽が決まる
- 「すべての素数は奇数である」 → 偽（2は偶数の素数）
命題でないもの
- 「こんにちは」 → 挨拶（真偽を問えない）
- 「x > 5」 → xが未定義（変数に値が代入されれば命題になる）
- 「この文を読んでください」 → 命令文
2.論理結合子（Logical Connectives）
命題論理では、基本的な命題を論理結合子で組み合わせて複合命題を作ります。
(1) 論理積・連言（Conjunction）: ∧ / AND
$P ∧ Q$ （「PかつQ」）
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
(2) 論理和・選言（Disjunction）: ∨ / OR
$P ∨ Q$ （「PまたはQ」）
| P | Q | P ∨ Q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
ここまで内容がなかなか理解できなかった場合は、論理学の初歩の初歩を読んでみてください。
(3) 含意（Implication）: → / ⊃
$P → Q$ あるいは $P ⊃ Q$（「PならばQ」）
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
重要な注意点:
$P → Q$は$¬P ∨ Q$と同値です。
前件が偽の場合、含意は常に真になります。
※「情報科学における論理」では$⊃$が使われてますが、本記事では、$→$を使おうと思います。
(4) 同値（Biconditional）: ↔
$P ↔ Q$ （「PとQは同値」）
| P | Q | P ↔ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
重要な注意点:
$P ↔ Q$は$(P ∧ Q) ∨ (¬P ∧ Q)$と同値です。
※文献によって同値とか双条件とか記述が違います。
(5) 否定（Negation）: ¬
$¬P$ （「Pではない」）
| P | ¬P |
|---|---|
| T | F |
| F | T |
上記以外にも論理結合子があります。簡単に紹介します。
(a) 排他的論理和（Exclusive OR）: ⊕ / XOR
$P ⊕ Q$ （「PまたはQ（ただし両方ではない）」）
| P | Q | P ⊕ Q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
(b) 否定論理積（Not AND）: | / NAND
$P ｜ Q$ （「PかつQではない」）
| P | Q | P｜Q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
(c) 否定論理和（Not OR）: ↓ / NOR
$P ↓ Q$ （「PまたはQではない」）
| P | Q | P ↓ Q |
|---|---|---|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
3.トートロジーとは何か
トートロジー（Tautology） とは、構成要素の命題がどのような真理値を取っても、常に真（True）となる論理式のことです。日本語では「恒真式」とも呼ばれます。
基本的な例
最もシンプルなトートロジーの例：
$P ∨ ¬P$ （排中律「PまたはPでない」）
(1) トートロジーの判定方法
真理表を作成し、すべての行で結果が真になることを確認します。
例：(P → Q) ∨ (Q → P)
この式がトートロジーかどうか検証してみましょう。
| P | Q | P → Q | Q → P | (P → Q) ∨ (Q → P) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
最後の列がすべて真なので、この式はトートロジーです。
表からわかるように真偽を確かめるには、論理式を分解して、その分解した論理式の真偽を確かめていきます。この分解した論理式を部分論理式といいいます。
4.付値
付値とは、真か偽のどちらかを返すだと思ってください。数学で$f(x)=x+1$とかあったと思いますが、この関数$f(x)$に1を入れると、2が返ってきますし、2を入れると、3が返ってきます。これと一緒で、命題論理では付値$v(P)$とか付値$v(P ∧ Q)$など、$v$で表し、カッコ内には、命題変数や論理式が入ります。
基本的な命題変数への付値は、論理結合子を通じて複合命題へと拡張されます。
以下では「Pがなりたつための必要十分条件はQがなちたつことである」ことを表すため、⟺の記号を用います。
拡張規則：
$v(P ∧ Q) = t ⟺ v(P) =v(Q) = t$
$v(P ∨ Q) = t ⟺ v(P) = t$ または $v(Q) = t$
$v(P → Q) = t ⟺ v(P) = f$ または $v(Q) = t$
$v(¬P) = t ⟺ v(P) = f$
5.充足可能性
充足可能性（satisfiability）
ある真理値の割り当てで真になる論理式が存在すれば、その論理式は「充足可能（satisfiable）」です。
例えば、P∧Q は、P = 真, Q = 真 のときだけ真になる。つまり少なくとも1つの割り当てで真になるので「充足可能」です。充足可能でないときは、「充足不可能（unsatisfiable）」といいます。
トートロジーとの違いは、以下の通りです。
トートロジー：どんな真理値を付与してもすべての解釈で真になる
充足可能性：ある解釈（少なくとも1つ）で真になる
6.基本的な同等
論理式Pと論理式Qが同等であるとき、$P≡Q$とかきます。
- べき等律
$P∧P≡P$
$P∨P≡P$ - 結合律
$P∧(Q∧R)≡(P∧Q)∧R$
$P∨(Q∨R)≡(P∨Q)∨R$ - 交換律
$P∧Q≡Q∧P$
$P∨Q≡Q∨P$ - 吸収律
$P∧(P∨Q)≡P$
$P∨(P∧Q)≡P$ - 分配律
$P∧(Q∨R)≡(P∧Q)∨(P∧R)$
$P∨(P∧Q)≡(P∨Q)∧(P∨R)$ - 対合律
$¬¬P≡P$ - ド・モルガン律
$¬(P ∧ Q) ≡ ¬P ∨ ¬Q$
$¬(P ∨ Q) ≡ ¬P ∧ ¬Q$ - 含意（再掲）
$P → Q ≡ ¬P ∨ Q$
$P → Q ≡ ¬(P ∧ ¬Q)$ - 同値（再掲）
$P ↔ Q ≡ (P → Q) ∧ (Q → P)$
$ P ↔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)$
7.標準形
(1) 論理和標準形
この節では命題変数$p_1, p_2, ..., p_n$を含む命題を考えます。
1個の命題変数$p_1$や¬をつけた$¬p_1$をリテラルといいます。
また、前者を正のリテラル、負のリテラルといいます。
リテラルとリテラルを∧で結び（リテラルの積）、なおかつ、同じ命題変数を含んでいないものを基本積といいます。
例：
基本積：$p_1∧p_2$, $p_1∧¬p_2∧p_3$
基本積ではない：$p_1∧¬p_1$, $p_1∧p_2∧p_1$
基本積と基本積を∧で結んだ形（基本積の和）を、標準形あるいは積和形といいます。
例：$(p_1∧p_2)∨(p_3∧p_4)$, $(p_1∧p_2)∨(p_1∧¬p_2∧p_3)$
標準形のうち、どの基本積もすべての命題変数を含んでいるものを、論理和標準形といいます。
例：命題変数$p_1, p_2, p_3$含む命題
(p_1 \land \lnot p_2 \land p_3) \lor(p_1 \land \lnot p_2 \land \lnot p_3) \lor (\lnot p_1 \land p_2 \land p_3)
論理和標準形ではない例（命題変数が足りていない基本積がある）：
(p_1 \land \lnot p_2 ) \lor(\lnot p_2 \land \lnot p_3) \lor (\lnot p_1 \land p_2 \land p_3)
(2) 論理積標準形
論理和標準形の$\land$を$\lor$に、$\lor$を$\land$に入れ替えたものを論理積標準形といいます。
例：命題変数$p_1, p_2, p_3$含む命題
$$
(p_1 \lor \lnot p_2 \lor p_3) \land (p_1 \lor \lnot p_2 \lor \lnot p_3) \land (\lnot p_1 \lor p_2 \lor p_3)
$$
8.論理結合子の制限
論理結合子として$∧, ∨, →, ↔, ¬$などが出てきましたが、例えば、
$P∧Q≡ ¬(¬P ∨ ¬Q), P → Q ≡ ¬P ∨ Q$
がなりたつので実は、$∨, ¬$のみで論理式を表すことができるのです。
制限可能な論理結合子
- $∨, ¬$
例：上記に記載 - $∧, ¬$
例：$P∨Q ≡ ¬(¬P∧ ¬Q), P → Q ≡ ¬(P ∧ ¬Q)$ - $→, ¬$
例：$P∧Q ≡ ¬(P→ ¬Q), P∨Q ≡¬P→Q$
ここで、新しい論理結合子を導入します。
第2節(b)で示した否定論理積（NAND）です。記号は"|"です（シェファーの縦棒と呼ばれる）。否定論理積を使うと，たった1つですべての論理式を表すことができます。
例：$¬P≡P|P, P∨Q ≡ (P|Q)|(P|Q)$（このあとは、上記2.と同様）