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

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。 / 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.

bound variable

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

Karnaugh map

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

total order

全順序 (全形順序); 全ての要素の間順序が決まっている関係

even number

偶数; 奇数の反対で、2で割れる整数

digital root

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

duality principle

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

binary operation

二項演算; 二つの被演算子を使う演算

proof about sets

集合についての証明; 二つの集合が同等であることによる証明

prime number

素数; 自分と1でしか割り切れない自然数

neutral element

単位元; ある演算において、他のどの元と演算してもその元が変わらないもの

Cartesian product (set)

直積 (集合); 複数の集合からすべての組み合わせを選んだ順序対や n字組の集合

transitive closure

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

absorption law

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

quadruple

四項組 (四字組); 順序が決まった四つの項目の組; 例: (a, b, c, d)

equivalence relation

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

ペアノの公理 (合計 12 点)

足算の公理も含めペアノの公理を四つ記述しなさい (8 点)。

• 1 は自然数
• a が自然数であれば s(a) は自然数 (s は successor, 後者)
• s(x) = 1 という x は存在しない
• a と b が自然数の場合、a + s(b) = s(a + b)

ペアノの公理の意義を説明しなさい (4 点)。

数学はできるだけ少ない前提からスタートし、できるだけ多くのことを証明するのが目的である。 幼稚園の園児でも分かるぐらいの数の数え方、足し算の法則 (結合率など) や自然数そのものを当たり前と思わず、 もっと基本的な公理から導くので、まさに数学の基礎である算数をもっとも数学らしくした。

基数変換 (12 点)

次の表の基数変換を行いなさい。

群と部分群 (24 点)

ある代数系の (真の) 部分代数系は、その代数系の集合の同代数系の条件を全て満たす (真の) 部分集合と定義されている。 ここで群の部分代数系である部分群について考える。

一般の群において、真でない部分群の数とその特徴について書きなさい。(3 点)

一般の群には真でない部分群は2つある。一つは元の群そのもの。もう一つは単位限だけからなる群。

真かどうか問わず、一つの部分群しかない群について説明しなさい。(2 点)

大きさ1の群 (単位限のみ) は自分自身しか (真でない) 部分群として持っていません。

論理関数 (36 点)

下記の表に論理式 ¬D∨(B→C)∧¬C の計算の途中経過と結果を記入しなさい。(12 点)

論理式 ¬D∨(B→C)∧¬C に相当する論理回路を書きなさい。(8 点)

上記の式を段階的に単純化し、それぞれの段階でどのような性質や法則を使ったかを書きなさい。(8 点)

標準形の特徴を四つ列挙しなさい。(8 点)

1. 作成は手間がかかるが、簡単
2. どのブール関数に対しても作成可能
3. 式が浅い (回路で実装すると早い)
4. 式が長くなる可能性がある (回路は場所を要する)

関係の表現 (24 点)

P = {2, 3, 5, 7, 11, 13} 内の関係 R で、xRy は x を y で割った余りが 1 以上 3 以下の場合だけ真である。R を下記の五つの表現形式で書きなさい。

順序対の集合 (内包的記法): {(x,y) | x∊P ∧ y∊P ∧ 1 ≦ (x mod y) ≦ 3}

順序対の集合 (外延的記法): {(2,3), (2,5), (2,7), (2,11), (2,13), (3,2), (3,5), (3,7), (3,11), (3,13), (5,2), (5,3), (7,2), (7,3), (7,5), (11,2), (11,3), (11,5), (13,2), (13,3), (13,5), (13,11)}

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

  [大きい丸括弧省略]

R の場合、授業で習った四つの関係の性質の内、三つについて、順序対の追加で性質が成り立つようになる場合、最低どの順序対を追加したら成り立つのか、 逆に順序対の追加で性質が成り立つことが不可能な場合、最低どの順序対を削除したら成り立つのかを、性質と追加・削除を明記して書きなさい。 (9 点)

(2,2), (3,3), (5,5), (7,7), (11,11), (13,13) の追加で R が反射的になる。
(5,7), (5,11), (5,13), (11,13) の追加で R が対称的になる。
(2,3), (2,5), (2,7), (2,11), (2,13), (3,5), (3,7), (3,11), (3,13) の削除で R が反対称的になる。

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

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。「英語」とだけ答えないこと。)
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.)

@@@@
@@@@

一回目の授業では参考書の購入 (又は借り出し) と熟読が強く進められました。熟読した参考書の詳細を書きなさい。参考書を読まなかった場合、その理由を書きなさい。

廣瀬健著、情報数学、
電子情報通信学会編、コロナ者

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

下記の数、学生、ペット、食料などについての英文に相当する式を作成しなさい。授業で習った記号は全て使って構いません。学生の集合は S、ペットの集合は P、食料の集合は F、学生 s はペット p が好きということを like(s, p)、学生 s が食料 f を所有するということを own(s, f) で表す。それ以外、名前付きの述語、関係、関数を使わないこと。
Create the formulæ corresponding to the English sentences below about numbers, students, pets, food,... You can use all the symbols that were introduced in this course. Use S for the set of students, P for the set of pets, F for the set of foods, like(s, p) to express that student s likes pet p, and own(s, f) to express that student s owns food f. Do not use any other named predicates, relations, or functions.

All students like all foods. ∀s∈S: ∀f∈F: like(s,f)

There is a pet who likes every food. ∃p∈P: ∀f∈F: like(p,f)

Every student likes a pet. ∀s∈S: ∃p∈P: like(s,p)

There is a food which is liked by all students. ∃f∈F: ∀s∈S: like(s,f)

There is a student who is disliked by all pets. ∃s∈S: ∀p∈P: ¬like(p,s)

All pets dislike a food. ∀p∈P: ∃f∈F: ¬like(p,f)

All foods are liked by a student and a pet. ∀f∈F: (∃s∈S: like(p,s)) ∧ (∃p∈P: like(p,s))

Every student owns a pet or a food. ∀s∈S: (∃p∈P: own(s,p)) ∨ (∃f∈F: own(s,f))

No food liked by a pet is liked by a student. ∀f∈F: (∃p∈P: like(p,f)) → ∀s∈S: ¬like(s,f)

If every pet dislikes a food, then every student likes a pet.

(∀p∈P: ∃f∈F: ¬like(p,f)) → (∀s∈S: ∃p∈P: like(s,p))

Every student likes two foods and a pet.

∀s∈S: ∃f,g∈F: ∃p∈P: f≠g ∧ like(s,f) ∧ like(s,g) ∧ like(s,p)

No two students like the same pet or the same foods.

∀s,t∈S: s≠t → (¬∃p∈P: like(s,p)∧like(t,p)) ∧ (¬∃f∈F: like(s,f)∧like(t,f))

Any student who owns a pet owns some food liked by this pet.

∀s∈S: ∀p∈P: own(s,p) → ∃f∈F: own(s,f) ∧ like(p,f)

If a student likes a pet, and this pet likes a food, then the student also likes this food.

∀s∈S: ∀p∈P: like(s,p) → (∀f∈F: like(p,f) → like(s,f))

The division of any natural number by any complex number produces a rational number.

∀a∈ℕ: ∀b∈ℂ: a/b∈ℚ

フィボナッチ関数の性質の証明 (30 点)

次のフィボナッチ関数の値を表に記入しなさい。(5 点)

フィボナッチ関数の値が引数とちょうど同じ数の集合を書きなさい。(4 点)

外延的記法: {0, 1, 5}                 内包的記法: {a | a∈ℕ, fib(n)=n}

フィボナッチ関数の値が引数の二乗になっている場合の値の集合を書きなさい。(4 点)

外延的記法: {0, 1, 144}             内包的記法: {a | a∈ℕ, ∃b∈ℕ: a = fib(b)=b²}

フィボナッチ関数の定義を書きなさい。(5 点)

fib(0) = 0; fib(1) = 1; ∀n>1: fib(n)=fib(n-1)+fib(n-2)

次のフィボナッチ関数の性質を式で表しなさい: 全ての n において、fib(0) から fib(n) までの総和は fib(n+2)-1 と等しい。(4 点)

∑_{i = 0} ⁿfib(i) = fib(n+2) - 1

上記の性質を数学的帰納法で証明しなさい (ヒント: 両側に fib(n+1) を足す; 12 点)

ステップ 1: 基底: n=0 の場合、左側は fib(0)=0 のみで、右側の fib(2)-1 = 1-1 と等しい。
ステップ 2: 帰納: 証明したいこと: n=k+1>0 において、性質が成立する、すなわち ∑^k+1_{i = 0} fib(i) = fib(k+3) - 1 であること。
a. 仮定: n=k において、∑^k_{i = 0} fib(i) = fib(k+2) - 1 が成立していること。
b. 仮定からスタートする: ∑^k_{i = 0} fib(i) = fib(k+2) - 1
両側に fib(k+1) を足す: ∑^k_{i = 0} fib(i) + fib(k+1) = fib(k+2) + fib(k+1) - 1
総和の性質 (左側) とフィボナッチ関数の定義 (右側) を利用して両側を単純化:
∑^k+1_{i = 0} fib(i) = fib(k+3) - 1
これはちょうど証明したい式と同じなので、Q.E.D.

木による式の構造の表現 (12 点)

次の式を木の形で書きなさい。

¬Q∨X∧W 3+7≧4*5 NOR(A, B, XOR(C,D))

   ∨                       ≧                          NOR
  / \                     / \                        / | \
 ¬   ∧                   +   *                      A  B  XOR
 |  / \                 / \ / \                          /   \
 Q  X W                 3 7 4 5                          C   D

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

部分問題 X.6 と X.7 (△ と ▽) の積ブール代数の回答では「最大」や「最小」がでた筈。冪集合ブール代数の X.6 と X.7 に書いた概念を、同じ「最大」や「最小」を使って説明し、その概念を表す「最大」や「最小」を含む熟語を作ってください。

X.6 (△) の概念。(3 点)

積集合は二つの非演算子の集合を両方含む最大の集合なので、熟語には最大共通集合がいい。

X.7 (▽) の概念。(3 点)

和集合は二つの非演算子の集合を含む最小の集合なので、熟語には最小包含集合がいい。

ブール代数のハッセ図で任意の二つの頂点 a と b に対し、▽ の演算の結果をどのように求めるかを説明しなさい。説明の中で「最大」や「最小」を使いなさい。(6 点)

a を含む a から下へ向く辺を全部下向きに再帰的に辿って、到達できる全て頂点に印を付ける。
同様に b から下へ行きながら辿り着ける全頂点に別の印を付ける。
両方の印が付いている一番高い位置にある (即ち、最大の) 頂点が ▽ 演算の結果です。

言語としての数学 (5 点)

授業では数学を言語と位置づけた。情報テクノロジーにとって大切な他の言語とも比べ、なぜ数学が言語といわれているのかを考え、説明しなさい。

言語は自分の物事についての考えを言える・記述できる、他人の考えを理解できるものと考えられる。 数学は他の情報テクノロジーにとって大切な日本語、英語、プログラミング言語と同様にそういう役割を果している。 場合によって、例えば日本語で言いにくいことは数学ではっきり表せることもある。