《離散數(shù)學作業(yè).doc》由會員分享，可在線閱讀，更多相關《離散數(shù)學作業(yè).doc（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 離散數(shù)學作業(yè)布置 第1次作業(yè)（P15） 1.16 設p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（ r∧s）→(p∧ q)=（0∧1）→(1∧0)=0→0=1 1.17 判斷下面一段論述是否為真：“π是無理數(shù)。并且，如果3是無理數(shù)，則 也是無理數(shù)。另外只有6能被2整除，6才能被4整除?！? 解： p: π是無理數(shù) 1 q:

2、 3是無理數(shù) 0 r: 是無理數(shù) 1 s:　6能被2整除 1 t: 6能被4整除 0 命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。 1.19 用真值表判斷下列公式的類型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁ q) （6）((p→q) ∧(q→r)) →(p→r) 解： （4） p q p→q q p q→ p (p→q)→( q→ p) 0 0 1

3、1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式類型為永真式 ，最后一列全為1 （5）公式類型為可滿足式（方法如上例），最后一列至少有一個1 （6）公式類型為永真式（方法如

4、上例，最后一列全為1）。 第2次作業(yè)（P38） 2.3 用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ﹁(﹁(p∧q) ∨q) (p∧q) ∧﹁qp∧(q ∧﹁q) p∧0 0 所以公式類型為矛盾式 (2)（p→(p∨q)）∨(p→r) (﹁p∨(p∨q))∨(﹁ p∨r) ﹁p∨p∨q∨r1 所以公式類型為永真式 (3) (p∨q) → (p∧r) ￢(p∨q) ∨ (p∧r) (￢p

5、∧￢q) ∨(p∧r) 易見, 是可滿足式, 但不是重言式. 成真賦值為: 000,001, 101, 111 P q r ￢p∧￢q p∧r (￢p∧￢q) ∨(p∧r) 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1

6、0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 所以公式類型為可滿足式 2.4 用等值演算法證明下面等值式： (2) ( (p→

7、q)∧(p→r) ) (p→(q∧r)) (4)(p∧﹁q)∨(﹁p∧q) (p∨q)∧﹁(p∧q) 證明（2）(p→q)∧(p→r) ( ﹁p∨q)∧(﹁p∨r) ﹁p∨(q∧r)) p→(q∧r) （4）(p∧﹁q)∨(﹁p∧q) (p∨(﹁p∧q)) ∧(﹁q∨(﹁p∧q) ) (p∨﹁p)∧(p∨q)∧(﹁q∨﹁p) ∧(﹁q∨q) 1∧(p∨q)∧ (﹁p∨﹁q)∧1 (p∨q)∧﹁(p∧q) 第3次作業(yè)（P38） 2.5 求下列公式的主析取范式, 并求成真賦值: (1)( ￢p→q) →(￢q∨p) (2) (￢p→q) ∧q∧r (3

8、)(p∨ (q∧r)) →(p∨q∨r) (4) ￢(p→q) ∧q∧r 解： (1)(￢p→q) →(￢q∨p) ￢(p∨q) ∨(￢q∨p) ￢p∧￢q ∨￢q ∨p ￢q ∨p (吸收律) (￢p∨p)∧￢q ∨p∧(￢q∨q) ￢p∧￢q∨p∧￢q ∨p∧￢q ∨p∧q m0∨m2∨m2∨m3 m0∨m2∨m3 成真賦值為 00, 10, 11. (2) (￢p→q) ∧q∧r (p∨q) ∧q∧r (p∧q∧r) ∨q∧r (p∧q∧r) ∨(￢p ∨p) ∧q∧r p∧q∧r∨￢p ∧q∧r∨p∧q∧r m3∨m7 成真賦

9、值為011，111. (3) (p∨(q∧r)) →(p∨q∨r) ￢(p∨(q∧r)) ∨(p∨q∨r) ￢p∧￢(q∧r) ∨(p∨q∨r) ￢p∧(￢q∨￢r)∨(p∨q∨r) ￢p∧￢q∨￢p∧￢r∨p∨q∨r ￢p∧￢q∧(r∨￢r)∨￢p∧(q∨￢q)∧￢r∨p∧(q∨￢q) ∧(r∨￢r) ∨ (p∨￢p) ∧q∧(r∨￢r)∨(p∨￢p) ∧(q∨￢q) ∧r m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7, 為重言式. (4) ￢(p→q) ∧q∧r ￢(￢p∨q) ∧q∧r (p∧￢q) ∧q∧r p∧(￢q ∧q)∧r 0 主析取范式為0,

10、 無成真賦值, 為矛盾式. 第4次作業(yè)（P38） 2.6 求下列公式的主合取范式, 并求成假賦值: (1) ￢(q→￢p) ∧￢p (2)(p∧q) ∨ (￢p∨r) (3)(p→(p∨q)) ∨r 解： (1) ￢(q→￢p) ∧￢p ￢(￢q∨￢p) ∧￢p q∧p ∧￢p q∧0 0 M0∧M1∧M2∧M3 這是矛盾式. 成假賦值為 00, 01, 10, 11. (2)(p∧q) ∨ (￢p∨r) (p∧q) ∨￢p∨r (p∨￢p)∧(￢p ∨q)∨r (￢p ∨q)∨r ￢p ∨q∨r M4, 成假賦值為100. (3)(p→

11、(p∨q)) ∨r (￢p∨(p∨q)) ∨r (￢p∨p)∨q ∨r 1 主合取范式為1, 為重言式. 第5次作業(yè)（P41） 2.32 用消解原理證明下述公式是矛盾式: (1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r (2) ￢((p∨q) ∧ ￢p→q) 解： (1) (￢p∨q) ∧ (￢p∨r) ∧ (￢q∨￢r) ∧ (p∨￢r) ∧r 第一次循環(huán) S0=Φ, S1=｛￢p∨q,￢p∨r,￢q∨￢r,p∨￢r,r｝, S2=Φ 由￢p∨r, p∨￢r消解得到λ 輸出“no”，計算結(jié)束 (2) ￢((p∨q) ∧

12、 ￢p→q) ￢(￢((p∨q) ∧ ￢p) ∨q) ((p∨q) ∧ ￢p) ∧￢q (p∨q) ∧ ￢p ∧￢q 第一次循環(huán) S0=Φ, S1=｛p∨q,￢p, ￢q｝, S2=Φ 由p∨q,￢p消解得到q, 由q, ￢q消解得到λ, 輸出“no”，計算結(jié)束 2.33 用消解法判斷下述公式是否可滿足的: (1) p∧ (￢p∨￢q) ∧q (2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r) 解： (1) p∧ (￢p∨￢q) ∧q 第一次循環(huán) S0=Φ, S1=｛p, ￢p∨￢q, q｝, S2=Φ 由p, ￢p∨￢q消解得到￢q, 由q, ￢q消

13、解得到λ, 輸出“no”，計算結(jié)束 (2) (p∨q) ∧(p∨￢q) ∧(￢p∨ r) 第一次循環(huán) S0=Φ, S1=｛p∨q, p∨￢q, ￢p∨ r｝, S2=Φ 由p∨q, p∨￢q消解得到p, 由p∨q, ￢p∨ r消解得到q ∨r, 由p∨￢q, ￢p∨ r消解得到￢q ∨r, 由p, ￢p∨ r消解得到r, S2=｛p, q ∨r, ￢q ∨r, r｝ 第二次循環(huán) S0=｛p∨q, p∨￢q, ￢p∨ r｝, S1=｛p, q ∨r, ￢q ∨r, r｝, S2=Φ 由p∨q, ￢q ∨r消解得到p∨r, 由p∨￢q, q ∨r消解得到p∨r, 由p∨

14、￢q, q ∨r消解得到p∨r, 由￢p∨ r, p 消解得到r, S2=｛p∨r｝ 第三次循環(huán) S0=｛p, q ∨r, ￢q ∨r, r｝, S1=｛p∨r｝, S2=Φ S2=Φ 輸出“yes”，計算結(jié)束 第6次作業(yè)（P52） 3.6 判斷下面推理是否正確. 先將簡單命題符號化, 再寫出前提, 結(jié)論, 推理的形式結(jié)構(gòu)(以蘊涵式的形式給 出)和判斷過程(至少給出兩種判斷方法): (1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 則明天是星期三

15、；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 則明天是星期二或星期三. 今天是星期一. 所以明天是星期二. (6)今天是星期一當且僅當明天是星期三；今天不是星期一. 所以明天不是星期三. 設p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式結(jié)構(gòu)為 (p→r) ∧p→r 此形式結(jié)構(gòu)為重言式, 即 (p→r) ∧pr 所以推理正確. (2)推理的形式結(jié)構(gòu)為 (p→q) ∧q→p 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (3)推理形式結(jié)構(gòu)為

16、(p→r) ∧￢r→￢p 此形式結(jié)構(gòu)為重言式, 即 (p→r) ∧￢r￢p 故推理正確. (4)推理形式結(jié)構(gòu)為 (p→q) ∧￢p→￢q 此形式結(jié)構(gòu)不是重言式, 故推理不正確. (5)推理形式結(jié)構(gòu)為 (p→(q∨r) )∧p →q 它不是重言式, 故推理不正確. (6)推理形式結(jié)構(gòu)為 (p?r) ∧￢p→￢r 此形式結(jié)構(gòu)為重言式, 即 (p?r) ∧￢p￢r 故推理正確. 推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等值演算法. 證明推理正確還可用構(gòu)造證明法. 下面用等值演算法和構(gòu)造證明法證明(6)推理正確. 1. 等值演算法 (p?r) ∧

17、￢p→￢r (p→r) ∧(r→p)∧￢p→￢r ￢((￢p∨r) ∧(￢r∨p)∧￢p) ∨￢r ￢ (￢p∨r) ∨￢(￢r∨p) ∨p ∨￢r (p∧￢r)∨(r∧￢p)∨p ∨￢r (r∧￢p)∨p ∨￢r 吸收律 (r∧￢p)∨￢（￢p ∨r） 德摩根律 1 即(p?r) ∧￢p￢r 故推理正確 2.構(gòu)造證明法 前提: (p?r), ￢p 結(jié)論: ￢r 證明: ① p?r 前提引入 ② (p→r) ∧ (r→p) ①置換 ③ r→p ②化簡律 ④￢p

18、 前提引入 ⑤￢r ③④拒取式 所以, 推理正確. 第7次作業(yè)（P53-54） 3.15 在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1)前提: p→(q→r), s→p, q 結(jié)論: s→r (2)前提: (p∨q) →(r∧s), (s∨t) →u 結(jié)論: p→u (1)證明: ① s 附加前提引入 ②s→p 前提引入 ③ p ①②假言推理 ④p→(q→r) 前提引入 ⑤q→r ③④假言推理 ⑥ q 前提引入 ⑦ r ⑤

19、⑥假言推理 (2)證明: ① P 附加前提引入 ②p∨q ①附加 ③(p∨q) →(r∧s) 前提引入 ④r∧s ②③假言推理 ⑤ S ④化簡 ⑥s∨t ⑤附加 ⑦(s∨t) →u 前提引入 ⑧ u ⑥⑦假言推理 3.16 在自然推理系統(tǒng)P中用歸謬法證明下面推理: (1)前提: p→￢q, ￢r∨q, r∧￢s 結(jié)論: ￢p (2)前提: p∨q, p→r, q→s 結(jié)論: r∨s (1)證明: ① P 結(jié)論否定引入 ②p→￢q 前提引入 ③￢q ①②假言推理 ④￢r

20、∨q 前提引入 ⑤￢r ③④析取三段論 ⑥r(nóng)∧￢s 前提引入 ⑦ r ⑥化簡規(guī)則 ⑧￢r∧r ⑤⑦合取引入規(guī)則 ⑧為矛盾式, 由歸謬法可知, 推理正確. (2)證明: ①￢(r∨s) 結(jié)論否定引入 ②p∨q 前提引入 ③p→r 前提引入 ④q→s 前提引入 ⑤(p→r) ∧(q→s) ∧(p∨q) ②③④合取引入規(guī)則 ⑥r(nóng)∨s ⑤構(gòu)造性二難 ⑦(r∨s) ∧￢(r∨s) ④⑤合取引入規(guī)則 ⑦為矛盾式, 所以推理正確. 第8次作業(yè)（P65-66） 4.5 在一階邏輯中將下列命題符號化: (1)火車都比輪船快. (2)有的

21、火車比有的汽車快. (3)不存在比所有火車都快的汽車. (4)“凡是汽車就比火車慢”是不對的. 解：因為沒指明個體域, 因而使用全總個體域 (1) "x"y(F(x) ∧G(y) H(x,y)) 其中, F(x): x 是火車, G(y): y 是輪船, H(x,y):x 比y 快. (2) $x$y(F(x) ∧G(y) ∧H(x,y)) 其中, F(x): x 是火車, G(y): y 是汽車, H(x,y):x 比y 快. (3) ￢?x(F(x) ∧"y(G(y) H(x,y))) 或? "x(F(x) ?y(G(y) ∧￢H(x,y))) 其中, F(x):

22、 x 是汽車, G(y): y 是火車, H(x,y):x 比y 快. (4) ￢?x?y(F(x) ∧ G(y) H(x,y)) 或 ?x?y(F(x) ∧G(y) ∧￢H(x,y) ) 其中, F(x): x 是汽車, G(y): y 是火車, H(x,y):x 比y 慢. 4.9 給定解釋 I 如下: (a)個體域為實數(shù)集合R. (b)特定元素 =0. (c)特定函數(shù)(x,y)=x-y, x,y∈R. (d)謂詞(x,y): x=y,(x,y): x

23、y)) (2) ??x?y(F(f(x,y),a) G(x,y)) (3) ??x?y(G(x,y) ￢F(f(x,y),a)) (4) ??x?y(G(f(x,y),a) F(x,y)) 解： (1) ??x?y(x

24、； (c)(x,y)：(3,3)=(4,4)=0,(3,4)=(4,3)=1. 試求下列公式在I下的真值: (1) ?x?yF(x,y) (2) ?x?yF(x,y) (3) ?x?y(F(x,y)→F(f(x),f(y))) 解： (1) ?x?yF(x,y) (F(3,3)∨F(3,4))∧(F(4,3)∨F(4,4)) (0∨1)∧(1∨0) 1 (2) ?x?yF(x,y) (F(3,3)∧F(3,4))∨(F(4,3)∧F(4,4)) (0∧1)∨(1∧0) 0 (3) ?x?y(F(x,y)→F(f(x),f(y)))

25、 (F(3,3)→F(f(3),f(3))) ∧(F(4,3)→F(f(4),f(3))) ∧(F(3,4)→F(f(3),f(4))) ∧(F(4,4)→F(f(4),f(4))) (0→0)∧(1→1)∧(1→1)∧(0→0) 1 5.12 求下列各式的前束范式. (1)?xF(x)→?yG(x, y) (3)?xF(x, y) ??xG(x, y) (5) ?x1F(x1, x2)→(F(x1)→￢?x2G(x1, x2)). 解： 前束范式不是唯一的. (1) ?xF(x)→?yG(x, y) ?x (F(x)→?yG(t, y)) ?x

26、?y(F(x)→G(t, y)). (3) ?xF(x, y) ??xG(x, y) (?xF(x, y)→?xG(x, y))∧(?xG(x, y)→?xF(x, y)) (?xF(x, y)→?uG(u, y))∧(?xG(x, y)→?vF(v, y)) ?x?u(F(x, y)→G(u, y))∧?x?v(G(x, y)→F(v, y)) ?x?u(F(x, y)→G(u, y))∧?w?v(G(w, y)→F(v, y)) ?x?u?w?v ((F(x, y)→G(u, y))∧(G(w, y)→F(v, y))) (5)?x1F(x1, x2)→(F(x1)→￢?

27、x2G(x1, x2)) ?x1F(x1, x2)→(F(x1)→?x2￢G(x1, x2)) ?x1F(x1, x2)→?x2(F(x1)→￢G(x1, x2)) ?x1F(x1, x3)→?x2(F(x4)→￢G(x4, x2)) ?x1(F(x1, x3)→?x2(F(x4)→￢G(x4, x2))) ?x1?x2 (F(x1, x3)→(F(x4)→￢G(x4, x2))) 第10次作業(yè)（P79-80） 5.15 在自然推理系統(tǒng)FL中,構(gòu)造下面推理的證明: (1) 前提: ?xF(x) →?y((F(y)∨G(y))→R(y)),?xF(x) 結(jié)論:?xR(x).

28、(2) 前提:?x(F(x)→(G(a)∧R(x))),?xF(x) 結(jié)論:?x(F(x)∧R(x)) (3) 前提:?x(F(x)∨G(x)), ￢?xG(x) 結(jié)論:?xF(x) (4) 前提:?x(F(x)∨G(x)),?x(￢G(x)∨￢R(x)),?xR(x) 結(jié)論: ?xF(x) (1)證明: ① ?xF(x) →?y((F(y)∨G(y))→R(y)) 前提引入 ② ?xF(x) 前提引入 ③ ?y((F(y)∨G(y))→R(y))

29、 ①②假言推理 ④ (F(c)∨G(c))→R(c) ③全稱量詞消去規(guī)則 ⑤ F(c) ①存在量詞消去規(guī)則 ⑥ F(c) ∨ G(c) ⑤附加 ⑦ R(c) ④⑥假言推理 ⑧ ?xR(x) ⑦存在量詞引入規(guī)則 (2) 證明: ① ?xF(x)

30、 前提引入 ② F(c) ①存在量詞消去規(guī)則 ③ ?x(F(x)→(G(a)∧R(x))) 前提引入 ④ F(c)→(G(a)∧R(c)) ④全稱量詞消去規(guī)則 ⑤ G(a)∧R(c) ②④假言推理 ⑥ R(c)

31、 ⑤化簡 ⑦ F(c)∧R(c) ②⑥合取引入 ⑧ ?x(F(x)∧R(x)) ⑦存在量詞引入規(guī)則 (3) 證明: ① ￢?xG(x) 前提引入 ② ?x￢G(x) ①置換 ③ ￢G(c) ②全稱量詞消去規(guī)則 ④ ?x(F(x)∨G(x))

32、 前提引入 ⑤ F(c)∨G(c) ④全稱量詞消去規(guī)則 ⑥ F(c) ③⑤析取三段論 ⑦ ?xF(x) ⑥存在量詞引入規(guī)則 (4) 證明: ① ?x(F(x)∨G(x)) 前提引入 ② F(y)∨G(y) ①全稱量詞消去規(guī)則 ③?x(￢G(x)∨￢R(x))

33、 前提引入 ④ ￢G(y) ∨￢R(y) ③全稱量詞消去規(guī)則 ⑤ ?xR(x) 前提引入 ⑥ R(y) ⑤全稱量詞消去規(guī)則 ⑦ ￢G(y) ④⑥析取三段論 ⑧ F(y) ②⑦析取三段論 ⑥ ?xF(x)

34、 ⑧存在量詞引入規(guī)則 第11次作業(yè)（P96） 6.4. 設 F 表示一年級大學生的集合, S 表示二年級大學生的集合, M表示數(shù)學專業(yè)學生的集合, R 表示計算機專業(yè)學生的集合, T表示聽離散數(shù)學課學生的集合, G 表示星期一晚上參加音樂會的學生的集合, H 表示星期一晚上很遲才睡覺的學生的集合. 問下列各句子所對應的集合表達式分別是什么? 請從備選的答案中挑出來. (1)所有計算機專業(yè)二年級的學生在學離散數(shù)學課. (2)這些且只有這些學離散數(shù)學課的學生或者星期一晚上去聽音樂會的學生在星期一晚上很遲才睡覺. (3)聽離散數(shù)學課的學生都沒參加星期一晚上

35、的音樂會. (4)這個音樂會只有大學一, 二年級的學生參加. (5)除去數(shù)學專業(yè)和計算機專業(yè)以外的二年級學生都去參加了音樂會. 備選答案: ①TG∪H ②G∪HT ③S∩RT ④H＝G∪T ⑤T∩G＝ ⑥F∪SG ⑦GF∪S ⑧S-(R∪M) G ⑥GS-(R∩M) 解: (1) ③S∩RT (2) ④H=G∪T (3) ⑤T∩G= (4) ⑦GF∪S (5) ⑧S-(R∪M) G 6.5. 確定下列命題是否為真: (1) (2) ∈ (3) {} (4) ∈{} (5){a, b}{a, b, c, {a, b, c}} (6){a

36、, b}∈{a, b, c, {a, b }} (7){a, b}{a, b, {{a, b}}} (8){a, b}∈{a, b, {{a, b}}} 解: (1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假 第12次作業(yè)（P130-131） 7.1. 已知 A={,{}},求AP(A). 解: AP(A)= {,{}}{,{},{{}},{,{}}} ={<, >,<,{}>,<,{{}}>,<,{,{}}>,<{},>,<{},{}>,<{},{{}}>, <{},{,{}}>} 7.7. 列出集合 A={2, 3, 4}上的恒等關系I

37、A, 全域關系EA, 小于或等于關系LA, 整除關系DA. 解: IA={<2,2>,<3,3>,<4,4>} EA=AA={<2,2>,<2,3>,<2,4>,<3,2>,<3,3>,<3,4>,<4,2>,<4,3>,<4,4>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,2>,<2,4>,<3,3>,<4,4>} 7.12.設A={0, 1, 2, 3}, R 是A 上的關系, 且 R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?} 2 3 0 1 0

38、 給出R的關系矩陣和關系圖. 解: 第13次作業(yè)（P131） 7.13.設 A = {?1, 2?, ?2, 4?, ?3, 3?} B = {?1, 3?, ?2, 4?, ?4, 2?} 求A∪B, A∩B, domA, dom(A∪B), ranA, ranB, ran(A∩B), fld(A?B). 解:A∪B={?1,2?, ?1,3?, ?2,4?, ?3,3?, ?4,2?} A∩B={?2,4?} domA={1,2,3} dom(A∪B)={1,2,3,4} ranA={2,3,4} ranB

39、={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3} 7.15.設 A={??,{?,{?}}?,?{?},??} 求A?1,A2,A3,A?{?},A[?],A??,A?{{?}},A[{{?}}]. 解: A?1={?{?,{?}},??,??,{?}?}, A2={?{?},{?,{?}}?}, A3=?, A?{?}={??,{?,{?}}?}, A[?]={?,{?}},  A??=?, A?{{?}}={?{?},??}, A[{{?}}]=? 7.16.設A={a,b,c,d}

40、, R1,R2 為A上的關系, 其中 R1={?a,a?,?a,b?,?b,d?} R2={?a,d?,?b,c?,?b,d?,?c,b?} 求R1○R2, R2○R1,R12,R23. 解: R1○R2={?a,a?,?a,c?,?a,d?}, R2○R1={?c,d?}, R12={?a,a?,?a,b?,?a,d?}, R23={?b,c?,?b,d?,?c,b?} 7.17.設A={a,b,c}, 試給出A 上兩個不同的關系R1和R2,使得 R12=R1, R23=R2. 解: R1={?a,a?,?b,b?}, R2={

41、?b,c?,?c,b?} 第14次作業(yè)（P131-133） 7.21. 設A={1，2，…,10},定義A上的關系 R={|x,y∈A∧x+y=10} 說明R具有哪些性質(zhì)并說明理由。 解:只有對稱性。因為1+1≠10,<1,1>R,所以R不是自反的；又由于<5,5>∈R,因此R不是反自反的；根據(jù)xRy?x+y =10=>yRx ,可知R是對稱的；又由于<1,9>,<9,1>都是屬于R,因此R不是反對稱的；<1,9>,<9,1>都屬于R,如果R是傳遞的,必有<1,1>屬于R.但這是不成立的,因此R也不是傳遞的. 7.26. 設A={1，2

42、，3，4，5，6}，R為A上的關系，R的關系圖如圖3.13所示： 1 2 3 4 5 6 解: (1)R={<1,5>,<2,5>,<3,1>，<3,3>,<4,5>} R={<3,3>,<3,1>,<3,5>}, R3= {<3,3>,<3,1>,<3,5>}. (2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} 　 s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>} 　 T(R)={<1,5>,<2,5

43、>,<3,3>,<3,1>,<3,5>,<4,5>} 第15次作業(yè)（P134-135） 7.41.設A={1，2，3，4}，R為AA上的二元關系, 〈a，b〉，〈c，d〉 AA , 〈a，b〉R〈c，d〉a + b = c + d (1) 證明R為等價關系. (2) 求R導出的劃分. (1)證明：R ∴R是自反的 任意的,∈AA 設R，則a+b=c+d ∴c+d=a+b ∴R ∴R是對稱的 任意的,,

44、>∈AA 若R,R 則a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是傳遞的 ∴R是 AA上的等價關系 (2) ∏={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}} 7.43.對于下列集合與整除關系畫出哈斯圖: (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,1

45、2} 解:哈斯圖如下圖所示: 　　 7.46.分別畫出下列各偏序集的哈斯圖,并找出A的極大元`極小元`最大元和最小元. (1)A={a,b,c,d,e} R={,,,,,,}IA. (2)A={a,b,c,d,e}, R={}IA. 解: （1）極大元e；極小元a；最大e；最小元a。 （2）極大元a,b,d,e；極小元a,b,c,e；沒有最大與最小元。 第16次作業(yè)（P161-135） 4. 判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪

46、些是雙射的? (1) f:NN, f(x)=x2+2 (2) f:NN,f(x)=(x)mod 3, x除以3的余數(shù) (3) f:NN,f(x)= (4) f:N{0,1},f(x)= (5) f:N-{0}R,f(x)=lgx (6) f:RR,f(x)=x2-2x-15 解: (1)不是滿射，不是單射 (2)不是滿射，不是單射 (3)不是滿射，不是單射 (4)是滿射，不是單射 (5)不是滿射，是單射 (6)不是滿射，不是單射 37. 根據(jù)自然數(shù)的集合定義計算

47、： (1) 3∪6, 2∩5 ; (2)4–3,3⊕1 (3)∪4 , ∩1 (4)14 ，2 解: (1) 3∪6 = 6, 2∩5 = 2; (2)4–3 ={3},3⊕1 = {1,2} (3)∪4 = 3, ∩1 = 0 (4)14 = {<0,0>,<0,1>,<0,2>,<0,3>},2= {,,,}，其中: 　　 ={<0,0>,<1,0>} = {<0,0>,<1,1>} 38. 計算下列集合的基數(shù)： 解: (1)3, (2), (3), (4), (5), (6), 第17次作業(yè)（P178-180） 4．判斷下列集合對所給的二元運算是否

48、封閉： （1）整數(shù)集合Z和普通的減法運算。 （2）非零整數(shù)集合Z*和普通的除法運算。 （3）全體nn實矩陣集合Mn（R）和矩陣加法及乘法運算，其中n≥2。 （4）全體實可逆矩陣集合關于矩陣加法及乘法運算，其中n錯誤！未找到引用源。2。 （5）正實數(shù)集合錯誤！未找到引用源。和錯誤！未找到引用源。運算，其中錯誤！未找到引用源。運算定義為： 錯誤！未找到引用源。 （6）錯誤！未找到引用源。關于普通的加法和乘法運算。 （7）A = { 錯誤！未找到引用源。n錯誤！未找到引用源。運算定義如下： 錯誤！未找到引用源。 （8）S = 錯誤！未找到引用源。關于普通的加法和乘法運算。

49、（9）S = {0,1},S是關于普通的加法和乘法運算。 （10）S = 錯誤！未找到引用源。 ,S關于普通的加法和乘法運算。 5．對于上題中封閉的二元運算判斷是否適合交換律，結(jié)合律，分配律。 解: （1）封閉,不滿足交換律和結(jié)合律，無零元和單位元 （2）不封閉 （3）封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元； 乘法單位元是單位矩陣，零元是零矩陣； （4）不封閉 （5）不封閉 因為 （6）封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0，無零元； 乘法無單位元（），零元是0；單位元是1 （7）封閉 不滿足交

50、換律，滿足結(jié)合律， （8）封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律 （9）加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律 （10）加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律 10．令S={a，b}，S上有四個運算：*，錯誤！未找到引用源。分別有表10.8確定。 (a) (b) (c) (d) (1)這4個運算中哪些運算滿足交換律，結(jié)合律，冪等律？ (2)求每個運算的

51、單位元，零元以及每一個可逆元素的逆元。 解: (a) 交換律，結(jié)合律，冪等律都滿足， 零元為a,沒有單位元； (b)滿足交換律和結(jié)合律，不滿足冪等律，單位元為a,沒有零元 (c)滿足交換律,不滿足冪等律,不滿足結(jié)合律 沒有單位元, 沒有零元 (d) 不滿足交換律，滿足結(jié)合律和冪等律 沒有單位元, 沒有零元 16．設V=〈 N，+ ，錯誤！未找到引用源?！?，其中+ ，錯誤！未找到引用源。分別代表普通加法與乘法，對下面給定的每個集合確定它是否構(gòu)成V的子代數(shù)，為什么？ （1）S1=錯誤！未找到引用源。 （2）S2=錯誤！未找到引用源。

52、（3）S3 = {-1，0，1} 解: （1）是 （2）不是 加法不封閉 （3）不是，加法不封閉 第18次作業(yè)（P202-205） 8.設S={0，1，2，3}，為模4乘法，即 x,y∈S, xy=(xy)mod 4 問〈S，〉是否構(gòu)成群？為什么？ 解：(1) x,y∈S, xy=(xy)mod 4,是S上的代數(shù)運算。 (2) x,y,z∈S,設xy=4k+r (xy)z =((xy)mod 4)z=rz=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz) =(xyz)mod

53、 4 所以，(xy)z = x(yz)，結(jié)合律成立。 (3) x∈S, (x1)=(1x)=x,，所以1是單位元。 (4) 0和2沒有逆元 所以，〈S，〉不構(gòu)成群 9.設Z為整數(shù)集合，在Z上定義二元運算。如下： x,y∈Z,xoy= x+y-2 問Z關于o運算能否構(gòu)成群？為什么？ 解：(1) x,y∈Z, xoy= x+y-2,o是Z上的代數(shù)運算。 (2) x,y,z∈Z, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，結(jié)合律成立。 (3)設是單位元，x∈Z, x

54、o= ox=x,即x+-2= +x-2=x, e=2 (4) x∈Z , 設x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, 所以， 所以〈Z，o〉構(gòu)成群 22.設G為群，a是G中給定元素，a的正規(guī)化子N（a）表示G中與a可交換的元素構(gòu)成的集合，即 N（a）={x∣x∈G∧xa=ax} 證明N（a）構(gòu)成G的子群。 證明：ea=ae, 　　,所以 由，得，即，所以 所以N（a）構(gòu)成G的子群 36.設是5元置換，且 ， (1)計算； (2)將表示成不交的輪換之積。 (3)將（2）中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換。 解：(1) (2) (3) 奇置換， 偶置換 奇置換