用語の説明 (16 点)

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

duality principle

相対原理; 集合演算や論理演算に追えての例えば T と F、又はとかつを入れ換えられる原理

boolean algebra

ブール代数; ベキ集合上の集合演算やビット毎の論理演算を抽象化した代数係

semiordered set

(半)順序集合; 半順序で定義された順序つきの集合

equivalence class

同値類; 集合の中の同値であるものの部分集合

Abelian group

可換群; 交換律が成り立つ群

octal

八進数(の); 数を 0-7 の八つの記号で表す仕組み

predicate logic

述語論理; 命題ではなく、引数を取る述語を使う論理

existential quantifier

存在限量子や存在記号; ある論理式が変数が少なくともある一つの値の場合真であることを示す記号

集合の演算 (6 点)

次の集合を基に、表の通り計算しなさい。U={x|xは正数かつx<11}; A={2, 3, 5, 7}; B={2, 4, 6, 8, 10}; C={3, 4, 5}

番号	問題	解答
	A∪B	{2, 3, 4, 5, 6, 7, 8, 10}
	A∩C	{3, 5}
	Bc	{1, 3, 5, 7, 9}
	P(C)	{ {}, { 3 }, { 4 }, { 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 }, { 3, 4, 5 } }
	|B|	5
	|P(U)|	1024

NOR の被演算子の数 (8 点)

単項の NOR(A) は 二項の NOR を用いて NOR(A, A) と書くことができる。同様にして、三項の NOR(A, B, C) を二項の NOR のみを用いて書きなさい。

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

関係の性質 (16 点)

下記の表に列挙されている関係について、a) から h) が必ず真になる場合は「○」、そうでない場合は「×」を記入して、表を完成しなさい。

1. 自分と合成しても変わらない。
2. 行列表現で対角線は全て T。
3. (x, y) ∈ R ⇒ (y, x) ∈ R
4. 行列表現で対角線は全て F。
5. xRy かつ yRx ならば x=y である。
6. 例として (正数上などの)「<」がある。
7. 行列表現で対角線で反射したら対角線以外のところの F と T が全て入れ替わる。
8. ハッセ図で表現可能である。

	a)	b)	c)	d)	e)	f)	g)	h)
反射的関係	×			×
(半)順序	○	○		×
非対称的関係				×
対称的関係				×
全順序	○	○		×
反対称的関係				×	○	○
推移的関係	○			×
同値関係	○	○		×

基数変換 (12 点)

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

番号	a	a の基数	b	b の基数
例	15	10	1111	2
	21202201212	3	252655	9
	2049	10	501801	16
	1AE	16	440430	10
	F5CB	16	1111010111001011	2
	71	10	1000111	2
	54217	8	101100010001111	2
	66	10	123	7
	FE8G	25	30241331	5
	11100101110111	2	34567	8
	11011011	2	219	10
	1001010101110101101	2	4ABAD	16
	4763	8	213303	4

真理表 (8 点)

下記の表を右に延ばして、(G∧H∨¬K)→H の論理式の途中経過と結果を計算しなさい。

G	H	K
F	F	F
F	F	T
F	T	F
F	T	T
T	F	F
T	F	T
T	T	F
T	T	T

三分木 (合計 16 点)

三分木は二分木と同様に定義されているが、内部節は子供を二つではなく三つ持つ (例参照)。

次の表にそれぞれの内部節の数の三分木の葉の数と全体の節の数を記入しなさい (5 点)。

内部節の数	葉の数	節の数
0	1	1
1	3	4
2	5	7
3	7	10
4	9	13
5	11	16

上記の表から三分木において内部節の数 n と葉の数 h の関係を式で表しなさい (3 点)。

h = 2n + 1

上記の式を数学的帰納法を用いて、帰納法の各部分を明記の上証明しなさい (8 点)。

基底: n=0 のとき、h が 1 なので h = 2n + 1 が明らか。

帰納: 木が少しずつ伸びるように節の数を一個一個増やす。 増やし方は葉を一つ選んで、内部節に変え、この内部節に新たに三つの葉を伸ばすようにする。 一回伸ばしたときに、新しい葉の数 h' は現在の葉の数 h - 1 + 3、すなわち h + 2 (内部節になった分を引いて、新たに伸びた葉の数を足す)。新しい内部節の数 n' は n+1。 帰納のステップでは h = 2n + 1 -> h' = 2n' + 1 を証明すればよい。h = 2n + 1 -> h+2 = 2n+3 = 2(n+1)+1 -> h' = 2n' + 1 で証明が完了。

関係の表現 (15 点)

A={1, 2, 3, 4, 5, 6, 7, 8} の場合、 { (a, b) | a∈A ∧ b∈A ∧ a>b ∧ (a mod b)>1 } の関係を下記の三つの表現形式で書きなさい。ただし、x mod y は x を y で割った結果の余りである。

表	行列	グラフ

分配律 (合計 10 点)

含意と論理和の考えられる分配律を 4つ列挙しなさい (4 点)。

a->(bvc) = (a->b)v(a->c)         (avb)->c = (a->c)v(b->c)
(a->b)vc = (avc)->(bvc)           av(b->c) = (avb)->(avc)

上記の内一つ自分で選んで、それが恒真であるか否かを示しなさい (6 点)。

A	B	C
F	F	F
F	F	T
F	T	F
F	T	T
T	F	F
T	F	T
T	T	F
T	T	T

論理回路の図 (6 点)

論理式 NOR(A, NAND(XOR(B, C), D)) に相当する論理回路を書きなさい。

標準形 (合計 14 点)

標準形の性質を列挙しなさい (3 点)。

• どの真理表 (論理関数) に対しても簡単に作られる
• 式の深さが浅い
• 式が大きくなる可能性がある

ある n 変数の論理式で、 T の数が t である場合、 それぞれの標準形の場合について、∨ と ∧ の演算子の数を式で表しなさい (5 点)。

標準形の種類	∨ の数	∧ の数
加法標準形	t-1	t(n-1)
乗法標準形	(2n - t) (n - 1)	2n - t - 1

¬ の数は一定ではない。n=6 と t=30 の 場合、加法標準形のとりうる ¬ の最大の数と最小の数を求め、その求め方を含めて解答しなさい (6 点)。 (ヒント: パスカルの三角形)

¬の最大の数は一番 F の多い行を見ればよい。一番多い行には F が 6個ある。その次の F が 5個の行は 6行で、その次の F が 4個の行は 15行ある。行の数を 30行にするには後 F が 3個の 20行の内 8行を使う。
それぞれの行の数は ₆C_{(F の数)} の組み合わせの数で、パスカルの三角形から得られる。
¬の最大の数これで 6x1 + 5x6 + 4x15 + 3x8 = 6+30+60+24= 120 である。
¬の最小の数を同じ方法で計算すると 0x1 + 1x6 + 2x15 + 3x8 = 0+6+30+24= 60 である。

論理関数の単純化 (8 点)

¬(D∨E)∨(¬D∧E) の式を段階的に単純化し、それぞれの段階でどの様な性質を使ったかを書きなさい。

単純化	使用した性質
¬(D∨E)∨(¬D∧E)	ド・モーガンの法則
(¬D∧¬E)∨(¬D∧E)	分配律
¬D∧(¬E∨E)	排中立
¬D∧T	真偽の性質
¬D	(終わり)

量記号 (8 点)

(∀x: ∃y: P(x,y)) △ (∃y: ∀x: P(x,y)) での △ をどういう演算子にすれば全体の式が恒真になるのかを、その理由とともに書きなさい。

####上記の二つの式が違います。
左側は各 x において少なくとも一つの y が存在すると言う。
右側は少なくともある一つにおいて、全ての y の場合 P(x,y) が成立すると言う。

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

情報テクノロジーにおいて数学は言語として大きな役割を担っている。これについて、自分の経験をふまえて論ぜよ。