青山学院大学

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

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

関係の性質 (16 点)

下記の表に列挙されている関係の種類について、a) から h) が必ず真になる場合は「○」、そうでない場合は「×」を記入して、表を完成しなさい。

  1. (x, y) ∈ R ⇒ (y, x) ∈ R
  2. 行列表現で対角線は全て F。
  3. ハッセ図で表現可能である。
  4. 行列表現で対角線は全て T。
  5. xRy かつ yRx ならば x=y である。
  6. 自分と合成しても変わらない。
  7. 行列表現で対角線で反射したら対角線以外のところの F と T が全て入れ替わる。
  8. 例として (正数上などの)「≤」がある。
a) b) c) d) e) f) g) h)
全順序 ×
対称的関係 × × × × × × × ×
非対称的関係 × × × × × × ×
同値関係 × × × × ×
推移的関係 × × × × × ×
反射的関係 × × × × ×
(半)順序 × ×
反対称的関係 × × × × × ×

真理表 (12 点)

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

A B C ¬A | ¬C | B→C | ¬C∧(B→C) ¬A∨¬C∧(BC)
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

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

論理回路の図 (15 点)

使える部品だけを用いて、指定した入力から指定した出力を出す回路の図を書きなさい。

使える部品: 全て
入力: A, B, C
出力: A ∨ C ∧ B
使える部品: NOT と AND
入力: A, B
出力: A → B
使える部品: NOR
入力: A, B
出力: A ∧ B

論理式の作成 (16 点)

ある大学のある学科の学生の集合 S とこの学科で教えられている科目の集合 L で、学生 s が科目 l が好きということを like(s, l) で表す場合、下記の英文を論理式に変換しなさい。(dislike(s, l) は解答中に使わないこと。)

例: All students like all lectures.

∀s∈S: ∀l∈L: like(s, l)

Every student has a lecture that (s)he likes.

∀s∈S: ∃l∈L: like(s, l)

Every student has a lecture that (s)he dislikes.

∀s∈S: ∃l∈L: ¬like(s, l)

There is a student who likes all lectures.

∃s∈S: ∀l∈L: like(s, l)

All lectures have at least one student who likes them.

∀l∈L: ∃s∈S: like(s, l)

Not every lecture is disliked by some student(s).

¬∀l∈L: ∃s∈S: ¬like(s, l)

Every lecture has at least two students who like it.

∀l∈L: ∃s∈S: ∃t∈S: (like(s, l) ∧ like(t, l) ∧ s≠t)

If a student likes one lecture, then (s)he likes all lectures.

∀s∈S: ((∃l∈L: likes(s, l)) → ∀l∈L: likes(s, l))

There is a student who dislikes exactly one lecture.

∃s∈S: ∃l∈L: (¬like(s, l) ∧ (∀m∈L: m=l ∨ like(s, m)))

青山学院大学

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

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

用語の説明 (24 点)

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。単にカタカナ表記にするのは避けること。

proof by counterexample
反例による証明; 反例を使って何かの仮定が成り立たないことの証明
powerset
ベキ集合; ある集合の元の全ての組み合わせの集合
free variable
自由変数; ある式で量記号で束縛されてない変数
hexadecimal
十六進数; 2進数の短縮形、1バイトを2桁で表現できる
vertex
節 (又は頂点); グラフで線や矢印でモスばれている点見ないなところ
bitwise or
ビット毎論理和; 二つのビット列でビットごとに論理和をとる演算
absorption law
吸収律; A ∧ (A∨B) = A など
neutral element
単位元; ある演算において、他のどの元と演算してもその元が変わらないもの
proposition
命題; 客観的に真か偽が判断できる文 (質問でもない)
deduction
演繹; 一般の原理から特定な場合を推論
Cartesian product (set)
直積 (集合); 複数の集合からすべての組み合わせを選んだ順序対や n字組の集合
duality principle
双対原理; 恒真式が T/F と ∧/∨ を入れ替えても恒真式が恒真のまま、の原理

基数変換 (8 点)

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

番号 a の基数 a b の基数 b
2 1011 1100 16 BC
6 234 10 94
10 185 13 113
2 1100 0000 1101 1010 16 CODA
27 AGHI 3 101 121 122 200
16 E53BC 4 32 1103 2330
5 1432 15 112
8 3675 2 111 1011 1101
16 CB79 8 145571

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

同値の性質 (16 点)

次の性質 P(n) を全ての n≥1 の場合に証明しなさい。
P(n): n 個の論理変数 Xi (1≤in) に対して、 X1X2 ↔ ... ↔ Xn = YXi の内に F の変数の数が偶数の場合に Y=T、 F の変数の数が奇数の場合に Y=F である。

n≥1 について、数学的帰納法で証明する。

基底の場合、n=1。F が奇数個ある場合、X1 = F = F で、偶数個あれば X1 = T = T で成立。

帰納の仮定: 1≤m≤k で P(m) が成立。

帰納で証明すべき: P(k+1)。表を使って証明する。k+1 項の式を任意に左側と右側 (それぞれの長さ m が 1≤m≤k) に分割する。右側も左側も二つの場合 (式の F の数が奇数で結果が F; 式の F の数が偶数で結果が T; 計四つの場合) を考慮。欄 (6) (右側↔左側の結果) と欄 (7) (欄 (3) で計算した F の合計の奇数・偶数から推測される結果) がどの場合でも一致するので、証明が完成。

(1) (2) (3) (4) (5) (6) (7)
左側の F の数) 右側の F の数 合計の F の数 ((1) と (2) から算術による) 左側の結果 (仮定による) 右側の結果 (仮定による) 全体の結果 ((4)↔(5)) 全体の結果 (3 から)
奇数 奇数 偶数 F F T T
奇数 偶数 奇数 F T F F
偶数 奇数 奇数 T F F F
偶数 偶数 偶数 T T T T

関係の表現 (20 点)

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

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

順序対の集合 (外延的記法): {(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)}

表 (4 点) 行列 (4 点) グラフ (4 点)
xy xy
3257
3562
4265
4372
4673
5276
54  
    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

  [大きい丸括弧省略]
[図省略]

青山学院大学

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

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

標準形 (16 点)

三つの論理変数 A, B, C のうち、ちょうど偶数個の変数が F の場合に結果が T になる論理関数の標準形をそれぞれ名称とともに書きなさい。 (10 点)

名称: 加法標準形     式: (A∧¬B∧¬C)∨(¬A∧B∧¬C)∨(¬A∧¬B∧C)∨(A∧B∧C)

名称: 乗法標準形     式: (¬A∨¬B∨¬C)∧(¬A∨B∨C)∧(A∨¬B∨C)∧(A∨B∨¬C)

この場合、標準形の単純化が不可能である理由を説明しなさい。(6 点)

カーノー図表を作りますと、T と F がチェスボードの白黒模様のようになって、縦や横に二つの升でもまとまらない。
式で単純化しようとすると、ひとつの変数以外否定の有無が一致する二つの項目を見つけないといけないが、見つかりません。

n 進法での計算 (10 点)

次の表の計算を行いなさい。結果は被演算子と同じ基数を使って書きなさい。

番号 計算の基数 第一被演算子 演算子 第二被演算子 計算結果
7 342 321 + 343 335 1 015 656
9 73 142 + 412 315 485 457
6 12 345 + 53 142 105 531
2 101 1010 1001 + 110 1011 0101 1100 0101 1110
11 101 * 123 12423
8 12 * 321 4052
10 209 848 367 mod 9 2
16 A B3FD 7C2E mod F C
10 318 mod 7 1
10 1615 mod 27 10
10 4110 mod 37 33

授業へのコメント (4 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)

@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)

@@@@

青山学院大学

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

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

ブール代数とその部分代数 (合計 12 点)

ある代数系の (真の) 部分代数系は、その代数系の集合の同代数系の条件を全て満たす (真の) 部分集合と定義されている。 授業で使ったブール代数系の具体例で言えば、{1, 3, 4, 12} の真の部分ブール代数は {1, 12} 一つ。 {1, 3} は部分ブール代数ではない。なぜならば、基のブール代数では否定が 12/n で定義され、¬3=12/3=4 が部分集合に含まれない。

授業で使った定義で、ブール代数 {00, 01, 10, 11} の真の部分ブール代数を書きなさい。 (2 点)

{00, 11}

同様に、{000, 001, 010, 011, 100, 101, 110, 111} の四つの真の部分ブール代数全てを書きなさい。 (4 点)

{000, 111}, {000, 001, 110, 111}, {000, 010, 101, 111}, {000, 100, 011, 111}

大きさ 16 のブール代数の大きさ 2 の部分ブール代数の数を書きなさい。(2 点) 1

大きさ 16 のブール代数の大きさ 4 の部分ブール代数の数を書きなさい。(2 点) 7

大きさ 16 のブール代数の大きさ 8 の部分ブール代数の数を書きなさい。(2 点) 6

論理関数の単純化 (15 点)

(AB )∨¬(¬AB ) 下記の式を段階的に単純化し、それぞれの段階でどの様な性質を使ったかを書きなさい。同じ性質を複数並行に使うときには一つの段階を使ってよい。立て続けに同じ性質を使うときには立て続けに別に記入しなさい。交換律と結合律の使用はまとめて一段にしてよいが、記入を忘れずに。

単純化 使用した性質
(BA) ∨ ¬ABC ∨ ¬AB¬C ----
分配律
(B→A) ∨ ¬A∧B ∧ (C∨¬C)
排中律
(B→A) ∨ ¬A∧B ∧ T
真偽の性質
(B→A) ∨ ¬A∧B
含意の除去
(¬B∨A) ∨ (¬A∧B)
分配律
(¬B∨A∨¬A) ∧ (¬B∨A∨B)
交換律
(¬B∨A∨¬A) ∧ (A∨¬B∨B)
排中律
(¬B∨T) ∧ (A∨T)
真偽の性質
T ∧ T
∧ の定義
T
----