九工大 情報工学府 専門科目（知能情報工学） 2025年度 院試 過去問 解答例・解説（全2問）

問題1

$A=\{a,b,c\}$, $B=\{b,c\}$ とする。

$$2^A=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\},$$ $$2^B=\{\varnothing,\{b\},\{c\},\{b,c\}\}.$$ したがって $$2^A-2^B=\{\{a\},\{a,b\},\{a,c\},\{a,b,c\}\}.$$

また直積は、第1成分を $B$、第2成分を $A$ から取るので $$B\times A =\{(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}.$$

$A$ 上の二項関係は $A\times A$ の部分集合である。対称的な関係では、対角成分 $(a,a),(b,b),(c,c)$ は各々自由に選べ、非対角成分は $$\{(a,b),(b,a)\},\quad \{(a,c),(c,a)\},\quad \{(b,c),(c,b)\}$$ の3組について「両方入れる」か「両方入れない」かを選ぶ。よって個数は $$2^3\cdot 2^3=2^6=64.$$

反射的かつ反対称的な関係では、対角成分3個はすべて含める必要がある。各非対角ペアについては、両方向を同時に入れることはできないので、 $$\text{入れない},\quad \text{片方向だけ入れる},\quad \text{逆方向だけ入れる}$$ の3通りである。非対角ペアは3組あるから $$3^3=27.$$

$A$ から $B$ への全域的関数は、$A$ の3要素それぞれの行き先を $B$ の2要素から選ぶので $$2^3=8.$$

$2^A$ から $B$ への全域的関数の定義域は8要素、値域候補は2要素である。全射でない関数は、全ての定義域要素を $b$ に送るもの、全てを $c$ に送るものの2つだけである。

問題2

$R_1$ は $$xR_1y \Longleftrightarrow x+2y \text{ が偶数}$$ である。$2y$ は常に偶数だから、これは $x$ が偶数であることと同値である。したがって $$\begin{array}{c|c|l} \text{性質} & \text{判定} & \text{理由}\\ \hline \text{反射性} & \times & 1R_1 1 \text{ ではない}\\ \text{対称性} & \times & 2R_1 1 \text{ だが }1R_1 2\text{ ではない}\\ \text{反対称性} & \times & 2R_1 4,\ 4R_1 2 \text{ だが }2\ne 4\\ \text{推移性} & \circ & xR_1y,\ yR_1z \Rightarrow x\text{ は偶数} \Rightarrow xR_1z \end{array}$$

$R_2$ は $$xR_2y \Longleftrightarrow xy=3^{n-1}\quad (n\in\mathbb{Z}_{>0})$$ である。正の整数の積が3の冪になるには、$x,y$ がともに3の冪であることが必要十分である。これより $$\begin{array}{c|c|l} \text{性質} & \text{判定} & \text{理由}\\ \hline \text{反射性} & \times & 2R_2 2 \text{ ではない}\\ \text{対称性} & \circ & xy=3^{n-1}\Rightarrow yx=3^{n-1}\\ \text{反対称性} & \times & 1R_2 3,\ 3R_2 1 \text{ だが }1\ne 3\\ \text{推移性} & \circ & xR_2y,\ yR_2z \Rightarrow x,z\text{ も3の冪} \Rightarrow xR_2z \end{array}$$

問題3

判定は $$\begin{array}{c|cccccccc} & (3\text{-}1)&(3\text{-}2)&(3\text{-}3)&(3\text{-}4)&(3\text{-}5)&(3\text{-}6)&(3\text{-}7)&(3\text{-}8)\\ \hline \text{判定} & \times&\times&\circ&\circ&\times&\circ&\circ&\circ \end{array}$$ である。

補足する。(3-1)は同じ語を左右にコピーする条件を含み、有限オートマトンでは一般に記憶できない。(3-2)は $a$ と $b$ の個数差を無制限に覚える必要があるので非正規である。(3-3)は $a$ の個数を17で割った余りだけ覚えればよい。(3-4)は全体の $a$ の個数が偶数であることと同値であり正規である。(3-5)は $a$ と $b$ を対応させる非正規な構造を生成する。(3-6)は $b^*aa$ 型の言語なので正規である。(3-7)はNFAとDFAの同等性、(3-8)は正規言語の和集合に関する閉包性である。