真理表、標準形、単純化 (合計 35 点)

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

問題 1.1 の論理式の二つの標準形を書きなさい。 (8 点)

加法標準形 (disjunctive normal form): ¬B∧¬G∧¬H ∨ ¬B∧¬G∧H ∨ ¬B∧G∧¬H ∨ B∧¬G∧H ∨ B∧G∧¬H

乗法標準形 (conjunctive normal form): (B∨¬G∨¬H) ∧ (¬B∨G∨H) ∧
(¬B∨¬G∨¬H)

問題 1.1 の論理式、基本的な論理演算子 (∧、∨、¬) のみを使う式に段階的に変換し、単純化してください。それぞれの段階でどの様な性質を使ったかを書きなさい。 同じ性質を複数並行に使うときには一つの段階を使ってよい。立て続けに同じ性質を使うときには立て続けに別に記入しなさい。 交換律と結合律の使用はまとめて一段にしてよいが、記入を忘れずに。 (15 点)

ヒント 1: XOR(A, B) を「XOR の定義」で ¬(A↔B) に変換できます。

ヒント 2: 単純化の結果を片方の標準形と比較することで、結果の確認ができます (カルノー図表の応用)。

数式の証明 (16 点)

最初の n 個の奇数の二乗の合計が n(4n²-1)/3 であることを証明しなさい。
例えば n=5 の場合、1 + 9 + 1525 + 49 + 81 = 165 = 5(4·5²-1)/3.

ヒント： 多項式を展開し、同じようになることを見せる。

論理回路の図 (10 点)

次の論理式の回路の図を書きなさい。

用語の説明 (24 点)

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

permutation

順列; ある集合から順番を考慮して重複なしに元を選ぶときにできるものやその数

axiom

公理; ある理論の基となる、証明されない「定理」みたいなもの、常識に近いものが多い

exponentiation

べき乗演算; x^y の演算、x を y 回掛け合わせた結果

bound variable

束縛変数; 量記号によりある式内に束縛されている変数

subset

部分集合; ある集合の元の一部を含まれる集合

proposition

命題; 客観的に真か偽が判断できる文 (質問でもない)

binary operation

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

equivalence relation

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

proof about sets

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

greatest common divisor

最大公約数; 複数の整数をすべて割り切れる最大の数

multi-valued logic

多値論理; 「真」と「偽」以外の値、例えば「分からない」、も使う論理

prime number

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

基数変換 (8 点)

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

関係の表現 (26 点)

集合 C = {2, 3, 4, 5, 6, 7} 内の関係 R (relation R on set C) は下記左側の表で与えられています。 残りの四つの表現形式で書きなさい。

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

  [大きい丸括弧省略]

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

順序対の集合 (内包的記法、connotation、6 点): { (x,y) | x∊C ∧ y∊C ∧
(x mod y = 0 ∨ y - x = 3) }

R について、授業で習った四つの関係の性質 （properties of relations） について、その有無と有無の理由を書きなさい。(8点)

1. 反射的である。なぜなら、行列表現の対角線が
   全て 1。
2. 対称的ではない。なぜなら、対角線に反射しても同じにならない
   (例: (4,2)∊R が (2,4)∉R)
3. 反対称的ではない。なぜなら、対角線を向かい合っている対で両方が 1 のケースがある (例: (6,2) と (2,6))
4. 推移的ではない。なぜなら、R を自分と合成すると R と違う結果となる(例: (3,6)∘(6,2)=(3,2)∉R)

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

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

@@@@

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

@@@@

n 進法での計算 (11 点)

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

ブール代数 (合計 12 点)

|B| = 8 のブール代数 (Boolean algebra) を一つ選び、それについて各情報を表に書き込み、表の下にハッセ図を書きなさい。

ハッセ図

式の作成 (16 点)

下記の数や学生、ペットなどについての英文に相当する式を作成しなさい。授業で習った記号は全て使って構いません。学生の集合は S,ペットの集合は P で、学生 s がペット p が好きということを like(s, p), 学生 s の年齢を age(s) と表す。それ以外、述語や関数を作らないこと。

例: All natural numbers are greater than -1.

∀n∈ℕ: n > -1

There is a rational number that is not an integer.

∃x∈ℚ: x∉ℤ

The number of natural numbers, the number of integers, and the number of rational numbers is the same.

|ℕ| = |ℤ| = |ℝ|

Every natural number greater than 0 is divisible by 1 and by itself.

∀n∈ℕ,n>0: n mod 1 = 0 ∧ n mod n = 0

There is no greatest natural number.

∀n∈ℕ: ∃m∈ℕ: m>n

Divisibility (the fact that a natural number divides another natural number) is transitive.

∀a,b,c∈ℕ: a mod b = 0 ∧ b mod c = 0 → a mod c = 0

Every student likes a pet.

∀s∈S: ∃p∈P: likes(s,p)

There is a student who likes all pets.

∃s∈S: ∀p∈P: likes(s,p)

Every pet is liked by a student.

∀p∈P: ∃s∈S: likes(s,p)

All students are older than 18.

∀s∈S: age(s) > 18

There is exactly one student who is 30.

|{s| s∈S ∧ age(s) = 30}| = 1

Every pet is disliked by a student.

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

There is a pet that is disliked by all students who are older than 20.

∃p∈P: ∀s∈S: age(s) > 20 → ¬likes(s,p)

群とその同形 (12 点)

下記の表 A から H までは三種類に分けられます：

1. 群 (group) ではないもの
2. 群であるが、表現上に問題が存在
3. 群である、表現上に問題がない

それぞれ A から H の表の直下に次のことを書きなさい。

• 1. の場合、その旨と理由
• 2. と 3. の場合、その群と同形 (isomorphic) の群すべて
• さらに、2. の場合、表現上の問題点