単純化した式と標準形 (14 点)

下記の式はそれぞれ標準形から単純化された結果である。途中経過も示しながら、
その式を標準形に戻し、その標準形の名称を明記しなさい。

単純化された式: A∧B∨B∧￢C

途中経過: A∧B ∨ B∧￢C = A∧B∧T ∨ T∧B∧￢C = A∧B∧(C∨￢C) ∨ (A∨￢A)∧B∧￢C = A∧B∧C ∨ A∧B∧￢C ∨ A∧B∧￢C ∨ ￢A∧B∧￢C = A∧B∧C ∨ A∧B∧￢C ∨ ￢A∧B∧￢C

標準形: A∧B∧C ∨ A∧B∧￢C ∨ ￢A∧B∧￢C

名称: 加法標準形 [又は選言標準形]

単純化された式: A∧B∧￢C∨C (短い方の標準形を選びなさい)

途中経過: A∧B∧￢C ∨ C = (A∨C) ∧ (B∨C) ∧ (￢C∨C) = (A∨(B∧￢B)∨C) ∧ ((A∧￢A)∨B∨C) ∧ T = (A∨B∨C) ∧ (A∨￢B∨C) ∧ (A∨B∨C) ∧ (￢A∨B∨C) = (A∨B∨C) ∧ (A∨￢B∨C) ∧ (￢A∨B∨C)

標準形: (A∨B∨C) ∧ (A∨￢B∨C) ∧ (￢A∨B∨C)

名称: 乗法標準形 [又は連言標準形]

法則の数 (12 点)

ある代数の場合に n (n ≥ 0) 個の演算子があると、次の法則はそれぞれ何種類ありうるのかを式で表しなさい。
さらに法則の数の式の有効範囲、可能な法則の合計の変数と合計の演算子を書きなさい。

関係の合成の推移的閉包 (6 点)

下記の推移的閉包を求め、求め方を説明しなさい。

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

1 1 1
0 1 1
0 1 1

上記の配列を自分と合成する (配列の掛算、ただし足し算の代わりは ∨) と上記のようになる。これをさらにもとの行列と合成しても変わらないので、推移的閉包である。

命題論理の性質 (28 点)

整数、有理数、実数などにおいて、a=b ⇔ a+c = b+c が成立する。命題論理において、a=b ⇔ a∨c = b∨c が成立するかどうかを真理表を使って確かめ、成立しなかったら a=b と a∨c = b∨c の間にどの記号を入れたら式が成立するかを述べなさい (12 点)。

真理表により、a=b ⇔ a∨c=b∨c の欄には F も入っているので成立しないが、 a=b → a∨c = b∨c は成立する。

上記で成立した式に相対な式を書きなさい (2 点)。

a=b → a∧c = b∧c

命題論理において、a = a∨b ⇔ a∧b = b を真理表を使わないで証明しなさい (6 点)。

[方法は複数ある、例えば 1) (a↔(a∨b)) ↔ ((a∧b)↔b) の式の変換・単純化 (最後に T になる)
2) a=a∨b ⇒(この問題の前半参照) a∧b=(a∨b)∧b ⇔(吸収律使用) a∧b=b により a=a∨b ⇒ a∧b=b; 逆方向は同様 (相対原理)]

ブール関数においても a = a∨b ⇔ a∧b = b が成立する。その場合だけ a と b が半順序関係にある (a≥b) ことが知られている。|B| > 6 のブール代数の具体例で確認、説明しなさい (8 点)。

三つの元の集合 {牛, 犬, 虫} の冪集合を B にします。
半順序関係が部分集合関係 b ⊂ a である。∨ は和集合、∧ は積集合である。
a = a∪b の場合は確かに b⊂a, かつ b⊂a の場合、a = a∪b
同様に a∩b = b の場合も b⊂a, かつ b⊂a の場合、a∩b = b
よって、上記の集合だけではなく、一般の (有限) 集合の冪集合においても、a = a∪b ⇔ b⊂a ⇔ a∩b = b がよく分かる。

論理回路の図 (10 点)

次の論理式に相当する回路の図を書きなさい。

基数変換 (12 点)

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

用語の説明 (20 点)

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

octal

十六進数、2進数の短縮形、1バイトを2桁で表現できる

Karnaugh map

カルノー図; 論理関数を単純化するための図

well-formed formula

整論理式; 文法的に整っている論理式、例: W∧V はOKが、W∧∧V は違う

neutral element

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

quadruple

四字組; 順番が決まった四つのもの

law of excluded middle

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

conjunction

論理積、かつ: A かつ B の場合 A も B も真の場合だけ論理積が真

inverse relation

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

antisymmetric relation

反対称的関係; 行列表現で対角線に対し対称的な位置のところに高々一つが真

bound variable

束縛された変数; ある量記号の影響の下の変数

関係の表現 (15 点)

右記に A = {2, 3, 4, 5, 12, 35, 36} 内の関係 R のでハッセ図がある。

R を下記の五つの形式で表現しなさい。矢印が下向きになるようにしなさい。

順序対の集合 (外延的記法): {(2,2), (3,3), (4,2), (4,4), (5,5), (12,2), (12,3), (12,4), (12,12), (35,5), (35,35), (36,2), (36,3), (36,4), (36,12), (36,36), }

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

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

  [大きい丸括弧省略]

n 進法での計算 (6 点)

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

量記号の性質 (6 点)

量記号の性質から ∨ 又は ∧、そして含意を含むものを一つ選んで、具体例をで説明しなさい。

∀x: P(x) ∨ ∀x: R(x) → ∀x: (P(x) ∨ R(x)) を選びました。[∃x: P(x) ∧ ∃x: R(x) ← ∃x: (P(x) ∧ R(x)) でもよい] P(x) は x が女性で、R(x) は x は男性だとすると、左から右への含意は「あるパーティに全員が女性又は全員が男性ならば、パーティに来る人すべては女性又は男性である。 逆に右から左はうまくいかない： あるパーティの人全員が女性又は男性であれば、パーティの全員が女性とも限らないし、全員が男性とも限らない。

b分木 (10 点)

b分木は二分木と同様に定義されているが、内部節は子供を二つではなく b個を持つ。
b分木において、内部節が n (n≥0) で、葉の数が h の場合、h = (b-1)n + 1 であることを証明しなさい。

数学的帰納法を用いてます。
基底: n=0 のとき、節は一個の葉だけなので h が 1 なので h = (b-1)n + 1 が明らか。

帰納: 仮定: n = k の時、h = (b-1)k + 1 (k≥0) を仮定する。
そこから内部節が k+1 の場合、h = (b-1)(k+1) + 1 を証明しないといけない。
木を内部節が k 個から内部節が k+1 個になるように、内部節を一つ増やす。一つの葉を内部節に変更し、そこから b個の葉を新しく伸ばすと、内部節が k+1 で、葉の数が (b-1)k + 1 + b - 1 = (b-1)k + (b-1) + 1 = (b-1)(k+1) + 1 Q.E.D.

同値関係の行列表現の数 (10 点)

関係の行列表現で行と列の順番を同じままでしたら、どの順列でもよい。しかし関係の性質を見分けたい場合、制限される。その場合に可能な順列の数とその理由を書きなさい。

同値類の数が 2, それぞれの大きさが n₁ と n₂:
2 n₁! n₂!
理由: 同値類ごとにまとめないと対角線中心に1が正方形の形をしているかどうか見分けられない。どの同値類を先にするのかで二つの選択肢がある。同値類の中の順列が自由なので、それぞれ数の階上になる。

同値類の数が d, それぞれの大きさが n₁ ... n_d:
d! ∏^d_i=1n_i!
理由: 上記と同様。同値類の数が d なので、同値類そのものの順列が d! になり、各同値類内の順列の数の積と掛け合わせないといけない。

ペアノの公理 (合計 14 点)

足算の公理も含めペアノの公理を四つ記述しなさい (8 点)。

• 1 は自然数
• a が自然数であれば s(a) は自然数 (s は successor, 後者)
• s(x) = 1 という x は存在しない
• a と b が自然数の場合、a + s(b) = s(a + b)

ペアノの公理の意義を説明しなさい (5 点)。

数学はできるだけ少ない前提からスタートして、できるだけたくさんのことを証明したい目的がある。 幼稚園の園児でも分かるぐらいの物の数を数える自然数や足し算の法則を (結合率など) を当たり前と思わず、 もっと基本的な公理から導くので、まさに数学の基礎である算数をもっとも数学らしくした。