📂集合論

命題と論理結合子、真理値表

定義 ¹

真か偽かの二つのうちの一つである陳述を 命題 だと言う。命題は真か偽の二つのうちの一つの 真理値^{truth value}を持つ。二つの命題 $p$、$q$ の真理値が同じなら、$p$ と $q$ は **（論理的に）同値^{(Logically) equivalent}**であると言い、$p \equiv q$ のように示される。複合命題を構成する方法として次の記号を 接続詞^connectivesと言う:

1. 否定: $\lnot$
2. 論理積: $\land$
3. 論理和: $\lor$
4. 条件: $\to$
5. 双条件: $\leftrightarrow$

真理表

通常、真は $T$ で、偽は $F$ で示される。上記の接続詞は定義による論理値を持つ。命題に接続詞を適用して得られた命題の真理値は、以下のような 真理表 で確認すると便利である:

否定

$p$ が真ならば $\lnot p$ は偽で、$p$ が偽ならば $\lnot p$ は真である。

• $\text{NOT}$ ゲート

論理積

$p$ と $q$ が両方真ならば $p \land q$ も真であり、それ以外は偽である。一般に、コンピュータ科学などの分野では $0$ を偽、$0$ 以外の数を真とみなす。$0$ でない二つの数 $a$、$b$ を考えれば $a \times b = ab \ne 0$ は真だが、一つでも $0$ なら $a \times b = 0$ で偽となる。この意味で、$\land$ は論理’積’と呼ばれる。

• $\text{AND}$ ゲート

論理和

$p$ または $q$ のどちらか一方が真ならば $p \lor q$ も真であり、両方が偽の時のみ偽である。論理積と同様に $a + b = 0$ なら偽で、それ以外は真であるため、$\lor$ は論理’和’と言われる。当然 $b = -a \ne 0$ なら $a$、$b$ は両方とも真だけど、$a+b = 0$ が偽でも、細かいことを言わないこと。だから、ただの’和’ではなく’論理和’なのだ。

• $\text{OR}$ ゲート

条件式

$p$ が真の時に $q$ が真ならば $p \to q$ も真である。実際の言葉と違って、$p$ が偽なら、$q$ が何であれ $p \to q$ も真になることに注目。一方、$p \to q \equiv \lnot p \lor q$ で、これは真理表を通して簡単に証明できる。文書の下部を参照せよ。

双条件式

$p \to q$ と $q \to p$ が両方とも真ならば $p \leftrightarrow q$。式で書くと、$(p \to q) \land (q \to p) \equiv p \leftrightarrow q$ になる。真理表で見ると、$p$ と $q$ が同時に真であるか、または同時に偽、すなわち同じ真理値を持つ時、$p \leftrightarrow q$ は真となる。

定理

条件式の論理的同値

$$p \to q \equiv \left( \lnot p \lor q \right)$$

証明

否定と論理和の定義により

■