コンピュータIIL（情報科学入門）第12回

12.1 真理値

12.1.1 真理値とは

コンピュータの扱うデータの中では、数値に並んで真理値というものも重要です。

命題 （ proposition ）とは、真偽がはっきり定まる表現のことです。 例えば、「5は6より小さい」という表現は真の命題です。 また、「8は7より小さい」という表現は偽の命題です。

命題の持つ、この真と偽という値を、 真理値 （ truth-value ）または 論理値 （ logical value ）と呼びます。 真理値は、しばしば記号TとFで表されます。 また、ビットと対応させ、1と0で表されることもあります。

12.1.2 論理演算

数値は、100+200 のような四則演算ができます。 命題にも、「5は6より小さい、かつ、8は7より小さい」のような演算があります。

これ以上分解できない命題を 原子命題 （ atomic proposition ）と呼びます。 命題の演算を表す記号を、 論理演算子 （ logical operator ）または 論理結合子 （ logical connective ）と呼びます。 命題は、原子命題と論理演算子から構成されます。 論理演算子には、論理積（AND）、論理和（OR）、否定（NOT）などがあります。

論理積 （ conjunction ）は、「かつ」を意味する演算です。 つまり、両方が真のときに真となります。 英語の"and"に対応しますので、 AND とも表されます。 記号では∧と書きます。

論理和 （ disjunction ）は、「または」を意味する演算です。 つまり、少なくとも一方が真のときに真となります。 英語の"or"に対応しますので、 OR とも表されます。 記号では∨と書きます。

否定 （ negation ）は、「〜でない」を意味する演算です。 つまり、真ならば偽、偽ならば真となります。 英語の"not"に対応しますので、 NOT とも表されます。 記号では¬と書きます。

原子命題の真理値がどのような組み合わせであっても2つの命題の真理値が一致することを、2つの命題は 同値 （ equivalence ）であると言います。 例えば、命題 ¬( P ∧ Q ) と (¬ P )∨(¬ Q ) は同値です。 つまり、「 P も Q も、ではない」と「 P でないか、 Q でないか」は同じ意味であるということです。

2つの命題が同値かどうかは、真理値表で確かめられます。 真理値表 （ truth-table ）とは、原子命題の真理値のすべての組み合わせの演算をまとめた表のことです。

例題1. 命題 ¬( P ∧ Q ) と (¬ P )∨(¬ Q ) が同値であることを、真理値表を作成して証明してください。

解答例1.

例題2. 命題 ( P ∧ Q )∨ R と ( P ∨ R )∧( Q ∨ R ) が同値であることを、真理値表を作成して証明してください。

解答例2.

12.2 今後の予定

今後の予定は以下の通りです。

1月19日（金）

授業中に試験を行います。 今日の演習問題をよく見直しておいてください。

1月26日（金）

全員にレポートの提出状況をメールで知らせます。

1月31日（水）

レポートの最終締め切り日です。 これ以降提出されたレポートは採点しません。

12.3 成績評価について

この授業の成績は、レポートの提出と試験の得点で決まります。

S

レポートはすべて提出。 レポートの完成度が高い。 試験の得点は「優」相当。

A

レポートはすべて提出。 試験の得点は「優」相当。

B

レポートはおおむね提出。 試験の得点は「良」相当。

C

レポートは未提出が目立つ。 試験は「可」相当。

F

レポートは未提出が多い。 試験は「不可」相当。

成績に関して次のような事情のある人はメールで連絡してください。 できる限り対処します。

• 春から留学するので、書類作成上、合否だけでも早めに知りたい。
• 奨学金をもらっているので、SでないならFにしてほしい。

12.4 演習12

問1. CPUに関する説明として、最も適切なものを一つ選んでください。

A. CPUは、データを記憶する装置です。

B. CPUは、各種の制御や演算を行う装置です。

C. CPUは、データを入力する装置です。

D. CPUは、データを出力する装置です。

問2. 10進数の13を2進数に変換した結果として、最も適切なものを一つ選んでください。

A. 1101

B. 1011

C. 1001

D. 1111

問3. 2進数の足し算 110 + 11 の結果として、最も適切なものを一つ選んでください。

A. 1001

B. 101

C. 111

D. 1011

問4. 負数を2の補数で表現した場合、1バイトで表現できる数の範囲として、最も適切なものを一つ選んでください。

A. -128から127まで

B. -128から128まで

C. -127から127まで

D. -127から128まで

問5. スタックに関する説明として、最も適切なものを一つ選んでください。

A. スタックは、最初に格納したデータが最初に取り出せるので、後入れ先出しと呼ばれます。

B. スタックは、最初に格納したデータが最初に取り出せるので、先入れ先出しと呼ばれます。

C. スタックは、最後に格納したデータが最初に取り出せるので、後入れ先出しと呼ばれます。

D. スタックは、最後に格納したデータが最初に取り出せるので、先入れ先出しと呼ばれます。

問6. 機械語の命令に関する説明として、最も適切なものを一つ選んでください。

A. 前半は付加データを表すオペランド、後半は命令の種類を表すオペコードです。

B. 前半は付加データを表すオペコード、後半は命令の種類を表すオペランドです。

C. 前半は命令の種類を表すオペランド、後半は付加データを表すオペコードです。

D. 前半は命令の種類を表すオペコード、後半は付加データを表すオペランドです。

問7. Java仮想マシンで、数8を第1変数に格納する方法として、最も適切なものを一つ選んでください。

A. 数8をスタックにプッシュし、第1変数の値をスタックにプッシュします。

B. 数8をスタックにプッシュし、スタックからポップした値を第1変数に格納します。

C. 第1変数の値をスタックにプッシュし、数8をスタックにプッシュします。

D. スタックからポップした値を第1変数に格納し、数8をスタックにプッシュします。

問8. Java仮想マシンで、10 + 20 + 30 を計算する方法として、最も適切なものを一つ選んでください。

A. スタックに10と20をプッシュし、足し算を実行し、30をプッシュし、足し算を実行します。

B. スタックに10をプッシュし、足し算を実行し、20をプッシュし、足し算を実行し、30をプッシュし、足し算を実行します。

C. スタックに10をプッシュし、足し算を実行し、20と30をプッシュし、足し算を実行します。

D. スタックに10と20と30をプッシュし、足し算を実行します。

問9. コンパイラに関する説明として、最も適切なものを一つ選んでください。

A. コンパイラとは、高級言語で書かれたプログラムを機械語に変換するソフトウェアです。

B. コンパイラとは、アセンブリ言語で書かれたプログラムを機械語に変換するソフトウェアです。

C. コンパイラとは、機械語で書かれたプログラムを高級言語に変換するソフトウェアです。

D. コンパイラとは、機械語で書かれたプログラムをアセンブリ言語に変換するソフトウェアです。

問10. 逆ポーランド記法 x x * y y * + の意味として、最も適切なものを一つ選んでください。

A. x に x を掛けたものと、 y に y を掛けたものを足します。

B. x に y を掛けたものと、 y に x を掛けたものを足します。

C. x と y を足したものに、 x を掛けて y を掛けます。

D. x と x を足したものに、 y を掛けて y を掛けます。

問11. バッカス・ナウア記法に関する説明として、最も適切なものを一つ選んでください。

A. 文法的に正しい表現とは、書換え規則に従って、一回の書換えを行って得られるものです。

B. 文法的に正しい表現とは、書換え規則に従って、決められた回数の書換えを行って得られるものです。

C. 文法的に正しい表現とは、書換え規則に従って、決められた回数以下の書換えを行って得られるものです。

D. 文法的に正しい表現とは、書換え規則に従って、回数を決めずに書換えを行って得られるものです。

問12. 文字0と1を使った回文（右から読んでも左から読んでも同じ文字列）の構文規則として、最も適切なものを一つ選んでください。

A. <回文> ::= 0<回文>0 | 1<回文>1

B. <回文> ::= <回文>0<回文> | <回文>1<回文>

C. <回文> ::= <空列> | 0 | 1 | 0<回文>0 | 1<回文>1

D. <回文> ::= <空列> | 0 | 1 | <回文>0<回文> | <回文>1<回文>

問13. ASCII符号に関する説明として、最も適切なものを一つ選んでください。

A. 1文字を16ビットで符号化する固定長符号です。

B. 1文字を8ビットで符号化する固定長符号です。

C. 1文字を8ビットから16ビットで符号化する可変長符号です。

D. 1文字を8ビットから24ビットで符号化する可変長符号です。

問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. 計算量 O ( n ^ 2) の説明として、最も適切なものを一つ選んでください。

A. 問題のサイズが2倍、3倍、4倍となっても、計算時間は変わりません。

B. 問題のサイズが2倍、3倍、4倍となると、計算時間は2倍、3倍、4倍となります。

C. 問題のサイズが2倍、3倍、4倍となると、計算時間は4倍、9倍、16倍となります。

D. 問題のサイズが2倍、3倍、4倍となると、計算時間は8倍、27倍、64倍となります。

問20. 計算量に関する説明として、最も適切なものを一つ選んでください。

A. 問題のサイズが1増えると計算時間が1増える問題は、事実上、計算機では解けません。

B. 問題のサイズが1増えると計算時間が2倍になる問題は、事実上、計算機では解けません。

C. 問題のサイズが2倍になると計算時間が1増える問題は、事実上、計算機では解けません。

D. 問題のサイズが2倍になると計算時間が2倍になる問題は、事実上、計算機では解けません。

12.5 レポート課題

今日の演習12の答案をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（1月12日）を明記してください。

12.6 参考文献

• R. Sedgewick: Algorithms in C, Addison-Wesley, 1990. 野下浩平（他訳）『アルゴリズムC』近代科学社、1996.
• 長尾真（他編集）『岩波情報科学辞典』岩波書店、1990.
• The Java Language Specification, http://java.sun.com/docs/books/jls/
• The Java Virtual Machine Specification, http://java.sun.com/docs/books/vmspec/