跳到主要内容

電気通信大学 情報理工学研究科 情報学専攻 2020年8月実施 選択問題 離散数学

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

問1​

X,YX,Y を集合、f:X→Yf:X\to Y を写像とする。A⊆XA\subseteq X, B⊆YB\subseteq Y に対して

f(A)={f(a)∣a∈A},f−1(B)={a∣f(a)∈B}f(A)=\{f(a)\mid a\in A\}, \qquad f^{-1}(B)=\{a\mid f(a)\in B\}

と定義する。空欄 1 から 8 に、選択肢

0◯ =,1◯ ∈,2◯ ⊂,3◯ ⊇,4◯ →,5◯ ↦\text{\textcircled{0} }=,\quad \text{\textcircled{1} }\in,\quad \text{\textcircled{2} }\subset,\quad \text{\textcircled{3} }\supseteq,\quad \text{\textcircled{4} }\to,\quad \text{\textcircled{5} }\mapsto

から適切なものを入れよ。

  1. a 1 {a,b}a\ \boxed{1}\ \{a,b\}
  2. {a} 2 {a,b}\{a\}\ \boxed{2}\ \{a,b\}
  3. {a} 3 {{a},{a,b}}\{a\}\ \boxed{3}\ \{\{a\},\{a,b\}\}
  4. {{a,b}} 4 {{a},{a,b}}\{\{a,b\}\}\ \boxed{4}\ \{\{a\},\{a,b\}\}
  5. f:{1,2,3}→{a,b}f:\{1,2,3\}\to\{a,b\} に対して f({1,2})={a}f(\{1,2\})=\{a\}、f(3)=bf(3)=b であるとき、f:2 5 af:2\ \boxed{5}\ a であり、f({2,3}) 6 {a,b}f(\{2,3\})\ \boxed{6}\ \{a,b\} である。
  6. 写像 f:X→Yf:X\to Y と集合 A⊆XA\subseteq X, B⊆YB\subseteq Y に対して次を埋めよ。
    • ff が単射なら一般に f−1(f(A)) 7 Af^{-1}(f(A))\ \boxed{7}\ A。
    • ff が単射なら一般に f(f−1(B)) 8 Bf(f^{-1}(B))\ \boxed{8}\ B。

問2​

述語を

P(x,y)=「図書館 x は本 y を所有する」,Q(y)=「本 y は数学の本である」P(x,y)=\text{「図書館 }x\text{ は本 }y\text{ を所有する」}, \qquad Q(y)=\text{「本 }y\text{ は数学の本である」}

と定義する。空欄 9 から 24 に、選択肢

0◯ ∀x,1◯ ∀y,2◯ ∃x,3◯ ∃y,4◯ ¬,5◯ ∨,6◯ ∧,7◯ ⇒,8◯ ⇔\text{\textcircled{0} }\forall x,\quad \text{\textcircled{1} }\forall y,\quad \text{\textcircled{2} }\exists x,\quad \text{\textcircled{3} }\exists y,\quad \text{\textcircled{4} }\neg,\quad \text{\textcircled{5} }\lor,\quad \text{\textcircled{6} }\land,\quad \text{\textcircled{7} }\Rightarrow,\quad \text{\textcircled{8} }\Leftrightarrow

から適切なものを入れよ。

  1. 「どの図書館も本を所有する」: 9 10 P(x,y)\boxed{9}\ \boxed{10}\ P(x,y)
  2. 「ありとあらゆる本を所有する図書館は存在しない」を次の三通りで表せ。
    • 11 ∃x 12 P(x,y)\boxed{11}\ \exists x\ \boxed{12}\ P(x,y)
    • 13 ¬ 14 P(x,y)\boxed{13}\ \neg\ \boxed{14}\ P(x,y)
    • 15 ∃y 16 P(x,y)\boxed{15}\ \exists y\ \boxed{16}\ P(x,y)
  3. 「数学の本であるなら全て所有する図書館がある」: 17 18 (Q(y) 19 P(x,y))\boxed{17}\ \boxed{18}\ (Q(y)\ \boxed{19}\ P(x,y))
  4. 「全ての図書館に必ず置いてある本がある」: 20 21 P(x,y)\boxed{20}\ \boxed{21}\ P(x,y)
  5. 「全ての図書館に必ず置いてある数学の本がある」: 22 23 (Q(y) 24 P(x,y))\boxed{22}\ \boxed{23}\ (Q(y)\ \boxed{24}\ P(x,y))

問3​

n≥2n\ge2 の自然数に対して、次の不等式を数学的帰納法で証明せよ。

∑t=1n1t2<2−1n.\sum_{t=1}^n\frac1{t^2}<2-\frac1n.

問4​

集合 X,YX,Y と写像 f:X→Yf:X\to Y に対し、ff の順像を与える写像

If:2X→2Y,If(A)={f(a)∣a∈A}I_f:2^X\to2^Y, \qquad I_f(A)=\{f(a)\mid a\in A\}

を定義する。∣X∣=∣Y∣|X|=|Y| とし、写像の集合

Γ={Ih∣h:X→Y, h は全単射},\Gamma=\{I_h\mid h:X\to Y,\ h\text{ は全単射}\},
Δ={J∣J:2X→2Y, J は全単射}\Delta=\{J\mid J:2^X\to2^Y,\ J\text{ は全単射}\}

を考える。

  1. X={1,2}X=\{1,2\}、Y={a,b}Y=\{a,b\} とする。
    • Γ\Gamma の要素を一つ図示せよ。
    • Δ∖Γ\Delta\setminus\Gamma の要素を一つ図示せよ。
  2. ∣X∣=∣Y∣=n|X|=|Y|=n とする。
    • ∣Γ∣|\Gamma| を求めよ。
    • ∣Δ∣|\Delta| を求めよ。

题目描述​

第 1 题：设 X,YX,Y 为集合，f:X→Yf:X\to Y 为映射，并定义

f(A)={f(a)∣a∈A},f−1(B)={a∣f(a)∈B}.f(A)=\{f(a)\mid a\in A\},\qquad f^{-1}(B)=\{a\mid f(a)\in B\}.

从 =,∈,⊂,⊇,→,↦=,\in,\subset,\supseteq,\to,\mapsto 中选择符号，填写上文 1—8 号空格；内容包括元素与集合、集合包含关系、具体映射的记法，以及在 ff 为单射时 f−1(f(A))f^{-1}(f(A)) 与 AA、f(f−1(B))f(f^{-1}(B)) 与 BB 的关系。

第 2 题：定义谓词

P(x,y)=“图书馆 x 拥有图书 y”,Q(y)=“图书 y 是数学书”.P(x,y)=\text{“图书馆 }x\text{ 拥有图书 }y\text{”},\qquad Q(y)=\text{“图书 }y\text{ 是数学书”}.

从 ∀x,∀y,∃x,∃y,¬,∨,∧,⇒,⇔\forall x,\forall y,\exists x,\exists y,\neg,\lor,\land,\Rightarrow,\Leftrightarrow 中选择量词或联结词，填写 9—24 号空格，用谓词公式表示：每家图书馆都拥有图书；不存在拥有所有图书的图书馆（用三种等价形式）；存在一家图书馆拥有所有数学书；存在一本所有图书馆都拥有的书；以及存在一本所有图书馆都拥有的数学书。

第 3 题：对自然数 n≥2n\ge2，用数学归纳法证明

∑t=1n1t2<2−1n.\sum_{t=1}^n\frac1{t^2}<2-\frac1n.

第 4 题：对映射 f:X→Yf:X\to Y，定义其顺像映射

If:2X→2Y,If(A)={f(a)∣a∈A}.I_f:2^X\to2^Y,\qquad I_f(A)=\{f(a)\mid a\in A\}.

在 ∣X∣=∣Y∣|X|=|Y| 下，令 Γ\Gamma 为所有由双射 h:X→Yh:X\to Y 诱导的 IhI_h 的集合，Δ\Delta 为所有双射 J:2X→2YJ:2^X\to2^Y 的集合。当 X={1,2}X=\{1,2\}、Y={a,b}Y=\{a,b\} 时，分别画出一个 Γ\Gamma 中的元素和一个 Δ∖Γ\Delta\setminus\Gamma 中的元素；当 ∣X∣=∣Y∣=n|X|=|Y|=n 时，求 ∣Γ∣|\Gamma| 与 ∣Δ∣|\Delta|。

Kai​

問1​

空欄選択肢記号
1①∈\in
2②⊂\subset
3①∈\in
4②⊂\subset
5⑤↦\mapsto
6⓪==
7⓪==
8②⊂\subset

空欄 7 について、任意の写像では A⊆f−1(f(A))A\subseteq f^{-1}(f(A)) であり、単射なら逆向きの包含も成立するため等号となる。 空欄 8 については一般に

f(f−1(B))=B∩f(X)⊆Bf(f^{-1}(B))=B\cap f(X)\subseteq B

である。ここで選択肢 ② の ⊂\subset は包含関係を表す。

問2​

空欄選択肢内容
9⓪∀x\forall x
10③∃y\exists y
11④¬\neg
12①∀y\forall y
13⓪∀x\forall x
14①∀y\forall y
15⓪∀x\forall x
16④¬\neg
17②∃x\exists x
18①∀y\forall y
19⑦⇒\Rightarrow
20③∃y\exists y
21⓪∀x\forall x
22③∃y\exists y
23⓪∀x\forall x
24⑥∧\land

完成した論理式は次のとおりである。

  1. ∀x ∃y P(x,y)\forall x\,\exists y\,P(x,y)

  2. 次の三式は De Morgan の法則により同値である。

    ¬∃x ∀y P(x,y),\neg\exists x\,\forall y\,P(x,y),
    ∀x ¬∀y P(x,y),\forall x\,\neg\forall y\,P(x,y),
    ∀x ∃y ¬P(x,y).\forall x\,\exists y\,\neg P(x,y).

  3. ∃x ∀y (Q(y)⇒P(x,y))\exists x\,\forall y\,(Q(y)\Rightarrow P(x,y))

  4. ∃y ∀x P(x,y)\exists y\,\forall x\,P(x,y)

  5. ∃y ∀x (Q(y)∧P(x,y))\exists y\,\forall x\,(Q(y)\land P(x,y))。これは Q(y)Q(y) が xx に依存しないため、∃y (Q(y)∧∀x P(x,y))\exists y\,(Q(y)\land\forall x\,P(x,y)) と同値である。

問3​

Sn=∑t=1n1/t2S_n=\sum_{t=1}^n1/t^2 とおく。

n=2n=2 のとき

S2=1+14=54<32=2−12S_2=1+\frac14=\frac54<\frac32=2-\frac12

なので成立する。

k≥2k\ge2 で Sk<2−1/kS_k<2-1/k が成立すると仮定する。k<k+1k<k+1 より

1(k+1)2<1k(k+1)\frac1{(k+1)^2}<\frac1{k(k+1)}

であるから、

Sk+1=Sk+1(k+1)2<2−1k+1k(k+1)=2−1k+1.\begin{aligned} S_{k+1} &=S_k+\frac1{(k+1)^2}\\ &<2-\frac1k+\frac1{k(k+1)}\\ &=2-\frac1{k+1}. \end{aligned}

よって数学的帰納法により、すべての n≥2n\ge2 で不等式が成立する。

問4​

(1-1)​

h(1)=ah(1)=a, h(2)=bh(2)=b とする。このとき Ih∈ΓI_h\in\Gamma は次の対応である。

(1-2)​

次の JJ は 2X2^X から 2Y2^Y への全単射である。

しかし任意の写像 hh について Ih(∅)=∅I_h(\varnothing)=\varnothing であるため、この JJ は IhI_h の形ではない。したがって J∈Δ∖ΓJ\in\Delta\setminus\Gamma である。

(2-1)​

XX から YY への全単射は n!n! 個ある。異なる hh は単元集合 {x}\{x\} の像で区別でき、異なる IhI_h を与える。よって

∣Γ∣=n!.\boxed{|\Gamma|=n!}.

(2-2)​

∣2X∣=∣2Y∣=2n|2^X|=|2^Y|=2^n なので、この二つの集合の間の全単射の個数は

∣Δ∣=(2n)!\boxed{|\Delta|=(2^n)!}

である。

本页目录