「北海道大学大学院情報科学院修士課程入学試験」（令和6年8月実施）の情報理工学コース「情報数学」対策ページです。
分野別対策
情報数学
形式言語
参考にしたサイトは以下のとおり。
第2回 形式言語とオートマトン---「文」のルールを知り，機械に解釈させる _ 日経クロステック（xTECH）.html
参考にしたサイトは以下のとおり。
うさぎでもわかるオートマトンと言語理論 第02羽 非決定性オートマトン(NFA)の書き方・決定性オートマトン(DFA)への変換 _ 工業大学生ももやまのうさぎ塾.html
- 正規言語 (Regular Language)
- 正規言語は、有限オートマトン（有限状態機械）によって認識される言語である。
- 正規文法によって生成される。
- 正規文法の例
- 正規文法とは、生成規則が次のような形で表される文法である：
- \( A \rightarrow aB \) （左辺が1つの非終端記号、右辺が1つの終端記号と1つの非終端記号）
- \( A \rightarrow a \) （左辺が1つの非終端記号、右辺が1つの終端記号）
- 例えば、次のような生成規則からなる文法を考える：
- \( S \rightarrow aS \)
- \( S \rightarrow bS \)
- \( S \rightarrow \epsilon \) （\(\epsilon\)は空文字を表す）
- この文法は、次のような言語を生成する：
- \(\{a, b\}\)からなる任意の文字列（例えば、\(\epsilon\), \(a\), \(b\), \(aa\), \(ab\), \(ba\), \(bb\) など）
- 決定性有限オートマトン（DFA）や非決定性有限オートマトン（NFA）で認識可能である。
- \(a \rightarrow b\)において、\(b\)が終端記号、または終端記号の後に非終端記号を付ける。
- 例：\(L = { a^n | n ≥ 0 }\)(空文字列または任意の個数の \(a\) からなる言語。)
- 例：\(L = (ab)^*\)(\(ab\) の繰り返しからなる言語。)
- 文脈自由言語 (Context-Free Language, CFL)
- 文脈自由言語は、文脈自由文法（CFG）によって生成される言語である。
- 文脈自由文法は、1つの非終端記号が文字列に置き換えられる生成規則を持つ。
- 文脈自由文法の例
- 文脈自由文法は、生成規則が左辺に1つの非終端記号を持ち、右辺が任意の文字列であるような形をしている文法である。
- \( S \rightarrow aSb \)
- \( S \rightarrow \epsilon \)
- この文法は、次のような言語を生成する：
- 同数の \(a\) と \(b\) を持つ文字列（例えば、\(\epsilon\), \(ab\), \(aabb\), \(aaabbb\) など）
- この言語は、正規文法では表現できないが、文脈自由文法で生成可能である。
- プッシュダウンオートマトン（PDA）で認識可能である。
- スタックを使用して構造を保持するため、より複雑な構造を認識できる。
- \(a \rightarrow b\)において、\(a\)が非終端記号１つだけから成る。
- 例：\(L = { a^n b^n | n ≥ 0 }\)(同じ数の \(a\) と \(b\) からなる言語。)
- 例：\(ww^R | w ∈ {a, b}^*\)(任意の文字列 \(w\) とその逆順 \(w^R\) からなる言語。)
- 具体例
- 文脈依存言語 (Context-Sensitive Language, CSL)
- 文脈依存言語は、文脈依存文法（CSG）によって生成される言語である。
- 文脈依存文法の生成規則は、形式 \(α A β → α γ β\) を持ち、ここで \(A\) は非終端記号、\(α\)、\(β\)、および \(γ\) は任意の文字列である。
- 線形有界オートマトン（LBA）で認識可能である。
- メモリが有限で、入力の長さに比例して制約される。
- \(a \rightarrow b\)において、\(b\)の長さが\(a\)の長さ以上である。
- 例：\(L = { a^n b^n c^n | n ≥ 1 }\)(同じ数の \(a, b, c\) からなる言語。)
- クリーネ閉包
- アルファベット \(Σ = {a, b}\) に対して、そのクリーネ閉包（Kleene closure）、またはクリーネスター（Kleene star）とは、\(Σ\) から生成されるすべての有限長の文字列の集合を指す。
- 記号としては \(Σ*\) と表現される。
- 具体的には、\(Σ*\) は以下のようなすべての文字列を含む集合である：
- 空文字列\(ε\)
- \(a\) と \(b\) の任意の組み合わせ
- 文字列の長さはゼロ以上
- つまり、\(Σ*\) は次のような集合である：
- \(ε\)（空文字列）
- 長さ1の文字列： \(a, b\)
- 長さ2の文字列： \(aa, ab, ba, bb\)
- 長さ3の文字列： \(aaa, aab, aba, abb, baa, ...\)
- など、任意の有限長のすべての組み合わせ
- ポンピング定理
- 任意の正規言語 \(L\) について、あるポンピング長 \(p\)（自然数）が存在して、\(L\) のすべての文字列 \(s\) が以下の条件を満たす場合に限り、\(s \in L\) である：
- \(s\) の長さは \(p\) 以上である。
- \(s\) は \(s = xyz\) という形に分割できる。
- \(|xy| \leq p\)。
- \(y \neq \epsilon\)。
- 任意の非負整数 \(i\) に対して、文字列 \(xy^iz \in L\) である。
- 具体例
- \(L\) から \(s\) を選ぶ。ここで、\(s = 0^p 1^p\) とする。この文字列 \(s\) の長さは \(2p\) で、ポンピング補題の条件を満たす。
- ポンピング補題に従い、\(s\) を \(s = xyz\) の形に分割する。ここで、\(|xy| \leq p\) であり、\(y \neq \epsilon\) である。
- ポンピング補題により、任意の非負整数 \(i\) に対して、文字列 \(xy^iz\) が \(L\) に属するはずである。
- \(i = 0\) のとき、
\(xy^0z = xz = 0^a 0^{p-a-b} 1^p = 0^{p-b} 1^p\)である。ここで、\(b > 0\) なので、この文字列は \(0\) の数と \(1\) の数が一致せず、\(L\) に属さない。
- \(i = 2\) のとき、
\(xy^2z = xyyz = 0^a 0^{2b} 0^{p-a-b} 1^p = 0^{p+b} 1^p\)である。ここでも、\(b > 0\) なので、この文字列も \(0\) の数と \(1\) の数が一致せず、\(L\) に属さない。
- 正規表現
- 具体例
- アルファベット \(\Sigma = \{a, b\}\) とし、次の言語を表す正規表現を書け。なお、演算の優先順位（+ < · < *）を考慮して省略可能な場合には、括弧「()」を省略してもよい。
- \( ba \) で始まり、 \( ba \) で終わる系列からなる言語
- 最後から2番目の記号が \( b \) である系列からなる言語
- (1-2) の言語を受理する非決定性有限オートマトンを遷移図で示せ。なお、解答するオートマトンの状態を3つとし、開始状態は向きが斜めの矢印が指す状態とし、受理状態は2重丸とすること。
- (1-2) の言語を受理する決定性有限オートマトンを遷移図で示せ。なお、解答するオートマトンの状態を4つとし、開始状態は向きが斜めの矢印が指す状態とし、受理状態は2重丸とすること。
- 任意の正規表現が表す言語を受理する非決定性有限オートマトンが存在することを数学的帰納法を用いて構成的に証明せよ。
- (1-1) \(ba\) で始まり、\(ba\) で終わる系列からなる言語
- \( ba(a + b)^*ba \)
- (1-2) 最後から2番目の記号が \(b\) である系列からなる言語
- \( (a + b)^* b (a + b) \)
- (1-2) の言語を受理する非決定性有限オートマトン (NFA) は、次のような状態遷移図で表すことができる。
- \( q_0 \)（開始状態）: 任意の文字 \( a \) または \( b \) を受け入れて \( q_0 \) へ遷移、\( b \) を受け入れて \( q_1 \) へ遷移。
- \( q_1 \): 任意の文字 \( a \) または \( b \) を受け入れて \( q_2 \) へ遷移。
- \( q_2 \)（受理状態）: 遷移なし。
- NFAをDFAに変換するには、NFAの状態遷移表を書けばよい。
- その上で、今回は
\begin{align} q_0 : q_0, q_0 q_1 : q_1, q_0 q_2 : q_2, q_0 q_1 q_2 : q_3 \end{align}という対応付けを行なえばよい。
- (1-2) の言語を受理する決定性有限オートマトン (DFA) は、次のような状態遷移図で表すことができる。
- \( q_0 \)（開始状態）: \( a \) を受け入れて \( q_0 \) へ遷移、\( b \) を受け入れて \( q_1 \) へ遷移。
- \( q_1 \): \( a \) を受け入れて \( q_2 \) へ遷移、\( b \) を受け入れて \( q_3 \) へ遷移。
- \( q_2 \)（受理状態）: \( a \) を受け入れて \( q_0 \) へ遷移、\( b \) を受け入れて \( q_1 \) へ遷移。
- \( q_3 \)（受理状態）: \( a \) を受け入れて \( q_2 \) へ遷移、\( b \) を受け入れて \( q_3 \) へ遷移。
- 有限オートマトン、言語の受理
- 有限集合 \(Q\): 状態の集合。
- 有限アルファベット \(\Sigma\): 入力シンボルの集合。
- 遷移関数 \(\delta: Q \times \Sigma \rightarrow Q\): 状態と入力シンボルに基づく次の状態を決定する関数。
- 初期状態 \(q_0 \in Q\): 計算の開始状態。
- 受理状態の集合 \(F \subseteq Q\): 計算が終了したとき、この集合に含まれる状態であれば入力文字列は受理される。
問題
ある言語が正規言語(正則言語ともいう)であるとはどういうことかを説明し、正規言語であるような言語を一つ与えよ。 さらに、ある言語が文脈自由言語であるとはどういうことかを説明し、文脈自由言語であるが、正規言語ではないような言語を一つ与えよ。
解答
正規言語（正則言語ともいう）とは、有限オートマトンによって認識される言語を指す。つまり、正規言語は、有限の状態遷移を持つオートマトンを用いて、言語の文字列がその言語に属するかどうかを判定できる言語である。また、正規表現でも定義可能な言語でもある。例えば、正規言語の一例として、aの0回以上の繰り返しを含む言語 \(\{a^n \mid n \geq 0\}\) が挙げられる。
一方、文脈自由言語とは、文脈自由文法によって生成される言語を指す。文脈自由文法は、生成規則が左辺に1つの非終端記号を持ち、右辺が任意の文字列であるような形をしている。この文法によって生成される言語は、一般的に、構文解析が容易であるためプログラミング言語などでよく使われる。文脈自由言語であるが正規言語ではない例として、 \(\{a^n b^n \mid n \geq 0\}\) という言語がある。この言語は、aの数とbの数が同じである文字列を含むが、有限オートマトンでは認識できないため、正規言語ではない。
問題：言語 \(L = \{0^n 1^n \mid n \geq 0\}\) が正規言語でないことをポンピング定理を使って証明せよ。
仮に、言語 \(L = \{0^n 1^n \mid n \geq 0\}\) が正規言語であると仮定する。すると、ポンピング長 \(p\) が存在するはずである。
\(|xy| \leq p\) なので、\(x\) と \(y\) はすべて \(0\) から構成される。具体的には、\(x = 0^a\)、\(y = 0^b\)、\(z = 0^{p-a-b} 1^p\) という形になる。ここで、\(a\) と \(b\) は非負整数であり、\(a + b \leq p\)、かつ \(b > 0\) である。
しかし、\(i \neq 1\) の場合を考える。
これらの例から、\(xy^iz\) が \(L\) に属さない \(i\) が存在することが示される。したがって、ポンピング補題の条件を満たさないため、仮定に矛盾する。
したがって、言語 \(L = \{0^n 1^n \mid n \geq 0\}\) は正規言語ではないことが証明された。
問題
オートマトンと正規表現に関する以下の問いに答えよ。なお、アルファベット \(\Sigma = \{a_1, \dots, a_k\}\) 上の正規表現を、以下の (i), (ii) で定義する。
(i) \( a_1, \dots, a_k, \epsilon \)（空列）, \(\emptyset\)（空集合）は正規表現であり、それぞれ集合 \(\{a_1\}, \dots, \{a_k\}, \{\epsilon\}, \emptyset\) を示す。
(ii) \( r \) と \( s \) が正規表現のとき、\( r + s \), \( r \cdot s \), \( r^* \) は正規表現であり、集合演算として \( + \) はそれぞれ和集合、連接、クリーネ閉包に対応する。
また、決定性有限オートマトンは \( (Q, \Sigma, \delta, q_0, F) \) で表される。ただし、\( Q \) は状態の有限集合、\( \Sigma \) は有限のアルファベット、\( \delta \) は遷移関数、\( q_0 \) は開始状態、\( F \) は最終状態の集合である。非決定性有限オートマトンも空列 \(\epsilon\) を用いて同様に \( (Q, \Sigma \cup \{\epsilon\}, \delta, q_0, F) \) で表される。
(1)の解答
(2)の解答
(3)の解答
(4)の解答
問題
有限オートマトンの定義について述べよ。また、有限オートマトンによって受理される言語を正規言語という。 ここで、「言語が受理される」とはどのような意味か、有限オートマトンの定義を踏まえて説明せよ。 さらに、アルファベット \(\Sigma\) 上の言語 \(L \subseteq \Sigma^*\)（\(\Sigma^*\) は \(\Sigma\) の反射的推移閉包）が有限オートマトンで受理されるとき、 その補集合 \(\overline{L} = \Sigma^* - L\) も有限オートマトンで受理されるかどうか、理由を添えて答えよ。
解答
有限オートマトン（有限状態機械とも呼ばれる）は、入力文字列に応じて状態を遷移し、最終的に受理状態に到達するかどうかを判定するモデルである。有限オートマトンは次のような構成要素から成り立つ：
言語が受理される意味 :
有限オートマトンがある言語 \(L\) を受理するということは、そのオートマトンが入力文字列を読み込んだとき、最終的に受理状態に到達する文字列の集合が \(L\) であることを意味する。言い換えると、有限オートマトンが受理する言語とは、オートマトンがその文字列を受理状態で終了する全ての文字列の集合である。
補集合も有限オートマトンで受理されるか :
有限オートマトンが受理する言語が \(L\) であるとき、その補集合 \(\overline{L}\) も有限オートマトンで受理される。これは、すべての状態遷移が明示的に決定されているため、受理状態を非受理状態に、非受理状態を受理状態に変更するだけで、補集合を受理する新たな有限オートマトンを構成できるからである。
したがって、有限オートマトンで受理される言語 \(L\) の補集合 \(\overline{L}\) も有限オートマトンで受理されることが証明できる。これは、正規言語の閉包性の一例であり、正規言語の補集合もまた正規言語であることを意味する。
論理式
参考にしたサイトは以下のとおり。
カルノー図って何？2,3,4変数の論理式の簡単化のやり方を丁寧に解説！ – 「なんとなくわかる」大学の数学・物理・情報.html
- 具体例
- １つ目の論理式について、真理値表は以下のようになる。
x y z ¬ y x → ¬ y ¬ y → z (x → ¬ y) → (¬ y → z) x ∨ ¬ y ((x → ¬ y) → (¬ y → z)) ∧ (x ∨ ¬ y) 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 - ２つ目の論理式について、真理値表は以下のようになる。
x y z y ∧ z x → (y ∧ z) (y ∧ z) → x (x → (y ∧ z)) ∧ ((y ∧ z) → x) 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 - 積和標準形を作るには、全体の真理値が１になる最小項をORでつなげばよい。
よって、
- １つ目の論理式の積和標準形は、
\begin{align} &(\neg x \land \neg y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land \neg z) \lor (x \land y \land z) \\ = &(\neg y \land z) \lor (x \land y) \end{align}
- ２つ目の論理式の積和標準形は、
\begin{align} &(\neg x \land \neg y \land \neg z) \lor (\neg x \land \neg y \land z) \lor (\neg x \land y \land \neg z) \lor (x \land y \land z) \\ = &(\neg x \land \neg y) \lor (\neg x \land \neg z) \lor (x \land y \land z) \end{align}
- １つ目の論理式の積和標準形は、
- 和積標準形を作るには、全体の真理値が０になる最大項をANDでつなげばよいが、積和標準形を二重否定してド・モルガン即を使うだけでよい。
よって、
- １つ目の論理式の積和標準形は、
\begin{align} &\neg(\neg((\neg y \land z) \lor (x \land y))) \\ = &\neg(\neg(\neg y \land z) \land \neg(x \land y)) \\ = &\neg((y \lor \neg z) \land (\neg x \lor \neg y)) \\ = &\neg((y \land \neg x) \lor (y \land \neg y) \lor (\neg z \land \neg x) \lor (\neg z \land \neg y)) \\ = &\neg((y \land \neg x) \lor (\neg z \land \neg x) \lor (\neg z \land \neg y)) \\ = &\neg((y \land \neg x) \lor (\neg z \land \neg y)) \text{ ∵下のカルノー図を用いた} \\ = &(\neg y \lor x) \land (z \lor y) \end{align}
yz 00 01 11 10 x 0 1 0 1 1 1 1 0 0 0 - ２つ目の論理式の積和標準形は、
\begin{align} &(\neg x \land \neg y) \lor (\neg x \land \neg z) \lor (x \land y \land z) \\ = &\neg(\neg((\neg x \land \neg y) \lor (\neg x \land \neg z) \lor (x \land y \land z))) \\ = &\neg((x \lor y) \land (x \lor z) \land (\neg x \lor \neg y \lor \neg z)) \\ = &\neg((\neg x \land z) \lor (\neg x \land y) \lor (\neg y \land x) \lor (\neg y \land z) \lor (\neg z \land x) \lor (\neg z \land y)) \\ = &\neg((\neg x \land z) \lor (\neg y \land x) \lor (\neg z \land y)) \text{ ∵下のカルノー図を用いた} \\ = &(x \lor \neg z) \land (y \lor \neg x) \land (z \lor \neg y) \\ \end{align}
yz 00 01 11 10 x 0 0 1 1 1 1 1 1 0 1
- １つ目の論理式の積和標準形は、
- \(\neg P = P | P\)
- \(P \land Q = (P|Q)|(P|Q)\)
- \(P \lor Q = (P|P)|(Q|Q)\)
以下の命題論理式それぞれについて、その積和標準形 (DNF; 選言標準形) および和積標準形 (CNF; 連言標準形) を求めよ。ただし、∨ は論理和、∧ は論理積、¬ は否定、→ は含意を表す。なお、どの論理式が求めた DNF や CNF であるかを明示すること。
1. \(\left((x \rightarrow \neg y) \rightarrow (\neg y \rightarrow z)\right) \land (x \lor \neg y)\)
2. \((x \rightarrow y \land z) \land (y \land z \rightarrow x)\)
問題
3つの論理結合子 \(\neg\), \(\land\), \(\lor\) を含む論理式によって、すべての真理関数（n個の真理値 \(\{1, 0\}^n\) を入力とし真理値 \(\{1, 0\}\) を出力する関数）を表せる（十全である）ことがわかっている。これを利用して、以下の真理値表で表現される論理結合子 \( P \mid Q \) 1つだけで十全であることを示せ。
| P | Q | P | Q |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
解答
論理結合子|１つだけで十全であることを示すには、|が3つの論理結合子 \(\neg\), \(\land\), \(\lor\) を表現可能であることを示せばよい。
3つの論理結合子 \(\neg\), \(\land\), \(\lor\)は、それぞれ以下のように表すことができる（|がNANDであることに気づくと楽）。
命題論理
参考にしたサイトは以下のとおり。
「正直村と嘘つき村」正直村に行くには！？｜レベルは難しい！高校生向けの答え付きなぞなぞ _ なぞっち.html
- 具体例
- 以下の3つの命題 P、Q、R を考える。
- P: 「A村は右の道に繋がっている。」
- Q: 「村人 \( \alpha \) はA村の住民である。」
- R: 「村人 \( \alpha \) は、右の道に繋がっている村の住民である。」
- 命題 P と論理的に同値な命題を、命題 Q と命題 R から作られた合成命題（論理和 \( \lor \)、論理積 \( \land \)、否定 \( \neg \) を使って合成された命題）によって表せ。
- 村人 \( \alpha \) 自身に命題 R の真偽を答えてもらう。ただし、A村の住民は常に正しい答えを言い、B村の住民は常に間違った答えを言うものとする。このとき、村人 \( \alpha \) の答えからA村が右左どちらの道に繋がっているかを知ることができる理由を説明せよ。
- \( Q \) は「村人 \( \alpha \) はA村の住民である」
- \( R \) は「村人 \( \alpha \) は、右の道に繋がっている村の住民である」
- \((\forall x \in \textbf{P} \, \exists y \in \textbf{N} \, p(x, y)) \rightarrow (\exists y \in \textbf{N} \, \forall x \in \textbf{P} \, p(x, y))\)
- \((\forall x \in \textbf{P} \, \exists y \in \textbf{P} \, p(x, y)) \rightarrow (\exists y \in \textbf{P} \, \forall x \in \textbf{P} \, p(x, y))\)
命題論理に関する以下の問いに答えよ。
左右2つに分かれている道があり、一方はA村へ、もう一方はB村に繋がっている。A村、B村どちらかの村人 \( \alpha \) が、その分岐点に立っている。
(1)の解答
命題 \( P \) は「A村は右の道に繋がっている」という命題であり、これは次のように命題 \( Q \) と \( R \) を使って表すことができる。
まず、村人 \( \alpha \) がA村の住民であれば、\( R \) は \( P \) と同値であり、村人 \( \alpha \) がB村の住民であれば、\( R \) は \( \neg P \) と同値である。したがって、命題 \( P \) は次の合成命題で表せる。
(2)の解答
村人 \( \alpha \) がA村の住民であれば、命題 \( R \) は真実を反映するため、村人 \( \alpha \) が「はい」と答えればA村は右の道に繋がっており、「いいえ」と答えればA村は左の道に繋がっている。
一方、村人 \( \alpha \) がB村の住民であれば、村人は常に嘘をつくため、命題 \( R \) の答えは逆になる。つまり、村人 \( \alpha \) が「はい」と答えた場合、実際にはA村は左の道に繋がっており、「いいえ」と答えた場合、A村は右の道に繋がっている。
したがって、村人 \( \alpha \) の答えが「はい」であれば、実際にA村は右の道に繋がっており、「いいえ」であればA村は左の道に繋がっていることがわかる。
問題
すべての正の整数からなる集合を N、すべての素数からなる集合を P とし、述語 p(x, y) は「x は y で割り切れる」を意味するとき、1 は素数ではないことに注意して、つぎの論理式の真偽を説明せよ。ただし、∀ は全称記号、∃ は存在記号である。
(i)の解答
左側の命題（前件）は「全ての素数 \( x \) に対して、ある自然数 \( y \) が存在し、\( x \) は \( y \) で割り切れる」という意味である。実際、どの素数 \( x \) に対しても、少なくとも \( y = 1 \) を選べば \( p(x, y) \) は真である。しかし、右側の命題（後件）は「ある自然数 \( y \) が存在し、全ての素数 \( x \) に対して \( p(x, y) \) が真である」という意味であり、これは \( y \) が全ての素数で割り切れる必要があることを意味するが、そのような自然数 \( y \) は存在しないため、命題全体として偽である。
(ii)の解答
左側の命題（前件）は「全ての素数 \( x \) に対して、ある素数 \( y \) が存在し、\( x \) は \( y \) で割り切れる」という意味である。素数 \( x \) が他の素数 \( y \) で割り切れる場合、\( x = y \) の場合を除いて、そのような \( y \) は存在しないため、この命題は真である。しかし、右側の命題（後件）は「ある素数 \( y \) が存在し、全ての素数 \( x \) に対して \( p(x, y) \) が真である」という意味であり、これは \( y \) が全ての素数で割り切れる必要があるが、そのような素数 \( y \) は存在しないため、命題全体として偽である。
距離
参考にしたサイトは以下のとおり。
距離空間の定義と6つの具体例～ユークリッド・マンハッタン距離～ _ 数学の景色.html
- 具体例
- \( \mathbb{R}^2 \) の任意の3点、\( A = (a_1, a_2) \), \( B = (b_1, b_2) \), \( C = (c_1, c_2) \) に対して、\( d(A, C) \leq d(A, B) + d(B, C) \) が成り立つことを示せ。
- 関数 \( d \) が距離関数であることを示せ。ただし、距離関数とは任意の3点 \( A, B, C \) に対して以下の i)～iii) を満たす関数である。
- i) \( d(A, B) \geq 0 \) であり、\( d(A, B) = 0 \) \(\Leftrightarrow\) \( A = B \)
- ii) \( d(A, B) = d(B, A) \)
- iii) \begin{align} d(A, C) \leq d(A, B) + d(B, C) \text{（三角不等式）} \end{align}
- 新たに関数 \( \hat{d} : \mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R} \) を以下のように定義する。
- i) 非負性および同一性: \( d(A, B) \geq 0 \) であり、\( d(A, B) = 0 \) \(\Leftrightarrow\) \( A = B \)。
- ii) 対称性: \( d(A, B) = d(B, A) \)。
- iii) 三角不等式: \( d(A, C) \leq d(A, B) + d(B, C) \) が成り立つこと。
- i) 非負性および同一性: \begin{align} d(A, B) = \max\{|a_1 - b_1|, |a_2 - b_2|\} \geq 0 \end{align}であり、\( d(A, B) = 0 \) のとき、\( A = B \) である。
- ii) 対称性: \( d(A, B) = d(B, A) \) は明らかに成り立つ。
- iii) 三角不等式: (1) で証明したように、三角不等式が成り立つ。
- i) 非負性および同一性: \( \hat{d}(A, B) \geq 0 \) であるが、\( \hat{d}(A, B) = 0 \) のとき、\( A = B \) であるとは限らない。したがって、この条件は満たされない。
- ii) 対称性: \( \hat{d}(A, B) = \hat{d}(B, A) \) である。
- iii) 三角不等式: \( \hat{d}(A, C) \leq \hat{d}(A, B) + \hat{d}(B, C) \) が成り立つ場合があるが、同一性が満たされないため、距離関数ではない。
問題
実数の組の全体 \( \mathbb{R}^2 \) において、\( \mathbb{R}^2 \) の2点、\( A = (a_1, a_2) \), \( B = (b_1, b_2) \) に対して関数 \( d: \mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R} \) を以下のように定義する。
このとき以下の問いに答えよ。
この \( \hat{d} \) は距離関数であるか、距離関数である場合にはそれを示し、距離関数でない場合にはその理由を述べよ。
(1)の解答
関数 \( d: \mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R} \) は次のように定義される：
この関数が三角不等式 \( d(A, C) \leq d(A, B) + d(B, C) \) を満たすことを示すために、以下の成分ごとの不等式を確認する：
これは三角不等式の性質によって常に成り立つ。したがって、
が成り立ち、
が示される。
(2)の解答
距離関数であるためには、以下の3条件を満たす必要がある：
これらの条件を確認する：
したがって、関数 \( d \) は距離関数である。
(3)の解答
新しい関数
したがって、関数 \( \hat{d} \) は距離関数ではない。
二項関係・同値関係
参考にしたサイトは以下のとおり。
- 具体例
- 二項関係 \( x \equiv y \) が同値関係であることを証明せよ。
- 同値関係 \( x \equiv y \) に対して、\(\mathbb{Z}\) の \(\equiv\) による商集合（すなわち、すべての同値類の集合） \(\mathbb{Z}/\equiv\) を示せ。
- 反射律：任意の \( x \in \mathbb{Z} \) について、\( x \equiv x \)
- 対称律：任意の \( x, y \in \mathbb{Z} \) について、\( x \equiv y \) ならば \( y \equiv x \)
- 推移律：任意の \( x, y, z \in \mathbb{Z} \) について、\( x \equiv y \) かつ \( y \equiv z \) ならば \( x \equiv z \)
- 任意の \( x \in \mathbb{Z} \) について、\( x = x + 3 \cdot 0 \)が成り立つ。したがって、\( x \equiv x \) である。
- 任意の \( x, y \in \mathbb{Z} \) について、\( x \equiv y \) ならば、\( x = y + 3k \)を満たす \( k \in \mathbb{Z} \) が存在する。 このとき、\( y = x - 3k \)であり、\( -k \in \mathbb{Z} \) なので、\( y \equiv x \) である。
- 任意の \( x, y, z \in \mathbb{Z} \) について、\( x \equiv y \) かつ \( y \equiv z \) ならば、\( x = y + 3k \)および\( y = z + 3m \)を満たす \( k, m \in \mathbb{Z} \) が存在する。 このとき、\( x = (z + 3m) + 3k = z + 3(m + k) \)であり、\( m + k \in \mathbb{Z} \) なので、\( x \equiv z \) である。
- \([0] = \{ \ldots, -6, -3, 0, 3, 6, \ldots \}\)
- \([1] = \{ \ldots, -5, -2, 1, 4, 7, \ldots \}\)
- \([2] = \{ \ldots, -4, -1, 2, 5, 8, \ldots \}\)
- 反射律：任意の \( x \in A \) に対して、\( xRx \) が成り立つ。
- 対称律：任意の \( x, y \in A \) に対して、\( xRy \) ならば \( yRx \) が成り立つ。
- 推移律：任意の \( x, y, z \in A \) に対して、\( xRy \) かつ \( yRz \) ならば \( xRz \) が成り立つ。
- 自然数 \( x, y \) に対し、
\begin{align} xRy \iff |x - y| = 6 \end{align}と定義すれば \( R \) は自然数の集合上の二項関係となる。このとき \( R \) は、反射律、対称律、推移律を満たすか、各々の性質について、満たす場合は証明し、満たさない場合は反例をあげよ。
- （1）の二項関係 \( R \) を含む最小の同値関係を求めよ。
- \( x = 1, y = 7, z = 13 \) の場合
- \( |1 - 7| = 6 \), \( |7 - 13| = 6 \)
- しかし、\( |1 - 13| = 12 \) であり、6 ではない。
整数全体の集合を \(\mathbb{Z}\) とし、\(\mathbb{Z}\) 上での二項関係 \( x \equiv y \) は、\( x = y + 3k \) を満たすような \( k \in \mathbb{Z} \) が存在することを表すとする。この二項関係 \(\equiv\) について、以下の問いに答えよ。
同値関係は、以下の3つの性質を満たす必要がある：
これらの性質を順に確認する。
反射律以上より、二項関係 \( x \equiv y \) は同値関係であることが示された。
2. 同値関係 \( x \equiv y \) に対して、\(\mathbb{Z}\) の \(\equiv\) による商集合 \(\mathbb{Z}/\equiv\) を示せ同値関係 \( x \equiv y \) による同値類は、\( 3 \) の倍数の差を持つ整数の集合である。具体的には、任意の \( x \in \mathbb{Z} \) について、次のように同値類を表すことができる：
整数全体の集合 \(\mathbb{Z}\) に対して、同値類は次の3つに分類される：
したがって、\(\mathbb{Z}/\equiv\) は次のように表せる：
\(\mathbb{Z}/\equiv = \{ [0], [1], [2] \}\)
問題
二項関係に関する以下の問いに答えよ。
集合 \( A \) 上の二項関係 \( R \) は以下の3つの性質を満たすとき、同値関係であるという。
(1)の解答
反射律とは、任意の \( x \in A \) に対して \( xRx \) が成り立つことである。つまり、この場合は \( |x - x| = 6 \) が成り立つかどうかを確認する必要がある。
これは常に 0 であり、6 ではない。したがって、この関係 \( R \) は反射律を満たさない。
(2)の解答
反例: 任意の \( x \in A \) に対して \( xRx \) が成り立たない。例えば、\( x = 1 \) の場合、
対称律とは、任意の \( x, y \in A \) に対して \( xRy \) ならば \( yRx \) が成り立つことである。つまり、この場合は \( |x - y| = 6 \) ならば \( |y - x| = 6 \) であるかどうかを確認する必要がある。
これは常に成り立つため、対称律は満たされる。
推移律とは、任意の \( x, y, z \in A \) に対して \( xRy \) かつ \( yRz \) ならば \( xRz \) が成り立つことである。つまり、この場合は \( |x - y| = 6 \) かつ \( |y - z| = 6 \) ならば \( |x - z| = 6 \) であるかどうかを確認する必要がある。
反例:
したがって、この関係は推移律を満たさない。
(2)の解答
\( R \) を含む最小の同値関係を求める。
同値関係とは、反射律、対称律、推移律をすべて満たす関係である。\( R \) を含む最小の同値関係を求めるには、次のように考える。
まず、\( R \) に反射律を加えるためには、各 \( x \in A \) に対して \( xRx \) を加える必要がある。次に、推移律を加えるために、すべての関係 \( xRy \), \( yRz \) に対して \( xRz \) を加える必要がある。
したがって、最小の同値関係 \( S \) は次のように定義される。
完全二部グラフ
参考にしたサイトは以下のとおり。
うさぎでもわかる離散数学（グラフ理論） 第9羽 グラフの基礎3 _ 工業大学生ももやまのうさぎ塾.html
- 具体例
- \( K_{3,2} \) での長さ最大の単純パスの個数を求めよ。
- \( K_{m,2} \)（\( m > 2 \)）での長さ最大の単純パスの個数を求めよ。
- \( K_{m,n} \)（\( m > n \)）での長さ最大の単純パスの個数を求めよ。
- \( K_{n,n} \) での長さ最大の単純パスの個数を求めよ。
- \(K_{3, 2}\)においては、長さ最大の単純パスは必ず\(V_1 \rightarrow V_2 \rightarrow V_1 \rightarrow V_2 \rightarrow V1\)の順番で頂点をたどって形成される。
- したがって、\(\frac{1}{2} \times 3 \times 2 \times 2 \times 1 \times 1 = 6\)通りある。
- \(K_{m, 2} \text{ m > 2 }\)においても、長さ最大の単純パスは必ず\(V_1 \rightarrow V_2 \rightarrow V_1 \rightarrow V_2 \rightarrow V1\)の順番で頂点をたどって形成される。
- したがって、
\begin{align}\frac{1}{2} \times m \times 2 \times (m-1) \times 1 \times (m-2) = m(m-1)(m-2)\end{align}通りある。
- \(K_{m, n} \text{ m > n }\)においても、長さ最大の単純パスは必ず\(V_1 \rightarrow V_2 \rightarrow V_1 \rightarrow V_2 \cdots\)の順番で頂点をたどって形成される。
- したがって、
\begin{align} &\frac{1}{2} \times m \times n \times (m-1) \times (n-1) \times (m-2) \times (n-2) \times \cdots \times (m-n-1) \times 1 \times (m-n) \\ = &\frac{1}{2} \times m \times (m-1) \times (m-2) \times (m-n) \times \cdots \times n \times (n-1) \times (n-2) \times \cdots \times 1 \\ = &\frac{m!n!}{(m-n-1)!} \end{align}
- \(V_1\)からスタートするとき、これまでの議論より、\(\frac{n!n!}{2}\)通り。
- \(V_2\)からスタートする場合も同数あるので、全部で\(n!n!\)通り。
無向グラフ \( G = (V, E) \) が \( V = V_1 \cup V_2 \), \( V_1 \cap V_2 = \emptyset \), \(|V_1| = m\), \(|V_2| = n\), \( E = V_1 \times V_2 \) を満たすときに、このグラフを完全二部グラフ \( K_{m,n} \) とよぶ。ここで、頂点集合を \( V = \{v_1, v_2, \dots, v_{m+n}\} \) とする。この完全二部グラフ \( K_{m,n} \) において、以下を満たす頂点の系列 \( v_{i_0}, v_{i_1}, \dots, v_{i_k} \) を長さ \( k \) の単純パスとよぶ。ここで、\( v_{ij} \in V \) である。
任意の \( 0 \leq j < k \) に対して \( (v_{ij}, v_{i_{j+1}}) \in E \) が成立し、任意の \( 0 \leq j' \leq k \) に対して \( v_{ij} \neq v_{ij'} \) が成立する。
なお、2つの系列 \( v_{i_0}, v_{i_1}, \dots, v_{i_k} \) と \( v_{i_k}, v_{i_{k-1}}, \dots, v_{i_0} \) は同じ単純パスとみなす。
問１
問２
問３
問４
イデアル
参考にしたサイトは以下のとおり。
ユークリッドの互除法(大きい数の最大公約数) - 小野研究室.html
- 具体例
- 正の整数 \( a_1, a_2, \dots, a_k \) に対して、
\begin{align} I = \{c_1a_1 + c_2a_2 + \dots + c_k a_k \mid c_1, c_2, \dots, c_k \in \mathbb{Z} \} \end{align}とおく。このとき、\( I \) は \( \mathbb{Z} \) のイデアルであることを証明せよ。
- \( I = d\mathbb{Z} \) となる正の整数 \( d \) が存在するとき、この \( d \) は \( a_1, a_2, \dots, a_k \) の最大公約数になることを証明せよ。
- 正の整数 \( a_1, a_2, \dots, a_k \) に対して、任意の \( j \) (2 ≤ j ≤ k) について、\( a_j \) を \( a_1 \) で割ったときの商を \( q_j \)、余りを \( r_j \) とするとき、次が成立つことを示せ。
\begin{align} \text{gcd}(a_1, a_2, \dots, a_k) = \text{gcd}(a_1, r_2, \dots, r_k) \end{align}
- (3) を利用することで gcd(8413, 10561, 11993) を求めよ。解答には (3) を利用した過程を示すこと。
- \( 0 \in I \) であること：
- 任意の整数 \( c_1, c_2, \dots, c_k \) に対して \( c_1 = c_2 = \dots = c_k = 0 \) を選べば、
\begin{align} 0 = 0 \times a_1 + 0 \times a_2 + \dots + 0 \times a_k \in I \end{align}であるため、\( 0 \in I \) が成立する。
- \( x, y \in I \) ならば、 \( x + y \in I \) であること：
- \( x, y \in I \) であれば、それぞれ
\begin{align} x = c_1a_1 + c_2a_2 + \dots + c_ka_k \\ y = d_1a_1 + d_2a_2 + \dots + d_ka_k \end{align}で表される。したがって、\begin{align} x + y = (c_1 + d_1)a_1 + (c_2 + d_2)a_2 + \dots + (c_k + d_k)a_k \in I \end{align}であり、\( x + y \) も \( I \) に属する。
- 任意の \( c \in \mathbb{Z} \) に対して、 \( cx \in I \) であること：
- \( x \in I \) であれば、
\begin{align} x = c_1a_1 + c_2a_2 + \dots + c_ka_k \end{align}で表される。したがって、\begin{align} cx = (cc_1)a_1 + (cc_2)a_2 + \dots + (cc_k)a_k \in I \end{align}であり、\( cx \) も \( I \) に属する。
- \(c_1, c_2, \cdots, c_k\)が任意の整数であることに注意すると、\(a_1, a_2, \cdots, a_k \in I\)である。
- したがって、
\begin{align} a_1 = d b_1, a_2 = d b_2, \cdots a_k = d b_k \end{align}とかける。
- ここで、\(b_1, b_2, \cdots b_k \in \mathbb{Z}\)である。
- よって、\(d\)は\(a_1, a_2, \cdots, a_k\)の公約数である。
- \(m\)を正の整数\(a_1, a_2, \cdots, a_k\)の公約数とすると、
\begin{align} a_1 = m a_1', a_2 = m a_2', \cdots a_k = m a_k' \end{align}とかける。
- ここで、\(a_1', a_2', \cdots a_k' \in \mathbb{Z}\)である。
- 一方、
\begin{align} d = c_1 a_1 + c_2 a_2 + \cdots + c_k a_k \end{align}とかけるから、\begin{align} d = m(c_1 a_1' + c_2 a_2' + \cdots c_k a_k') \end{align}となる。
- すなわち、\(m\)は\(d\)の約数である。
- ゆえに、\(d\)は\(a_1, a_2, \cdots, a_k\)の最大公約数である。
- ユークリッドの互除法より、\(gcd(a_j, a_1) = gcd(a_1, r_j)\)である。
- 簡単に、\(k = 3\)の場合を考える。
- 先の式から、以下が成り立つ。
\begin{align} gcd(a_1, a_2) = gcd(a_1, r_2) \\ gcd(a_1, a_3) = gcd(a_1, r_3) \end{align}
- \(a_1, a_2, a_3\)の最大公約数は「\(a_1, a_2\)の最大公約数」と「\(a_1, a_3\)の最大公約数」の最大公約数であることを用いると、上の２式から以下の式が得られる。
\begin{align} gcd(a_1, a_2, a_3) = gcd(a_1, r_2, r_3) \end{align}
- 一般の\(k\)に対して、同様に\(a_1, a_2, \cdots, a_k\)の最大公約数が「\(a_1, a_2\)の最大公約数」と「\(a_1, a_3\)の最大公約数」と\(\cdots\)と「\(a_1, a_k\)の最大公約数」の最大公約数であることを用いれば、所望の式を得ることができる。
-
\begin{align} &gcd(8413, 10561, 11993) \\ = &gcd(8413, 2148, 3580) \\ = &gcd(1969, 2148, 1432) \\ = &gcd(537, 716, 1432) \\ = &gcd(537, 179, 358) \\ = &gcd(0, 179, 0) \\ = &179 \end{align}
問題
(1)の解答
イデアルの定義に従って、以下の条件を満たすことを示す：
以上の条件が満たされるため、\( I \) は \( \mathbb{Z} \) のイデアルであることが示された。
(2)の解答
(3)の解答
(4)の解答
集合
- 具体例
- \(m = -l\)
- \(n = l\)
問題
集合 \(A = \{5l \mid l \in \mathbb{Z}\}\) と集合 \(B = \{10m + 15n \mid m, n \in \mathbb{Z}\}\) が等しいことを示せ. ただし, \(\mathbb{Z}\) は整数の集合である.
解答
この問題は、集合 \(A\) と集合 \(B\) が等しいこと、すなわち任意の要素が \(A\) に属するならば \(B\) にも属し、逆に任意の要素が \(B\) に属するならば \(A\) にも属することを示す必要がある。
1. \(A \subseteq B\) であることの証明任意の \(a \in A\) を取る。\(a\) は \(A\) の定義より \(a = 5l\) （ただし \(l \in \mathbb{Z}\)）である。
\(B\) の要素は \(b = 10m + 15n\) であり、ここで \(m\) と \(n\) は以下のように選ぶことができる:
すると、
したがって、\(a = 5l\) は \(B\) の元となる。従って \(A \subseteq B\) である。
2. \(B \subseteq A\) であることの証明任意の \(b \in B\) を取る。\(b\) は \(B\) の定義より \(b = 10m + 15n\) （ただし \(m, n \in \mathbb{Z}\)）である。
この式を分解すると、
\(l = 2m + 3n\) と置けば、\(l\) は整数であるから、\(b\) は \(5l\) の形を取る。したがって、\(b \in A\) であることが示された。
結論以上より、集合 \(A\) と集合 \(B\) は互いに包含関係を持つ。従って、\(A = B\) であることが証明された。