後期試験 ・ 2014 年 1 月 31 日 2 時限実施 ・ ページ
授業 科目 |
情報数学 I | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
氏名 | ||||||||||||||||
担当者 | DÜRST, Martin J. |
下記の表に列挙されている関係の種類について、a) から h) が必ず真になる場合は「○」、そうでない場合は「×」を記入して、表を完成しなさい。
a) | b) | c) | d) | e) | f) | g) | h) | |
---|---|---|---|---|---|---|---|---|
全順序 | ○ | × | ○ | ○ | ○ | ○ | ○ | ○ |
対称的関係 | × | × | × | × | × | × | × | × |
非対称的関係 | × | × | × | × | × | × | × | ○ |
同値関係 | ○ | × | × | ○ | × | ○ | × | × |
推移的関係 | × | × | × | × | × | ○ | × | ○ |
反射的関係 | ○ | × | × | ○ | × | × | × | ○ |
(半)順序 | ○ | × | ○ | ○ | ○ | ○ | × | ○ |
反対称的関係 | × | × | × | × | ○ | × | × | ○ |
下記の表に論理式 ¬A∨¬C∧(B→C) の計算の途中経過と結果を記入しなさい。
A | B | C | ¬A | ¬C | B→C | ¬C∧(B→C) |
¬A∨¬C∧(B→C) |
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 時限実施 ・ ページ
使える部品だけを用いて、指定した入力から指定した出力を出す回路の図を書きなさい。
使える部品: 全て 入力: A, B, C 出力: A ∨ C ∧ B |
使える部品: NOT と AND 入力: A, B 出力: A → B |
使える部品: NOR 入力: A, B 出力: A ∧ B |
---|---|---|
ある大学のある学科の学生の集合 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. |
次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。単にカタカナ表記にするのは避けること。
次の表の基数変換を行いなさい。
番号 | 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 時限実施 ・ ページ
次の性質 P(n) を全ての n≥1 の場合に証明しなさい。
P(n): n 個の論理変数 Xi (1≤i≤n) に対して、
X1 ↔ X2 ↔ ... ↔ Xn = Y
で Xi の内に 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 |
C = {2, 3, 4, 5, 6, 7} 内の関係 R で、xRy は x を y で割った余りが 1、又は y を x で割った余りが 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 点) | |||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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. |
三つの論理変数 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 がチェスボードの白黒模様のようになって、縦や横に二つの升でもまとまらない。
式で単純化しようとすると、ひとつの変数以外否定の有無が一致する二つの項目を見つけないといけないが、見つかりません。
次の表の計算を行いなさい。結果は被演算子と同じ基数を使って書きなさい。
番号 | 計算の基数 | 第一被演算子 | 演算子 | 第二被演算子 | 計算結果 |
---|---|---|---|---|---|
例 | 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 |
この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)
@@@@
この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)
@@@@
後期試験 ・ 2014 年 1 月 31 日 2 時限実施 ・ ページ
授業 科目 |
情報数学 I | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
氏名 | ||||||||||||||||
担当者 | DÜRST, Martin J. |
ある代数系の (真の) 部分代数系は、その代数系の集合の同代数系の条件を全て満たす (真の) 部分集合と定義されている。 授業で使ったブール代数系の具体例で言えば、{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
(A→B )∨¬(¬A↔B )
下記の式を段階的に単純化し、それぞれの段階でどの様な性質を使ったかを書きなさい。同じ性質を複数並行に使うときには一つの段階を使ってよい。立て続けに同じ性質を使うときには立て続けに別に記入しなさい。交換律と結合律の使用はまとめて一段にしてよいが、記入を忘れずに。
単純化 | 使用した性質 |
---|---|
(B→A) ∨ ¬A ∧ B ∧ C ∨ ¬A ∧ B ∧ ¬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 | |
---- |