《離散數(shù)學(xué)第1-7章 習(xí)題詳解》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第1-7章 習(xí)題詳解（15頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、
第一章 命題邏輯基本概念
課后練習(xí)題答案
1、是命題的為（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13）
是簡單命題的為（1）、（2）、（7）、（10）、（13）
是真命題的為（1）、（2）、（3）、（10）、（11）
真值現(xiàn)在不知道的為（13）
2、3略
4.將下列命題符號(hào)化，并指出真值：
?。?）p∧q,其中，p:2是素?cái)?shù)，q:5是素?cái)?shù),真值為1；
?。?）p∧q,其中，p:是無理數(shù)，q:自然對數(shù)的底e是無理數(shù),真值為1；
?。?）p∧┐q,其中，p:2是最小的素?cái)?shù)，q:2是最小的自然數(shù),真值為1；
?。?）p
2、∧q,其中，p:3是素?cái)?shù)，q:3是偶數(shù),真值為0；
?。?）┐p∧┐q,其中，p:4是素?cái)?shù)，q:4是偶數(shù),真值為0.
5.將下列命題符號(hào)化，并指出真值：
（1）p∨q,其中，p:2是偶數(shù)，q:3是偶數(shù),真值為1；
（2）p∨q,其中，p:2是偶數(shù)，q:4是偶數(shù),真值為1；
?。?）p∨┐q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為0；
?。?）p∨q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為1；
?。?）┐p∨┐q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為0；
6.（1）(┐p∧q)∨(p∧┐q),其中，小麗從筐里拿一個(gè)蘋果，q：小麗從筐里拿一個(gè)梨；
3、 ?。?）(p∧┐q)∨(┐p∧q),其中，p：劉曉月選學(xué)英語，q：劉曉月選學(xué)日語；.
7.因?yàn)閜與q不能同時(shí)為真.
8. 設(shè)p:2<1，q:3<2
(1) p→q，真值為1
(2) p→┐q，真值為1
(3) ┐q→p，真值為0
(4) ┐q→p，真值為0
(5) ┐q→p，真值為0
(6) p→q，真值為1
9.（2）、（6）真值為0，其余為1
10. （1）、（4）真值為0，其余為1
11、12略
13.設(shè)p:今天是星期一，q:明天是星期二，r:明天是星期三：
?。?）p→q，真值為1（不會(huì)出現(xiàn)前件為真，后件為假的情況）；
?。?）q→p，真值為1
4、（也不會(huì)出現(xiàn)前件為真，后件為假的情況）；
?。?）pq，真值為1；
?。?）p→r，若p為真，則p→r真值為0，否則，p→r真值為1.
14略
15、p、q為真命題，r為假命題，（4）的真值為1，其余為0
16、（4）的真值為1，其余為0
17、真
18、小王會(huì)唱歌，小李不會(huì)跳舞
19、（1）（4）（6）為重言式，（3）為矛盾式，其余為非重言式的可滿足式
20、（1）01,10,11
（2）00,10,11
（3）00,01,10
（4）01,10,11
21、（1）011；（2）010,110,101,100；（3）100,101
22、無成真賦值
23、無
5、成假賦值
24、均為重言式
25、均為矛盾式
26、前者為矛盾式，后者為重言式
27略；28不能；29略；30不能
返回
第二章 命題邏輯等值演算
本章自測答案
3、（1）矛盾式；（2）重言式；（3）可滿足式
5.(1)：∨∨,成真賦值為00、10、11；
(2)：0，矛盾式，無成真賦值；
(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部為成真賦值；
7.(1)：∨∨∨∨?∧∧；
(2)：∨∨∨?∧∧∧；
8.(1)：1?∨∨∨,重言式；
(2)：∨?∨∨∨∨∨∨；
(3)：∧∧∧∧∧∧∧?
6、0，矛盾式.
11.(1)：∨∨?∧∧∧∧；
(2)：∨∨∨∨∨∨∨?1；
(3)：0?∧∧∧.
12.A?∧∧∧∧?∨∨.
第三章 命題邏輯的推理理論
本章自測答案
?
6.在解本題時(shí)，應(yīng)首先將簡單陳述語句符號(hào)化，然后寫出推理的形式結(jié)構(gòu)*，其次就是判斷*是否為重言式，若*是重言式，推理就正確，否則推理就不正確，這里不考慮簡單語句之間的內(nèi)在聯(lián)系
(1)、(3)、(6)推理正確，其余的均不正確，下面以(1)、(2)為例，證明(1)推理正確，(2)推理不正確
(1)設(shè)p:今天是星期一，q:明天是星期三，推理的形式結(jié)構(gòu)為
(p→q)∧p→q(
7、記作*1)
在本推理中，從p與q的內(nèi)在聯(lián)系可以知道，p與q的內(nèi)在聯(lián)系可以知道，p與q不可能同時(shí)為真，但在證明時(shí)，不考慮這一點(diǎn)，而只考慮*1是否為重言式.
可以用多種方法（如真值法、等值演算法、主析取式）證明*1為重言式，特別是，不難看出，當(dāng)取A為p,B為q時(shí)，*1為假言推理定律，即
(p→q)∧p→q ? q
(2)設(shè)p:今天是星期一，q:明天是星期三，推理的形式結(jié)構(gòu)為
(p→q)∧p→q(記作*2)
可以用多種方法證明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等
(p→q)∧q→p
?(┐p∨q) ∧q →
8、p
?q →p
?┐p∨┐q
??∨∨
從而可知，*2不是重言式，故推理不正確，注意，雖然這里的p與q同時(shí)為真或同時(shí)為假，但不考慮內(nèi)在聯(lián)系時(shí)，*2不是重言式，就認(rèn)為推理不正確.
9.設(shè)p:a是奇數(shù)，q:a能被2整除，r:a：是偶數(shù)
推理的形式結(jié)構(gòu)為
(p→q┐)∧(r→q)→(r→┐p) (記為*)
可以用多種方法證明*為重言式，下面用等值演算法證明：
(p→┐q)∧(r→q)→(r→┐p)
?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交換律)
?(p∨q)∨(┐p∧r)∨┐q∨┐r
?(┐p∨
9、q)∨(┐q∧┐r)
?┐p∨(q∨┐q)∧┐r
?1
10.設(shè)p:a,b兩數(shù)之積為負(fù)數(shù)，q:a,b兩數(shù)種恰有一個(gè)負(fù)數(shù)，r：a，b都是負(fù)數(shù).
推理的形式結(jié)構(gòu)為
(p→q)∧┐p→(┐q∧┐r)
?(┐p∨q) ∧┐p→(┐q∧┐r)
?┐p→(┐q∧┐r) (使用了吸收律)
?p∨(┐q∧┐r)
?∨∨∨
由于主析取范式中只含有5個(gè)W極小項(xiàng)，故推理不正確.
11.略
14.證明的命題序列可不惟一，下面對每一小題各給出一個(gè)證明
① p→(q→r) 前提引入
?、?P 前提引入
10、③ q→r ①②假言推理
?、?q 前提引入
⑤ r ③④假言推理
?、?r∨s 前提引入
?。?）證明：
① ┐(p∧r) 前提引入
?、?┐q∨┐r ①置換
?、?r 前提引入
?、?┐q ②③析取三段論
⑤ p→q 前提引入
?、?┐p ?、堍菥苋∈?
?。?）證明：
?、?p→q 前提引入
② ┐q∨q ①置換
?、?(┐p∨q)∧(┐p∨p) ②置換
?、?┐
11、p∨(q∧p ③置換
?、?p→(p∨q) ④置換
15.(1)證明：
?、?S 結(jié)論否定引入
?、?S→P 前提引入
③ P ?、佗诩傺酝评?
?、?P→(q→r) 前提引入
⑤ q→r ③④假言推論
?、?q 前提引入
⑦ r ?、茛藜傺酝评?
（2）證明：
?、?p 附加前提引入
?、?p∨q ①附加
?、?(p∨q)→(r∧s) 前提引入
④ r∧s ②③假言推理
?、?s
12、 ④化簡
?、?s∨t ⑤附加
⑦ (s∨t)→u 前提引入
?、?u ?、蔻呔苋∈?
16.(1)證明：
① p 結(jié)論否定引入
?、?p→ ┐q 前提引入
③ ┐q ①② 假言推理
?、?┐r∨q 前提引入
⑤ ┐r ?、邰芪鋈∪握?
?、?r∧┐s 前提引入
?、?r ⑥化簡
?、?┐r∧r ⑤⑦合取
?。?）證明：
① ┐(r∨s) 結(jié)論否定引入
?、?┐r∨┐s ①置換
③ ┐r
13、 ②化簡
?、?┐s ?、诨?
⑤ p→r 前提引入
?、?┐p ?、邰菥苋∈?
⑦ q→s 前提引入
?、?┐q ?、堍呔苋∈?
⑨ ┐p∧┐q ⑥⑧合取
⑩ ┐(p∨q) ⑨置換
口 p∨q 前提引入
?、息倏?┐(p∨q) ∧(p∨q) ⑩口合取
17．設(shè)p：A到過受害者房間，q: A在11點(diǎn)以前離開，r：A犯謀殺罪，s：看門人看見過A。
前提：(p∧┐q) →r , p ,q →s , ┐s
結(jié)論：r
證明：
① q→s 前提
14、引入
?、?┐s 前提引入
?、?┐q ①②拒取式
?、?p 前提引入
?、?p∧┐q ③④合取
⑥（p∧┐q）→r 前提引入
?、?r ⑤⑥假言推理
18．（1）設(shè) p：今天是星期六，q：我們要到頤和園玩，s：頤和園游人太多。
前提：p→(p∨r) , s→┐q , p , s
結(jié)論：r
證明：
?、?s→┐q 前提引入
② s 前提引入
?、?┐q ①②假言推理
?、?p 前提引入
?、?p→(q∨r) 前提引入
?、?q∨r
15、 ④⑤假言推理
?、遰 ③⑥析取三段論
（2）設(shè)p:小王是理科學(xué)生，q：小王數(shù)學(xué)成績好，r：小王是文科學(xué)生。
前提：p→q ,┐r→p ,┐q
結(jié)論：r
證明：
① p→q 前提引入
?、?┐q 前提引入
?、?┐p ?、佗诰苋∈?
?、?┐r→p 前提引入
⑤ r ?、邰芫苋∈?
返回
第四章 (一階)謂詞邏輯基本概念
本章自測答案
4.(1)┐x(F(x)∧ ┐G(x))?x( F (x) →G (x) ),其中,F(x)：x是有理數(shù),G(x) ：x能表示成分?jǐn)?shù)
16、；
(2)┐x( F (x) →G (x) ) ?x(F(x)∧ ┐G(x)),其中,F (x)：x在北京賣菜,G (x) ：x是外地人；
(3)x( F (x) →G (x) ),其中,F (x)：x是烏鴉,G (x) ：x是黑色的；
(4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天鍛煉身體。
因?yàn)楸绢}中沒有指明個(gè)體域,因而使用全總個(gè)體域。
5.(1)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火車,G(y) ：y是輪船,H(x,y)：x比y快；
(2)xy (F(x) ∧ G( y ) → H(x,y)),其
17、中,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(F(x)→y(G(y) → H(x,y)))?xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽車,G(y) ：y是火車,H(x,y)：x比y慢。
6.各命題符號(hào)化形式如下：
(1)xy (x ．y = 0)；
(2)xy (x ．y = 0)；
(3)xy (y =x+1)
18、
(4)xy(x ．y = y．x)
(5)xy(x ．y =x+ y)
(6)xy (x + y ＜0 )
9.(1)對任意數(shù)的實(shí)數(shù)x和y,若x ＜y,則x ≠ y；
(2)對任意數(shù)的實(shí)數(shù)x和y,若x–y = 0,則x＜y；
(3)對任意數(shù)的實(shí)數(shù)x和y,若x＜y,則x–y≠0；
(4)對任意數(shù)的實(shí)數(shù)x和y,若x–y ＜0,則x=y.
其中,(1)(3)真值為1(2)與(4)真值為0.
11.(1)、(4)為永真式,(2)、(6)為永假式,(3)、(5)為可滿足式。
這里僅對(3)、(4)、(5)給出證明。
(3)取解釋I 為：個(gè)體域?yàn)樽匀粩?shù)集合N,F(x,y
19、)：x ≤ y,在下,xy F(x,y)為真,而xy F(x,y)也為真(只需取x =0即可),于是(3)中公式為真,取解釋 為：個(gè)體域仍為自然數(shù)集合N,而F(x,y)：x = y。此時(shí),xyF(x,y)為真(取y為x即可),可是xyF(x,y)為假,于是(3)中公式在 下為假,這說明(3)中公式為可滿足式。
(4)設(shè)I為任意一個(gè)解釋,若在I下,蘊(yùn)涵式前件xy F(x,y)為假,則
xyF(x,y)→yxF(x,y)為真,若前件xyF(x,y)為真,必存在I的個(gè)體域D1中的個(gè)體常項(xiàng)x0,使yF(x0,y)為真,并且對于任意y∈,F(x0,y)為真,由于有x0∈,F(x0,y)為真,所以x
20、F(x,y)為真,又其中y是任意個(gè)體變項(xiàng),所以 yxF(x,y )為真,由于I的任意性,所以(4)中公式為永真式(其實(shí),次永真式可用第五章的構(gòu)造證明法證明之)。
(5)取解釋為：個(gè)體域?yàn)樽匀粩?shù)集合,F(x,y)：x = y在下,(5)中公式為真,而將F(x,y)改為F(x,y)：x ＜ y,(5)中公式就為假了,所以它為可滿足式。
13．（1）取解釋為：個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)（x）：x為奇數(shù)，G（x）：x為偶數(shù)，在 下， x（F（x）∨G（x））為真命題。
取解釋為：個(gè)體域?yàn)檎麛?shù)集合Z，F(xiàn)（x）：x為正整數(shù)，G（x）：x為為負(fù)整數(shù)，在 下， x（F（x）∨G（x））為假命題。
21、
?。?）與（3）可類似解答。
14．提示：對每個(gè)公式分別找個(gè)成真的解釋，一個(gè)成假的解釋。
返回
第五章 謂詞邏輯等值演算與推理
本章自測答案
2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c))
(2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c))
(3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c))
(4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))
5.提示：先消去量詞，后求真值，注
22、意，本題3個(gè)小題消去量詞時(shí)，量詞的轄域均不能縮小，經(jīng)過演算真值分別為：1,0,1 .
(1) 的演算如下：
xyF(x,y)
?x (F(x,3)∨F(x,4))
?(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4))
?1∧1?1
6.乙說得對，甲錯(cuò)了。本題中，全稱量詞 的指導(dǎo)變元為x ，轄域?yàn)?F (x)→G(x,y)),其中F(x )與G(x,y)中的x都是約束變元，因而不能將量詞的轄域縮小。
7.演算的第一步，應(yīng)用量詞轄域收縮與擴(kuò)張算值式時(shí)丟掉了否定聯(lián)結(jié)詞“ ┐”。演算的第二步，在原錯(cuò)的基礎(chǔ)上又用錯(cuò)了等值式，即
(F(x)∧(G(y)→
23、 H(x,y))) ≠(F(x) ∧G(y)→H (x,y))
12.公式的前束范式不唯一，下面每題各給出一個(gè)答案。
(1) xy (F(x)→ G(z,y));
(2) xt (x,y) → G(x,t,z));
(3) x4 ((F(,y) →G(,y))∧(G(,y) →F(x4,y)));
(4) ((F()→G(,)) → (H () → L(,)));
(5) (F(,)→(F() → ┐G (,))).
13.(1)xy(F(x) ∧G(y) ∧H(x ,y)),其中，F(xiàn)(x):x是汽車，G(y)：y是火車，H(x，y)：x比y跑的快；
(2
24、)xy(F(x) ∧G(y)→H(x ,y)),其中，F(xiàn)(x):x是火車，G(y)：y是汽車，H(x，y)：x比y跑的快；
(3)xy(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(xiàn)(x):x是火車，G(y)：y是汽車，H(x，y)：x比y跑的快；
(4)xy(F(x) ∧G(y) → ┐H(x ,y)),其中，F(xiàn)(x):x是飛機(jī)，G(y)：y是汽車，H(x，y)：x比y慢；
14.(1)對F(x) → xG(x)不能使用EI規(guī)則，它不是前束范式，首先化成前束范式。
F(x) → xG(x) <=> x(F(y)→G(x))
因?yàn)榱吭~轄域(F(y)→G(x
25、))中，除x外還有自由出現(xiàn)的y，所以不能使用EI規(guī)則。
(2)對 x F(x) → y G(y)也應(yīng)先化成前束范式才能消去量詞，其前束范式為 x y(F(x) →G(y)),要消去量詞，既要使用UI規(guī)則，又要使用EI規(guī)則。
(3)在自然推理系統(tǒng)F中EG規(guī)則為
A(c)/∴x(x)
其中c為特定的個(gè)體常項(xiàng)，這里A(y) = F(y) →G(y)不滿足要求。
(4)這里，使F(a)為真的a不一定使G(a)為真，同樣地使G(b)為真的b不一定使F(b)為真，如，F(xiàn)(x):x為奇數(shù)，G(x):x為偶數(shù)，顯然F(3)∧G(4)為真，但不存在使F(x)∧G(x)為真的個(gè)
26、體。
(5)這里c為個(gè)體常項(xiàng)，不能對F(c)→G(c)引入全稱量詞。
15.(1)證明：①xF(x) 前提引入
?、趚F(x)→ y((F(y)∨G(y)) →R(y)) 前提引入
?、踶((F(y)∨G(y)) →R(y) ?、佗诩傺酝评?
④F(c) ?、貳I
⑤(F(c)∨G(c))→R(c) ③UI
?、轋(c)∨G(c) ④附加
?、逺(c) ⑤⑥假言推理
⑧xR(x) ?、逧G
27、
(2)證明①xF(x) 前提引入
②x((F(x)→G(a)∧R(x))) 前提引入
?、跢(c) ①EI
?、蹻(c)→G(a)∧R(a) ?、赨I
⑤G(a)∧R(c) ?、邰芗傺酝评?
⑥R(c) ⑤化簡
?、逨(c)∧R(c) ③⑥合取
?、鄕(F(x)∧R(x)) ⑦EG
(3)證明：①┐xF(x) 前提引入
?、趚┐F(x)
28、 ?、僦脫Q
③┐F(c) ②UI
?、躼(F(x)∨G(x)) 前提引入
?、軫(c)∨G(c) ④UI
⑥F(c) ③⑤析取三段論
?、選F(x) ⑥EG
(4)證明①x(F(x)∨G(x)) 前提引入
?、贔(y)∨G(y) ①UI
③x(┐G(x)∨┐R(x)) 前提引入
?、堠碐(y)┐R(y) ③UI
⑤x
29、R(x) 前提引入
⑥R(y) ⑤UI
?、擤碐(y) ④⑥析取三段論
⑧F（y） ②⑦析取三段論
⑨xF(x) ⑧UG
17．本題不能用附加前提證明法.
20.(1)與(2)均可用附加前提證明法。
22.(1)設(shè)F(x)：x為偶數(shù)，G(x):x能被2整除。
前提:x(F(x)→G(x))，F(xiàn)(6)
結(jié)論：G(6)
(2)設(shè)F(x)：x是大學(xué)生，G(x):x是勤奮的，a：王曉山。
前提:x(F
30、(x)→G(x))，┐G(a)
結(jié)論：┐F(a)
23.(1)設(shè)F(x)：x是有理數(shù)，G(x):x是實(shí)數(shù)，H(x)：x是整數(shù)。
前提:x( F(x)→G(x))， x(F(x)∧H(x))
結(jié)論:x(G(x)∧H(x))
證明提示：先消存在量詞。
(2)設(shè)F(x)：x是有理數(shù)，G(x):x是無理數(shù)，H(x)：x是實(shí)數(shù)，I(x)：x是虛數(shù)。
前提:x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x))
結(jié)論:x(I(x)→(┐F(x)∧┐G(x)))
證明①x(I(x)→(┐H(x)) 前提引入
?、贗(y
31、)→H(y) ①UI
?、踴((F(x)∨G(x))→H(x)) 前提引入
?、?F(y)∨G(y))→H(y) ?、踀I
?、荸碒(y)→(┐F(y)∧┐G(y)) ?、苤脫Q
?、轎(y)→(┐F(y)∧┐G(y)) ?、冖菁傺匀握?
?、選(I(x)→(┐F(x)∧┐G(x)) ?、郩G
24.設(shè)F(x)：x喜歡步行，G(x)：x喜歡騎自行車，H(x)：x喜歡乘汽車。
前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x)
結(jié)
32、論:x┐F(x)
證明①x┐H(x) 前提引入
?、讴碒(c) ①UI
?、踴(G(x)∨H(x)) 前提引入
?、蹽(c)∨H(c) ③UI
?、軬(c) ②④析取三段論
?、辺(F(x) →G(x)) 前提引入
?、逨(c)→┐G(c) ?、轚I
?、喋碏(c) ⑤⑦拒取式
?、醲┐F(x)
33、 ⑧UG
25.設(shè)F(x)：x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在事業(yè)中獲得成功。
前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(xiàn)(a)，H(a)
結(jié)論：I(a)
證明①F(a) 前提引入
②x(F(x)→G(x)) 前提引入
?、跢(a)→G(a) ?、赨I
④G(a) ?、佗奂傺酝评?
⑤H(a)
34、 前提引入
?、辺(G(x)∧H(x)→I(x)) 前提引入
?、逩(a)∧H(a)→I(a) ⑥UI
?、郍(a)∧H(a) ④⑤合取
?、酙(a) ⑦⑧假言推理
返回
第六章 集合代數(shù)
本章自測答案
4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧
6.只有(2)為真，其余為假。
9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}.
11
35、.(1)； (2) {1,4,5}.
22.(2)、(3)、(4)、(8)、(10)為真，其余為假。
24.(1)為真，其余為假，因?yàn)?
(P-Q) = P ? (P-Q)∩Q = P∩Q ? = P∩Q
(2)(3)(4)的反例：P ={1} ，Q ={2}
26.(A–B)∪(B–A) = (A∩B)∪(B∩A)
=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)
=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)
27.(1)(A-B)-C = A∩B∩C =A∩(B∪C) = A-(B∪C)
(2)(A-C)-(B-C)A∩C∩(B∩C
36、)
=A∩C∩(B∪C) = (A∩C∩B)∪(A∩C∩C)
=A∩∩C=(A–B)- C
(3)(A–B-C=A∩B∩C =A∩C∩B=(A–C)–B
28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪
=A∩B=B∩A
(2)((A∪B)∩A) = (A∪B)∪A
=(A∩B)∪A = A
29.由第26題有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),與(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾
37、.
30.AB?x(x∈A→x∈B)?x(xB→xA)
?x(x∈B→x∈A)?BA
AB ? A∪AA∪B ? EA∪B
而A∪BE，因此AB ? A∪B=E反之，
A∪B = E ? A∩(A∪B)= A ? A∩B = A ? AB
綜合上述，AB?A∪B = E
AB ? A-B = ? A-BB
反之A-BB ? (A-B)∪BB ? A∪BB ? A∪B = B ? AB
綜合上述AB?A-BB
31.任取x ,x∈A ? {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ? x∈B
32.先證C
38、A∧CB ? CA∩B,任取x,x∈C ? x∈C∧x∈C ? x∈A∧x∈B ? x∈A∪B,從而得到CA∪B.再證CA∩B ? CA∧CB，這可以由CA∩BA,CA∩BB得到。
33.PQ ? P-Q= ? P-QP，反之，P-QP ? P∩(P-Q)P∩P ? P-Q= ? PQ
34.令X=，則有∪Y =，即Y = .
35.AB ? A∪AB∪A ? EB∪A因?yàn)镋為全集,B∪AE綜合上述B∪A=E.
36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有：
(A∩C)∪(A-C) (B∩C)∪(B-C)
? (A∩C)∪(A∩C)(B∩C)∪(B∩C)
?
39、 (A∩(C∪C)(B∩(C∪C) ? A∩EB∩E ? AB
37.恒等變形法
B=B∩(B∪A)=B∩(AB)=B∩(AC)
=(B∩A)∪(B∩C)=(A∩C)∪(B∩C)
=(A∪B)∩C=(A∪C)∩C=C
39.任取x，有x∈P(A) ? x A ? x B ? x∈P(B)，因此P(A)P(B).
40.(1)任取x有
x∈P(A)∩P(B)?x∈P(A)∧x∈P(B)?xA∧xB
?xA∩B?x∈P(A∩B)
(2)任取x有
x∈P(A)∪P(B)?x∈P(A)∨x∈P(B)?xA∧xB
? x
40、A∪B?x∈P(A∪B)
注意與(1)的推理不同，上面的推理中有一步是“ ? ”符號(hào)，而不是“?”符號(hào)。
(3)反例如下：A = {1}，B = {2}，則
P(A)∪P(B)= {,{1},{2}}
P(A∪B)={,{1},{2},{1,2}}
返回
第七章 二元關(guān)系
本章自測答案
3.(1) 任取< x,y >,有
∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D
?x ∈A∧x ∈ B∧y ∈C∧y ∈ D
?(x ∈A∧y ∈C )∧(x∈B∧y∈D)
?∈A×C∧< x,y >∈B
41、×D
?∈(A×C)∩(B×D)
(2)都為假,反例如下:
A ={1}, B ={1,2}, C ={2}, D ={3}
4.(1)為假,反例如下:A ={1}, B =,C = {2};
(2)為真,證明如下:任取有
∈A×(B∩C)×(C∩D)?x∈A∩B∧y∈B∧y∈C
?(x∈A∧y∈B)∧(x∈A∧y∈C)
?∈A×B∧∈A×C?∈(A×B)∩(A×C)
(3)為真,令A(yù) = 即可;
(4)為假,反例如下: A =
7.={<2,2>,<3,3 >,<4,4>}
={
42、<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪
LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}
DA={<2,2>,<2,4>,<3,3>,<4,4>}
9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>}
(2){<1,2>,<2,1>};
(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>}
(4){<1,
43、2>,<2,2>,<4,2>,<6,2>}
12.（略）
13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>}
domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4}
ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3}
14.RR = {<0,2>,<0,3>,<1,3>}
R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}
R{0,1}
44、= {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}
R[{1,2}] = {2,3}
18.(1)F(G∪H) = FG∪FH
任取 ,有
∈F (G∪H)?t(∈F∧∈G∪H)
?t(∈F∧(∈G∨∈H))
?t((∈F∧∈G)∨(∈F∧∈H))
?t(∈F∧∈G)∨t(∈F∧∈H))
?∈FG∨∈FH?∈FG∪FH
(2)和(4)類似可證
1
45、9.(2)任取y,有
y∈R[T∪W]?x(x∈T∪W∧∈R)
?x((x∈T∨x∈W)∧∈R
?x((x∈A∧∈R)∨(x∈W∧∈R))
?x(x∈T∧∈R)∨x(x∈W∧∈R)
?y∈R[T]∨y∈R[W]?y∈R[T]∩R[W]
(3)任取,有
∈F(A∩B)?x∈A∩B∈F
?x∈A∧x∈B∧∈F
?(x∈A∧∈F)(x∈B∧∈F)
?∈FA∧∈FB
?∈FA∩F B
46、20.(1)任取,有
∈(∪) <=>∈∪
?∈∨∈
?∈∨∈
?∈∪
(2)和(1)類似可證.
21.只有對稱性,因?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也不是傳遞的.
22.(1)關(guān)系圖如圖7.15所示; (P
47、148)
(2)具有反自反性、反對稱性、傳遞性.
26.(1)R={<3,3>,<3,1>,<3,5>}, = {<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>}
31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>
48、,<3,4>,<4,3>}∪；(2)R； (3)R.
32.(1)不是等價(jià)關(guān)系，因?yàn)?1,1> R，R不是自反的；
(2)不是等價(jià)關(guān)系，因?yàn)镽不是傳遞的，1R3，3R2但是沒有1R2；
(3)不是等價(jià)關(guān)系，因?yàn)?2,2> R，R不是自反的；
(4)不是等價(jià)關(guān)系，因?yàn)镽不是傳遞的。
(5)是等價(jià)關(guān)系。
33．關(guān)系圖如圖7.17說示 (P151)
[a] = [b] ={a,b},[c] = [d] = {c,d}
38.現(xiàn)取x，有x∈A ? ∈R ? ∈R∧∈R
? ∈R∧∈ ? ∈
49、R∩R
任取,有∈ R∩ ? ∈R∧∈
? ∈ ∧∈R ? ∈R∩R
任取,,有
∈R∩ ∧∈R∩
? ∈R∧∈ ∧∈R∧∈
? (∈R∧∈R)∧(∈ ∧∈
? ∈R∧∈R ? ∈R∩R
42.x,x∈A ? ∈R ? ∈R∧∈R ? ∈T,T是自反的。
x,
50、y∈A,∈T?∈R∧∈R
?∈R∧∈R ? ∈T,T是對稱的。
x,y,z∈A,∈T∧∈T
?∈R∧∈R∧∈R∧∈R
? ∈R∧∈R∧∈R∧∈R
? ∈R∧∈R ? ∈T
T是傳遞的。
43．哈斯圖如下圖所示.
44.(a)偏序集,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪
51、 (b)偏序集,A={a,b,c,d,e,f},R={,,}∪
(c)偏序集,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪
45.(a)A={a,b,c,d,e,f,g}, ={,,,,,,, ,,}∪ (b)A = {a,b,c,d,e,f,g},R口 = {,,,,,
52、f>,}∪
46.哈斯圖如圖7.19所示 （P153）
?。?）極大元e,f；極小元a,f；沒有最大與最小元。
?。?）極大元a,b,d,e；極小元a,b,c,e；沒有最大與最小元。
返回
5、設(shè)無向圖G有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3，問G至少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、。
解：由握手定理圖G的度數(shù)之和為：
3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。
其余頂點(diǎn)的度數(shù)共有6度。
其余頂點(diǎn)的度數(shù)均小于3，欲使G的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取2,
所以，G至少有7個(gè)頂點(diǎn), 出度
53、數(shù)列為3,3,4,4,2,2,2,.
7、設(shè)有向圖D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，求D的入度列，并求，
,.
解：D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，D的入度列為1,1,1,2.
,,
14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對可圖化的數(shù)列，試給出3種非同構(gòu)的無向圖，其中至少有兩個(gè)時(shí)簡單圖。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4
解：(1) 2+2+3+3+4+4+5=23 是奇數(shù)，不可圖化；
(2) 2＋2+2+2+3+3+4+4=16, 是偶數(shù)，可圖化；
離散數(shù)學(xué)第1-7章 習(xí)題詳解
