コンピュータの扱うデータの中では、数値に並んで真理値というものも重要です。
命題 ( 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 |
原子命題の真理値がどのような組み合わせであっても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 |
今後の予定は以下の通りです。
この授業の成績は、レポートの提出と試験の得点で決まります。
成績に関して次のような事情のある人はメールで連絡してください。 できる限り対処します。
問1. 記憶装置の説明として、最も適切なものを以下から一つ選んでください。
問2. 10進数の12は2進数でどう表現されるか、最も適切なものを以下から一つ選んでください。
問3. 2進数の足し算 101 + 111 の結果はどうなるか、最も適切なものを以下から一つ選んでください。
問4. 負の数を2の補数で表す場合、-1は1バイトの2進数でどう表現されるか、最も適切なものを以下から一つ選んでください。
問5. 機械語における命令の説明として、最も適切なものを以下から一つ選んでください。
問6. スタックの説明として、最も適切なものを以下から一つ選んでください。
問7. Java仮想マシンで、変数 x の値を変数 y に格納する方法として、最も適切なものを以下から一つ選んでください。
問8. Java仮想マシンで、変数 x , y について、 x - y を計算する方法として、最も適切なものを以下から一つ選んでください。
問9. プログラミング言語の説明として、最も適切なものを以下から一つ選んでください。
問10. Java仮想マシンにおいて、逆ポーランド記法で x y z + + と表される数式はどのような命令に変換されるか、最も適切なものを以下から一つ選んでください。
問11. 書き換えによる構文規則の説明として、最も適切なものを以下から一つ選んでください。
問12.
「2進数とは
0
か
1
を1つ以上並べたものである」という構文規則を、バッカス・ナウア記法で表したものとして、最も適切なものを以下から一つ選んでください。
0
|
1
| <2進数>
0
|
1
|
0
<2進数> |
1
<2進数>
0
<2進数> |
1
<2進数>
問13. アルファベットの大文字(26文字)を固定長符号で表すには何ビットが必要か、最も適切なものを以下から一つ選んでください。
問14. ハフマン符号の説明として、最も適切なものを以下から一つ選んでください。
問15. 暗号の説明として、最も適切なものを以下から一つ選んでください。
問16. 公開鍵方式の説明として、最も適切なものを以下から一つ選んでください。
問17. チューリング機械の説明として、最も適切なものを以下から一つ選んでください。
問18. チャーチの定立の説明として、最も適切なものを以下から一つ選んでください。
問19. 計算量の説明として、最も適切なものを以下から一つ選んでください。
問20. 計算量 O (2 ^ n ) の説明として、最も適切なものを以下から一つ選んでください。
今日の演習12の答案をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(1月13日)を明記してください。