離散數學作業(yè)2

1、離散數學作業(yè)布置第1次作業(yè)（P15）1.16 設p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 解：（1）p(qr)=0(01)=0 （2）（pr）(qs)=（01）(11)=01 =0 （3）（pqr）(pqr)=（111） (000)=0(4)（ rs）(p q)=（01）(10)=00=11.17 判斷下面一段論述是否為真：“是無理數。并且，如果3是無理數，則 也是無理數。另外只有6能被2整除，6才能被4整除?！苯猓?p: 是無理數 1 q: 3是無理數 0 r: 是無理數 1 s:6能被2整除 1t: 6能被4整除 0 命題符號化為： p(qr)(ts)的真值為1，所以這

2、一段的論述為真。1.19 用真值表判斷下列公式的類型：（4）(pq) (qp)（5）(pr) (p q)（6）(pq) (qr) (pr)解： （4） p q pq q p q p (pq)( 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) (pqq)(2

3、)(p(pq)(pr)(3)(pq)(pr)解：(1) (pqq) Û(pq) q) Û(pq) qÛp(q q) Û p0 Û0所以公式類型為矛盾式(2)（p(pq)）(pr) Û (p(pq)( pr) ÛppqrÛ1 所以公式類型為永真式(3) (pq) (pr) Û (pq) (pr) Û (pq) (pr) 易見, 是可滿足式, 但不是重言式. 成真賦值為: 000,001, 101, 111P q r pq pr (pq) (pr)0 0 0 1 0 10 0 1 1 0 10 1

4、0 0 0 00 1 1 0 0 01 0 0 0 0 01 0 1 0 1 11 1 0 0 0 01 1 1 0 1 1 所以公式類型為可滿足式2.4 用等值演算法證明下面等值式：(2) ( (pq)(pr) ) Û (p(qr)(4)(pq)(pq) Û (pq)(pq)證明（2）(pq)(pr)Û( pq)(pr)Ûp(qr)Ûp(qr)（4）(pq)(pq) Û (p(pq) (q(pq) ) Û (pp)(pq)(qp) (qq) Û1(pq) (pq)1 Û (pq)(pq)第3次作業(yè)（P3

5、8）2.5 求下列公式的主析取范式, 并求成真賦值:(1)( pq) (qp)(2) (pq) qr(3)(p (qr) (pqr)(4) (pq) qr解：(1)(pq) (qp)Û(pq) (qp)Ûpq q pÛq p (吸收律) Û (pp)q p(qq)Ûpqpq pq pqÛm0m2m2m3 Ûm0m2m3成真賦值為 00, 10, 11.(2) (pq) qrÛ (pq) qrÛ (pqr) qrÛ (pqr) (p p) qrÛpqrp qrpqrÛm3m7成

6、真賦值為011，111.(3) (p(qr) (pqr)Û(p(qr) (pqr)Ûp(qr) (pqr)Ûp(qr)(pqr)ÛpqprpqrÛpq(rr)p(qq)rp(qq) (rr) (pp) q(rr)(pp) (qq) rÛm0m1m2m3m4m5m6m7, 為重言式.(4) (pq) qrÛ(pq) qrÛ (pq) qrÛ p(q q)rÛ0主析取范式為0, 無成真賦值, 為矛盾式.第4次作業(yè)（P38）2.6 求下列公式的主合取范式, 并求成假賦值:(1) (qp) p(2)(p

7、q) (pr)(3)(p(pq) r解：(1) (qp) pÛ(qp) pÛqp pÛq0Û0ÛM0M1M2M3這是矛盾式. 成假賦值為 00, 01, 10, 11.(2)(pq) (pr)Û(pq) prÛ(pp)(p q)rÛ (p q)rÛ p qrÛM4, 成假賦值為100.(3)(p(pq) rÛ(p(pq) rÛ(pp)q rÛ1主合取范式為1, 為重言式.第5次作業(yè)（P41）2.32 用消解原理證明下述公式是矛盾式:(1) (pq) (pr) (qr

8、) (pr) r(2) (pq) pq)解：(1) (pq) (pr) (qr) (pr) r第一次循環(huán) S0=, S1=pq,pr,qr,pr,r, S2=由pr, pr消解得到輸出“no”，計算結束(2) (pq) pq)Û(pq) p) q)Û(pq) p) qÛ (pq) p q第一次循環(huán) S0=, S1=pq,p, q, S2=由pq,p消解得到q,由q, q消解得到,輸出“no”，計算結束2.33 用消解法判斷下述公式是否可滿足的:(1) p (pq) q(2) (pq) (pq) (p r)解：(1) p (pq) q第一次循環(huán) S0=, S1=p,

9、 pq, q, S2=由p, pq消解得到q,由q, q消解得到,輸出“no”，計算結束(2) (pq) (pq) (p r)第一次循環(huán) S0=, S1=pq, pq, p r, S2=由pq, pq消解得到p,由pq, p r消解得到q r,由pq, p r消解得到q r,由p, p r消解得到r,S2=p, q r, q r, r第二次循環(huán) S0=pq, pq, p r, S1=p, q r, q r, r, S2=由pq, q r消解得到pr,由pq, q r消解得到pr,由pq, q r消解得到pr,由p r, p 消解得到r,S2=pr第三次循環(huán) S0=p, q r, q r, r,

10、 S1=pr, S2=S2=輸出“yes”，計算結束第6次作業(yè)（P52）3.6 判斷下面推理是否正確. 先將簡單命題符號化, 再寫出前提, 結論, 推理的形式結構(以蘊涵式的形式給出)和判斷過程(至少給出兩種判斷方法):(1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三.(2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一.(3)若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一.(4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二.(5)若今天是星期一, 則明天是星期二或星期三. 今天是星期一. 所以明天是

11、星期二.(6)今天是星期一當且僅當明天是星期三；今天不是星期一. 所以明天不是星期三.設p: 今天是星期一, q: 明天是星期二, r: 明天是星期三.(1)推理的形式結構為(pr) pr此形式結構為重言式, 即(pr) pÞr所以推理正確.(2)推理的形式結構為(pq) qp此形式結構不是重言式, 故推理不正確.(3)推理形式結構為(pr) rp此形式結構為重言式, 即(pr) rÞp故推理正確.(4)推理形式結構為(pq) pq此形式結構不是重言式, 故推理不正確.(5)推理形式結構為(p(qr) )p q它不是重言式, 故推理不正確.(6)推理形式結構為(pr) pr

12、此形式結構為重言式, 即(pr) pÞr故推理正確.推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等值演算法. 證明推理正確還可用構造證明法.下面用等值演算法和構造證明法證明(6)推理正確.1. 等值演算法(pr) prÛ(pr) (rp)prÛ(pr) (rp)p) rÛ (pr) (rp) p rÛ(pr)(rp)p rÛ (rp)p r吸收律Û (rp)（p r）德摩根律Û1即(pr) pÞr故推理正確2.構造證明法前提: (pr), p結論: r證明: pr 前提引入 (pr) (r

13、p) 置換 rp 化簡律p 前提引入r 拒取式所以, 推理正確.第7次作業(yè)（P53-54）3.15 在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1)前提: p(qr), sp, q 結論: sr (2)前提: (pq) (rs), (st) u 結論: pu (1)證明: s 附加前提引入sp 前提引入 p 假言推理p(qr) 前提引入qr 假言推理 q 前提引入 r 假言推理(2)證明: P 附加前提引入pq 附加(pq) (rs) 前提引入rs 假言推理 S 化簡st 附加(st) u 前提引入 u 假言推理3.16 在自然推理系統(tǒng)P中用歸謬法證明下面推理: (1)前提: pq, r

14、q, rs 結論: p (2)前提: pq, pr, qs 結論: rs (1)證明: P 結論否定引入pq 前提引入q 假言推理rq 前提引入r 析取三段論rs 前提引入 r 化簡規(guī)則rr 合取引入規(guī)則為矛盾式, 由歸謬法可知, 推理正確. (2)證明: (rs) 結論否定引入pq 前提引入pr 前提引入qs 前提引入(pr) (qs) (pq) 合取引入規(guī)則rs 構造性二難(rs) (rs) 合取引入規(guī)則為矛盾式, 所以推理正確.第8次作業(yè)（P65-66）4.5 在一階邏輯中將下列命題符號化:(1)火車都比輪船快.(2)有的火車比有的汽車快.(3)不存在比所有火車都快的汽車.(4)“凡是汽

15、車就比火車慢”是不對的.解：因為沒指明個體域, 因而使用全總個體域(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

16、快.(4) xy(F(x) G(y) ®H(x,y)或xy(F(x) G(y) H(x,y) ) 其中, F(x): x 是汽車, G(y): y 是火車, H(x,y):x 比y 慢.4.9 給定解釋 I 如下:(a)個體域為實數集合R.(b)特定元素 =0.(c)特定函數(x,y)=x-y, x,yR.(d)謂詞(x,y): x=y,(x,y): x<y, x,yR.給出下列公式在I 下的解釋, 并指出它們的真值:(1) xy(G(x,y) ®F(x,y)(2) xy(F(f(x,y),a) ®G(x,y)(3) xy(G(x,y) ®F(f(

17、x,y),a)(4) xy(G(f(x,y),a) ®F(x,y)解：(1) xy(x<y®xy), 真值為1.(2) xy(x-y=0) ®(x<y), 真值為0.(3) xy(x<y) ® (x-y0), 真值為1.(4) xy(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) xyF(x,y)

18、 (2) xyF(x,y) (3) xy(F(x,y)F(f(x),f(y) 解：(1) xyF(x,y) Û (F(3,3)F(3,4)(F(4,3)F(4,4) Û (01)(10) Û 1 (2) xyF(x,y) Û (F(3,3)F(3,4)(F(4,3)F(4,4) Û (01)(10) Û 0 (3) xy(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) Û

19、(00)(11)(11)(00) Û15.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)Û xy(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)Ûxu(F(x, y

20、)G(u, y)xv(G(x, y)F(v, y)Ûxu(F(x, y)G(u, y)wv(G(w, y)F(v, y)Ûxuwv (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)x2G(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)Ûx1x2 (F(x1, x3)(F(x4

21、)G(x4, x2)第10次作業(yè)（P79-80）5.15 在自然推理系統(tǒng)FL中,構造下面推理的證明:(1) 前提: xF(x) y(F(y)G(y)R(y),xF(x)結論:xR(x).(2) 前提:x(F(x)(G(a)R(x),xF(x)結論:x(F(x)R(x)(3) 前提:x(F(x)G(x), xG(x)結論:xF(x)(4) 前提:x(F(x)G(x),x(G(x)R(x),xR(x)結論: 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)

22、 存在量詞消去規(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) 前提引入 xG(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) 前

23、提引入 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. 設 F 表示一年級大學生的集合, S 表示二年級大學生的集合, M表示數學專業(yè)學生的集合, R 表示計算機專業(yè)學生的集合, T表示聽離散數學課學生的集合, G 表示星期一晚上參加音樂會的學生的集合, H 表示星期一晚上很遲才睡覺的學生的集合. 問下列各句子所對應的集合表達式分別是什么? 請從備選的答案中挑出來.(1)所有計算機專業(yè)二

24、年級的學生在學離散數學課.(2)這些且只有這些學離散數學課的學生或者星期一晚上去聽音樂會的學生在星期一晚上很遲才睡覺.(3)聽離散數學課的學生都沒參加星期一晚上的音樂會.(4)這個音樂會只有大學一, 二年級的學生參加.(5)除去數學專業(yè)和計算機專業(yè)以外的二年級學生都去參加了音樂會.備選答案:TÍGH GHÍT SRÍTHGT TGÆ FSÍGGÍFS S-(RM) ÍG GÍS-(RM)解:(1) SRÍT(2) H=GT(3) TG=Æ(4) GÍFS(5) S-(RM) Í

25、;G6.5. 確定下列命題是否為真:(1) ÆÍÆ(2) ÆÆ(3) ÆÍÆ(4) ÆÆ(5)a, bÍa, b, c, a, b, c(6)a, ba, b, c, a, b (7)a, bÍa, b, a, b(8)a, ba, b, a, b解:(1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假第12次作業(yè)（P130-131）7.1. 已知 A=Æ,Æ,求A×P(A).解:A×P(A)= Æ,

26、Æ×Æ,Æ,Æ,Æ,Æ=<Æ, Æ>,<Æ,Æ>,<Æ,Æ>,<Æ,Æ,Æ>,<Æ,Æ>,<Æ,Æ>,<Æ,Æ>, <Æ,Æ,Æ>7.7. 列出集合 A=2, 3, 4上的恒等關系IA, 全域關系EA, 小于或等于關系LA, 整除關系DA.解:IA=&l

27、t;2,2>,<3,3>,<4,4>EA=A×A=<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

28、 上的關系, 且R=0, 0, 0, 3, 2, 0, 2, 1, 2, 3, 3, 223010給出R的關系矩陣和關系圖. 解:第13次作業(yè)（P131）7.13.設A = 1, 2, 2, 4, 3, 3B = 1, 3, 2, 4, 4, 2求AB, AB, domA, dom(AB), ranA, ranB, ran(AB), fld(AB).解:AB=1,2, 1,3, 2,4, 3,3, 4,2 AB=2,4domA=1,2,3dom(AB)=1,2,3,4ranA=2,3,4ranB=3,4,2ran(AB)=4fld(AB)=1,2,37.15.設A=,求A1,A2,A3,A,A

29、,A,A,A.解:A1=,A2=,A3=,A=,A=, A=,A=,A=7.16.設A=a,b,c,d, R1,R2 為A上的關系, 其中R1=a,a,a,b,b,dR2=a,d,b,c,b,d,c,b求R1R2, R2R1,R12,R23.解:R1R2=a,a,a,c,a,d,R2R1=c,d,R12=a,a,a,b,a,d,R23=b,c,b,d,c,b7.17.設A=a,b,c, 試給出A 上兩個不同的關系R1和R2,使得 R12=R1, R23=R2.解:R1=a,a,b,b,R2=b,c,c,b第14次作業(yè)（P131-133）7.21. 設A=1，2，,10,定義A上的關系 R=&l

30、t;x,y>|x,yAx+y=10說明R具有哪些性質并說明理由。解:只有對稱性。因為1+110,<1,1>R,所以R不是自反的；又由于<5,5>R,因此R不是反自反的；根據xRyx+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，3，4，5，6，R為A上的關系，R的關系圖如圖3.13所示：123456解: (1)R=&

31、lt;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

32、,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.設A=1，2，3，4，R為AA上的二元關系, a，b，c，d AA , a，bRc，da + b = c + d(1) 證明R為等價關系.(2) 求R導出的劃分.(1)證明：<a，b AA a+b=a+b<a,b>R<a,b

33、> R是自反的任意的<a,b>,<c,d>A×A設<a,b>R<c,d>，則a+b=c+dc+d=a+b <c,d>R<a,b>R是對稱的任意的<a,b>,<c,d>,<x,y>A×A若<a,b>R<c,d>,<c,d>R<x,y>則a+b=c+d,c+d=x+ya+b=x+y <a,b>R<x,y>R是傳遞的R是 A×A上的等價關系(2)=<1,1>,<1,2&

34、gt;,<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,12解:哈斯圖如下圖所示: 7.46.分別畫出下列各偏序集<A,R>的哈斯圖,并找出A的極大元極小

35、元最大元和最小元.(1)A=a,b,c,d,eR=<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. 判斷下列函數中哪些是滿射的?哪些是單射的?哪些是雙射的? (1) f:NN, f(x)=x2+2 (2) f:NN,f(x)=(x)mod 3, x除以3的余

36、數 (3) f:NN,f(x)= (4) f:N0,1,f(x)= (5) f:N-0R,f(x)=lgx (6) f:RR,f(x)=x2-2x-15 解:(1)不是滿射，不是單射(2)不是滿射，不是單射(3)不是滿射，不是單射(4)是滿射，不是單射(5)不是滿射，是單射(6)不是滿射，不是單射37. 根據自然數的集合定義計算：(1) 36, 25 ;(2)43,31(3)4 , 1 (4)1×4 ，2解:(1) 36 = 6, 25 = 2;(2)43 =3,31 = 1,2(3)4 = 3, 1 = 0(4)1×4 = <0,0>,<0,1>,

37、<0,2>,<0,3>,2= ,，其中: =<0,0>,<1,0> = <0,0>,<1,1>38. 計算下列集合的基數：解:(1)3, (2), (3), (4), (5), (6),第17次作業(yè)（P178-180）4判斷下列集合對所給的二元運算是否封閉：（1）整數集合Z和普通的減法運算。（2）非零整數集合Z*和普通的除法運算。（3）全體n×n實矩陣集合Mn（R）和矩陣加法及乘法運算，其中n2。（4）全體實可逆矩陣集合關于矩陣加法及乘法運算，其中n錯誤！未找到引用源。2。（5）正實數集合錯誤！未找到引用源。和錯

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