離散數(shù)學(xué)作業(yè) (2)

1、.離散數(shù)學(xué)作業(yè)布置第1次作業(yè)（P15）1.16 設(shè)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 判斷下面一段論述是否為真：“是無理數(shù)。并且，如果3是無理數(shù)，則 也是無理數(shù)。另外只有6能被2整除，6才能被4整除。”解： p: 是無理數(shù) 1 q: 3是無理數(shù) 0 r: 是無理數(shù) 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)(

3、2)(p(pq)(pr)(3)(pq)(pr)解：(1) (pqq) (pq) q) (pq) qp(q q) p0 0所以公式類型為矛盾式(2)（p(pq)）(pr) (p(pq)( pr) ppqr1 所以公式類型為永真式(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 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

4、所以公式類型為可滿足式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è)（P38）2.5 求下列公式的主析取范式, 并求成真賦值:(1)( pq) (qp)(2) (pq) qr(3)(p (qr) (pqr)(4) (pq) qr解：(1)(pq) (qp)(pq) (qp)pq q pq p (吸收律) (pp)q

5、p(qq)pqpq pq pqm0m2m2m3 m0m2m3成真賦值為 00, 10, 11.(2) (pq) qr (pq) qr (pqr) qr (pqr) (p p) qrpqrp qrpqrm3m7成真賦值為011，111.(3) (p(qr) (pqr)(p(qr) (pqr)p(qr) (pqr)p(qr)(pqr)pqprpqrpq(rr)p(qq)rp(qq) (rr) (pp) q(rr)(pp) (qq) rm0m1m2m3m4m5m6m7, 為重言式.(4) (pq) qr(pq) qr (pq) qr p(q q)r0主析取范式為0, 無成真賦值, 為矛盾式.第4次作

6、業(yè)（P38）2.6 求下列公式的主合取范式, 并求成假賦值:(1) (qp) p(2)(pq) (pr)(3)(p(pq) r解：(1) (qp) p(qp) pqp pq00M0M1M2M3這是矛盾式. 成假賦值為 00, 01, 10, 11.(2)(pq) (pr)(pq) pr(pp)(p q)r (p q)r p qrM4, 成假賦值為100.(3)(p(pq) r(p(pq) r(pp)q r1主合取范式為1, 為重言式.第5次作業(yè)（P41）2.32 用消解原理證明下述公式是矛盾式:(1) (pq) (pr) (qr) (pr) r(2) (pq) pq)解：(1) (pq) (p

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

8、) (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, S1=pr, S2=S2=輸出“yes”，計算結(jié)束第6次作業(yè)（P52）3.6 判斷下面推理是否正確.

9、 先將簡單命題符號化, 再寫出前提, 結(jié)論, 推理的形式結(jié)構(gòu)(以蘊(yùn)涵式的形式給出)和判斷過程(至少給出兩種判斷方法):(1)若今天是星期一, 則明天是星期三；今天是星期一. 所以明天是星期三.(2)若今天是星期一, 則明天是星期二；明天是星期二. 所以今天是星期一.(3)若今天是星期一, 則明天是星期三；明天不是星期三. 所以今天不是星期一.(4)若今天是星期一, 則明天是星期二；今天不是星期一. 所以明天不是星期二.(5)若今天是星期一, 則明天是星期二或星期三. 今天是星期一. 所以明天是星期二.(6)今天是星期一當(dāng)且僅當(dāng)明天是星期三；今天不是星期一. 所以明天不是星期三.設(shè)p: 今天是星

10、期一, q: 明天是星期二, r: 明天是星期三.(1)推理的形式結(jié)構(gòu)為(pr) pr此形式結(jié)構(gòu)為重言式, 即(pr) pr所以推理正確.(2)推理的形式結(jié)構(gòu)為(pq) qp此形式結(jié)構(gòu)不是重言式, 故推理不正確.(3)推理形式結(jié)構(gòu)為(pr) rp此形式結(jié)構(gòu)為重言式, 即(pr) rp故推理正確.(4)推理形式結(jié)構(gòu)為(pq) pq此形式結(jié)構(gòu)不是重言式, 故推理不正確.(5)推理形式結(jié)構(gòu)為(p(qr) )p q它不是重言式, 故推理不正確.(6)推理形式結(jié)構(gòu)為(pr) pr此形式結(jié)構(gòu)為重言式, 即(pr) pr故推理正確.推理是否正確, 可用多種方法證明. 證明的方法有真值表法, 等值演算法. 證

11、明推理正確還可用構(gòu)造證明法.下面用等值演算法和構(gòu)造證明法證明(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) pr故推理正確2.構(gòu)造證明法前提: (pr), p結(jié)論: r證明: pr 前提引入 (pr) (rp) 置換 rp 化簡律p 前提引入r 拒取式所以, 推理正確.第7次作業(yè)（P53-54）3.15 在自然推理系統(tǒng)P中用附加前提法證明下面各推理: (1)前提: p(qr), sp, q 結(jié)論: sr (2)前提: (pq) (rs)

12、, (st) u 結(jié)論: 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, rq, rs 結(jié)論: p (2)前提: pq, pr, qs 結(jié)論: rs (1)證明: P 結(jié)論否定引入pq 前提引入q 假言推理rq 前提引入r 析取三段論rs 前提引入 r 化簡規(guī)則rr 合取引入規(guī)則為矛盾式, 由歸謬法可知, 推

13、理正確. (2)證明: (rs) 結(jié)論否定引入pq 前提引入pr 前提引入qs 前提引入(pr) (qs) (pq) 合取引入規(guī)則rs 構(gòu)造性二難(rs) (rs) 合取引入規(guī)則為矛盾式, 所以推理正確.第8次作業(yè)（P65-66）4.5 在一階邏輯中將下列命題符號化:(1)火車都比輪船快.(2)有的火車比有的汽車快.(3)不存在比所有火車都快的汽車.(4)“凡是汽車就比火車慢”是不對的.解：因為沒指明個體域, 因而使用全總個體域(1) xy(F(x) G(y) H(x,y) 其中, F(x): x 是火車, G(y): y 是輪船, H(x,y):x 比y 快.(2) $x$y(F(x) G(

14、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) 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)個體域為實(shí)數(shù)集合R.(b)特定元素 =0.(c)特定函數(shù)(x,y)=x-y, x,yR.(d)謂詞(

15、x,y): x=y,(x,y): xy, 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(x,y),a)(4) xy(G(f(x,y),a) F(x,y)解：(1) xy(xyxy), 真值為1.(2) xy(x-y=0) (xy), 真值為0.(3) xy(xy) (x-y0), 真值為1.(4) xy(x-y0) (x=y), 真值為0.第9次作業(yè)（P79-80）5.5 給定解釋I如下: (a) 個體域D=3,4； (b) (x)：(3)=4, (4)=3

16、；(c)(x,y)：(3,3)=(4,4)=0,(3,4)=(4,3)=1. 試求下列公式在I下的真值: (1) xyF(x,y) (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

17、(4),f(4) (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)G(u, y)xv(G(x, y)F(v, y)xu

18、(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)G(x4, x2)第10次作業(yè)（P79-80）5.15 在自然推理系統(tǒng)FL中,構(gòu)造下面推理的證明:(1) 前提: xF(x) y(F(y

19、)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

20、) 存在量詞消去規(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) 前提引入 F(y)G(y) 全稱量詞消去規(guī)則x(G(x)R(x) 前提引入 G(y) R(y) 全稱量詞消去規(guī)則 xR(x) 前提引入 R(

21、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é)課的

22、學(xué)生都沒參加星期一晚上的音樂會.(4)這個音樂會只有大學(xué)一, 二年級的學(xué)生參加.(5)除去數(shù)學(xué)專業(yè)和計算機(jī)專業(yè)以外的二年級學(xué)生都去參加了音樂會.備選答案:TGH GHT SRTHGT TG FSGGFS S-(RM) G GS-(RM)解:(1) SRT(2) H=GT(3) TG=(4) GFS(5) S-(RM) G6.5. 確定下列命題是否為真:(1) (2) (3) (4) (5)a, ba, b, c, a, b, c(6)a, ba, b, c, a, b (7)a, ba, b, a, b(8)a, ba, b, a, b解:(1) 真(2)假(3) 真(4) 真(5) 真(6)

23、 真(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=,EA=AA=,LA=,DA=,7.12.設(shè)A=0, 1, 2, 3, R 是A 上的關(guān)系, 且R=0, 0, 0, 3, 2, 0, 2, 1, 2, 3, 3, 223010給出R的關(guān)系矩陣和關(guān)系圖. 解:第13次作業(yè)（P131）7.13.設(shè)A = 1, 2, 2, 4, 3, 3B = 1, 3, 2, 4, 4, 2求AB, AB, domA, dom

24、(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.設(shè)A=,求A1,A2,A3,A,A,A,A,A.解:A1=,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,dR2=a,d,b,c,b,d,c,b求R1R2, R2R1,R12,R23.解:R1R2=a,a,a,c,a,d,R

25、2R1=c,d,R12=a,a,a,b,a,d,R23=b,c,b,d,c,b7.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,yAx+y=10說明R具有哪些性質(zhì)并說明理由。解:只有對稱性。因為1+110,R,所以R不是自反的；又由于R,因此R不是反自反的；根據(jù)xRyx+y =10=yRx ,可知R是對稱的；又由于,都是屬于R,因此R不是反對稱的；,都屬于R,如果R是傳遞的,必有屬于R.但這是不成立的,因

26、此R也不是傳遞的.7.26. 設(shè)A=1，2，3，4，5，6，R為A上的關(guān)系，R的關(guān)系圖如圖3.13所示：123456解: (1)R=,，,R=, R3= ,. (2)r(R)=, s(R)=, T(R)=,第15次作業(yè)（P134-135）7.41.設(shè)A=1，2，3，4，R為AA上的二元關(guān)系, a，b，c，d AA , a，bRc，da + b = c + d(1) 證明R為等價關(guān)系.(2) 求R導(dǎo)出的劃分.(1)證明：a，b AA a+b=a+bR R是自反的任意的,AA設(shè)R，則a+b=c+dc+d=a+b RR是對稱的任意的,AA若R,R則a+b=c+d,c+d=x+ya+b=x+y RR是

27、傳遞的R是 AA上的等價關(guān)系(2)=, , , 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的極大元極小元最大元和最小元.(1)A=a,b,c,d,eR=,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ù)中哪些是滿射的?哪些是單射的?哪些是雙射的? (1)

28、f:NN, f(x)=x2+2 (2) f:NN,f(x)=(x)mod 3, x除以3的余數(shù) (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. 根據(jù)自然數(shù)的集合定義計算：(1) 36, 25 ;(2)43,31(3)4 , 1 (4)14 ，2解:(1) 36 = 6, 25 = 2;(2)43 =3,31 = 1,2(3)4 = 3, 1 =

29、 0(4)14 = ,2= ,，其中: =, = ,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)算，其中n2。（4）全體實(shí)可逆矩陣集合關(guān)于矩陣加法及乘法運(yùn)算，其中n錯誤！未找到引用源。2。（5）正實(shí)數(shù)集合錯誤！未找到引用源。和錯誤！未找到引用源。運(yùn)算，其中錯誤！未找到引用源。運(yùn)算定義為：錯誤！未找到引用源。（6）錯誤！未找到引用源。關(guān)于普通的加法和乘法

30、運(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）不封閉 因為 （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)算的單位元，零元以及每一個可逆元素的逆元。解: