| 目次 | 索引 |
|---|---|
コンピュータの扱うデータの中では、数値に並んで真理値というものも重要です。
命題 （ proposition ）とは、真偽がはっきり定まる表現のことです。 例えば、「5は6より小さい」という表現は真の命題です。 また、「8は7より小さい」という表現は偽の命題です。
命題の持つ、この真と偽という値を、 真理値 （ truth-value ）または 論理値 （ logical value ）と呼びます。 真理値は、しばしば記号TとFで表されます。 また、ビットと対応させ、1と0で表されることもあります。
| 真理値 | 記号 | ビット |
|---|---|---|
| 真 | T | 1 |
| 偽 | F | 0 |
数値は、100+200 のような四則演算ができます。 命題にも、「5は6より小さい、かつ、8は7より小さい」のような演算があります。
これ以上分解できない命題を 原子命題 （ atomic proposition ）と呼びます。 命題の演算を表す記号を、 論理演算子 （ logical operator ）または 論理結合子 （ logical connective ）と呼びます。 命題は、原子命題と論理演算子から構成されます。 論理演算子には、論理積（AND）、論理和（OR）、否定（NOT）などがあります。
論理積 （ conjunction ）は、「かつ」を意味する演算です。 つまり、両方が真のときに真となります。 英語の"and"に対応しますので、 AND とも表されます。 記号では∧と書きます。
| P | Q | P∧Q | P | Q | P∧Q |
|---|---|---|---|---|---|
| T | T | T | 1 | 1 | 1 |
| T | F | F | 1 | 0 | 0 |
| F | T | F | 0 | 1 | 0 |
| F | F | F | 0 | 0 | 0 |
論理和 （ disjunction ）は、「または」を意味する演算です。 つまり、少なくとも一方が真のときに真となります。 英語の"or"に対応しますので、 OR とも表されます。 記号では∨と書きます。
| P | Q | P∨Q | P | Q | P∨Q |
|---|---|---|---|---|---|
| T | T | T | 1 | 1 | 1 |
| T | F | T | 1 | 0 | 1 |
| F | T | T | 0 | 1 | 1 |
| F | F | F | 0 | 0 | 0 |
否定 （ negation ）は、「〜でない」を意味する演算です。 つまり、真ならば偽、偽ならば真となります。 英語の"not"に対応しますので、 NOT とも表されます。 記号では¬と書きます。
| P | ¬P | P | ¬P |
|---|---|---|---|
| T | F | 1 | 0 |
| F | T | 0 | 1 |
論理和と「または」には微妙な違いがあります。 普通、「または」と言えば、両方は意味しないからです。 片方が真のときに真となる演算は、 排他的論理和 （ exclusive disjunction ）と呼ばれます。 これは XOR （ exclusive OR ）とも表され、記号では丸の中にプラスの(+)です。
| P | Q | P(+)Q | P | Q | P(+)Q |
|---|---|---|---|---|---|
| T | T | F | 1 | 1 | 0 |
| T | F | T | 1 | 0 | 1 |
| F | T | T | 0 | 1 | 1 |
| F | F | F | 0 | 0 | 0 |
原子命題の真理値がどのような組み合わせであっても2つの命題の真理値が一致することを、2つの命題は 同値 （ equivalence ）であると言います。 例えば、命題 ¬( P ∧ Q ) と (¬ P )∨(¬ Q ) は同値です。 つまり、「 P も Q も、ではない」と「 P でないか、 Q でないか」は同じ意味であるということです。
2つの命題が同値かどうかは、真理値表で確かめられます。 真理値表 （ truth-table ）とは、原子命題の真理値のすべての組み合わせの演算をまとめた表のことです。
例題1. 命題 ¬( P ∧ Q ) と (¬ P )∨(¬ Q ) が同値であることを、真理値表を作成して証明してください。
解答例1.
| P | Q | P∧Q | ¬(P∧Q) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
| P | Q | ¬P | ¬Q | (¬P)∨(¬Q) |
|---|---|---|---|---|
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
例題2. 命題 ( P ∧ Q )∨ R と ( P ∨ R )∧( Q ∨ R ) が同値であることを、真理値表を作成して証明してください。
解答例2.
| P | Q | R | P∧Q | (P∧Q)∨R) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | F | T |
| T | F | F | F | F |
| F | T | T | F | T |
| F | T | F | F | F |
| F | F | T | F | T |
| F | F | F | F | F |
| P | Q | R | P∨R | Q∨R | (P∨R)∧(Q∨R) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | T | F | T | T | T |
| T | F | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | T | T | T |
| F | T | F | F | T | F |
| F | F | T | T | T | T |
| F | F | F | F | F | F |
論理型 （ logical type ）
| 真理値と演算子 | 一般的な記号 | Javaプログラム |
|---|---|---|
| 真 | T | true |
| 偽 | F | false |
| 論理積 | ∧ | && |
| 論理和 | ∨ | || |
| 否定 | ¬ | ! |
/* 1*/ class Ex3 { /* 2*/ public static void main (String[] args) { /* 3*/ boolean x = (5 < 6); /* 4*/ System.out.println(x); /* 5*/ } /* 6*/ }
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l% java Ex3 true b04a001@AsiaA1:~/comp2l%
...
/* 3*/ boolean x = (8 < 7);
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l% java Ex3 false b04a001@AsiaA1:~/comp2l%
...
/* 3*/ boolean x = true;
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l%
... 00000150: 000a 043c b200 021b b600 03b1 0000 0001 ...<............ ...
...
/* 3*/ boolean x = false;
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l%
... 00000150: 000a 033c b200 021b b600 03b1 0000 0001 ...<............ ...
...
/* 3*/ int x = 1;
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l%
... 00000150: 000a 043c b200 021b b600 03b1 0000 0001 ...<............ ...
...
/* 3*/ int x = 0;
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l%
... 00000150: 000a 033c b200 021b b600 03b1 0000 0001 ...<............ ...
ビット列 （ bit sequence ）
| 真理値と演算子 | 一般的な記号 | Javaプログラム |
|---|---|---|
| 真 | T | 1 |
| 偽 | F | 0 |
| 論理積 | ∧ | & |
| 論理和 | ∨ | | |
| 否定 | ¬ | ~ |
| 10進数 | 2進数 | 16進数 |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 2 |
| 3 | 0011 | 3 |
| 4 | 0100 | 4 |
| 5 | 0101 | 5 |
| 6 | 0110 | 6 |
| 7 | 0111 | 7 |
| 8 | 1000 | 8 |
| 9 | 1001 | 9 |
| 10 | 1010 | A |
| 11 | 1011 | B |
| 12 | 1100 | C |
| 13 | 1101 | D |
| 14 | 1110 | E |
| 15 | 1111 | F |
例題3. ビット列の演算 10 & 3 の値を求めてください。 始めに手計算で値を求め、次にプログラムEx3.javaを変更してjavacコマンドとjavaコマンドを実行し、出力を確認します。
解答例3.
0000 1010 & 0000 0011 ----------- 0000 0010
したがって、10 & 3 の値は 2 です。
...
/* 3*/ int x = 10 & 3;
...
b04a001@AsiaA1:~/comp2l% javac Ex3.java b04a001@AsiaA1:~/comp2l% java Ex3 2 b04a001@AsiaA1:~/comp2l%
問1. 命題 ¬( P ∨ Q ) と (¬ P )∧(¬ Q ) が同値であることを、真理値表を作成して証明してください。
問2. 命題 ( P ∨ Q )∧ R と ( P ∧ R )∨( Q ∧ R ) が同値であることを、真理値表を作成して証明してください。
問3. ビット列の演算 10 | 3 の値を求めてください。 始めに手計算で値を求め、次にプログラムEx3.javaを変更してjavacコマンドとjavaコマンドを実行し、出力を確認します。
今日の演習3の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（10月8日）を明記してください。