青山学院大学

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

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

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

Abelian group
可換群; 交換律が成り立つ群
implication
含意; a ならば b (a→b) の演算、結果がaがTでbがFの場合のみF
inverse element
逆元; 群において、ある元 t の逆元は、t と演算して単位元になる
greatest common divisor
最大公約数; 複数の整数をすべて割り切れる最大の数
axiom
公理; ある数学分野の根本となるできるだけ明白な、証明ができない定理みたいなもの
free variable
自由変数; ある式で量記号で束縛されてない変数
octal
八進数(の); 数を 0-7 の八つの記号で表す位取り表現
bitwise xor
ビットごと排他的又は; 二つのビット列の同じ位のビット同士での排他的又は
proof by contradiction
背理法; 矛盾を使った証明の方法
Karnaugh map
カルノー図表; 論理関数を単純化するための図表
quintuple
五字組; 順番が決まった五つのもの、五つの集合の直積や関係の場合などに使う
difference set
差集合; A-B と書いて、結果が A に属するが B に属さない要素のみからなる

一般的の性質の書き方 / Writing Laws in General Form (12 点)

二つの架空の演算子「∆」と「∇」で次の性質で考えられる書き方を全て列挙しなさい / Using two immaginary operators ∆ and ∇, list all possible forms of the laws given below.

結合律 / Associative Law
(a∆b)∆c=a∆(b∆c), a∇b∇c=a∇b∇c
交換律 / Commutative Law
a∆b=b∆a, a∇b=b∇a
吸収律 / Absorption Law
a∆(a∇b)=a, a∇(a∆b)=a
べき等律 / Idempotent Law
a∆a=a, a∇a=a
分配律 / Distributive Law
a∆(b∇c)=(a∆b)∇(a∆c), (a∆b)∇c=(a∇c)∆(b∇c),
a∇(b∆c)=(a∇b)∆(a∇c), (a∇b)∆c=(a∆c)∇(b∆c)

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

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

{△, ○, □} のベキ集合から作成されるブール代数のハッセ図を完成しなさい (4 点)。
Complete the Hasse Diagram for a Boolean Algebra created from the powerset of {△, ○, □}.

t 3 s 3 t 2 s 2 t 1 s 1 t 0 {△, ○, □} {○, □} {△, □} {△, ○} {□} {○} {△} {}

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

番号/#項目/item回答/answer
B {{}, {△}, {○}, {□}, {△, ○}, {△, □}, {○, □}, {△, ○, □}}
零元/zero element {}
単位元/unit element {△, ○, □}
¬ 補集合
積集合
和集合
半順序 部分集合

ここで大きさ n の集合のベキ集合から作られるブール代数を「n 次元のブール代数」と呼ぶことにする。このようなブール代数のハッセ図は上記のように、頂点の層 (t0,..., tn) と辺の層 (s1,..., sn) に分けることが可能。それについて、下記の文書の空白を埋めなさい。 Let's call a Boolean Algebra created from the powerset of a set of size n a "Boolean Algebra of dimension n". The Hasse Diagram of such a Boolean Algebra can be separated into layers of vertices (t0,..., tn) and layers of edges (s1,..., sn). Please fill in the blanks in the text below. (9 点)

一般の場合、層 s1 の辺の数は n で、層 sn の辺の数は n である。4次元のブール代数の場合、t0 から tn までの各層の頂点の数は 1 , 4 , 6 , 4 , 1 となる。 一般に tm の層の頂点の数を nCm と表し、
n! / ( m! (n - m)! ) で直接計算が可能。3次元のブール代数の場合、tm の各頂点から上の方向に出る辺の数が 3 - m になり、これは n 次元に一般化すると n - m になる。よって、n次元の場合、 層 sk の辺の数が
(n - (k-1)) n! / ( (k-1)! (n - (k-1))! ) である。

n次元のブール代数のハッセ図の辺の数が n 2n-1 であることを証明または説明しなさい。 Prove or explain that the total number of edges of the Hasse Diagram of a Boolean Algebra of dimension n is n 2n-1 (4 点).

ブール代数の構造は n次元の立方体です。ハッセ図の辺はその立方体の辺の数と同じです。 n次元の立方体の辺の数は n 方向にそれぞれ 2 の n-1 乗 ((n-1)次元の立方体の頂点の数) 伸びます。

青山学院大学

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

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

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

集合 H = {1, 2, 3, 4, 5, 6, 7} 内の関係 R では、4 で割った余りが同じ数だけが関係にある。関係 R の五つの表現形式を書きなさい。
In the relation R on set H = {1, 2, 3, 4, 5, 6, 7}, only those numbers that have the same remainder when divided by 4 are related. Write the five representations of this relation.

グラフ / Graph (4 点) 行列 / Matrix (4 点) 表 / Table (4 点)
[図省略]
   1 0 0 0 1 0 0
   0 1 0 0 0 1 0
   0 0 1 0 0 0 1
   0 0 0 1 0 0 0
   1 0 0 0 1 0 0
   0 1 0 0 0 1 0
   0 0 1 0 0 0 1

 [大きい丸括弧省略
big parentheses left out]
  a | b     a | b
  -----     -----
  1 | 1     5 | 1
  1 | 5     5 | 5
  2 | 2     6 | 2
  2 | 6     6 | 6
  3 | 3     7 | 3
  3 | 7     7 | 7
  4 | 4

順序対の集合の外延的記法 / denotation of the set of ordered pairs (4 点):
{(1,1), (1,5), (2,2), (2,6), (3,3), (3,7), (4,4), (5,1), (5,5), (6,2), (6,6), (7,3), (7,7)}

合同関係の記号を使って、順序対の集合の内包的記法 / connotation of the set of ordered pairs, using the symbol for the congruence relation (4 点):
{ (a, b) | a∊H ∧ b∊H ∧ a ≡(mod 4) b }

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

授業へのコメント / 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.)

@@@@
@@@@

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

数式の証明 (12 点)

最初の n 個の正の整数の三乗の合計が 1/4 n2(n+1)2 であることを証明しなさい。
Prove that the sum of the cubes of the first n positive integers is 1/4 n2(n+1)2.
例えば / As an example: n=4 の場合、1 + 8 + 27 + 64 = 16·25/4.

数学的帰納法を使います。

  1. 基底: n=1: 最初の正の整数は1で、その三乗 (の合計) も 1 になる. 1·4/4 も 1 となるので、基底が成立。
  2. 帰納: 証明する必要なのは、最初の k+1 個の正の整数の三乗の合計が 1/4 (k+1)2(n+2)2
    1. 仮定: 最初の k 個の正の整数の三乗の合計は 1/4 k2(n+1)2
    2. 13 + 23 + ... + (k+1)3 = [前提導入]
      = (1/4 k2(k+1)2) + (k+1)3 =
      = 1/4 (k2(k+1)2 + 4(k+1)2(k+1)) =
      = 1/4 (k2+4k+4)(k+1)2 =
      = 1/4 (k+1)2(k+2)2 で証明完了。

真理表 / Truth Table (12 点)

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

B D G ¬B | ¬G | D→G | ¬G ∧ (D→G) ¬B∨¬G∧(DG)
F F F T  | T | T   | T  T
F F T T  | F | T   | F  T
F T F T  | T | F   | F  T
F T T T  | F | T   | F  T
T F F F  | T | T   | T  T
T F T F  | F | T   | F  F
T T F F  | T | F   | F  F
T T T F  | F | T   | F  F

式の相対 / Duals of Formulæ (4 点)

次の式が恒真である前提の下、その双対を書きなさい。/ Write the dual of the following formulæ, assuming they are tautologies.

¬A ∨ F = ¬A

¬A ∧ T = ¬A

T∧F = F∧T

F∨T = T∧F

青山学院大学

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

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

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

次の表の計算を行いなさい。結果は左の被演算子と同じ基数を使って書きなさい。
Complete the calculations in the table below. For the result, use the same base as the left operand.
(*) 他に指定が無い場合 / Applies where not otherwise indicated.

番号 基数 一つ目の被演算子 演算子 二つ目の被演算子 結果
Number Base (*) First Operand Operand Second Operand Result
例/Example 10 1234 + 6543 7777
  2 1110 1010 + 1111 0001 1 1101 1011
  7 54321 + 54321 141642
  16 ABCDEF + 86420 B4320F
  12 1001 * 123A 123B23A
  8 4321 * 7 36667
  2 10 1101 * 3210 101 1010 0000
  10 1357864 mod 9 7
  17 A7B359 mod 16 D
  10 1615 mod 27 10
  10 456 mod 39 12
  10 533 mod 127 111
  4 1230321 * 810 31213020

基数変換 / Base Conversion (13 点)

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

番号/# Base of a の基数 a Base of b の基数 b
2 1011 1100 16 BC
10 93 5 333
7 123 10 66
16 12A 10 298
3 212211110 9 25743
6 222 3 10012
25 AF89 5 20301314
2 1101111010101111 16 DEAF
8 7531 4 331121
32 CEG 8 30720
16 13AF 2 1001110101111
10 356 17 13G
10 200 9 242
6 234 4 1132

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

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

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

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

There is an integer that is not a natural number.

∃x∈ℤ: x∉ℕ

The size of the powerset of a set is the fifth power of the size of the set.

|P(A)| = |A|5

The number of natural numbers is the same as the number of rational numbers.

|ℕ| = |ℚ|

Addition and multiplication over integers is commutative.

∀a,b∈ℤ: (a+b = b+a) ∧ (ab=ba)

All students play all instruments.

∀s∈S: ∀g∈G: play(s,g)

Not all students play an instrument.

¬∀s∈S: ∃g∈G: play(s,g)

Every instrument is played by some student.

∀g∈G: ∃s∈S: play(s,g)

There is an instrument that is not played by all students.

∃g∈G: ¬∀s∈S: play(s,g)

There is an instrument that is not played by any student.

∃g∈G: ¬∃s∈S: play(s,g)

Every student plays some instrument.

∀s∈S: ∃g∈G: play(s,g)

No student plays more than two instruments.

∀s∈S: |{g|g∈G ∧ play(s,g)}| < 3

The maximum number of instruments played by a student
is smaller than the minimum number of students that play any instrument.

∃x∈ℝ: (∀s∈S: |{g|g∈G ∧ play(s,g)}|<x ∧ ∀g∈G: |{s|s∈S ∧ play(s,g)}|>x)

青山学院大学

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

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

標準形 / Normal Form (合計 10 点)

四つの変数 A, B, C, D の内、一つだけの変数が真のときのみ偽になる論理関数の短い方の標準形を書きなさい。/ For a Boolean function of four variables A, B, C, and D that is false only if exactly one of the variables is true, write the shorter normal form. (5 点)

(¬A∨B∨C∨D)∧(A∨¬B∨C∨D)∧(A∨B∨¬C∨D)∧(A∨B∨C∨¬D)

上記の標準形の名前 / Name of the above normal form: 乗法標準形 (または連言標準形)

もう一つの標準形の名前 / Name of the other normal form: 加法標準形 (または選言標準形)

もう一つの標準形で使われる「又は」の演算子の数 / Number of OR operators in the other normal form: 11

もう一つの標準形で使われる「かつ」の演算子の数 / Number of AND operators in the other normal form: 36

もう一つの標準形で使われる否定の演算子の数 / Number of negation operators in the other normal form: 20

論理回路の図 / Diagrams of Logical Circuits (15 点)

使える部品 (gates) だけを用いて、指定した入力 (inputs) から指定した出力 (output) を出す回路の図を書きなさい。
Using only the available gates (gates), write diagrams of circuits that produce the indicated output (output) given the indicated inputs (inputs).

番号      
Gates 全て / all NOR NOT, AND
Inputs G, H, K A, B Q, W
Output G ∨ H ∧ K A ∧ B Q → W
  [図省略] [図省略] [図省略]