用語の説明 / Explain Terms (22 24 点)

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。 / For the following English terms from Discrete Mathematics, write their Japanese equivalent and a short explanation. For the Japanese terms, avoid Katakana as much as possible.

proposition

命題; 客観的に真か偽が判断できる文 (質問でもない)

duality principle

双対原理; 恒真式が T/F と ∧/∨ を入れ替えても恒真式が恒真のまま、の原理

half adder

半加算器; 二進数一ビットと一ビットを足し、合計と繰り上がりを出力する回路

inverse relation

逆関係; ある2項関係の2項組を全て逆にしたもの

proof by counterexample

判例による証明; 判例を示すことで、ある主張の一般性に反証する

tautology

恒真; 常に真の論理式

congruence class

合同類; (ある法に対し) 合同である数全てを含まれる集合

bound variable

束縛された変数; ある量記号の影響の下の変数

power set

ベキ集合; ある集合の全ての部分集合

bitwise xor

ビットごと排他的又は; 二つのビット列の同じ位のビット同士での排他的又は

transitive closure

推移的閉包; ある関係を結果が変わらなくなるまで自分と結合した結果

power set

ベキ集合、ある集合の全ての部分集合の集合、P(A) と書く

n 進法での計算 / Calculations in Base n (8 点)

次の表の計算を行いなさい。結果は右の被演算子と同じ基数を使って書きなさい。
Complete the calculations in the table below. For the result, use the same base as the right operand.

数式の証明 / Proof of a Mathematical Formula (28 点)

Fibonacci 関数 fib(n) について、次の式を証明しなさい / For the Fibonacci function fib(n), prove the following formula:

fib(n) = ∑_{i = 0} ^{⌊(n-1)/2⌋} _(n-1-i)C_i (formula 1)

この表に入っているような数値の配置が何と呼ばれるか書きなさい。
Please give the overall name for the arrangement of numbers in this table. (2 点)

パスカルの三角形

上記の表で、formula 1 で使われる fib(4) の項に ∆ で、 fib(5) の項に ∇ で、そして fib(6) の項に ◇ で印を付けなさい。/ In the table above, mark the terms of fib(4) in formula 1 with a ∆, the terms of fib(5) with a ∇, and the terms of
fib(6) with ◇. (3 点)

なぜ formula 1 が fib(0) の場合正しいのか説明しなさい。/ Explain why formula 1 is correct for fib(0). (3 点)

⌊(n-1)/2⌋ = -1. よって、総和の項目数がなくて、足し算の単位元が 0 のため、結果が 0 で正しい。

基底として、fib(1) と fib(2) の場合に formula 1 が正しいことを示しなさい。
For the base cases, show that formula 1 is true for fib(1) and fib(2). (4 点)

fib(1) の場合、総和の唯一の項が ₀C₀=1 で、fib(1)=1 とあっている。 fib(2) の場合、総和の唯一の項が ₁C₀=1 で、fib(2)=fib(1)+fib(0)=1 とあっている。

Give the two assumptions needed to prove fib(k+1) = ∑_{i = 0}^⌊k/2⌋ _(k-i)C_i の証明に必要な二つの仮定を書きなさい。 (4 点)

fib(k-1) = ∑_{i = 0} ^{⌊(k-2)/2⌋} _(k-2-i)C_i, fib(k) = ∑_{i = 0} ^{⌊(k-1)/2⌋} _(k-1-i)C_i

even(k) の場合、帰納のステップの証明をしなさい。/ Prove the induction step for the case even(k). (8 点)

@@@@
@@@@
@@@@
@@@@
@@@@
@@@@
@@@@

(odd(k) の場合の証明は春休み中で結構です。The proof for the case of odd(k) is left for the spring break.)

真理表 / Truth Table (31 点)

下記の真理表に右上の角の論理式の計算の途中経過と結果を記入しなさい。 / In the truth table below, enter the intermediate and final results for the calculation of the Boolean formula in the upper right corner. (10 点)

真理表の結を使って、A∨C∧(A→¬B) を単純化しなさい。
Using the result of the truth table, simplify A∨C∧(A→¬B). (2 点)

A ∨ C

A∨C∧(A→¬B) を式の変換を使って単純化しなさい。それぞれの段階でどの様な性質を使ったかを書きなさい。(14 点)
Simplify the formula A∨C∧(A→¬B) using formula manipulation. For each step, indicate what laws or properties you used.

A∨C∧(A→¬B) の短い方の標準形をその名称とともに書きなさい。
Give the shorter normal form of A∨C∧(A→¬B) including its name. (5 点)

標準形: (A∨B∨C) ∧ (A∨¬B∨C); 名称: 乗法標準形 (または連言標準形)

合同算術による剰余の計算 / Calculating Remainders using Modular Arithmetic (8 点)

次の剰余演算を途中経過も含め計算しなさい。/ Calculate the following remainders, including intermediate results

45⁶ mod 39

45⁶ ≡₃₉ 6⁶ = 36³ ≡₃₉ (-3)³ = -27 ≡₃₉ 12

3³⁸ mod 25

3³⁸ = 27¹²·9 ≡₂₅ 2¹²·9 = 32²·4·9 = 32²·36 ≡₂₅ 7²·11 = 49·11 = 539 ≡₂₅ 14

授業へのコメント / Comments about Course (6 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。「英語」とだけ答えないこと。)
What was most difficult to understand in this course? (There is no definite answer. Do not simply answer "English".)

@@@@
@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)
What topic in this course was most interesting for you? (There is no definite answer.)

@@@@
@@@@

関係の表現 / Representations of a Relation (28 点)

D は 36 の全ての約数の集合です。D を書きなさい。 / D is the set of all divisors of 36. Give D.
ヒント/Hint: |D | = 9 (2 点)

D = {1, 2, 3, 4, 6, 9, 12, 18, 36}

D 上の関係 R は、a が b で割り切れる順序対 (a, b) からなる。順序対を辞書式順序で並べた場合、 R の最初の10個の順序対を書きなさい。/ The relation R on D is comprised of all tuples (a, b) where a is divisible by b (without remainder). Write the first 10 tuples of R when putting the tuples are in lexical order. (4 点)

(1,1), (2,2), (2,1), (3,1), (3,3), (4,1), (4,2), (4,4), (6,1), (6,2)

|R | =    36 (2 点)

R を内包的記法で書きなさい。 / Give the connotation of R. (4 点)

R = { (a, b) | a∊D ∧ b∊D ∧ a mod b = 0}

   1 0 0 0 0 0 0 0 0
   1 1 0 0 0 0 0 0 0
   1 0 1 0 0 0 0 0 0
   1 1 0 1 0 0 0 0 0
   1 1 1 0 1 0 0 0 0
   1 0 1 0 0 1 0 0 0
   1 1 1 1 1 0 1 0 0
   1 1 1 0 1 1 0 1 0
   1 1 1 1 1 1 1 1 1

 [大きい丸括弧省略
big parentheses left out]

 a | b   a | b   a | b
 -----   -----   -----
 1 | 1   9 | 1  18 | 6
 2 | 1   9 | 3  18 | 9
 2 | 2   9 | 9  18 |18
 3 | 1  12 | 1  36 | 1
 3 | 3  12 | 2  36 | 2
 4 | 1  12 | 3  36 | 3
 4 | 2  12 | 4  36 | 4
 4 | 4  12 | 6  36 | 6
 6 | 1  12 |12  36 | 9
 6 | 2  18 | 1  36 |12
 6 | 3  18 | 2  36 |18
 6 | 6  18 | 3  36 |36

R の場合、授業で習った四つの関係の性質の有無を、「...である、...ではない」という形で書きなさい。
For R, for each of the four properties discussed in the course, write whether it holds or not. (4 点)
反射的である、対称的ではない、反対称的である、推移的である

ブール代数 / Boolean Algebra (合計 24 点)

    [図省略]
  

上記の二つの図の内、それぞれブール代数かどうかを判断し、判断の理由も書きなさい。/ For each of the above two diagrams, decide whether it is a Boolean algebra or not, and give the reasons for your decision. (4 点)

上記左のものはブール代数ではない。なぜかというと、有限のブール代数の大きさは 2ⁿ ですが、関係の下となる集合の大きさは 9 で 2の冪上とは異なる。上記右はブール代数である。なぜかというと、元の集合の大きさが 8 = 2³ で、構造は3次元の立方体である。

上記のブール代数について各情報を表に書き込みなさい。
For the Boolean algebra(s) above, complete the following table. (4 点)

一般の自然数 n において、そのすべての約数と「余りなしで割れる」関係でブール代数が作れる条件を、上記の 36 と 30 を例にして考えて説明しなさい。ヒント: 素因数分解。
Taking 36 and 30 used above as examples, explain the conditions that an arbitrary natural number n creates a Boolean algebra from all its divisors and the divisibility relation. Hint: prime factorization. (5 点)

36 の素因数分解は 2x2x3x3。30 の素因数分解は 2x3x5。ブール代数になるのは、同じ素数が高々一回しか使われてない 整数だけです。その場合、各素数はブール代数の立方体の一次元を確立する。同じ素数が一つでも複数回使われると、たとえば 1-2-4 みたいに、 連続して同じ方向になるので、ブール代数にならない。

上記の方法でブール代数が作れない 2 以上の最小の自然数を 5個書きなさい。/ Give the 5 smallest natural numbers greater than 2 that do not create a Boolean algebra with the method described above. (3 点)

4, 8, 9, 12, 16

述語論理の式の作成 / Creating Formulæ of Predicate Logic (24 点)

下記の数、学生、映画などについての英文に相当する式を作成しなさい。授業で習った記号は全て使って構いません。学生の集合は S, 映画の集合は M で、学生 s が映画 m を見るのことを watch(s, m) で表す。それ以外、名前付きの述語、関係、関数を使わないこと。
Create the formulæ corresponding to the English sentences below about numbers, students, movies,... You can use all the symbols that were introduced in this course. Use S for the set of students, M for the set of movies, and watch(s, m) to express that student s watches movie m. Do not use any other named predicates, relations, or functions.

例 / Example: All natural numbers are greater than -1: ∀n∈ℕ: n > -1

The size of the empty set is smaller than any positive integer.

∀i∈ℤ: i>0 → |{}|<i

There is a natural number that is not an rational number.

∃x∈ℕ: x∉ℚ

Substraction over real numbers are associative.

∀a,b,c∈ℝ: (a-b) - c = a - (b-c)

Addition and division of natural numbers is idempotent.

∀a∈ℕ: a+a = a ∧ a/a = a

All students watch all movies.

∀s∈S: ∀m∈M: watch(s,m)

Every student watches a movie.

∀s∈S: ∃m∈M: watch(s,m)

Not every movie is watched by a student.

¬∀m∈M: ∃s∈S: watch(s,m)

There is movie that is watched by all students.

∃m∈M: ∀s∈S: watch(s,m)

There is a student who doesn't watch any movie.

∃s∈S: ¬∃m∈M: watch(s,m)

No movie is watched by less than 5 students.

¬∃m∈M: |{s|s∈S ∧ watch(s,m)}| < 5

A student who watches at least 10 movies watches at least 50 movies.

∀s∈S: |{m|m∈M ∧ watch(s,m)}| ≥ 10 → |{m|m∈M ∧ watch(s,m)}| ≥ 50

No two students watch exactly the same set of movies.

∀s₁∈S, s₂∈S: s₁≠s₂ → {m|m∈M ∧ watch(s₁,m)}≠{m|m∈M ∧ watch(s₂,m)}

基数変換 / Base Conversion (10 点)

下記の基数変換の表を完成しなさい。 / Complete the base conversions in the table below.

論理回路の図 / Diagrams of Boolean Circuits (10 点)

次の論理式の回路の図を書きなさい。/ Draw the circuits diagrams for the following Boolean formulæ.

公理系の作成者 / The Creators of Axiomatic Systems (5点)

次の数学の分野で有名な公理系の作成者を指定した数、書きなさい。/ Give the given number of famous creators of axiom systems for the following Mathematical fields.

自然数 / natural numbers (1)

ペアノ

平面幾何学 / plane geometry (1)

ユークリッド

ブール論理とブール代数 / basic (Boolean) logic and Boolean algebra (3)

Huntington, Sheffer, Wolfram