群理論と合同算術 (合計 31 点)

n が素数である場合、集合 {1,..., n-1} とモジュロ n の掛け算で群が成立する。
If n is a prime number, the set {1,..., n-1} and multiplication modulo n form a group.

n=7 の場合のケイリー表を書きなさい / Write the Cayley table for n=7 (12 点)

任意の素数の n において、上記の場合に下記の群の性質や公理が満たされていることを証明しなさい。
Prove that the following properties/axioms for groups hold for the case above for arbitrary primes n.

閉性 / closure (5 点):
(演算の結果が集合からはみ出さないこと / the result of an operation stays in the set)

モジュロ n の演算の結果は定義上 {0,... n-1} に入る。0 にならないことを証明すればよい。
掛け算の結果が n の倍数になれば、モジュロ n は 0 になるが、n が素数のため、因数分解で n が含まれてないと n の倍数になりえない。

単位元の存在 / existence of a neutral element (3 点):

単位元は必ず 1 である。モジュロ n でも 1*a=a*1=a であるから。

結合率 / associativity (5 点):

(((a*b) mod n) * c) mod n [モジュロ演算の性質]
= ((a*b) * c) mod n [整数の掛け算の結合率]
= (a * (b*c)) mod n [モジュロ演算の性質]
= (a * ((b*c) mod n)) mod n

逆元の存在 / existence of an inverse element (6 点):
(ヒント： 全ての行や列に単位元が出現することに注目
Hint: Observe that the neutral element appears in each row and column)

元 b の逆元は b' と書く。b*b' = 1 (単位元) = b'*b で定義される。 よって、b の逆元は b の列に 1 を探し、その行頭の数が b' にあたる (行と列を交換した場合も同様)。
モジュロ演算をよく円で説明する。例えば「モジュロ12」はよく時計の文字盤で説明される。 上記の Cayley 表でも確認できるように、各列 (行) で n 当分の文字盤で 360/n * b 度の角度で 次々と進み、n が素数のため同じ値に二度と当たらないので、必ず 1 が現れる。

真理表 / Truth Table (12 点)

下記の真理表に論理式 XOR(A ∧ ¬B, C→A) の計算の途中経過と結果を記入しなさい。
In the truth table below, enter the intermediate and final results for the calculation of the Boolean formula XOR(A ∧ ¬B, C→A) (12 点)

基数変換 / Base Conversion (10 点)

下記の表の基数変換を行いなさい。 / Carry out the base conversions in the table below.

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

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

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

集合 A = {3, 4, 5, 6, 7, 8, 9} 内の関係 R は、 b が a を (余りなしで) 割れる、又は b-a が 4 以上である (a, b) の順序対で定義されている。五つの表現形式で書きなさい。
The relation R on set A = {3, 4, 5, 6, 7, 8, 9} is defined as the set of ordered pairs (a, b) where b divides a (without remainder) or b-a is 4 or greater. Write the five different representations of this relation.

順序対の集合 / set of ordered pairs (内包的記法 / connotation) (4 点): { (a, b) | a∊A ∧ b∊A ∧
(a mod b = 0 ∨ b - a ≧ 4) }

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

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

 [大きい丸括弧省略]

  a | b     a | b
  -----     -----
  3 | 3     8 | 8
  6 | 3     9 | 9
  9 | 3     3 | 7
  4 | 4     3 | 8
  8 | 4     3 | 9
  5 | 5     4 | 8
  6 | 6     4 | 9
  7 | 7     5 | 9

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

@@@@
@@@@

論理関数の標準形 / Normal Forms of Boolean Functions (合計 12 点)

次の論理式の標準形の名称を記述の上、もう一つの標準形に変換しなさい。
Give the name of each of the normal forms below and convert it to the other normal form.

D∧E ∨ ¬D∧¬E (3 点)

名称 / name: 加法標準形 [又は選言標準形]

もう一つの標準形 / other normal form: (D∨¬E) ∧ (¬D∨E)

(G∨¬H∨K) ∧ (G∨¬H∨¬K) ∧ (¬G∨¬H∨¬K) (6 点)

名称 / name: 乗法標準形 [又は連言標準形]

もう一つの標準形 / other normal form (*): ¬G∧¬H∧¬K ∨ ¬G∧¬H∧K ∨ G∧¬H∧¬K ∨ G∧¬H∧K ∨ G∧H∧¬K

(*) の標準形を単純化しなさい / Simplify the normal form marked with (*) (3 点)

¬H ∨ G∧H∧¬K

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

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。単にカタカナ表記にするのは避けること。
For the following English terms from Discrete Mathematics, write their Japanese equivalent and a short explanation. Do not just use Katakana.

free variable

自由変数; 量記号で束縛されてない変数

transitive closure

推移的閉包; ある二項関係を変わらないまで自分と繰り返し合成した結果

equivalence relation

同値関係; 反射的かつ対称的かつ推移的な関係

duality principle

相対原理; 論理演算において恒心の式で T と F、又はとかつを入れ換えられる原理

half adder

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

absorption law

吸収律; A ∧ (A∨B) = A など

proof by contradiction

背理法; 矛盾を使った証明の方法

inverse relation

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

digital root

数字根; ある数の各桁の和を、一ケタになるまで取り続けた結果

Peano Axioms

ペアノの公理; Guiseppe Peano が提案した算数を根本的な概念から作り上げる原理

Karnaugh map

カルノー図; 論理関数を単純化するための図

exclusive or

排他的論理和; 片方だけの被演算子が真の場合のみ結果が真になる論理演算

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

各ブール代数に「基本元」と言われる元がある。ある集合のベキ集合から作られるブール代数の場合、基本元は大きさ 1 の部分集合である。 ビット列とビット毎演算からブール代数を作る場合、基本元は、一つのビットだけが 1 となっているビット列である。
In each Boolean Algebra, there are some elements called basic elements. In a Boolean Algebra created from a powerset of a set, the basic elements are the subsets of size 1. In a Boolean Algebra created from bit strings and using bitwise operations, the basic elements are the bit strings where exactly one bit is 1.

大きさ 8 のブール代数の場合、基本元の数を書きなさい。 (2 点)
Write the number of basic elements in a Boolean algebra of size 8: 3

大きさ 2048 のブール代数の場合、基本元の数を書きなさい。 (2 点)
Write the number of basic elements in a Boolean algebra of size 2048: 11

ハッセ図において、零元と基本元の位置関係を説明しなさい。 (4 点)
In a Hasse diagram, describe the relative positions of the zero element and the basic elements:

ハッセ図では零元が一番下で、その直接上の層に基本元がある。零元は基本元のみとつながっている。

以下の全ての小問ではブール代数の二項演算が最大公約数と最小公倍数である。
For all the subproblems below, the binary operations of the Boolean algebras are GCD and LCM.

零元 1 で、基本元が 3, 5, 7 の場合のハッセ図を書きなさい。 (7 点)
Draw the Hasse diagram for the case where the zero element is 1 and basic elements are 3, 5, and 7.

基本元 2, 3, 6 でブール代数が作成可能ですか。可能でない理由を説明しなさい。(5 点)
Can you create such a Boolean algebra using basic elements 2, 3, and 6? Explain why not.

長さ三のビット列を使って因子の有無を決め、ブール代数を作ろうとすると 1, 2, 3, 6, 6, 12, 18, 36 の数が得られるが、6 がダブっているのでブール代数になりません。

2 の倍数からブール代数の基本元となる最小の四つのものを選びなさい。(4 点)
Find the four smallest multiples of two that can be used as basic elements for a boolean algebra.

2, 4, 6, 10

2 の冪 (2 の累乗数) からブール代数の基本元となる最小の四つのものを選びなさい。(6 点)
Find the four smallest powers of two that can be used as basic elements for a boolean algebra.

2, 4, 16, 256

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

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

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

There is a real number that is not an integer.

∃x∈ℝ: x∉ℤ

The number of natural numbers is smaller than the number of real numbers.

|ℕ| < |ℝ| |ℕ| <= |ℝ|

Implication is transitive.

∀a,b,c∈{T, F}: a→b ∧ b→c ⇒ a→c

Addition is associative and commutative.

∀a,b,c: (a+b)+c = a+(b+c) ∧ a+b = b+a

Conjunction and disjunction distribute over each other.

∀a,b,c∈{T, F}: (a∧b ∨ c = (a∨c) ∧ (b∨c)) ∧ ((a∨b) ∧ c = a∧c ∨ b∧c)

Every student reads a book.

∀s∈S: ∃b∈B: read(s,b)

Every book is read by at least one student.

∀b∈B: ∃s∈S: read(s,b)

Every student reads all books.

∀s∈S: ∀b∈B: read(s,b)

There is a student who reads all books.

∃s∈S: ∀b∈B: read(s,b)

There are two students who are together exactly 100kg heavy.

∃s∈S: ∃t∈S: s≠t ∧ weight(s)+weight(t) = 100kg

No book is read by all students.

¬∃b∈B: ∀s∈S: read(s,b)

There is a student who reads more books than his/her weight in kilograms.

∃s∈S: |{b|read(s,b)}| > weight(s)

数学的帰納法による証明 / Proof by Mathematical Induction (15 点)

全ての n∈ℕ⁺ の場合、1/(1·3) + 1/(3·5) + 1/(5·7) + ... + 1/((2n-1)·(2n+1)) = n/(2n+1) であることを証明しなさい。
For all n∈ℕ⁺, prove that 1/(1·3) + 1/(3·5) + 1/(5·7) + ... + 1/((2n-1)·(2n+1)) = n/(2n+1).

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

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