用語の説明 (20 点)

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

union

和集合; 二つの集合のどちらかでも含まれる元の集合

connotation

内包的記法; 集合をその元となる条件で定義する

well-formed formula

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

transitive closure

推移的閉包; ある関係を結果が変わらなくなるまで自分と結合した結果

Karnaugh map

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

permutation group

交換群; n次交換群はn個の置き換え全てを含み、群の二次演算は置き換えの連結

neutral element

単位元; ある演算に対して、もう一つの被演算子が結果と同じになる様な値

repeated combination

重複組み合わせ; あるnの大きさの集合から重複を許すm個の選択の数

isomorphic

同型; 例えばブール代数などで構造が同じで、それによって性質も同じ

proof by contradiction

背理法; 矛盾を使った証明の方法

真理表 (12 点)

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

D	E	G		G∧(E→D)∨¬D
F	F	F		T
F	F	T		T
F	T	F		T
F	T	T		T
T	F	F		F
T	F	T		FT
T	T	F		F
T	T	T		T

式の変換 (18 点)

次の式を、指定した演算子、関数や量記号だけを使うように変換しなさい。(必ずしも全ての演算子、関数や量記号が必要ない場合もある。)

番号	変換前の式	使える演算子、関数や量記号	変換後の式
例	¬A	NAND	NAND(A)
	(¬A∧¬B)	∨, ¬	¬(A∨B)
	A∨B	∧, ¬	¬(¬A∧¬B)
	A→B	∨, ¬	¬A∨B
	XOR(A,B)	∧, ∨, ¬	(¬A∧B)∨(A∧¬B)
	A↔B	∧, →	(A→B)∧(B→A)
	A↔B	∧, ∨, ¬	(A∧B)∨(¬A∧¬B)
	¬A→¬B	→	B→A
	¬∀x: P(x)	∃, ¬	∃x: ¬P(x)
	A∨A∧B	∨, ¬	A

ブール代数 (合計 18 点)

ブール代数の具体例 (10 点)

集合 {1, 3, 5, 7, 15, 21, 35, 105} でブール代数が作れる。 その場合に、ブール代数に必要な元と演算子はどういう風にすればいいのか書きなさい。

一般の書き方 (太字)	今回の場合
0 (零元)	1
1 (単位元)	105
∧	最大公約数
∨	最小公倍数
¬	105/n

ブール代数のハッセ図 (4 点)

上記のブール代数のハッセ図を書きなさい。

      105

15     21     35

3      5      7

       1

有限ブール代数と立方体 (4 点)

有限ブール代数と立方体の関係について簡単に説明しなさい。

有限ブール代数は全て n 次元の立方体の構造をもって、元の数が全ての場合 |B| = 2ⁿ

基数変換 (12 点)

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

番号	a の基数	a	b の基数	b
例	2	10101010	16	AA
	7	111	10	57
	16	256	10	598
	10	77	5	302
	9	1357	3	1101221
	3	12021111110	27	57DC
	2	1010101	10	85
	16	FDCB752	4	33313023131102
	8	6363	2	110011110011
	2	1111101011011110	16	FADE
	16	EF38B	2	11101111001110001011
	2	100101010011000100111001	8	45230471
	16	1F58D1	8	7654321

式の証明 (10 点)

n ≧ 4 の場合、2ⁿ < n ! を証明しなさい。

数学的帰納法を使って証明する。
基底: n=4: 2⁴ = 16 < 4! = 24
帰納: 2^k< k! を前提として、2^(k+1)< (k+1)! を証明できればいい。
2^(k+1)=2*2(k+1); (k+1)! = k!*(k+1); 2 < (k+1)
a<b かつ c<d ならば a*c < b*d なので、2^k< k! で証明完了。

関係の表現 (合計 15 点)

A={1, 2, 3, 4, 5, 6, 7, 8} の場合、 { (a, b) | a∈A ∧ b∈A ∧ a<b ∧ prime(a+b)>1 } の関係を下記の三つの表現形式で書きなさい。ただし、 prime(x) は x が素数という条件を表す。

表	行列	グラフ

関係の表現の特長 (6 点)

それぞれの関係の表現の特長を自分で考えて書きなさい。

表

3項関係などにも使える

行列

推移閉包など計算に便利

グラフ

直感的で分かりやすい

一般的の性質の書き方 (8 点)

二つの架空の演算子「∆」と「∇」で次の性質で考えられる書き方を全て列挙しなさい。

交換律

a∆b=b∆a, a∇b=b∇a

結合律

(a∆b)∆c=a∆(b∆c), a∇b∇c=a∇b∇c

分配律

a∆(b∇c)=(a∆b)∇(a∆c), (a∆b)∇c=(a∇c)∆(b∇c),
a∇(b∆c)=(a∇b)∆(a∇c), (a∇b)∆c=(a∆c)∇(b∆c)

論理回路の図 (8 点)

次の二つの論理式 S = NAND(A,B)∨¬C と T = XOR(NAND(A,B),C) に相当する論理回路を同じ図で書きなさい。

標準形 (10 点)

三つの変数 A、B と C のうちちょうど二つの変数が T だけのときに 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)

量記号の意味 (15 点)

次の論理記号を含まれる式の意味を簡単に説明しなさい。

∀x: 偶数(x) → 奇数(x+1)

全ての整数xにおいて、xが偶数でしたら、x+1 が基数。

∀x: (father(x, y) → parent(x, y))

全ての人間において、誰かの父であるならその人の親である。

∃y: ∀x: (y > x ∧ 素数 (y))

全ての整数 x より大きくかつ素数である整数が存在する (実はそんなことはない)。

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

背理法の元となる式: 「あるxでP(x)」でなければ、「全てのxでP(x)」は成立しない。

(S(b) ∧ ∀n≥b: S(n)→S(n+1)) → ∀n≥b: S(n)

数学的帰納法の元となる式: S が b で成立、しかも全ての b 以上の n において S(n) ならば S(n+1) の場合、全ての b 以上 の n において S(n)

記号論理 (合計 9 点)

記号論理の目的を簡単に説明しなさい。 (3 点)

記号で実世界のモデルを作って、記号演算だけでこのモデルについて推論する。

記号論理の種類を三つ列挙し、簡単に説明しなさい。 (6 点)

多値論理; 真と義以外に、例えば「分からない」という真理値も使う論理

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

二回述語論理: 述語の中でも述語を許す論理

関係の性質 (6 点)

下記の関係を、反射的かつ対称的でないかつ推移的かつ反対称的でない関係になるように完成しなさい。

	A	B	C	D
A	1	1	0	0
B	1	1	0	0
C	1	1	1	0
D	0	0	0	1