論理回路の図 (10 点)

次のように制限された部品から指定した回路の図を書きなさい。

量記号 (12 点)

A が動物の種類の集合で、S が情報数学 I を受講した学生の集合で、likes(s, a) が「学生 s は動物の種類 a が好き。」とする。次の式が表している意味をそれぞれの同意や違いがはっきりわかるように説明しなさい。

∃s∊S: ∀a∊A: likes(s, a)

全ての動物の種類が (同じ人が同時に) 好きな学生が少なくても一人いる。

∀a∊A: ∃s∊S: likes(s, a)

それぞれの動物の種類全てには (別々な人でもよいが) だれか好きな学生がいる。

∀s∊S: ∃a∊A: likes(s, a)

全ての学生にはそれぞれ何かの好きな動物の種類がある。

∃a∊A: ∀s∊S: likes(s, a)

全ての学生が好きな動物の種類は少なくとも一種がある。

上記四つの式から一番真になる可能性が高いと思われるものを選んで、選んだ理由を詳しく説明しなさい。

一番真になる可能性の高いのは3番です。全くどんな動物でも好きでない人もたまにいますが、とても珍しい。 1番はいくら動物が好きな人でも種類がいっぱいあるのでどうしても好きではないものもあるだろう。 2番もありそうですが、どうしても誰も好きになれない動物もありそうです。 4番は例えば多くの学生が好きな猫とかでもやはり好きでない学生もいるだろう。

言語としての数学 (5 点)

情報テクノロジーにおいて数学とその他大事な言語を比べ、数学の大切さについて論ぜよ。

カルノー図表 (12 点)

下記の二つのカルノー図表の一番上の行と一番左の欄を完成しなさい。

下記の二つのカルノー図表の直下にそれぞれの図で表現されている論理関数を単純化したものを書きなさい。

真理表 (10 点)

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

標準形 (8 点)

四つの論理変数 A, B, C, D のうちちょうど一つの変数だけが T のときだけに F になる論理関数の短い方の標準形とその名称を書きなさい。

名称: 乗法標準形

式: (¬A∨B∨C∨D)∧(A∨¬B∨C∨D)∧(A∨B∨¬C∨D)∧(A∨B∨C∨¬D)

標準形の性質を三つ簡単に説明しなさい。

1. 標準形の作成は決まった手順に従うだけなので簡単
2. 標準形はどんな論理関数からでも作られますので一般的
3. 標準形の式は浅いので、回路で実装すると早く作動する

基数変換 (12 点)

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

用語の説明 (20 点)

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

semigroup

半群; 群みたいなものだが、結合律だけ； 単位元と逆元は必要ない

denotation

外延的記法; 集合を元の列強(波括弧 ({}) 内) で記述する方法

empty set

空集合; 元が一つも入ってない集合、{} 又は ∅ と書く

neutral element

単位元; ある演算において、演算されても影響がないもの (例： 足し算の場合 0)

negation

論理否定; 論理演算で真を儀、儀を真に反転する演算

law of excluded middle

排中立； 論理演算において、真都議しかないということ (A ∨ ¬A = T)

tautology

恒真; 常に真の論理式

inverse relation

逆関係; ある2項関係の2項組を全て逆にしたもの

asymmetric relation

非対称的関係; 対象的ではない関係

closed formula

閉論理式; 自由変数を含まない論理式

ブール代数の例 (10 点)

有限ブール代数 B の大きさ |B| は全て 2ⁿ である。n=3 のブール代数の具体例を選んで、次の項目を書きなさい。

            {狼, 狐, 狸}

  {狼, 狐}    {狼, 狸}    {狐, 狸}

    {狼}       {狐}        {狸}

                {}
  [線省略]

B

{狼, 狐, 狸} の全ての部分集合

単位元

全集合: {狼, 狐, 狸}

零元

空集合: {}

単項演算

補集合演算

2項演算 (二つ)

積集合演算

和集合演算

半順序

部分集合

関係の表現 (15 点)

C = {1, 2, 3, 4, 5, 6, 7} 内の関係 R で、x Ry が次の三つの条件:

1. x-y が -3 より大きい
2. x と y のうち少なくとも一つが素数
3. x+y を 3 で割った余り (x+y mod 3) が 1

を全て満たさないと真にならない。R を下記の五つの表現形式で書きなさい。
(a を b で割っての余りは a mod b、a が素数は prime(a) と書く。)

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

  [大きい丸括弧省略]

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

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

含意と恒真 (12 点)

((A∧B)→C) → (A→(B→C)) が恒真であることを式の変換によって証明しなさい。変換ごとに使用した性質の名前を明記しなさい。

式の証明 (10 点)

n ≧ 1 の場合、1·2 + 2·3 + ... + n·(n+1) = n·(n+1)·(n+2)/3 を証明しなさい。

数学的帰納法を使って証明する。
基底: n=1: 1·2 = 2 = 1·2·3/3
帰納: 1·2 + 2·3 + ... + k·(k+1) = k·(k+1)·(k+2)/3 を前提として
1·2 + 2·3 + ... + k·(k+1) + (k+1)·(k+2) = (k+1)·(k+2)·(k+3)/3 を証明できればよい。
証明したいものから前提を両側で引くと (k+1)·(k+2) =
(k+1)·(k+2)·(k+3)/3 - k·(k+1)·(k+2)/3 = (k+1)·(k+2)·(k+3)/3 - (k+1)·(k+2)·k/3 =
((k+1)·(k+2)/3)((k+3)-k) = ((k+1)·(k+2)/3)·3 = (k+1)·(k+2) で証明が完了。
 

関係の性質の組合せ (14 点)

関係の性質には反射的、対称的、推移的、反対称的がある。 その性質の有無の組合せから、授業で詳しく説明した二つの組合せについて、名称と各性質の有無を記述し、行列表現での見分け方を簡単に説明しなさい。

名称: 同値関係

性質の有無: 有： 反射的、対称的、推移的； 無: 反対称的

見分け方: 行と列を同様に入れ替えることで 1 で左上から右下までの対角線を囲むお互いに重なってない正方形を作れる。

名称: 半順序関係

性質の有無: 有： 反射的、推移的、反対称的； 無: 対称的

見分け方: 行と列を同様に入れ替えることで 1 が左上から右下までの対角線以上 (又は以下) だけになるように出来ればよい。

対称的かつ推移的ではないかつ反対称的な関係の例を作ることは不可能である。このことを証明しなさい。

対称的かつ反対称的な関係が必ず推移的であることを証明すればよい。 行列表現で対称的というのは対角線の両側に対称的な位置にあるところが同じということ。 反対称的というのは対角線の両側に対称的な位置にあるところが高々一か所しか 1 がない。 対称的かつ反対称的というのは結果的に対角線意外に全て 0 になる。 しかし対角線意外に全て 0 の関係は必ず推移的であるので証明が完了です。