命題と論理結合子、真理値表
定義 1
真か偽かの二つのうちの一つである陳述を 命題 だと言う。命題は真か偽の二つのうちの一つの 真理値truth valueを持つ。二つの命題 $p$、$q$ の真理値が同じなら、$p$ と $q$ は **(論理的に)同値(Logically) equivalent**であると言い、$p \equiv q$ のように示される。複合命題を構成する方法として次の記号を 接続詞connectivesと言う:
- 否定: $\lnot$
- 論理積: $\land$
- 論理和: $\lor$
- 条件: $\to$
- 双条件: $\leftrightarrow$
真理表
通常、真は $T$ で、偽は $F$ で示される。上記の接続詞は定義による論理値を持つ。命題に接続詞を適用して得られた命題の真理値は、以下のような 真理表 で確認すると便利である:
否定
$p$ が真ならば $\lnot p$ は偽で、$p$ が偽ならば $\lnot p$ は真である。
論理積
$p$ と $q$ が両方真ならば $p \land q$ も真であり、それ以外は偽である。一般に、コンピュータ科学などの分野では $0$ を偽、$0$ 以外の数を真とみなす。$0$ でない二つの数 $a$、$b$ を考えれば $a \times b = ab \ne 0$ は真だが、一つでも $0$ なら $a \times b = 0$ で偽となる。この意味で、$\land$ は論理’積’と呼ばれる。
論理和
$p$ または $q$ のどちらか一方が真ならば $p \lor q$ も真であり、両方が偽の時のみ偽である。論理積と同様に $a + b = 0$ なら偽で、それ以外は真であるため、$\lor$ は論理’和’と言われる。当然 $b = -a \ne 0$ なら $a$、$b$ は両方とも真だけど、$a+b = 0$ が偽でも、細かいことを言わないこと。だから、ただの’和’ではなく’論理和’なのだ。
条件式
$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) $$
証明
否定と論理和の定義により
■
이흥천 역, You-Feng Lin. (2011). 집합론(Set Theory: An Intuitive Approach): p3~21. ↩︎