青山学院大学

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

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

真理表 (合計 17 点)

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

A  B  C    A→C    | ¬(A→C)   | ¬(A→C)∧B   C∨¬(AC)∧B
F F F    T      |  F       | F       F
F F T    T      |  F       | F       T
F T F    T      |  F       | F       F
F T T    T      |  F       | F       T
T F F    F      |  T       | F       F
T F T    T      |  F       | F       T
T T F    F      |  T       | T       T
T T T    T      |  F       | F       T

C∨¬(AC)∧B の短い方の標準形とその名称を書きなさい。 (4 点)

(A∨B∨C) ∧ (A∨¬B∨C) ∧ (¬A∨B∨C); 乗法標準形 (連言標準形)

上記の標準形を出来るだけ短く書きなさい。 (3 点)

A∧B ∨ C

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

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

¬QZT NAND(NOR(A,B),XOR(A,B))

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

掛け算のチェック (10 点)

下記の表の二つの非演算子 (非演算子 1 と非演算子 2) の掛け算が間違っている結果 (結果 1 又は結果 2) の右側の枠に×を付けなさい。間違っている結果は行ごと一つ。基数欄は非演算子と結果の基数を示す。

番号 基数 非演算子 1 非演算子 2 結果 1 判定 1 結果 2 判定 2
9 12 8 106 X 107  
10 3856378942 9846593 37972193895644606   37972093895644606 X
16 A83F B7C9 78C92277   7DC92277 X
3 12012101 20110012 1021112120102212 X 1020112120102212  
7 543201 6425310 5224164050310   5234164050310 X
20 GH9 FG73 D5HEGF7 X D6HEGF7  

基数変換 (12 点)

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

番号 a の基数 a b の基数 b
2 10111100 16 BC
6 1014 10 226
2 10101010 10 170
5 3020121314 25 FA789
7 6363 10 2250
10 999 3 1101000
4 13311203101 8 7654321
20 BG 10 236
9 83 18 4C
3 12202122212012 9 5678765
16 CAFE 2 1100 1010 1111 1110
16 78B4FDFE 4 1320231033313332
2 1111 1010 1101 1110 0000 1111 1111 16 FADE0FF

関係の合成の推移的閉包 (6 点)

下記の行列 (大きな丸括弧省略) の推移的閉包を求め、求め方を説明しなさい。

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

上記の配列を自分と合成する (配列の掛算、ただし足し算の代わりは ∨) と上記のようになる。これをさらにもとの行列と合成しても変わらないので、推移的閉包に達している。

青山学院大学

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

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

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

inverse element
逆元; 群において、ある元 t の逆元は、t と演算して単位元になる
multi-valued logic
多値論理; 「真」と「偽」以外の値、例えば「分からない」、も使う論理
exponentiation
べき乗演算; xy の演算、x を y 回掛け合わせた結果
equivalence relation
同値関係; 反射的かつ対称的かつ推移的な関係
propositional variable
命題変数; 命題を表す (代表する) 変数
axiomatization
公理化; ある分野の理論を小数の (できれば自明) な公理と証明だけで作り上げる
vertex
節 (又は頂点); グラフで線や矢印でモスばれている点見ないなところ
permutation
順列; ある集合から順番を考慮して重複なしに元を選ぶときにできるものやその数
bitwise and
ビットごとかつ; 二つのビット列の同じ位のビット同士での論理積
free variable
自由変数; ある式で量記号で束縛されてない変数
proper subset
真の部分集合; 元の集合以外の部分集合
inverse relation
逆関係; ある2項関係の2項組を全て逆にしたもの
Peano Axioms
ペアノの公理; Guiseppe Peano が提案した算数を根本的な概念から作り上げる原理
positional notation
位取り表現; 場所によって数字の重みが違う数値の表現の一つ
difference set
差集合; A - B の場合、A に属しているが B に属してない元の集合

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

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

AB ∧ T = F ∨ B

AB ∨ F = T ∧ B

F ∨ ¬Q = ¬T ∨ T

T ∧ ¬Q = ¬F ∧ F

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

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

@@@@
@@@@

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

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

関係の表現 (24 点)

C = {2, 3, 4, 5, 6, 7} 内の関係 R で、xRyxy で割った余りが 1、又は yx で割った余りが 2 の場合だけ真である。R を下記の五つの表現形式で書きなさい。

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

順序対の集合 (内包的記法): {(x,y) | x∊C ∧ y∊C ∧ (x mod y = 1 ∨ y mod x = 2)}

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

  [大きい丸括弧省略]
xy xy
3257
3562
4265
4372
4673
5276
54

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

青山学院大学

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

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

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

右のハッセ図のブール代数について、下の表を埋めなさい。(6 点)

番号/#項目/item回答/answer
0 1
1 105
105 / a
最大公   約数                 [@@@]
最小公倍数[###]
半順序 divisibility
105 35 21 15 7 5 3 1

[@@@] を定義しなさい。(2 点)

最大公約数は、引数を両方とも余りなく割れる最大の整数である。

[###] を定義しなさい。(2 点)

最小公倍数は、両方の引数の共通の最小の倍数である。

自然数 (正の整数) 一般において、以下の小問の法則について、それぞれ三つのことを書きなさい。①日本語の用語。②上記の [@@@] と [###] を使って、性質そのもの一つ ( の代わりに gcd, の代わりに lcm を、関数の形式で使うこと。) ③その性質が恒真であることが分かるような説明。(それぞれ 4 点)

例: commutative law: 交換率; gcd(a, b) = gcd(b, a); (説明: 都合により省略)

idempotent law: 冪等率; gcd(a, a) = a; a より大きい数では a を割れないが、a では a を割れるので、a は a を割れる最大の数、すなわち最大公倍数。

associative law: 結合率; lcm(lcm(a, b), c) = lcm(a, lcm(b, c)); 三つの自然数の最小公約数は、計算の順番に依存しないで同じ。

absorption law: 吸収率; gcd(a, lcm(a, b)) = a;
lcm(a,b) は a の倍数。a の倍数と a の最大公約数は a 以外ない。

distributive law: 分配率; gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)); 素因数分解で考えるとわかる。gcd は共通の素因数だけ (すなわち、かつ)、lcm はどちらかに含まれている素因数を全部 (すなわち、または) を使う。 素因数ごとに論理式に置き換えられるので、恒真である。

自然数の集合 ℕ+ は、上記の法則が恒真であるにもかかわらずなぜブール代数でないかを書きなさい。(4 点)

零元は 1 ですが、単位限 (太字の 1) は、ℕ+ に最大数がないので存在しない。そうすると ⫬ も定義できない。その二つがないと、ブール代数の条件を満たない。

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

ビット列の数の証明 / Proof of Number of Bitstrings (27 点)

一定の長さ n の、ある規則を満たすビット列とそれらの数 nob(n) を長さ n = 5 までに次のテーブルで示す。(nob は「number of bitstrings」の略。)

nビット列nob(n)
0"" (空のビット列)1
10, 12
200, 01, 103
3000, 001, 010, 100, 1015
40000, 0001, 0010, 0100, 0101, 1000, 1001, 1010 8
500000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101 13

規則を考え、書きなさい。ヒント: 1 のビットをよく見る。規則を満たさないビット列も考える。(3 点)

1 が連続ではない全てのビット列。

順番を上記の表の順番と同様にする場合、長さ6の規則を満たすビット列の最初の5個と最後の5個を書きなさい。(4 点)

最初の5個: 000000, 000001, 000010, 000100, 000101

最後の5個: 100100, 100101, 101000, 101001, 101010

規則を満たす長さ 6, 7, 8 それぞれのッビト列の場合の数を書きなさい (3 点):
nob(6) = 21       nob(7) = 34       nob(8) = 55

一般に長さ n の場合、規則に合うビット列の数を、n より小さい場合の数から計算できる式を書きなさい。その場合の n の有効範囲も書きなさい。(4 点)

式: nob(n) = nob(n-1) + nob(n-2)                          有効範囲: n >= 2

式の有効範囲以外の nob(n) の値を直接定義しなさい。(2 点) nob(0) = 1, nob(1) = 2

上記の式を数学的帰納法で証明しなさい。ヒント: 基底と仮定はそれぞれ二つ必要。式の変換は必要ない。ビット列の先頭を見るとよい。(10 点)

ステップ 1: 基底: 定義により、nob(0) = 1, nob(1) = 2、表で確認可能。
ステップ 2: 帰納: 証明したいこと: nob(k+1) = nob(k) + nob(k-1) (k>=1)
a. 仮定: nob(k) と nob(k-1) がそれぞれ長さ k、k-1 の、規則を満たすビット列の数。
b. 規則を満たす長さ k のビット列は規則を満たす k より小さい長さのビット列から作られる。
規則を満たす長さ k のビット列を二種類に分ける:
0 のビットからスタートするものと 1 のビットからスタートするもの。
0 のビットからスタートするものは、規則を満たす長さ k のビット列から、先頭に 0 を付けることで作成可能。その数は nob(k) である。 1 のビットからスタートするものは、その次のビットが 0 でないと規則に違反するため、必ず 10 からスタートする。 よって、1 からスタートするものは、規則を満たす長さ k-1 のビット列から、先頭に 10 を付けることで作成可能。その数は nob(k-1) である。 上記の二つの種類以外に規則を満たすビット列が存在しないので、合計は nob(k) + nob(k-1) である。Q.E.D.

nob に類似している授業で紹介された関数と nob(n) の関係を、関数の名称を含め書きなさい。(3 点)
nob(n) = fib(n+2); フィボナッチ関数

制限なしのビット列に対する、規則を満たすビット列の割合がちょうど 0.5 になる n を書きなさい。(1 点) n = 4

全小問の割合が 0.1 以下の最小の n を書きなさい。(2 点) n = 12

青山学院大学

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

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

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

下記の数、学生、ペットなどについての英文に相当する式を作成しなさい。授業で習った記号は全て使って構いません。学生の集合は S, ペットの集合は P、学生 s はペット p が好きということを like(s, p) で表す。それ以外、名前付きの述語、関係、関数を使わないこと。
Create the formulæ corresponding to the English sentences below about numbers, students, pets,... 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, and like(s, p) to express that student s likes pet p. Do not use any other named predicates, relations, or functions.

例 / Example: Five and seven is greater than seven and five: 5+7 > 7+5

All students like all pets. ∀s∈S: ∀p∈P: like(s,p)

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

There is a student who likes every pet. ∃s∈S: ∀p∈P: like(s,p)

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

There is a student who is liked by all pets.

There is a pet that likes no student. ∃p∈P: ¬∃s∈S: like(p,s)

No students likes all pets. ¬∃s∈S: ∀p∈P: like(p,s)

Some student dislikes all pets. ∃s∈S: ∀p∈P: ¬like(p,s)

Every student likes two pets.

∀s∈S: ∃p,q∈P: p≠q ∧ like(s,p) ∧ like(s,q)

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

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

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

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

If a pet is liked by a student, then all students like this pet.

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

Only some pets like all students.

(¬∀p∈P: ∀s∈S: like(p,s)) ∧ (∃p∈P: ∀s∈S: like(p,s))

For all rational numbers, the addition of two rational numbers is a natural number.

∀a, b∈ℚ: a+b∈ℕ