青山学院大学

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

授業
科目
情報数学 I 学生番号 学科 学年 フリ
ガナ
  評点
                        氏名    
担当者 DÜRST, Martin J.

用語の説明 / 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.

番号 左の被演算子 演算子 右の被演算子 結果
Number Left Operand Operator Right Operand Result
例/Ex. 123410 + 654310 7777
  432145 + 312405 130004
  1010 11002 + 1010 01102 1 0101 0010
  ABACAF16 + 8421016 B3EEBF
  543219 * 89 477778
  200116 * 124816 2491248
  101 10012 * 1610 1424101 1001 0000
  1357864212 mod 1110 310
  4372759 mod 89 4

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

数式の証明 / 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)Ci (formula 1)

次の表を埋めなさい。/Fill in the table below (4 点):

aCb b = 0 b = 1 b = 2 b = 3 b = 4 b = 5 b = 6
a = 0 1            
a = 1 1 1          
a = 2 1 2 1        
a = 3 1 3 3 1      
a = 4 1 4 6 4 1    
a = 5 1 5 10 10 5 1  
a = 6 1 6 15 20 15 6 1

使用可能な定義とヒント / Usable Definitions and Hints

  1. Definition for ⌊x/2⌋ の定義:
    x∈ℕ: even(x)∧⌊x/2⌋=x/2 ∨ odd(x)∧⌊x/2⌋=(x-1)/2
    (⌊x⌋ は x の床関数である/⌊x⌋ is the floor function of x)
  2. Definition for fib(n) の定義:
    • fib(0) = 0
    • fib(1) = 1
    • n∈ℕ, n>1: fib(n) = fib(n-1) + fib(n-2)
  3. Definition for aCb の定義:
    a∈ℕ: aC0 = aCa = 1,
    a∈ℕ, b∈ℕ, 0≦ba: aCb = (a-1)C(b-1) + (a-1)Cb
  4. 証明には二つの基底と二つの仮定が必要です。/ For the proof, two base cases and two assumptions are need.

この表に入っているような数値の配置が何と呼ばれるか書きなさい。
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) の場合、総和の唯一の項が 0C0=1 で、fib(1)=1 とあっている。 fib(2) の場合、総和の唯一の項が 1C0=1 で、fib(2)=fib(1)+fib(0)=1 とあっている。

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

fib(k-1) = i = 0 ⌊(k-2)/2⌋ (k-2-i)Ci, fib(k) = i = 0 ⌊(k-1)/2⌋ (k-1-i)Ci

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.)

青山学院大学

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

授業
科目
情報数学 I 学生番号 学科 学年 フリ
ガナ
  評点
                        氏名    
担当者 DÜRST, Martin J.

真理表 / 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 B C ¬B | A → ¬B | C ∧ (A → ¬B) AC∧(A→¬B)
FFF T | T | F F
FFT T | T | T T
FTF F | T | F F
FTT F | T | T T
TFF T | T | F T
TFT T | T | T T
TTF F | F | F T
TTT F | F | F T

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

A ∨ C

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

単純化 使用した性質
AC∧(A→¬B) ----
含意の除去
A∨C∧(¬A∨¬B)
分配率
A∨(C∧¬A)∨C∧¬B
分配率
(A∨C)∧(A∨¬A)∨C∧¬B
排中律
(A∨C)∧T∨C∧¬B
真偽の性質
(A∨C)∨C∧¬B
結合律
A∨(C∨C∧¬B)
吸収律
A∨C
----

AC∧(A→¬B) の短い方の標準形をその名称とともに書きなさい。
Give the shorter normal form of AC∧(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

456 mod 39
45639 66 = 36339 (-3)3 = -27 ≡39 12
338 mod 25
338 = 2712·9 ≡25 212·9 = 322·4·9 = 322·36 ≡25 72·11 = 49·11 = 539 ≡25 14

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

授業へのコメント / 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 は、ab で割り切れる順序対 (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∊H ∧ b∊H ∧ a mod b = 0}

R の行列 / Matrix of R (4 点) R の表 / Table of R (4 点) R のグラフ / Graph of R (4 点)
   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 点)
反射的である、対称的ではない、反対称的である、推移的である

青山学院大学

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

授業
科目
情報数学 I 学生番号 学科 学年 フリ
ガナ
  評点
                        氏名    
担当者 DÜRST, Martin J.

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

一つ前の問の関係 R のハッセ図を書きなさい。
Give the Hasse diagram of the relation R in the previous problem. (4 点)

    [図省略]
  

30 の全ての約数の集合で一つ前の問と同様に関係を作ったときのハッセ図を書きなさい。/ Give the Hasse diagram of all the divisors of 30 when creating a relation in the same way as in the previous problem. (4 点)

30 15 10 6 5 3 2 1

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

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

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

番号/#項目/item回答/answer
零元/zero element 1
最大公約数
最小公倍数
半順序 divisibility

一般の自然数 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

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

述語論理の式の作成 / 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.

∀s1∈S, s2∈S: s1≠s2 → {m|m∈M ∧ watch(s1,m)}≠{m|m∈M ∧ watch(s2,m)}

青山学院大学

後期試験 ・ 2019 年 1 月 25 日 2 時限実施 ・ ページ

授業
科目
情報数学 I 学生番号 学科 学年 フリ
ガナ
  評点
                        氏名    
担当者 DÜRST, Martin J.

基数変換 / Base Conversion (10 点)

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

番号/# Base of a の基数 a Base of b の基数 b
2 1011 1100 16 BC
10 200 9 242
2 100101111 10 303
3 1010202 10 830
25 GHA6C 5 3132201122
16 C0DE 2 1100 0000 1101 1110
2 10110 1010 1100 1100 8 265 314
7 465 14 135
4 332230001103 8 76540123
9 78134 3 2122011011
17 AG 10 186

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

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

NOR(NAND(H, G), K) Z ∨ ¬Y ∧ X

公理系の作成者 / 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