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

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

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

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

ここで大きさ n の集合のベキ集合から作られるブール代数を「n 次元のブール代数」と呼ぶことにする。このようなブール代数のハッセ図は上記のように、頂点の層 (t₀,..., t_n) と辺の層 (s₁,..., s_n) に分けることが可能。それについて、下記の文書の空白を埋めなさい。 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 (t₀,..., t_n) and layers of edges (s₁,..., s_n). Please fill in the blanks in the text below. (9 点)

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

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

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

関係の表現 / 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.

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

@@@@
@@@@

数式の証明 (12 点)

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

真理表 / 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.

式の相対 / 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

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.

基数変換 / Base Conversion (13 点)

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

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

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)

標準形 / 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).