離散課后作業(yè)答案.pdf

第一章第一章 命題邏輯命題邏輯 1 第 7 頁第 3 題 1 解 逆命題 如果我去公園 則天不下雨 反命題 如果天下雨 則我不去公園 逆反命題 如果我不去公園 則天下雨了 2 解 此題注意 P 僅當(dāng) Q 翻譯成PQ 逆命題 如果你去 那么我逗留 反命題 如果我不逗留 那么你沒去 逆反命題 如果你沒去 那么我不逗留 3 解 逆命題 如果方程 nnn xyz 無整數(shù)解 那么 n 是大于 2 的正整數(shù) 反命題 如果 n 不是大于 2 的正整數(shù) 那么方程 nnn xyz 有整數(shù)解 逆反命題 如果方程 nnn xyz 有整數(shù)解 那么 n 不是大于 2 的正整數(shù) 4 解 逆命題 如果我不完成任務(wù) 那么我不獲得更多的幫助 反命題 如果我獲得了更多的幫助 那么我能完成任務(wù) 逆反命題 如果我能完成任務(wù) 那么我獲得了更多的幫助 2 第 15 頁第 1 題 4 解 PQPT PQPQ PQPQ 重言式 9 解 PPQFQT 重言式 10 解 PQQTQQ 可滿足式 3 第 16 頁第 5 題 2 證明 PQP PQP PQP PQP PPQ FQ F 因此 PQPF 得證 4 證明 PPPP PPPP PP F 因此 PPPPF 得證 4 第 16 頁第 6 題 1 PQPQ 證明 設(shè)PQ 為真 那么 P 為真 并且 Q 為真 因此PQ 為真 所以PQPQ 2 PQRPQPR 證明 設(shè) PQPR 為假 于是PQ 為真 PR 為假 得 P 為真 Q 為真 R 為 假 于 是 得QR 為 假 由 P 為 真 可 得 PQR 為 假 因 此 PQRPQPR 得證 5 PPQPPRQR 證明 PPQPPR TQTR QR 因此 PPQPPRQR 得證 5 補(bǔ)充 試證明 QACAPCAPQC 證明 QACAPC QACAPC ACQACP ACPQ APQC APQC APQC APQC ACPQ 因此 QACAPCAPQC 得證 6 第 21 頁第 1 題 2 解 PQPQPQ 0 PPQPQ QPQ PQQQ PQ 7 第 21 頁第 2 題 只求主析取范式 4 解 PQSPQR 5 7 10 11 PQSRPQSRPQSRPQSR 8 第 25 頁第 3 題 證明 1 B P 規(guī)則 2 BAC P 規(guī)則 3 AC T 規(guī)則 1 2 4 ABC P 規(guī)則 5 AC T 規(guī)則 1 4 6 ACAC T 規(guī)則 5 7 AC T 規(guī)則 3 8 AC T 規(guī)則 6 7 9 AC T 規(guī)則 8 因此 AC 是題目的有效結(jié)論 AC 不是 9 第 26 頁第 7 題 a PQQRRP 證明 1 R P 規(guī)則 2 QR P 規(guī)則 3 Q T 規(guī)則 1 2 4 PQ P 規(guī)則 5 PQ T 規(guī)則 4 6 P T 規(guī)則 3 5 b PQRRS SPQ 證明 1 S P 規(guī)則 2 RS P 規(guī)則 3 R T 規(guī)則 1 2 4 PQR P 規(guī)則 5 PQ T 規(guī)則 3 4 6 PQ T 規(guī)則 5 c PQR RS QTP 證明 題目有問題 10 第 26 頁第 8 題 a PQQR RSPS 證明 1 P P 規(guī)則 假設(shè)前提 2 PQ P 規(guī)則 3 Q T 規(guī)則 1 2 4 QR P 規(guī)則 5 R T 規(guī)則 3 4 6 RS P 規(guī)則 7 S T 規(guī)則 5 6 8 PS CP 規(guī)則 1 7 b PQPPQ 證明 1 P P 規(guī)則 假設(shè)前提 2 PQ P 規(guī)則 3 Q T 規(guī)則 1 2 4 PQ T 規(guī)則 1 3 5 PPQ CP 規(guī)則 1 4 c PQRPQR 證明 1 PQ P 規(guī)則 假設(shè)前提 2 P T 規(guī)則 1 3 Q T 規(guī)則 1 4 PQ T 規(guī)則 2 3 5 PQR P 規(guī)則 6 R T 規(guī)則 4 5 7 PQR CP 規(guī)則 1 6 11 第 26 頁第 9 題 a RQ RS SQ PQP 證明 1 P P 規(guī)則 假設(shè)前提 2 P T 規(guī)則 1 3 PQ P 規(guī)則 4 Q T 規(guī)則 2 3 5 SQ P 規(guī)則 6 S T 規(guī)則 4 5 7 RS P 規(guī)則 8 R T 規(guī)則 6 7 9 RQ P 規(guī)則 10 Q T 規(guī)則 8 9 11 QQ T 規(guī)則 4 10 12 P F 規(guī)則 1 11 b SQ RSR PQP 證明 1 P P 規(guī)則 假設(shè)前提 2 P T 規(guī)則 1 3 PQ P 規(guī)則 4 Q T 規(guī)則 2 3 5 SQ P 規(guī)則 6 S T 規(guī)則 4 5 7 RS P 規(guī)則 8 R T 規(guī)則 6 7 9 R P 規(guī)則 10 RR T 規(guī)則 8 9 11 P F 規(guī)則 1 10 c PQRSQPR RPQ 證明 1 R P 規(guī)則 2 QPR P 規(guī)則 3 QP T 規(guī)則 1 2 4 RS T 規(guī)則 1 5 PQRS P 規(guī)則 6 PQ T 規(guī)則 4 5 7 PQ T 規(guī)則 6 8 PQQP T 規(guī)則 3 7 9 PQ T 規(guī)則 8 第二章第二章 謂詞邏輯謂詞邏輯 1 第 39 頁第 1 題 b x A xx B xx A xB x 證明 x A xx B x x A xx B x xA xx B x xA xB x x A xB x 還可以用推理的方法證明 證明 1 xA xB x P 假設(shè)前提 2 xA xB x T 3 xA xB x T 4 x A xxB x T 5 x A x T 6 xB x T 7 x A xx B x P 8 x B x T 5 7 9 B a ES 6 10 B a US 8 11 B aB a T 9 10 12 xA xB x F 1 11 d x A xB xx B xC xx C xx A x 證明 1 x C x P 2 C x US 1 3 xB xC x P 4 B xC x US 3 5 B x T 2 4 6 xA xB x P 7 A xB x US 6 8 A x T 5 7 9 x A x UG 8 2 第 39 頁 2 a x P xQ xx P xx Q x 證明 1 x P x P 假設(shè)前提 2 P x US 1 3 xP xQ x P 4 P xQ x US 3 5 Q x T 2 4 6 x Q x UG 5 7 x P xx Q x CP 1 6 b x P xQ xx P xx Q x 證明 由于 x P xx Q xxQ xx P x xQ xx P x 因此 原題等價(jià)于證明 x P xQ xxQ xx P x 1 xQ x P 假設(shè)前提 2 Q x US 1 3 xP xQ x P 4 P xQ x US 3 5 P x T 2 4 6 x P x UG 5 7 xQ xx P x CP 1 6 3 第 39 頁第 3 題 a 所有的有理數(shù)是實(shí)數(shù) 某些有理數(shù)是整數(shù) 因此某些實(shí)數(shù)是整數(shù) 解 首先定義如下謂詞 P xx是有理數(shù) R xx是實(shí)數(shù) I xx是整數(shù) 于是問題符號(hào)化為 x P xR xx P xI xx R xI x 推理如下 1 xP xI x P 2 P aI a ES 1 3 xP xR x P 4 P aR a US 3 5 P a T 2 6 I a T 2 7 R a T 4 5 8 R aI a T 6 7 9 xR xI x EG 8 b 任何人如果他喜歡步行 他就不喜歡乘汽車 每一個(gè)人或者喜歡乘汽車或者喜歡騎自 行車 有的人不愛騎自行車 因而有的人不愛步行 解 首先定義如下謂詞 P xx是人 F xx喜歡步行 C xx喜歡乘汽車 B xx 喜歡騎自行車 于是問題符號(hào)化為 x P xF xC xx P xC xB x x P xB xx P xF x 推理如下 1 xP xB x P 2 P aB a ES 1 3 P a T 2 4 B a T 2 5 xP xC xB x P 6 P aC aB a US 5 7 C aB a T 3 6 8 C a T 4 7 9 xP xF xC x P 10 P aF aC a US 9 11 P aF a T 8 10 12 P aF a T 11 13 F a T 3 12 14 P aF a T 3 13 15 xP xF x EG 14 c 每個(gè)科學(xué)工作者都是刻苦鉆研的 每個(gè)刻苦鉆研而且聰明的科學(xué)工作者在他的事業(yè)中 都將獲得成功 華為是科學(xué)工作者并且他是聰明的 所以 華為在他的事業(yè)中將獲得成功 解 首先定義如下謂詞 P xx是科學(xué)工作者 Q xx是刻苦鉆研的 R xx是聰明的 S xx在他的事業(yè)中將獲得成功 定義個(gè)體 a 華為 于是命題符號(hào)化為 x P xQ xx P xQ xR xS x P aR aS a 推理如下 1 xP xQ x P 2 P aQ a US 1 3 P aR a P 4 P a T 3 5 R a T 3 6 Q a T 2 4 7 xP xQ xR xS x P 8 P aQ aR aS a US 7 9 P aQ aR a T 3 6 10 S a T 8 9 d 每位資深名士或是中科院院士或是國務(wù)院參事 所有的資深名士都是政協(xié)委員 張偉 是資深名士 但他不是中科院院士 因此 有的政協(xié)委員是國務(wù)院參事 解 首先定義如下謂詞 P xx是資深名士 Q xx是中科院院士 R xx是國務(wù)院參事 S xx是政協(xié)委員 定義個(gè)體 a 張偉 于是命題符號(hào)化為 x P xQ xR xx P xS x P aQ ax S xR x 推理如下 1 P aQ a P 2 P a T 1 3 Q a T 1 4 xP xS x P 5 P aS a US 4 6 S a T 2 5 7 xP xQ xR x P 8 P aQ aR a US 7 9 Q aR a T 2 8 10 R a T 3 9 11 S aR a T 6 10 12 xS xR x EG 11 e 每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù) 自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被 2 整除 并不是所有 的自然數(shù)都能被 2 所整除 因此 有的自然數(shù)是奇數(shù) 解 首先定義如下謂詞 N xx是自然數(shù) Q xx是奇數(shù) O xx是偶數(shù) P xx能被 2 整除 于是命題符號(hào)化為 x N xQ xO xx N xO xP x x N xP xx N xQ x 推理如下 1 x N xP x P 2 xN xP x T 1 3 N aP a ES 2 4 N a T 3 5 P a T 3 6 xN xO xP x P 7 N aO aP a US 6 8 O aP a T 4 7 9 O a T 5 8 10 xN xQ xO x P 11 N aQ aO a US 10 12 Q aO a T 4 11 13 Q a T 9 12 14 N aQ a T 4 13 15 xN xQ x EG 14 f 如果一個(gè)人怕困難 那麼他就不會(huì)獲得成功 每個(gè)人或者獲得成功或者失敗過 有些 人未曾失敗過 所以 有些人不怕困難 解 首先定義如下謂詞 P xx是人 Q xx怕困難 R xx曾獲得成功 S xx曾獲得失敗 于是命題符號(hào)化為 x P xQ xR xx P xR xS x x P xS xx P xQ x 推理如下 1 xP xS x P 2 P aS a ES 1 3 P a T 2 4 S a T 2 5 xP xR xS x P 6 P aR aS a US 5 7 R aS a T 3 6 8 R a T 4 7 9 xP xQ xR x P 10 P aQ aR a US 9 11 P aQ a T 8 10 12 P aQ a T 11 13 Q a T 3 12 14 P aQ a T 3 13 15 xP xQ x EG 14 4 第 40 頁第 5 題 解 錯(cuò)誤 第 2 行的 y 是泛指 第 4 行的 y 是特制 更改如下 1 x P x P 2 P y ES 1 3 x P xQ x P 4 P yQ y US 3 5 Q y T 2 4 6 x Q x EG 5 5 第 40 頁第 6 題 a x P xxP xQ xR x x P xx Q xxy R xR y 證明 1 2 1 3 4 3 5 6 1 5 7 6 8 2 9 7 8 10 x P xP P aES x Q xP Q bES x P xxP xQ xR xP xP xQ xR xT P aQ aR aUS P aQ aT R aT P bQ bR bUS 6 11 4 12 10 11 13 9 12 14 13 15 14 P bQ bT R bT R aR bT y R aR yEG xy R xR yEG b x P xx Q xx P xQ x 證明 1 x P xx Q x P 2 x P xx Q x T 1 3 xP xx Q x T 2 4 xP xQ x T 3 5 xP xQ x T 4 6 第 42 頁第 1 題 a x P xy Q y 解 x P xy Q y xP xy Q y xyP xQ y b xyz P x yP y zu Q x y u 解 xyz P x yP y zu Q x y u xyz P x yP y zu Q x y u xyzP x yP y zu Q x y u xyzuP x yP y zQ x y u c xy A x yxy B x yy A y xB x y 解 xy A x yxy B x yy A y xB x y xy A x yxy B x yy A y xB x y xy A x yxy B x yyA y xB x y xy A x yuv B u vzA z u B u z xyuvzA x yB u vA z uB u z 7 第 42 頁第 2 題 b x P xyz Q x zz R x y 解 前束析取范式 x P xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zy R x y xP xyz Q x zu R x u xP xyzQ x zuR x u xyzuP xQ x zR x u xyzuP xQ x zR x u 由于 P xQ x zR x u 是基本和 因此前束合取范式與前束析取范式一樣 x P xyz Q x zz R x y xyzuP xQ x zR x u d x P xQ x yy P yz Q y z 解 前束析取范式 x P xQ x yy P yz Q y z x P xQ x yy P yz Q y z xP xQ x yy P yz Q y z x P xQ x yy P yz Q y z x P xQ x uy P yz Q u z xyzP xQ x uP yQ u z 前束合取范式 x P xQ x yy P yz Q y z xyzP xQ x uP yQ u z xyzP xP yQ u zQ x uP yQ u z xyzP xP yP xQ u zQ x uP yQ x u Q u z 第三章第三章 集合論集合論 1 第 46 頁第 3 題 給出集合A B和C的例子 使得AB BC 而AC 解 Aa Ba b Ca b c 2 第 46 頁第 6 題 2 1 2 3 解 設(shè) 1 2 3 A 則 1 2 3 A 5 解 3 第 46 頁第 9 題 1 解 子集個(gè)數(shù) 101 2 2 解 元素的奇數(shù)的子集個(gè)數(shù)為 101 100 2 2 2 3 解 不會(huì)有 102 個(gè)元素的子集 4 第 46 頁第 10 題 解 把 17 化為二進(jìn)制 是 00010001 1748 Ba a 把 31 化為二進(jìn)制 是 00011111 3145678 Ba a a a a 267 a a a 編碼為 01000110 為 70 B 18 a a 編碼為 10000001 為 129 B 5 第 53 頁第 5 題 1 ABCABC 證明 ABC ABC ABC ABC ABC ABC 上面是一種簡單的方法 還可以利用文字?jǐn)⑹?任取 x 屬于 ABC 證明 還有一種方法 就是利用第五章的特征函數(shù)證明 下面給出過程 1 1 1 A BC A BA BC AABAABC AABC ABC 1 1 1 AB C AAB C AABCBC ABCBC ABC 所以 A BCAB C 從而可得 ABCABC 2 ABCA CB 證明 ABC ABC ABC ACB ACB ACB 3 ABCA CBC 證明 ACBC ACBC ACBC ACBC ACBACC ABC ABC ABC 因此 ABCA CBC 6 第 53 頁第 9 題 1 ABA CA 解 由于 ABA CA 因此必有ABA 且A CA 也就是AB 并且AC 2 ABA C 解 由于 ABA C 因此必有AB 且A C 也就是AB 并且 AC 3 ABA C 解 ABAC ABAC ABC ABC 因此 ABA C 意味著 ABC 4 ABA C 解 ABAC ABAC ABACACAB ABACACAB ABCABC ABC 兩種可能 第一種BC 即 B C 第二種 ABC 或者 ABC 因此 此題答案為 BCABCABC 或者或者 7 第 53 頁第 11 題 1 ABCABAC 證明 ABAC ABACACAB ABACACAB ABAABCACAACB ABCACB ABCCB ABC 因此 ABCABAC 2 ABCABAC 注意 這個(gè)題目本身不正確 舉例如下 全集為 1 2 3 A 1 B 2 C 3 則 1 2 3 ABC 2 3 ABAC 不相等 8 第 57 頁第 3 題 解 設(shè) A B C 分別表示騎木馬 坐滑行軌道和乘宇宙飛船的兒童集合 由公園的總收入知 70 0 5 140ABC 20ABC 55ABCABCABCABC 因此 3 552 5540 95 ABACBC ABCABCABCABC ABC 沒有坐過任何一種的兒童總數(shù)為 75 75 75 1409520 10 ABC ABC ABCABACBCABC 答 一共 10 個(gè)兒童沒有坐過其中任何一種游樂設(shè)備 9 第 57 頁第 5 題 解 設(shè) A B C 分別是學(xué)習(xí)數(shù)學(xué) 物理 生物的大一學(xué)生集合 由題意可知 67 47 95 28 26 27 50 ABC ABACBC ABC 200 200 200 674795262728 50 ABC ABC ABCABACBCABC ABC 解方程 得 22ABC 因此 一共有 22 人三門功課都學(xué) 數(shù)學(xué) 物理 生物 E 22 4 6 5 35 14 64 50 10 第 59 頁第 1 題 1 1 AB 解 1 AB 2 2 AB 解 2 0 0 1 0 1 1 1 0 1 1 1 1 0 0 2 0 1 2 1 0 2 1 1 2 AB 3 2 BA 解 1 0 1 1 2 0 2 1 BA 2 1 0 1 0 1 0 1 1 1 0 2 0 1 0 2 1 1 1 1 0 1 1 1 1 1 1 2 0 1 1 2 1 2 0 1 0 2 0 1 1 2 0 2 0 2 0 2 1 2 1 1 0 2 1 1 BA 1 2 1 2 0 2 1 2 1 11 第 60 頁第 2 題 解 XY 表示在在笛卡爾坐標(biāo)系中 32x 且20y 的矩形區(qū)域內(nèi)的點(diǎn)集 12 第 60 頁第 3 題 1 ABCDA CB D 證明 任取 x yABCD 有 x yABCD xAByCD xAxByCyD xAyCxByD x yA Cx yBD x yA CBD 由 x y 取值的任意性知 ABCDA CB D 2 當(dāng)且僅當(dāng)才 才有 ABCABC 證明 當(dāng)CA 時(shí) ACA 于是 ABCACBCABC 當(dāng) ABCABC 時(shí) 任取xC 可知 xABC 由 ABCABC 知 xABC 于是得到xA 所以 CA 13 第 60 頁第 5 題 這種題目也可以不推理 只要舉出反例即可 1 ABCDA CB D 解 任取 x yABCD 有 x yABCD xAByCD xAxByCyD xAyCyDxByCyD xAyCxAyDxByCxByD x yA CADBCBD 選擇 A 1 B 2 C a D b 則 1 1 2 2 ABCDabab 1 2 A CB Dab 因此該等式不成立 2 ABCDA CB D 解 任取 x yABCD 有 x yABCD x yABCD xAByCD xAxByCyD xAyCxByD xAyCxByD xAyCxByD 選擇 A 1 2 B 1 C a b D a 2 ABCDb 1 2 2 A CB Dbab 因此 該等式不成立 3 ABCDA CB D 解 設(shè) A 1 2 B 2 C 3 4 D 4 則 1 3 ABCD 1 3 1 4 2 3 A CB D 因此 該等式不成立 4 ABCA CB C 解 取 x yABC 有 x yABC x yABC xAByC xAxByC xAyCxByC xAyCxByC x yA Cx yBC x yA CBC 因此 該等式成立 5 ABCA CB C 解 任取取 x yA CB C 有 x yA CBC xAyCxByCxByCxAyC xAyCxByCxByCxAyC xAyCxBxAxByC xAxBxAxByC xABAByC xAByC x y ABC 因此 該等式成立 第四章第四章 二元關(guān)系二元關(guān)系 1 第 63 頁第 2 題 解 12 1 2 2 4 3 3 1 3 4 2 RR 12 2 4 RR 1 1 2 3 D R 2 1 2 4 D R 1 2 3 4 R R 2 2 3 4 R R 12 1 2 3 4 D RR 12 4 R RR 2 第 63 頁第 3 題 解 1 1 1 2 1 3 1 6 2 2 2 3 2 6 3 3 3 6 6 6 L 1 1 1 2 1 3 1 6 2 2 2 6 3 3 3 6 6 6 D 1 1 1 2 1 3 1 6 2 2 2 6 3 3 3 6 6 6 LD 3 第 63 頁第 4 題 證明 設(shè) D R A D S B 1 任取xAB 則分為兩種情況 xA 或xB 當(dāng)xA 時(shí) 由 R 是自反的 知 x xR 于是 x xRS 當(dāng)xB 時(shí) 由 S 是自反的 知 x xS 于是 x xRS 因此不管任何情況 x xAB x xRS RS是自反的 2 任取xAB 則xA 且xB 由 R 和 S 都是自反的 知 x xR 并且 x xS 于是 x xRS 因此RS是自反的 4 第 63 頁第 5 題 證明 設(shè) D R A D S B 1 任取xAB 則xA 且xB 由 R 和 S 都是自反的 知 x xR 并且 x xS 于是 x xRS 因此RS是自反的 2 任取 x yRS 則 x yR 并且 x yS 由 R 和 S 是對(duì)稱的 知 y xR 并且 y xS 于是 y xRS 因此 RS是對(duì)稱的 3 任取 x yRS y zRS 可得 x yR y zR 并 且 x yS y zS 由 R 是可傳遞的 知 x zR 由 S 是可傳遞的 知 x zS 于是 x zRS 因此 RS是可傳遞的 5 第 63 頁第 7 題 解 任取xS 除 5 外 x xR 但5 5R 因此 R 是不自反的 若 x yR 即10 xy 可得10 yxy xR 知 R 是對(duì)稱的 3 7R 7 3R 但3 3R 可得 R 是不可傳遞的 綜上 R 是不自反的 對(duì)稱的 不可傳遞的 6 第 63 頁第 8 題 解 1 R 是集合 A 上的二元關(guān)系 A 為空集 2 R 是集合 A 上的二元關(guān)系 1 2 A 1 1 R 3 R 是集合 A 上的二元關(guān)系 A 為空集 4 R 是集合 A 上的二元關(guān)系 1 2 3 A 1 1 1 2 2 1R 1 3 7 第 69 頁第 1 題 解 0 3 21 123 0 1 2101 3 0010 R M 0 1001 0000 1 8 第 69 頁第 2 題 解 設(shè) 1 2 3 X X 中的二元關(guān)系有 2 3 2512 個(gè) 9 第 69 頁第 3 題 證明 集合 X 中的每個(gè)二元關(guān)系都是XX 的子集 X有n個(gè)元素 XX 有 2 n個(gè)元素 XX 有 2 2n個(gè)元素 每一個(gè)元素都是XX 的一個(gè)子集 也是一種二元關(guān)系 因而 在X中有 2 2n個(gè)不同的二元關(guān)系 10 第 69 頁第 4 題 僅說明關(guān)系的性質(zhì) a 自反的 不對(duì)稱的 不可傳遞的 b 不自反的 反對(duì)稱的 不可傳遞的 c 自反的 對(duì)稱的 可傳遞的 d 自反的 不對(duì)稱的 不可傳遞的 e 不自反的 不對(duì)稱的 不可傳遞的 f 不自反的 對(duì)稱的 不可傳遞的 g 自反的 反對(duì)稱的 可傳遞的 h 自反的 不對(duì)稱的 不可傳遞的 i 不自反的 對(duì)稱的 可傳遞的 j 自反的 反對(duì)稱的 不可傳遞的 k 自反的 反對(duì)稱的 可傳遞的 l 不自反的 反對(duì)稱的 可傳遞的 11 第 70 頁第 5 題 解 1 0 1 1 2 2 3 0 0 2 1 R 2 2 0 3 1 R 1 12 1 0 2 1 RR 2 21 2 0 2 1 3 2 RR 3 121 1 0 1 1 2 2 RRR 4 3 1 0 0 0 1 0 2 0 3 1 2 2 1 2 3 R 5 3 2 R 12 第 70 頁第 6 題 1 證明 任取xX 由于 1 R和 2 R是自反的 因此 1 x xR 2 x xR 可得 12 x xRR 由 x 取值的任意性可知 12 RR是自反的 2 設(shè) 12 1 2 3 1 3 3 1 XRR 則 12 1 1 RR 不是反自 反的 3 設(shè) 12 1 2 3 1 2 2 1 3 2 2 3 XRR 則 12 1 3 RR 不是對(duì)稱的 4 設(shè) 12 1 2 3 1 2 3 1 1 1 2 3 XRR 則 12 1 3 3 1 RR 不是反對(duì)稱的 5 設(shè) 12 1 2 3 4 5 1 2 2 3 1 3 5 4 2 3 XRR 3 5 2 5 4 4 則 12 1 3 1 5 2 5 5 4 RR 不可傳遞 13 第 70 頁第 7 題 證明 1 任取 13 x zRR 則一定存在某一個(gè)yX 使得 1 x yR 3 y zR 由 12 RR 知 13 23 23 yx yRy zR yx yRy zR x zRR 根據(jù) x z 取值的任意性 問題得證 1323 RRRR 2 任取 31 x zRR 則一定存在某一個(gè)yX 使得 3 x yR 1 y zR 由 12 RR 知 31 32 32 yx yRy zR yx yRy zR x zRR 根據(jù) x z 取值的任意性 問題得證 3132 RRRR 14 第 75 頁第 4 題 證明 設(shè) R 是 A 上的二元關(guān)系 1 若 R 是自反的 則 A IR 由于 A I的轉(zhuǎn)置仍是 A I 因此 A IR 故R是自反 的 2 若 R 是反自反的 則 A IR 把 A I和 R 都取轉(zhuǎn)置 由于 A I的轉(zhuǎn)置仍是 A I 因 此 A IR 故R是反自反的 3 若 R 是對(duì)稱的 任取 y xR 則 x yR 由 R 的對(duì)稱性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是對(duì)稱的 4 若 R 是反對(duì)稱的 任取 y xR 則 x yR 由 R 的反對(duì)稱性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是反對(duì)稱的 5 若 R 是可傳遞得 任取 x yRy zR 則 yxR z yR 由 R 的可傳遞性 可知 z xR 于是 x zR 故R是可傳遞的 15 第 75 頁第 5 題 解 R 的關(guān)系矩陣上 主對(duì)角線有多少個(gè)非零值 RR的關(guān)系矩陣中就有多少非零記入值 16 第 79 頁第 2 題 畫圖略去 解 a r Ra ab b s R t R b r Ra ab ba b s Ra aa bb a t Ra aa b c 圖中假設(shè) b 與 c 的連線箭頭方向指向 c r Ra ab bc ca bb cc a s Ra bb ab cc ba cc a t Ra bb cc aa cb ac b 17 第 85 頁第 2 題 解 121 1 22 21 22 nn n nnn CCC 18 第 85 頁第 5 題 改為判斷這兩個(gè)關(guān)系是否是等價(jià)關(guān)系 解 左側(cè)的關(guān)系不是等價(jià)關(guān)系 因?yàn)椴粷M足可傳遞性 右側(cè)的關(guān)系是等價(jià)關(guān)系 19 第 85 頁第 7 題 證明 1 當(dāng) R 是個(gè)等價(jià)關(guān)系時(shí) 由等價(jià)關(guān)系的定義知 等價(jià)關(guān)系滿足自反性 即 R 是自反的 任取 x y zX x yRy zR 由 R 的可傳遞性 知 x zR 再 由 R 的對(duì)稱性 知 z xR 根據(jù) x y z 取值的任意性 知 R 是循環(huán)的 2 當(dāng) R 是自反的 可知對(duì)任意xX x xR 任取yX 使得 x yR 因?yàn)?R 是循環(huán)的 故當(dāng) x xR x yR 時(shí) y xR 由 x y 取值的 任意性知 R 是對(duì)稱的 任取 x y zX x yRy zR 由 R 的循環(huán)性知 z xR 因?yàn)?R 是對(duì)稱的 因此 x zR 由 x y z 取值的任意性 知 R 是 可傳遞的 因?yàn)?R 是自反的 對(duì)稱的和可傳遞的 因此 R 是一個(gè)等價(jià)關(guān)系 20 第 86 頁第 8 題 證明 設(shè)等價(jià)關(guān)系 1 R造成的集合 X 的劃分為 111121 m CCCC 等價(jià)關(guān)系 2 R造成 的集合 X 的劃分為 221222 n CCCC 1 當(dāng) 1 C中的每一個(gè)等價(jià)類都包含于 2 C的某一個(gè)等價(jià)類之中時(shí) 任取 1 C中的一個(gè)等價(jià) 類 1i C 則必包含在 2 C的一個(gè)等價(jià)類里 設(shè)包含在 2 j C中 12ij CC 任取 1i C中 兩元素 x y 由等價(jià)類的性質(zhì)知 1 xR y 由 12ij CC 可知若 1 x yR 則 2 x yR 即 2 xR y 由 i j x y 取值的任意性知 12 RR 2 如果 12 RR 那么對(duì)任意的 1 x yR 2 x yR 永真 1 x yR 等價(jià)于 x y 落入 1 C的某個(gè)等價(jià)類 1i C中 2 x yR 等價(jià)于 x y 落入 2 C的某個(gè) 等價(jià)類 2 j C中 即若 1 i x yC 則 2 j x y C 由 x y 的任意性可知 12ij CC 由 i 的任意性可知 1 C中的每一個(gè)等價(jià)類都包含在 2 C的某一個(gè)等價(jià)類之中 綜上所述 當(dāng)且僅當(dāng) 1 C中的每一個(gè)等價(jià)類都包含于 2 C的某一個(gè)等價(jià)類之中 才有 12 RR 21 第 89 頁第 1 題 解 x1 x4 x5 x3 x6x2 1 56 x x 2 56 x x 45 x x 3 56 x x 45 x x 34 x x 35 x x 36 x x 合并后 有 345 x x x 356 x x x 4 345 x x x 356 x x x 23 x x 5 345 x x x 356 x x x 23 x x 12 x x 13 x x 16 x x 合并 得 123 x x x 136 x x x 345 x x x 356 x x x 綜上 最大相容類有四個(gè) 分別是 123 x x x 136 x x x 345 x x x 356 x x x 22 第 90 頁第 4 題 證明 設(shè) X SIRR 1 由于 XX IIRR 因此xX x xS 知 X IRR是自反的 2 任 取 x yX x yS 則 X x yI 或 者 x yR 或 者 x yR 若 X x yI 則xy X y xI y xS 若 x yR 則 yxR y xS 若 xyR 則 yxR R y xS 可知無論任何情況 x yS 則 y xS 故 X IRR是對(duì) 稱的 綜上所述 X IRR既是自反的又是對(duì)稱的 因此 X IRR是相容關(guān)系 23 第 90 頁第 5 題 解 23 1111 1 11 1 11 1 1 011 1 1 1 1 1 1 1 1 1 1011 1 11 1 11 1 1 RR RRR MMMM 24 第 90 頁第 6 題 證明 11 1 11 1 01 1 R S M 可知R S不是對(duì)稱的 因此 R S不是等價(jià)關(guān)系 25 第 90 頁第 7 題 舉個(gè)例子即可 解 1 1 2 2 1 1 3 3 1 X RI 2 1 2 2 1 X RI 26 第 95 頁第 1 題 1 1 2 3 4 6 8 24 12 2 1 2 3 4 6 8 12 5 10 9 7 11 27 第 95 頁第 4 題 解 集合 X 上的恒等關(guān)系 既是偏序關(guān)系又是等價(jià)關(guān)系 28 第 95 頁第 5 題 證明 設(shè) R 是 A 上的二元關(guān)系 a 若 R 是自反的 則 A IR 由于 A I的轉(zhuǎn)置仍是 A I 因此 A IR 故R是自反 的 b 若 R 是反自反的 則 A IR 把 A I和 R 都取轉(zhuǎn)置 由于 A I的轉(zhuǎn)置仍是 A I 因 此 A IR 故R是反自反的 c 若 R 是對(duì)稱的 任取 y xR 則 x yR 由 R 的對(duì)稱性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是對(duì)稱的 d 若 R 是反對(duì)稱的 任取 y xR 則 x yR 由 R 的反對(duì)稱性可知 y xR 于是 x yR 由 x y 取值的任意性知 R是反對(duì)稱的 e 若 R 是可傳遞得 任取 x yRy zR 則 yxR z yR 由 R 的可傳遞性 可知 z xR 于是 x zR 故R是可傳遞的 從上述 5 條可以證明 1 3 1 若 R 是擬序關(guān)系 即 R 是反自反的和可傳遞得 由 b e 可知 R也是反自反的 和可傳遞得 因此 R是擬序關(guān)系 2 若 R 是偏序關(guān)系 即 R 是自反的 反對(duì)稱的 可傳遞的 由 a d e 可知 R 也是自反的 反對(duì)稱的 可傳遞的 因此 R是偏序關(guān)系 3 若 R 是全序關(guān)系 則 R 是偏序關(guān)系 由 2 知R也是偏序關(guān)系 另知 x yA xRy或yRx成立 當(dāng)xRy時(shí) yRx 當(dāng)y R x時(shí) xRy 因此不論任何情況 x yA xRy或yRx總成立 綜上 R也是全序關(guān)系 4 舉例子 設(shè) S RN N 是自然數(shù)集合 則 S RN 是良序 但是 S RN 不是良序 因?yàn)槿∪?N 在 S RN 中沒有最小成員 第五章第五章 函數(shù)函數(shù) 1 第 100 頁第 3 題 解 Rf 為正奇數(shù)的集合 2 第 100 頁第 4 題 證明 f 的陪域?yàn)?E 設(shè)值域?yàn)?f R 假定 f 的陪域與值域不相等 即 f RE 那么一定存在 E 的一個(gè)元素 A 使得 f AR 因?yàn)?1212 f S SSS 因此 不存 在任何一個(gè) 12 S S 使得 12 SSA 設(shè) 1 SE 則對(duì)于任何 2 SE 122 SSS 由 12 SSA 知 2 SA 由 2 S取值的任意性可知 AE 這與 A 的取值在 E 中 相矛盾 因此 f 的陪域與值域不相等不成立 即f的陪域與值域相等 3 第 100 頁第 5 題 1 1 1 0 1 0 1 1 1 2 0 1 1 0 0 0 0 1 1 1 1 2 1 0 1 1 1 0 f 2 2 1 0 1 2 f R 3 2 0 1 0 0 0 0 1 1 1 0 1 1 1 0 f 4 f 定義域元素的個(gè)數(shù)是 9 值域元素的個(gè)數(shù)是 5 求 2 g AB 的個(gè)數(shù) 等同于求從 9 個(gè)元素的集合到 5 個(gè)元素集合滿射函數(shù)的個(gè)數(shù) 4 第 103 頁第 1 題 解 3 2 3 127gfg xxx 21 21 324fgfxxx 3 3 36fff xxx 21 2 21 143g ggxxx 2 23fhf xx 21 21 21 2h ghxxx 3 3 2hfh xx 1 2 0 5 33 5fh gf h gf xxx 5 第 103 頁第 2 題 1 10 種情況 0 0 1 1 2 2 0 0 1 0 2 2 0 1 1 1 2 2 0 0 1 1 2 0 0 2 1 1 2 2 0 0 1 1 2 1 0 0 1 2 2 2 0 1 1 1 2 1 0 2 1 2 2 f f f f f f f f f 一對(duì)一 二對(duì)一 2 0 0 1 0 2 0 f 三對(duì)一 2 4 種情況 0 0 1 1 2 2 0 1 1 0 2 2 0 2 1 1 2 0 0 0 1 2 2 1 f f f f 3 3 種情況 0 1 1 2 2 0 0 2 1 0 2 1 0 0 1 1 2 2 f f f 6 第 105 頁第 2 題 1 當(dāng)存在從 X 到 Y 的單射函數(shù)時(shí) mn 單射函數(shù)有 m n Cm 2 當(dāng)存在從 X 到 Y 的滿射函數(shù)時(shí) mn 滿射函數(shù)的個(gè)數(shù)有 1 1 1 2 2 1 1 1 mmmnm nC nnC nnC n n 3 當(dāng)存在從 X 到 Y 的雙射函數(shù)時(shí) mn 雙射函數(shù)的個(gè)數(shù)有 m個(gè) 7 第 115 頁第 1 題 證明 任取 x yI g y xy xyxyxxyxyg x y 因此 二元運(yùn) 算 是可交換的 任取 x y zI g x g y z xyz xyzyz xyzyzx yzyz xyzxyxzyzxyz g g x y z xyz xyxyz xyxyzxyxy z xyzxyxzyzxyz g x g y z 因此 運(yùn)算 是可結(jié)合的 該運(yùn)算的么元是 0 0 的逆元是 0 2 的逆元是 2 其余元素沒有逆元 8 第 116 頁第 2 題 證明 任取 x yN xy 由 xyx y xyx 知 y xxy 運(yùn)算不 是可交換的 任 取 x y zN 由 xyzxzx xy zxyx 知 xyzxyz 運(yùn)算是可結(jié)合的 任取xN x xx 可知 N 中的所有元素都是等冪的 運(yùn)算有右么元 任取 x yN xyx 知 N 中的所有元素都是右么元 運(yùn)算沒有左么元 證明 采用反證法 假定e為 運(yùn)算的左么元 取 bN be 由 的運(yùn)算公式知 e be 由么元的性質(zhì)知 e bb 得eb 這與be 相矛盾 因此 運(yùn)算沒有左么元 第六章第六章 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 1 第 121 頁第 1 題 證明 首先 U 和 V 都只含有一個(gè)二元運(yùn)算 因此是同類型的 第二 f的定義域是自然數(shù)集合N 值域是 0 1 是 V 定義域的子集 第三 驗(yàn)證是否運(yùn)算的像等于像的運(yùn)算 任取 x yN 分情況討論 1 x 和 y 都可以表示成2k 設(shè) 12 2 2 kk xy 那么 1212 22 2 1 kkkk f x yff 1f xf y 11 1 f xf yf x y 2 x 和 y 都不能表示成2k 那么x y也不能表示成2k 0f x y 0f xf y 0 00 f xf yf x y 3 x 可以表示成2k y 不能表示成2k 那么x y也不能表示成2k 0f x y 1 0f xf y 1 00 f xf yf x y 4 x 不可以表示成2k y 能表示成2k 那么x y也不能表示成2k 0f x y 0 1f xf y 010 f xf yf x y 可知 無論 x 和 y 如何取值 都能夠保證 f xf yf x y 綜上所述 f是 U 到 V 的同態(tài)映射 2 第 121 頁第 2 題 證明 設(shè) Ua b c 1 2 3 V 首先 U 和 V 都僅有一個(gè)二元運(yùn)算 因此 U 和 V 是同類型的 第二 U 和 V 的定義域大小相同 具備構(gòu)成雙射函數(shù)的條件 第三 尋找特異元素 U 中么元是 a 右零元是 c 三個(gè)元素都是等冪元 V 中么元是 3 右零元是 1 三個(gè)元素都是等冪元 第四 在 U 和 V 的定義域之間構(gòu)造雙射函數(shù)f 使得 3 2 1f af bf c 把 運(yùn)算表中的元素都用 f 下的像點(diǎn)代替 得 調(diào)整表頭的順序?yàn)?1 2 3 轉(zhuǎn)變?yōu)橄卤?跟 V 中 運(yùn)算表完全相同 因此代數(shù)系統(tǒng) a b c 和 1 2 3 是同構(gòu)的 3 第 121 頁第 3 題 解 首先 判斷兩個(gè)代數(shù)系統(tǒng)是否同類型 兩個(gè)代數(shù)系統(tǒng)都只含有一個(gè)二元運(yùn)算 因此滿足 同類型 第二 判斷兩個(gè)代數(shù)系統(tǒng)定義域的基數(shù)是否相同 都是 4 也滿足 第三 尋找特異元 為了方便起見 畫出其運(yùn)算表 5 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 4 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 3 2 1 3 2 1 3 2 1 2 2 2 1 1 1 1 2 3 1 2 3 1 1 1 2 2 2 1 2 3 V1 和 V2 都有么元 都沒有零元 除么元外 都只有一個(gè)與自身互為逆元的元素 都沒有 等冪元 都滿足交換律 第四 構(gòu)造映射 么元對(duì)應(yīng)么元 10 與自身互為逆元的元素對(duì)應(yīng)與自身互為逆元的元素 42 剩下兩個(gè)元素不是特異元素 因此我隨意指定一種指派 21 33 把 5的運(yùn)算表中元素都換成對(duì)應(yīng)的像點(diǎn) 構(gòu)造一張新表 0 1 3 2 0 0 1 3 2 1 1 2 0 3 3 3 0 2 1 2 2 3 1 0 為了便于比較跟 4 是否一致 調(diào)整表頭的順序?yàn)?0 1 2 3 如下 也就是交換表頭 2 和 3 所在的列 交換表頭 2 和 3 所在的行 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 可以看出 上表跟 4 的運(yùn)算表完全一致 因此 代數(shù)系統(tǒng) 5 1 1 2 3 4 V 和 4 2 0 1 2 3 V 是同構(gòu)的 f 為其同構(gòu) 映射 定義如下 1 0 2 1 3 3 4 2ffff 4 第 123 頁第 1 題 解 首先 判斷 m 是否是等價(jià)關(guān)系 任取xI 由于0 xxm 因此 m xx m 是自反的 任取 x yI 若 m xy 即xya m aI 則yxa m m yx 因此 m 是對(duì)稱的 任取 x y zI 若 mm xy yz 則xya m aI y z bm bI 于是 xzxyyzabm abI 因此 m xz 可知 m 是可傳遞的 因此 m 是等價(jià)關(guān)系 其次 判斷 m 關(guān)于 是否滿足代換性質(zhì) 任取 x yI 若 m xy 即存在某個(gè)pI 滿足xyp m mod k xxm mod k yym 則 01112220 1122101 mod k kkkkk kkkk kkkkk kkk xyp mm C yC yp mC yp mC yp m yp mC yC yp mC yp m 于是 1122101 1122101 kkkk kkk kkkk kkk xyp mC yC yp mC yp m pC yC yp mC yp mm 由于 1122101 kkkk kkk pCyCypmCypmI 因此 m xy m 關(guān)于 是滿足代換性質(zhì) 綜上所述 m 是U上的同余關(guān)系 5 第 123 頁第 2 題 解 1 對(duì)于 運(yùn)算 在二元運(yùn)算下 任取 1212 x x y yI 驗(yàn)證下式是否成立 11 22 1212 2 x Ry x Ry xx Ryy 行 取 1212 1 2 1 2xxyy 可知滿足 11 x Ry 22 x Ry 但 1212 xxyy 即 12 xx R 12 yy 可知對(duì)于運(yùn)算 R 不滿足代換性質(zhì) 2 對(duì)于 運(yùn)算 在二元運(yùn)算下 任取 1212 x x y yI 若 11 x Ry 22 x Ry 則必然滿足 1122 xyxy 于是 12121212 xxxxyyyy 可得 1212 xx Ryy 由 1212 x x y y取值的任意性可知 對(duì)于運(yùn)算 R 滿足代換性質(zhì) 6 第 123 頁第 5