基数変換 (12 点)

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

用語の説明 (20 点)

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

proof by counterexample

反例による証明; ある定理 A の反対 (A ではない) に違反する例を見つけて証明する

power set

ベキ集合; ある集合の全ての部分集合

semiorder relation

(半)順序関係; 反射的、反対称的、かつ推移的な関係

inverse element

逆元; 群において、ある元 t の逆元は、t と演算して単位元になる

complement

補集合; 集合 A の補集合は A に属していない元の集合

bitwise xor

ビットごと排他的又は; 二つのビット列の同じ位のビット同士での排他的又は

propositional logic

命題論理; 命題だけを使う論理

commutative law

交換律; ある演算 ∘ に対して、a∘b=b∘a のような性質

equivalence

同値; 論理に大切な演算子で、A ↔ B と書き、A と B が同じ値の時だけ真

quintuple

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

真理表 (10 点)

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

含意の一般性 (12 点)

NAND や NOR だけで全ての論理関数が実現可能ということはよく知られている。 含意で全ての論理関数が実現可能なのかどうかを考え、その結果を証明しなさい。
ヒント: NAND や NOR の場合には T、F を使わなくても実現可能だが、この問題は F と T も使える条件下で考えてください。

∧, ∨, そして ¬ が実現可能でしたら他の論理関数も実現可能です。それぞれ次のように含意で実現できる:
¬A = A→F (A→F の含意は A が T の時だけ F、それ以外 T)
含意の除去: C→D = ¬C∨D = ¬(C∧¬D)
A=¬C, B=D とすると A∨B = ¬A→B がえられ、よって A∨B = (A→F)→B
A=C, B=¬D とすると ¬(A∧B) = A→¬B がえられ、よって A∧B = ¬(A→¬B) = (A→(B→F))→F
∧, ∨, そして ¬ が実現可能が実現可能なので証明が完成

式の証明 (12 点)

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

数学的帰納法を使って証明する。
基底: n=1: 1³ = 1/4 1²(1+1)² = 1
帰納: 1³ + 2³ + ... + k³ = 1/4 k²(k+1)² を前提として 1³ + 2³ + ... + (k+1)³ = 1/4 (k+1)²(k+2)² を証明できればよい。
1³ + 2³ + ... + (k+1)³ = [前提導入]
= (1/4 k²(k+1)²) + (k+1)³ =
= 1/4 (k²(k+1)² + 4(k+1)²(k+1)) =
= 1/4 (k²+4k+4)(k+1)² =
= 1/4 (k+1)²(k+2)² で証明完了。

群 (10 点)

代数系の条件を含め群の条件を説明しなさい。

対処の集合が一つで、その集合の元の間の演算が一つ。演算の結果も集合の元になる。 群の公理が三つ: 結合律、単位元の存在、逆元の存在

群 (ℤ; +) において条件や定理を説明しなさい。

ℤ は整数で、+ は足し算で、整数をいくら足しても又整数になる。単位元は他の元 a と足し合わせても又その同じ a になるもなで、この場合は 0 でよい。ある元 a の逆元は a と足し合わせて単位元になるもので、今回の場合は -a で存在する。

半順序関係の性質 (9 点)

ある集合 B の中の関係 R が半順序関係であるための R の三つの条件 (性質) を列挙し、それぞれ簡単に説明しなさい。

反射的

全ての x ∊ B の場合に x∘x ∊ R; 対角線は全て 1

反対称的

全ての x, y ∊ B の場合、 x∘y ∊ R ∧ y∘x ∊ R ⇒ x=y

推移的

R を R と合成しても R のまま

三値記号論理 (合計 15 点)

記号論理の中では二値論理が一般的であるが、多値論理もある。真 (T) と偽 (F) の他「分からない」(?) の値も許す三値論理の論理積、論理和、論理否定の真理表を書いてみて、自分が選択した結果を説明しなさい。

関係の表現 (20 点)

A = {3, 4, 5, 6, 7, 8} 内の関係 R で、xRx は x を y で割った余り (x mod y) が 1 又は 2 の場合だけ真である。R を下記の五つの表現形式で書きなさい。

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

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

半加算機の論理回路の図 (8 点)

半加算機の論理回路の図を書きなさい。(ヒント: 入力は A と B、出力は S と C)

式の単純化 (9 点)

次の集合演算の式を、途中経過や理由を残しながら単純化しなさい。

(A∪B)^c∪A^c∩B

(A^c∩B^c)∪(A^c∩B) = A^c∩(B^c∪B) = A^c∩U = A^c

G∩H∩K∪G∩H^c∩K∪G^c

(H∪H^c)∩G∩K∪G^c = G∩K∪G^c = (G∪G^c)∩(K∪G^c) = K∪G^c

(C∩D)^c∩(C^c∪D)

二つ前と双対なので D^c

標準形の数 (10 点)

ある論理関数の標準形は二種類だけであるが、交換律の適応によって表面的に違う標準形の数はもっと多い。 その数を標準形の名称と共に式で表し、説明しなさい。n を変数の数、t を論理関数が T になる変数の値の組み合わせの数として使いなさい。

名称:加法標準形 式: t! (n!)^t
説明: 加法標準形は和の積で、各積内変数の数が n。よってそれぞろの積内の順列の数が n! で、積内の順列は自由に組み合わせ可能なのでお互いの掛け算になる。それに積の数が t なので、積そのものの順列を考慮するために t! を掛ける。

名称:乗法標準形 式: (2ⁿ-t)! (n!)^(2n-t)
説明: 積と和の役割は逆ですが、式は根本的に変わらない。 しかし t (T の数) を f (F の数、t+f = 2ⁿ)
に置き換えないといけない。

量記号の性質 (9 点)

次の式が表している量記号の性質について、この性質は何を言っているのか、なぜ成り立つのか、簡単に説明しなさい (例を使ってもよい)。

¬∃x: P(x) = ∀x: ¬P(x)

 
 

∀x: (P(x)∨R(x)) → ∀x:P(x) ∨ ∀x:R(x)

 
 

(∃x: P(x)) ∨ Q(y) = ∃x: (P(x) ∨ Q(y))

 
 

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

授業では数学を言語と位置づけた。他の情報テクノロジーにとって大切な言語とも比べ、なぜ数学が言語といわれているのかを考え、説明しなさい。

言語は自分の物事についての考えを言える・記述できる、他人の考えを取得できるものと考えられる。 情報数学は他に情報テクノロジーに大切な日本語、英語、プログラミング言語と同様にそういう役割を果している。 ものによって例えば日本語で言いにくいことは数学ではっきり表せることができる。