コンピュータIIL（情報科学入門）第12回
コンピュータの扱うデータの中では、数値に並んで真理値というものも重要です。
命題
（
proposition
）とは、真偽がはっきり定まる表現のことです。
例えば、「5は6より小さい」という表現は真の命題です。
また、「8は7より小さい」という表現は偽の命題です。
命題の持つ、この真と偽という値を、
真理値
（
truth-value
）または
論理値
（
logical value
）と呼びます。
真理値は、しばしば記号TとFで表されます。
また、ビットと対応させ、1と0で表されることもあります。
表
12.1
真理値を表す記号
数値は、100+200 のような四則演算ができます。
命題にも、「5は6より小さい、かつ、8は7より小さい」のような演算があります。
これ以上分解できない命題を
原子命題
（
atomic proposition
）と呼びます。
命題の演算を表す記号を、
論理演算子
（
logical operator
）または
論理結合子
（
logical connective
）と呼びます。
命題は、原子命題と論理演算子から構成されます。
論理演算子には、論理積（AND）、論理和（OR）、否定（NOT）などがあります。
論理積
（
conjunction
）は、「かつ」を意味する演算です。
つまり、両方が真のときに真となります。
英語の"and"に対応しますので、
AND
とも表されます。
記号では∧と書きます。
表
12.2
論理積の演算規則
| 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
とも表されます。
記号では∨と書きます。
表
12.3
論理和の演算規則
| 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
とも表されます。
記号では¬と書きます。
表
12.4
否定の演算規則
| 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.
表
12.5
命題 ¬(
P
∧
Q
) の真理値表
| P |
Q |
P∧Q |
¬(P∧Q) |
| T |
T |
T |
F |
| T |
F |
F |
T |
| F |
T |
F |
T |
| F |
F |
F |
T |
表
12.6
命題 (¬
P
)∨(¬
Q
) の真理値表
| 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.
表
12.7
命題 (
P
∧
Q
)∨
R
の真理値表
| 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 |
表
12.8
命題 (
P
∨
R
)∧(
Q
∨
R
) の真理値表
| 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月20日（金）
-
授業中に試験を行います。
今日の演習問題をよく見直しておいてください。
- 1月27日（金）
-
全員にレポートの提出状況をメールで知らせます。
- 1月31日（火）
-
レポートの最終締め切り日です。
これ以降提出されたレポートは採点しません。
この授業の成績は、レポートの提出と試験の得点で決まります。
- S
-
レポートはすべて提出。
レポートの完成度が高い。
試験の得点は「優」相当。
- A
-
レポートはすべて提出。
試験の得点は「優」相当。
- B
-
レポートはおおむね提出。
試験の得点は「良」相当。
- C
-
レポートは未提出が目立つ。
試験は「可」相当。
- F
-
レポートは未提出が多い。
試験は「不可」相当。
成績に関して次のような事情のある人はメールで連絡してください。
できる限り対処します。
-
春から留学するので、書類作成上、合否だけでも早めに知りたい。
-
奨学金をもらっているので、SでないならFにしてほしい。
問1.
記憶装置の説明として、最も適切なものを以下から一つ選んでください。
-
A.
記憶装置として、メモリは補助記憶、ハードディスクは主記憶に分類されます。
-
B.
記憶装置として、メモリは主記憶、ハードディスクは補助記憶に分類されます。
-
C.
記憶装置として、メモリとハードディスクは補助記憶に分類されます。
-
D.
記憶装置として、メモリとハードディスクは主記憶に分類されます。
問2.
10進数の12は2進数でどう表現されるか、最も適切なものを以下から一つ選んでください。
-
A.
1001
-
B.
1000
-
C.
1100
-
D.
1010
問3.
2進数の足し算 101 + 111 の結果はどうなるか、最も適切なものを以下から一つ選んでください。
-
A.
1000
-
B.
1001
-
C.
1010
-
D.
1100
問4.
負の数を2の補数で表す場合、-1は1バイトの2進数でどう表現されるか、最も適切なものを以下から一つ選んでください。
-
A.
10000000
-
B.
10000001
-
C.
11111110
-
D.
11111111
問5.
機械語における命令の説明として、最も適切なものを以下から一つ選んでください。
-
A.
1バイト以上のオペランドの後に、0バイト以上のオペコードが続きます。
-
B.
1バイト以上のオペランドの後に、1バイト以上のオペコードが続きます。
-
C.
1バイト以上のオペコードの後に、0バイト以上のオペランドが続きます。
-
D.
1バイト以上のオペコードの後に、1バイト以上のオペランドが続きます。
問6.
スタックの説明として、最も適切なものを以下から一つ選んでください。
-
A.
スタックに1をプッシュし、次に2をプッシュしますと、スタックからポップした値は1で、次にポップした値は2です。
-
B.
スタックに1をプッシュし、次に2をプッシュしますと、スタックからポップした値は1で、次にポップした値は1です。
-
C.
スタックに1をプッシュし、次に2をプッシュしますと、スタックからポップした値は2で、次にポップした値は2です。
-
D.
スタックに1をプッシュし、次に2をプッシュしますと、スタックからポップした値は2で、次にポップした値は1です。
問7.
Java仮想マシンで、変数
x
の値を変数
y
に格納する方法として、最も適切なものを以下から一つ選んでください。
-
A.
スタックからポップした値を
x
に格納し、
y
の値をスタックにプッシュします。
-
B.
スタックからポップした値を
y
に格納し、
x
の値をスタックにプッシュします。
-
C.
x
の値をスタックにプッシュし、スタックからポップした値を
y
に格納します。
-
D.
y
の値をスタックにプッシュし、スタックからポップした値を
x
に格納します。
問8.
Java仮想マシンで、変数
x
,
y
について、
x
-
y
を計算する方法として、最も適切なものを以下から一つ選んでください。
-
A.
引き算の命令を実行し、
y
の値をスタックにプッシュし、
x
の値をスタックにプッシュします。
-
B.
引き算の命令を実行し、
x
の値をスタックにプッシュし、
y
の値をスタックにプッシュします。
-
C.
y
の値をスタックにプッシュし、
x
の値をスタックにプッシュし、引き算の命令を実行します。
-
D.
x
の値をスタックにプッシュし、
y
の値をスタックにプッシュし、引き算の命令を実行します。
問9.
プログラミング言語の説明として、最も適切なものを以下から一つ選んでください。
-
A.
高級言語を機械語に変換するのも、アセンブリ言語を機械語に変換するのも、アセンブラです。
-
B.
高級言語を機械語に変換するのも、アセンブリ言語を機械語に変換するのも、コンパイラです。
-
C.
高級言語を機械語に変換するのがアセンブラで、アセンブリ言語を機械語に変換するのがコンパイラです。
-
D.
高級言語を機械語に変換するのがコンパイラで、アセンブリ言語を機械語に変換するのがアセンブラです。
問10.
Java仮想マシンにおいて、逆ポーランド記法で
x
y
z
+ + と表される数式はどのような命令に変換されるか、最も適切なものを以下から一つ選んでください。
-
A.
順番に、変数
x
の値、変数
y
の値、変数
z
の値をスタックにプッシュし、足し算の命令を2回実行します。
-
B.
順番に、変数
z
の値、変数
y
の値、変数
x
の値をスタックにプッシュし、足し算の命令を2回実行します。
-
C.
足し算の命令を2回実行し、順番に、変数
x
の値、変数
y
の値、変数
z
の値をスタックにプッシュします。
-
D.
足し算の命令を2回実行し、順番に、変数
z
の値、変数
y
の値、変数
x
の値をスタックにプッシュします。
問11.
書き換えによる構文規則の説明として、最も適切なものを以下から一つ選んでください。
-
A.
表現は、ある書き換えで導出できれば文法的に正しいとされ、どのように書き換えても導出できなければ文法的に間違いとされます。
-
B.
表現は、ある書き換えで導出できれば文法的に間違いとされ、どのように書き換えても導出できなければ文法的に正しいとされます。
-
C.
表現は、どのように書き換えても導出できれば文法的に正しいとされ、ある書き換えで導出できなければ文法的に間違いとされます。
-
D.
表現は、どのように書き換えても導出できれば文法的に間違いとされ、ある書き換えで導出できなければ文法的に正しいとされます。
問12.
「2進数とは
0
か
1
を1つ以上並べたものである」という構文規則を、バッカス・ナウア記法で表したものとして、最も適切なものを以下から一つ選んでください。
-
A.
<2進数> ::=
0
|
1
| <2進数>
-
B.
<2進数> ::=
0
|
1
|
0
<2進数> |
1
<2進数>
-
C.
<2進数> ::= <空列> | <2進数>
-
D.
<2進数> ::= <空列> |
0
<2進数> |
1
<2進数>
問13.
アルファベットの大文字（26文字）を固定長符号で表すには何ビットが必要か、最も適切なものを以下から一つ選んでください。
-
A.
5ビット
-
B.
6ビット
-
C.
3ビット
-
D.
4ビット
問14.
ハフマン符号の説明として、最も適切なものを以下から一つ選んでください。
-
A.
連続する文字に短い符号を割り当てます。
-
B.
連続する文字を文字数と文字に置き換えます。
-
C.
よく現れる文字に短い符号を割り当てます。
-
D.
よく現れる文字を文字数と文字に置き換えます。
問15.
暗号の説明として、最も適切なものを以下から一つ選んでください。
-
A.
良い暗号とは、鍵ありで復号するのも、鍵なしで解読するのも、容易なものです。
-
B.
良い暗号とは、鍵ありで復号するのも、鍵なしで解読するのも、困難なものです。
-
C.
良い暗号とは、鍵ありで復号するのが容易で、鍵なしで解読するのが困難なものです。
-
D.
良い暗号とは、鍵ありで復号するのが困難で、鍵なしで解読するのが容易なものです。
問16.
公開鍵方式の説明として、最も適切なものを以下から一つ選んでください。
-
A.
平文を秘密鍵で暗号化し、暗号文を公開鍵で復号します。
-
B.
平文を秘密鍵で暗号化し、暗号文を秘密鍵で復号します。
-
C.
平文を公開鍵で暗号化し、暗号文を公開鍵で復号します。
-
D.
平文を公開鍵で暗号化し、暗号文を秘密鍵で復号します。
問17.
チューリング機械の説明として、最も適切なものを以下から一つ選んでください。
-
A.
テープ記号の種類、状態の種類、およびテープの長さは無限です。
-
B.
テープ記号の種類は有限で、状態の種類とテープの長さは無限です。
-
C.
テープ記号の種類と状態の種類は有限で、テープの長さは無限です。
-
D.
テープ記号の種類、状態の種類、およびテープの長さは有限です。
問18.
チャーチの定立の説明として、最も適切なものを以下から一つ選んでください。
-
A.
問題を解くチューリング機械が存在すれば、その問題を解くアルゴリズムは存在しません。
-
B.
問題を解くチューリング機械が存在すれば、その問題を解くアルゴリズムが存在します。
-
C.
問題を解くアルゴリズムが存在すれば、その問題を解くチューリング機械は存在しません。
-
D.
問題を解くアルゴリズムが存在すれば、その問題を解くチューリング機械が存在します。
問19.
計算量の説明として、最も適切なものを以下から一つ選んでください。
-
A.
サイズが同じ問題に対する計算時間の最小値を基準とするのが平均計算量です。
-
B.
サイズが同じ問題に対する計算時間の最大値を基準とするのが平均計算量です。
-
C.
サイズが同じ問題に対する計算時間の最小値を基準とするのが最悪計算量です。
-
D.
サイズが同じ問題に対する計算時間の最大値を基準とするのが最悪計算量です。
問20.
計算量
O
(2 ^
n
) の説明として、最も適切なものを以下から一つ選んでください。
-
A.
問題のサイズが大きくなると、計算時間がそれに比例して増大するので、事実上計算できません。
-
B.
問題のサイズが大きくなっても、計算時間は変わらないので、事実上計算できません。
-
C.
問題のサイズが大きくなると、計算時間が急激に増大するので、事実上計算できません。
-
D.
問題のサイズが大きくなると、計算時間がその2乗に比例して増大するので、事実上計算できません。
今日の演習12の答案をメールで提出してください。
メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。
メールの本文には、学生番号、氏名、科目名、授業日（1月13日）を明記してください。
2006年1月13日更新
小西 善二郎
konishi@twcu.ac.jp
Copyright (C) 2006 Zenjiro Konishi.
All rights reserved.