大阪大学 情報科学研究科 情報工学 2020年8月実施 離散構造

Author

祭音Myyura

Description

非負の整数全体の集合を と書く。 実数 に対して、 を超えない最大の整数を と書く。 任意の に対して、実区間 から への写像 (mapping) を以下の漸化式 (recurrence relation) により定める。

以下の各問に答えよ。

(1) 次の値をそれぞれ求めよ：, , 。

(2) 命題 (proposition)「ある が存在し は単射 (injective) である」の真偽を判定せよ。その理由を述べよ。

(3) 命題「 が正かつ偶数ならば は全射 (surjective) である」の真偽を判定せよ。その理由を述べよ。

(4) における以下の二項関係 (binary relation) を考える。

• (4-1) が反射的 (reflexive) であるかを判定せよ。その理由を述べよ。
• (4-2) が反対称的 (antisymmetric) であるかを判定せよ。その理由を述べよ。

(5) 方程式

を考える。以下の各問に答えよ。

• (5-1) 非負の実数 が方程式 (i) の解であると仮定する。ある実数 が存在し が成り立つことを示せ。
• (5-2) 方程式 (i) の解を一つ求めよ。

(6) 方程式

の解を一つ求めよ。

Kai

(1)

(2)

の場合、

が単射であるので、命題は真である。

(3)

の場合（）を考える。

のとき、。

のとき、。

よって、 は全射ではない。ゆえに、命題は偽である。

(4)

(4-1)

任意の に対して、(2) より、

とおくと、 がわかるので、 が反射的 (reflexive) である。

(4-2)

二項関係 の定義より、 は対称的であることはほぼ自明なので、反対称的ではない。

(5)

(5-1)

(5-2)

（意味不明な設問）

(5-1) より、 は一つの解である。

(6)

なので、 と書くと、

方程式 を解くと、 を得る。

よって、 を仮定し、方程式 (iv) を解くと、 を得る。

最終的に を方程式 (ii) に代入して検証すると、 は方程式 (ii) の解であることがわかる。