nan2inf .cn
数学 旧 .com 迁移

离散数学 / 相关资料 / 第三次

从旧 .com 全量搬运的历史内容，来源路径：/math/课程/离散数学/resources/第三次/

约 4 分钟阅读
migrationlegacy-commathresourcecourse

迁移来源

第三次作业

习题四 13 #

note
  • R1∘R2={(1,4),(1,3)}R_1 \circ R_2=\{(1,4),(1,3)\}
  • R2∘R1={(3,4)}R_2 \circ R_1=\{(3,4)\}
  • R1∘R2∘R1=∅R_1\circ R_2\circ R_1=\varnothing
  • R13={(1,1),(1,4)}R_1^3=\{(1,1),(1,4)\}

习题四 15 #

note

AA 非空, 则 ∃ a∈A\exists\ a \in A 取 R1=∅,R2={(a,a)}R_1=\varnothing,R_2=\{(a,a)\}.

习题四 16 #

note

∀(a,b)∈R∩R~⇒(a,b)∈R∧(a,b)∈R~⇒(a,b)∈R∧(b,a)∈R⇒a=b.\forall (a,b) \in R\cap \widetilde{R} \Rightarrow (a,b) \in R \wedge (a,b) \in \widetilde{R} \\ \Rightarrow (a,b) \in R \wedge (b,a) \in R \Rightarrow a=b. 由此说明 R∩R~R \cap \widetilde{R} 中只有对角线可能非零, 即非零元素个数不超过 nn.

习题四 17 #

note
  • (1) 真, ∀a∈A,(a,a)∈R1∩(a,a)∈R2⇒(a,a)∈R1∘R2\forall a \in A, (a,a) \in R_1 \cap (a,a) \in R_2 \Rightarrow (a,a) \in R_1 \circ R_2.
  • (2) 假, 取 R1={(1,2)},R2={(2,1)}⇒R1∘R2={(1,1)}R_1=\{(1,2)\},R_2=\{(2,1)\}\Rightarrow R_1 \circ R_2=\{(1,1)\} 不是反自反的.
  • (3) 假, 取 R1={(1,2),(2,1)},R2={(2,3),(3,2)}⇒R1∘R2={(1,3)}R_1=\{(1,2),(2,1)\},R_2=\{(2,3),(3,2)\}\Rightarrow R_1\circ R_2=\{(1,3)\}.
  • (4) 假, 取 R1={(1,3),(2,3)},R2={(3,1),(3,2)}⇒R1∘R2={(1,1),(2,2),(1,2),(2,1)}R_1=\{(1,3),(2,3)\},R_2=\{(3,1),(3,2)\}\Rightarrow R_1\circ R_2=\{(1,1),(2,2),(1,2),(2,1)\}.
  • (5) 假, 取 R1={(1,4),(2,5)},R2={(4,2),(5,3)}⇒R1∘R2={(1,2),(2,3)}R_1=\{(1,4),(2,5)\},R_2=\{(4,2),(5,3)\}\Rightarrow R_1\circ R_2=\{(1,2),(2,3)\}.

习题四 18 #

note

由 R+∘R+=R+⇒(R+)+=⋃(R+)k=R+R^+\circ R^+=R^+ \Rightarrow (R^+)^+=\bigcup (R^+)^k=R^+.

同理 R∗∘R∗=R∗⇒(R∗)∗=R∗R^*\circ R^*=R^*\Rightarrow (R^*)^*=R^*.

习题四 19 #

  • (1) {{< admonition note “证明” false >}} 由 (1,2),(2,4)∈R,(1,4)∉R⇒R(1,2),(2,4) \in R,(1,4) \notin R\Rightarrow R 不是传递关系 .
  • (2) {{< admonition note “答案” false >}} R1={(1,2),(1,3),(1,4),(2,4),(2,3),(3,4),(4,3),(3,3)}R_1=\{(1,2),(1,3),(1,4),(2,4),(2,3),(3,4),(4,3),(3,3)\}.
  • (3) 存在, 全关系.

习题四 20 #

  • (1) {{< admonition note “证明” false >}} 自反: ∀(a,b)∈A×A,a+b=b+a⇒((a,b),(a,b))∈R\forall (a,b) \in A\times A,a+b=b+a\Rightarrow ((a,b),(a,b)) \in R. 对称: ∀((a,b),(c,d))∈R,a+d=b+c⇒c+b=d+a⇒((c,d),(a,b))∈R\forall ((a,b),(c,d))\in R,a+d=b+c \Rightarrow c+b=d+a\Rightarrow ((c,d),(a,b)) \in R. 传递: ∀((a,b),(c,d)),((c,d),(e,f))∈R,a+d=b+c,c+f=d+e⇒a−b=c−d=e−f⇒a+f=e+b⇒((a,b),(e,f))∈R\forall ((a,b),(c,d)),((c,d),(e,f))\in R,a+d=b+c,c+f=d+e\Rightarrow a-b=c-d=e-f\Rightarrow a+f=e+b\Rightarrow((a,b),(e,f))\in R.
  • (2) [(2,5)]R={(1,4),(2,5),(3,6),(4,7),(5,8)}[(2,5)]_R=\{(1,4),(2,5),(3,6),(4,7),(5,8)\}.
  • (3) 不对, RR 中的元素形式为 ((a,b),(c,d))((a,b),(c,d)) 而 A×AA\times A 中的元素形式为 (a,b)(a,b), 应该说 R⊆(A×A)×(A×A)R\subseteq (A\times A)\times(A\times A).

习题四 23 #

  • (1) {{< admonition note “证明” false >}} 自反: ∀a∈A,(a,a)∈R1∧(a,a)∈R2⇒(a,a)∈R1∩R2\forall a \in A, (a,a)\in R_1\wedge(a,a) \in R_2\Rightarrow (a,a)\in R_1 \cap R_2.

对称: ∀(a,b)∈R1∩R2,(a,b)∈R1∧(a,b)∈R2⇒(b,a)∈R1∧(b,a)∈R2⇒(b,a)∈R1∩R2\forall (a,b) \in R_1 \cap R_2,(a,b) \in R_1\wedge (a,b)\in R_2\Rightarrow (b,a) \in R_1\wedge (b,a)\in R_2\\ \Rightarrow (b,a) \in R_1 \cap R_2.

传递: ∀(a,b),(b,c)∈R1∩R2,(a,b),(b,c)∈R1⇒(a,c)∈R1\forall (a,b),(b,c) \in R_1\cap R_2,(a,b),(b,c) \in R_1\Rightarrow (a,c) \in R_1, 同理 (a,c)∈R2(a,c) \in R_2, 故 (a,c)∈R1∩R2(a,c) \in R_1\cap R_2.

  • (2) 取 R1={(1,1),(2,2),(3,3),(1,2),(2,1)},R2={(1,1),(2,2),(3,3),(2,3),(3,2)}R_1=\{(1,1),(2,2),(3,3),(1,2),(2,1)\},R_2=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}.

习题四 28 #

\begin{tikzpicture} \graph { 1 <-> 2; 1 <-> 3; 1 ->[loop above] 1; 2 ->[loop above] 2; 3 ->[loop left] 3; 2 <-> 3; 4 ->[loop above] 4; 5 <-> 6; 5 ->[loop above] 5; 6 ->[loop above] 6; }; \end{tikzpicture}

习题四 31 #

note
  • (1) \begin{tikzpicture}[node distance=10pt] \node[draw, circle] (4) {4}; \node[draw, circle, below=of 4] (2) {2}; \node[draw, circle, right=20pt of 2] (3) {3}; \node[draw, circle, below=of 2] (1) {1};

\graph{ (4) — (2) — (1); (3) — (1) }; \end{tikzpicture}

  • (2) \begin{tikzpicture}[node distance=10pt] \node[draw, circle] (36) {36}; \node[draw, circle, below=of 36] (12) {12}; \node[draw, circle, below=of 12] (6) {6}; \node[draw, circle, below=of 6] (3) {3}; \node[draw, circle, right=20pt of 3] (2) {2}; \node[draw, circle, right=20pt of 6] (26) {26};

\graph{ (36) — (12) — (6) — (3); (6) — (2); (26) — (2); }; \end{tikzpicture}

  • (3) \begin{tikzpicture}[node distance=15pt] \node[draw, circle] (8) {8}; \node[draw, circle, right=20pt of 8] (12) {12}; \node[draw, circle, below=of 12] (6) {6}; \node[draw, circle, below=of 8] (4) {4}; \node[draw, circle, below=of 6] (3) {3}; \node[draw, circle, below=of 4] (2) {2}; \node[draw, circle, right=20pt of 3] (5) {5}; \node[draw, circle, right=20pt of 5] (7) {7}; \node[draw, circle, right=20pt of 7] (11) {11}; \node[draw, circle, right=20pt of 6] (9) {9}; \node[draw, circle, below=of 3] (1) {1};

\graph{ (8) — (4) — (2) — (1); (12) — (6) — (3) — (1); (12) — (4); (6) — (2); (9) — (3); (1) — { (5),(7),(11) } }; \end{tikzpicture}

{2,3,6}:6,无,6,{2,3},6,1\{2,3,6\}:6,\text{无},6,\{2,3\},6,1.

{2,4,6}:无,2,{4,6},2,无,2\{2,4,6\}:\text{无},2,\{4,6\},2,\text{无},2.

{4,8,12}:无,4,{8,12},4,4,无\{4,8,12\}:\text{无},4,\{8,12\},4,4,\text{无}.

习题四 32 #

note

A={0,1,2,3,4,5,6}A=\{0,1,2,3,4,5,6\}.

\preceq=\{(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,1),\2,2),(2,5),(3,3),(3,5),(5,5),(4,4),(4,6),(6,6)}$.

习题四 34 #

note

自反: ∀(a,b)∈A×B\forall (a,b) \in A\times B 由 (a,a)∈⪯1∧(b,b)∈⪯2⇒((a,b),(a,b))∈⪯3(a,a) \in \preceq_1 \wedge (b,b) \in \preceq_2 \Rightarrow ((a,b),(a,b)) \in \preceq_3.

反对称: ∀((a1,b1),(a2,b2))∈⪯3∧((a2,b2),(a1,b1))∈⪯3,(a1,a2),(a2,a1)∈⪯1∧(b1,b2),(b2,b1)∈⪯2⇒a1=a2∧b1=b2⇒(a1,b1)=(a2,b2)\forall ((a_1,b_1),(a_2,b_2)) \in \preceq_3 \wedge ((a_2,b_2),(a_1,b_1)) \in \preceq_3, \\ (a_1,a_2),(a_2,a_1) \in \preceq_1 \wedge (b_1,b_2),(b_2,b_1) \in \preceq_2 \Rightarrow a_1=a_2\wedge b_1=b_2 \Rightarrow (a_1,b_1)=(a_2,b_2).

传递: ∀((a1,b1),(a2,b2)),((a2,b2),(a3,b3))∈⪯3,(a1,a2),(a2,a3)∈⪯1,⇒(a1,a3)∈⪯1\forall ((a_1,b_1),(a_2,b_2)),((a_2,b_2),(a_3,b_3)) \in \preceq_3, (a_1,a_2),(a_2,a_3) \in \preceq_1, \\ \Rightarrow (a_1,a_3)\in \preceq_1 同理 (b1,b3)∈⪯2⇒((a1,b1),(a3,b3))∈⪯3(b_1,b_3) \in \preceq_2 \Rightarrow ((a_1,b_1),(a_3,b_3)) \in \preceq_3.

综上 ⪯3\preceq_3 是 A×BA\times B 上的半序关系.

习题四 37 #

note
  • (1) 半序
  • (2) 良序
  • (3) 良序

讨论

评论

正在加载评论...