関係の性質 (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. 例として (正数上などの)「≤」がある。

真理表 (12 点)

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

論理回路の図 (15 点)

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

論理式の作成 (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)))

用語の説明 (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 点)

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

同値の性質 (16 点)

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

関係の表現 (20 点)

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)}

    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

  [大きい丸括弧省略]

標準形 (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 点)

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

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

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

@@@@

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

@@@@

ブール代数とその部分代数 (合計 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 点)

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