離散數(shù)學(xué)作業(yè)布置 第1次作業(yè)（P15） 1.16 設(shè)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: 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 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）公式類型為永真式（方法如上例，最后一列全為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∧￢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 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→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)(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 成真賦值為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, 無成真賦值, 為矛盾式. 第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→(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) ∧ ￢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消解得到λ, 輸出“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∨￢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)(以蘊(yùn)涵式的形式給 出)和判斷過程(至少給出兩種判斷方法): (1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 則明天是星期二或星期三. 今天是星期一. 所以明天是星期二. (6)今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三. 設(shè)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)為 (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) ∧￢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 前提引入 ⑤￢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 ⑤⑥假言推理 (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∨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)有的火車比有的汽車快. (3)不存在比所有火車都快的汽車. (4)“凡是汽車就比火車慢”是不對的. 解：因?yàn)闆]指明個體域, 因而使用全總個體域 (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): 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)個體域?yàn)閷?shí)數(shù)集合R. (b)特定元素 =0. (c)特定函數(shù)(x,y)=x-y, x,y∈R. (d)謂詞(x,y): x=y,(x,y): x<y, x,y∈R. 給出下列公式在I 下的解釋, 并指出它們的真值: (1) ??x?y(G(x,y) ￢F(x,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<yx≠y), 真值為1. (2) ??x?y((x-y=0) (x<y)), 真值為0. (3) ??x?y((x<y) (x-y≠0)), 真值為1. (4) ??x?y((x-y<0) (x=y)), 真值為0. 第9次作業(yè)（P79-80） 5.5 給定解釋I如下: (a) 個體域D={3,4}； (b) (x)：(3)=4, (4)=3； (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))) (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?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)→￢?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). (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)) ①②假言推理 ④ (F(c)∨G(c))→R(c) ③全稱量詞消去規(guī)則 ⑤ F(c) ①存在量詞消去規(guī)則 ⑥ F(c) ∨ G(c) ⑤附加 ⑦ R(c) ④⑥假言推理 ⑧ ?xR(x) ⑦存在量詞引入規(guī)則 (2) 證明: ① ?xF(x) 前提引入 ② F(c) ①存在量詞消去規(guī)則 ③ ?x(F(x)→(G(a)∧R(x))) 前提引入 ④ F(c)→(G(a)∧R(c)) ④全稱量詞消去規(guī)則 ⑤ G(a)∧R(c) ②④假言推理 ⑥ R(c) ⑤化簡 ⑦ F(c)∧R(c) ②⑥合取引入 ⑧ ?x(F(x)∧R(x)) ⑦存在量詞引入規(guī)則 (3) 證明: ① ￢?xG(x) 前提引入 ② ?x￢G(x) ①置換 ③ ￢G(c) ②全稱量詞消去規(guī)則 ④ ?x(F(x)∨G(x)) 前提引入 ⑤ 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)) 前提引入 ④ ￢G(y) ∨￢R(y) ③全稱量詞消去規(guī)則 ⑤ ?xR(x) 前提引入 ⑥ R(y) ⑤全稱量詞消去規(guī)則 ⑦ ￢G(y) ④⑥析取三段論 ⑧ F(y) ②⑦析取三段論 ⑥ ?xF(x) ⑧存在量詞引入規(guī)則 第11次作業(yè)（P96） 6.4. 設(shè) F 表示一年級大學(xué)生的集合, S 表示二年級大學(xué)生的集合, M表示數(shù)學(xué)專業(yè)學(xué)生的集合, R 表示計算機(jī)專業(yè)學(xué)生的集合, T表示聽離散數(shù)學(xué)課學(xué)生的集合, G 表示星期一晚上參加音樂會的學(xué)生的集合, H 表示星期一晚上很遲才睡覺的學(xué)生的集合. 問下列各句子所對應(yīng)的集合表達(dá)式分別是什么? 請從備選的答案中挑出來. (1)所有計算機(jī)專業(yè)二年級的學(xué)生在學(xué)離散數(shù)學(xué)課. (2)這些且只有這些學(xué)離散數(shù)學(xué)課的學(xué)生或者星期一晚上去聽音樂會的學(xué)生在星期一晚上很遲才睡覺. (3)聽離散數(shù)學(xué)課的學(xué)生都沒參加星期一晚上的音樂會. (4)這個音樂會只有大學(xué)一, 二年級的學(xué)生參加. (5)除去數(shù)學(xué)專業(yè)和計算機(jī)專業(yè)以外的二年級學(xué)生都去參加了音樂會. 備選答案: ①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, 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}上的恒等關(guān)系IA, 全域關(guān)系EA, 小于或等于關(guān)系LA, 整除關(guān)系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.設(shè)A={0, 1, 2, 3}, R 是A 上的關(guān)系, 且 R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?} 2 3 0 1 0 給出R的關(guān)系矩陣和關(guān)系圖. 解: 第13次作業(yè)（P131） 7.13.設(shè) 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={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3} 7.15.設(shè) A={??,{?,{?}}?,?{?},??} 求A?1,A2,A3,A?{?},A[?],A??,A?{{?}},A[{{?}}]. 解: A?1={?{?,{?}},??,??,{?}?}, A2={?{?},{?,{?}}?}, A3=?, A?{?}={??,{?,{?}}?}, A[?]={?,{?}},  A??=?, A?{{?}}={?{?},??}, A[{{?}}]=? 7.16.設(shè)A={a,b,c,d}, R1,R2 為A上的關(guān)系, 其中 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.設(shè)A={a,b,c}, 試給出A 上兩個不同的關(guān)系R1和R2,使得 R12=R1, R23=R2. 解: R1={?a,a?,?b,b?}, R2={?b,c?,?c,b?} 第14次作業(yè)（P131-133） 7.21. 設(shè)A={1，2，…,10},定義A上的關(guān)系 R={<x,y>|x,y∈A∧x+y=10} 說明R具有哪些性質(zhì)并說明理由。 解:只有對稱性。因?yàn)?+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. 設(shè)A={1，2，3，4，5，6}，R為A上的關(guān)系，R的關(guān)系圖如圖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>,<3,3>,<3,1>,<3,5>,<4,5>} 第15次作業(yè)（P134-135） 7.41.設(shè)A={1，2，3，4}，R為AA上的二元關(guān)系, 〈a，b〉，〈c，d〉 AA , 〈a，b〉R〈c，d〉a + b = c + d (1) 證明R為等價關(guān)系. (2) 求R導(dǎo)出的劃分. (1)證明：<a，b〉 AA a+b=a+b ∴<a,b>R<a,b> ∴R是自反的 任意的<a,b>,<c,d>∈AA 設(shè)<a,b>R<c,d>，則a+b=c+d ∴c+d=a+b ∴<c,d>R<a,b> ∴R是對稱的 任意的<a,b>,<c,d>,<x,y>∈AA 若<a,b>R<c,d>,<c,d>R<x,y> 則a+b=c+d,c+d=x+y ∴a+b=x+y ∴<a,b>R<x,y> ∴R是傳遞的 ∴R是 AA上的等價關(guān)系 (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.對于下列集合與整除關(guān)系畫出哈斯圖: (1) {1,2,3,4,6,8,12,24} (2) {1,2,3,4,5,6,7,8,9,10,11,12} 解:哈斯圖如下圖所示: 　　 7.46.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元`極小元`最大元和最小元. (1)A={a,b,c,d,e} R={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}IA. (2)A={a,b,c,d,e}, R={<c,d>}IA. 解: （1）極大元e；極小元a；最大e；最小元a。 （2）極大元a,b,d,e；極小元a,b,c,e；沒有最大與最小元。 第16次作業(yè)（P161-135） 4. 判斷下列函數(shù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (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ù)的集合定義計算： (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．判斷下列集合對所給的二元運(yùn)算是否封閉： （1）整數(shù)集合Z和普通的減法運(yùn)算。 （2）非零整數(shù)集合Z*和普通的除法運(yùn)算。 （3）全體nn實(shí)矩陣集合Mn（R）和矩陣加法及乘法運(yùn)算，其中n≥2。 （4）全體實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n錯誤！未找到引用源。2。 （5）正實(shí)數(shù)集合錯誤！未找到引用源。和錯誤！未找到引用源。運(yùn)算，其中錯誤！未找到引用源。運(yùn)算定義為： 錯誤！未找到引用源。 （6）錯誤！未找到引用源。關(guān)于普通的加法和乘法運(yùn)算。 （7）A = { 錯誤！未找到引用源。n錯誤！未找到引用源。運(yùn)算定義如下： 錯誤！未找到引用源。 （8）S = 錯誤！未找到引用源。關(guān)于普通的加法和乘法運(yùn)算。 （9）S = {0,1},S是關(guān)于普通的加法和乘法運(yùn)算。 （10）S = 錯誤！未找到引用源。 ,S關(guān)于普通的加法和乘法運(yùn)算。 5．對于上題中封閉的二元運(yùn)算判斷是否適合交換律，結(jié)合律，分配律。 解: （1）封閉,不滿足交換律和結(jié)合律，無零元和單位元 （2）不封閉 （3）封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元； 乘法單位元是單位矩陣，零元是零矩陣； （4）不封閉 （5）不封閉 因?yàn)? （6）封閉，均滿足交換律，結(jié)合律，乘法對加法滿足分配律 加法單位元是0，無零元； 乘法無單位元（），零元是0；單位元是1 （7）封閉 不滿足交換律，滿足結(jié)合律， （8）封閉 均滿足交換律，結(jié)合律，乘法對加法滿足分配律 （9）加法不封閉，乘法封閉；乘法滿足交換律，結(jié)合律 （10）加法不封閉，乘法封閉，乘法滿足交換律，結(jié)合律 10．令S={a，b}，S上有四個運(yùn)算：*，錯誤！未找到引用源。分別有表10.8確定。 (a) (b) (c) (d) (1)這4個運(yùn)算中哪些運(yùn)算滿足交換律，結(jié)合律，冪等律？ (2)求每個運(yùn)算的單位元，零元以及每一個可逆元素的逆元。 解: (a) 交換律，結(jié)合律，冪等律都滿足， 零元為a,沒有單位元； (b)滿足交換律和結(jié)合律，不滿足冪等律，單位元為a,沒有零元 (c)滿足交換律,不滿足冪等律,不滿足結(jié)合律 沒有單位元, 沒有零元 (d) 不滿足交換律，滿足結(jié)合律和冪等律 沒有單位元, 沒有零元 16．設(shè)V=〈 N，+ ，錯誤！未找到引用源。〉，其中+ ，錯誤！未找到引用源。分別代表普通加法與乘法，對下面給定的每個集合確定它是否構(gòu)成V的子代數(shù)，為什么？ （1）S1=錯誤！未找到引用源。 （2）S2=錯誤！未找到引用源。 （3）S3 = {-1，0，1} 解: （1）是 （2）不是 加法不封閉 （3）不是，加法不封閉 第18次作業(yè)（P202-205） 8.設(shè)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ù)運(yùn)算。 (2) x,y,z∈S,設(shè)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 4 所以，(xy)z = x(yz)，結(jié)合律成立。 (3) x∈S, (x1)=(1x)=x,，所以1是單位元。 (4) 0和2沒有逆元 所以，〈S，〉不構(gòu)成群 9.設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算。如下： x,y∈Z,xoy= x+y-2 問Z關(guān)于o運(yùn)算能否構(gòu)成群？為什么？ 解：(1) x,y∈Z, xoy= x+y-2,o是Z上的代數(shù)運(yùn)算。 (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)設(shè)是單位元，x∈Z, xo= ox=x,即x+-2= +x-2=x, e=2 (4) x∈Z , 設(shè)x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, 所以， 所以〈Z，o〉構(gòu)成群 22.設(shè)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.設(shè)是5元置換，且 ， (1)計算； (2)將表示成不交的輪換之積。 (3)將（2）中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換。 解：(1) (2) (3) 奇置換， 偶置換 奇置換