情報テクノロジーでの数学の役割 (4 点)

次の情報数学の概念について、その情報テクノロジー分野での応用例を一言で書きなさい。

NOR

論理回路

関係

データベース

数学的帰納法

アルゴリズムの証明; 繰り返しの設計

命題論理

実世界の出来事のモデル

論理式の評価 (合計 15 点)

下記の真理表を使って、¬C∨B∧¬A の論理式の途中経過と結果を記入しなさい (空のコマを全て埋めること)。 (5 点)

A	B	C	¬A	B∧¬A	¬C	¬C∨B∧¬A
F	F	F	T	F	T	T
F	F	T	T	F	F	F
F	T	F	T	T	T	T
F	T	T	T	T	F	T
T	F	F	F	F	T	T
T	F	T	F	F	F	F
T	T	F	F	F	T	T
T	T	T	F	F	F	F

論理式 ¬C∨B∧¬A に相当する論理回路を書きなさい。(4 点)

論理式 ¬C∨B∧¬A を標準形で書きなさい。二つの標準形のうち短い方を使いなさい。(3 点)

(A∨B∨¬C) ∧ (¬A∨B∨¬C) ∧ )¬A∨¬B∨¬C)

NAND への変換 (6 点)

論理式 E∧D∨¬F と同等な式を NAND だけで作りなさい。

NAND (F, NAND (D, E))

英語の概念の説明 (10 点)

次の英語の用語に対応する日本語の用語とその簡単な説明を記述しなさい。

conjunction

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

symbolic logic

記号論理、論理のモデルを作って、記号演算だけで論理ができるようにする。

denotation

外延的記法、集合の元を (波括弧 ({}) 内に) 全部列挙する

power set

ベキ集合、ある集合の全ての部分集合の集合、P(A) と書く

intersection

積集合、両方の被演算子の集合に含まれる元の集合

universal set

普遍集合・全体集合、 議論の対象にされている全ての要素の集合

hexadecimal

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

free variable

自由変数、量記号で束縛されてない変数

universal quantifier

全称限量子、全称記号、ある論理式がある変数の全ての値に対して成立することが書ける記号

transitive closure

推移的閉包、ある二項関係を変わらないまで自分と繰り返し合成した結果

同値関係の性質 (6 点)

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

反射的

全ての x ∈ A の場合に (x,x) ∈ R; 左上から右下の対角線は全て 1

対称的

全ての x,y ∈ A の場合、(x,y)∈R → (y,x)∈R; 行列で表すと対角線で対称的

推移的

全ての x,y,z ∈ A の場合、(x,y)∈R ⋀ (y,z)∈R → (x,z)∈R; 関係を自分と合成しても変わらない

関係の表現と半順序 (合計 15 点)

次に行列で示されている関係を有向グラフと表で表現しなさい。

行列	有向グラフ (4 点)	表 (5 点)
a b c d e a 1 0 0 1 0 b 0 0 1 0 0 c 0 0 0 1 0 d 0 0 0 0 0 e 1 0 1 1 0

上の関係は半順序ではない。半順序になるように最小限に 関係の元を足し、結果の関係をハッセ図で書きなさい。(6 点) (ヒント: 半順序に必要な性質を考えること。)

  d
 /|
a c
|/|
e b

命題論理の性質 (10 点)

次の命題論理の性質の式を書きなさい。

例: 同一律

A ∧ A = A, A ∨ A = A

交換律

A ∧ B = B ∧ A, A ∨ B = B ∨ A

分配律

(A ∨ B) ∧ C = (A ∧ C) ∨(B ∧ C), (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)

ド・モーガンの法則

¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B

二重否定

¬¬A = A

排中律

A ∨ ¬A = T

吸収律

A ∧ (A ∨ B) = A, A ∨ (A ∧ B) = A

含意の性質 (6 点)

論理記号の中では含意 (ならば) は分かりにくい点が多い。次の式を含めて示されている 含意の性質について、この性質は何を言っているのか、なぜ成り立つのか、簡単に説明して下さい (例を使ってもよい)。

背理法: A→¬A = ¬A

A と ¬A は同時には成らないので、A→¬A であると A なら矛盾になるので、¬A にならざるおえない。

対偶: A→B = ¬B→¬A

「卒業 (A) したら旅行に行く (B)」を例に使う。卒業しなかったら 旅行に行けないとは言ってない。しかし卒業したら必ず旅行に行くことなので、旅行に行かなかったのは結局卒業しなかったと言うことです。

基数変換 (10 点)

次の表の基数変換を行って下さい。

番号	a	a の基数	b	b の基数
例	15	10	1111	2
	211	3	22	10
	51	10	110011	2
	732	8	111011010	2
	4096	10	1000	16
	FC	16	252	10
	BA8	16	101110101000	2
	93	10	333	5
	100111100001	2	9E1	16
	10110101101	2	2655	8
	1010101	2	85	10

量記号の性質 (6 点)

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

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

P(x)を 「x が日本人」の例で説明する。「全ての学生が日本人」のが偽であれば、だれか一人、日本人でない人が存在する。逆に、一人でも日本人ではない学生がいれば、「全ての学生は日本人」とはならない。

∃x: (P(x)∧R(x)) → ∃x:P(x) ∧ ∃x:R(x)

二つの性質 P と R を同時に持つものがあれば、それぞれの性質を持つものはいる。しかし逆に、それぞれの性質のものがいても同時に同じものが二つの性質を持つとは限らないので、= ではない。

恒真の証明 (5 点)

論理式 P→(Q→P) が恒真であることを証明しなさい。

真理表での証明。最後の欄には T しかないので恒真である。

P	Q	Q→P	P→(Q→P)
F	F	T	T
F	T	F	T
T	F	T	T
T	T	T	T

数学的帰納法 (8 点)

次の式をみて、この中の規則を見つけ、仮説を立て、数学的帰納法で証明しなさい。

1	= 1
1 + 3	= 4
1 + 3 + 5	= 9
1 + 3 + 5 + 7	= 16
1 + 3 + 5 + 7 + 9	= 25

仮説:

1 から初めて、n 個の一番小さい正の奇数の和が n² と等しい。

基底:

n が 1 の場合 1 = 1² で明らかである。

帰納:

仮説が k≥1 の場合に成り立つと仮定し、k+1 の場合に成り立つことを証明する。 k+1 行目と k 行目の差が左も右も同じでしたら証明が成り立つ。左の差は k+1 行目の最後の基数で、 2k+1 となる。

右の差は (k+1)² - k² = k² + 2k + 1 - k² = 2k + 1。右も左の差も同じなので証明が完了。