離散數(shù)學(xué)習(xí)題匯總

1、命題邏輯習(xí)題課,,1,一.命題符號(hào)化P:天下雪。Q:我將去鎮(zhèn)上。R:我有時(shí)間。(1) 如果天不下雪且我有時(shí)間，那么我將去鎮(zhèn)上。 (2) 我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間。 (3) 天下雪，那么我不去鎮(zhèn)上。 (4) 或者你沒有給我寫信，或者它在途中丟失了。 令 P:你給我寫信。Q:信在途中丟失了。(5) 我們不能既劃船又跑步 令 P:我們劃船。Q:我們跑步。 (6)如果你來了，那么他唱不唱歌將看你是否為他伴奏而定。

2、 令 P:你來了。Q:你為他伴奏。 R:他唱歌。(7)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。令 P:上午下雨。Q:我去看電影。 R:我在家里讀書。S:我在家里看報(bào)。,2,(8)我今天進(jìn)城，除非下雨。令 P:我今天進(jìn)城。Q:今天下雨。(9)僅當(dāng)你走我將留下。令 P:你走。Q:我留下。,3,二.重言式的證明方法 方法1：列真值表。 方法2：公式的等價(jià)變換，化簡(jiǎn)成“T”。 方法3：用公式的

3、主析取范式。 (1)證明(P→Q)→(P→(P∧Q))是重言式。,4,三.重言蘊(yùn)涵式的證明方法方法1.列真值表。(即列永真式的真值表) (略)方法2.假設(shè)前件為真，推出后件也為真。方法3.假設(shè)后件為假，推出前件也為假。證明(?A?(B∨C) )∧(D∨E)∧((D∨E)??A) ? B∨C,5,四. 等價(jià)公式的證明方法方法1：用列真值表。（不再舉例）方法2：用公式的等價(jià)變換 (1) 證明((A∧B)→C)∧(B→(D

4、∨C))?(B∧(D→A))→ C(2)化簡(jiǎn)(A∧B∧C)∨(?A∧B∧C）,6,五.范式的寫法及應(yīng)用(1)寫出(P?(Q∧R))∧(?P?(?Q∧?R))的主析取范式和主合取范式方法1，用真值表方法2，等價(jià)變換(2) A,B,C,D四個(gè)人中要派兩個(gè)人出差，按下述三個(gè)條件有幾種派法？①若A去則C和D中要去一個(gè)人。②B和C不能都去。③C去則D要留下。,7,(3) 有工具箱A、B、C、D，各個(gè)箱內(nèi)裝的工具如下表所示。試問如何

5、攜帶數(shù)量最少工具箱，而所包含的工具種類齊全。,8,(4) 設(shè)計(jì)一個(gè)樓上、樓下開關(guān)的控制邏輯電路來控制樓梯上的路燈。使之在上樓前，用樓下開關(guān)打開電燈，上樓后，用樓上開關(guān)關(guān)滅電燈；或者在下樓前，用樓上開關(guān)打開電燈，下樓后，用樓下開關(guān)關(guān)滅電燈。,9,六. 邏輯推理 熟練掌握三種推理方法。(1)用三種推理方法證明： (A∨B)?(C∧D), (D∨E)?P ? A?P(2) 請(qǐng)根據(jù)下面事實(shí)，找出兇手：1. 清潔工或者秘書謀害了經(jīng)理。2.

6、 如果清潔工謀害了經(jīng)理，則謀害不會(huì)發(fā)生在午夜前。3.如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。4.如果秘書的證詞不正確，則午夜時(shí)屋里燈光未滅。5. 如果清潔工富裕，則他不會(huì)謀害經(jīng)理。6.經(jīng)理有錢且清潔工不富裕。7.午夜時(shí)屋里燈滅了。令A(yù):清潔工謀害了經(jīng)理。 B:秘書謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書的證詞是正確的. E:午夜時(shí)屋里燈光滅了。H:清潔工富裕. G:經(jīng)理有錢.

7、,10,謂詞邏輯習(xí)題課,,11,1.將下列命題符號(hào)化（1）在湖南高校學(xué)習(xí)的學(xué)生，未必都是湖南籍的學(xué)生（2）對(duì)于每一個(gè)實(shí)數(shù)x，存在一個(gè)更大的實(shí)數(shù)y（3）存在實(shí)數(shù)x，y和z，使得x與y之和大于x與z之積（4）某些汽車比所有的火車都慢，但至少有一列火車比每輛汽車快（5）對(duì)任何整數(shù)x和y，x≤y且y≤x是x=y的充要條件 （6）若m是奇數(shù)，則 2m 不是奇數(shù)（7）那位戴眼鏡的用功的大學(xué)生在看這本大而厚的巨著（8）每個(gè)自然數(shù)都有唯

8、一的后繼數(shù)（9）沒有一個(gè)自然數(shù)使數(shù)1是它的后繼數(shù)（10）每個(gè)不等于1的自然數(shù)都有唯一的一個(gè)數(shù)是它的直接先行者,12,2.變?cè)募s束（1）對(duì)下列謂詞公式中的約束變?cè)獡Q名?x(P(x)→(R(x)∨Q(x)))∧ ?xR(x)→?zS(x,z)（2）對(duì)下列謂詞公式中的自由變?cè)??yA(x,y)→?xB(x,z))∧ ?x?zC(x,y,z)3.討論在給定解釋下謂詞公式的真值（1）?x(P→Q(x))∨R(a)D={-

9、2,3,6} , P:2>1,Q(x):x≤3, R(x):x>5,a:5（2）?x?y(P(x)∧Q(x,y))D= {1,2}，P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F,,13,4.判斷下列公式是不是永真式，并加以說明（1）(?xP(x) →?xQ(x)) ? ?x(P(x) →Q(x))（

10、2）? x ? y(P(x) →Q(y)) →(?xP(x) → ? y Q(y))5.用形式推理證明：（1）?xP(x)∨?xQ(x)??x (P(x)∨Q(x))（2） ?xF(x)→?y(G(y)→H(y)), ?xM(x)→?yG(y) ? ?x (F(x)∧M(x))→?yH(y) （3）任何人如果他喜歡步行，他就不喜歡乘汽車；每個(gè)人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行（4）每個(gè)大學(xué)

11、生不是文科生就是理工科生，有的大學(xué)生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學(xué)生，他就是文科生,14,集合論習(xí)題課,,15,1. 判斷下面命題的真值(真的話證明，假的話舉反例)a)如果A∈B，B?C ，則 A∈ Cb)如果A∈B，B?C，則 A?C c)如果A?B，B∈C，則 A∈Cd)如果A?B，B∈C，則 A?C2.集合計(jì)算a) Φ∩{Φ} b){Φ}∩{Φ}c) {Φ,{

12、Φ}} -Φ d) {Φ,{Φ}}-{Φ}e) {Φ,{Φ}}-{{Φ}}3.在什么條件下，下面命題為真？a) (A-B)∪(A-C)=Ab) (A-B)∪(A-C)=Φc) (A-B)∩(A-C)=Φd) (A-B)?(A-C)=Φ4.集合的基數(shù) A,B是有限集合,已知|A|=3,|ρ(B)|=64,|ρ(A∪B)|=256, 則|B|=( ),|A∩B|=( ),|A-B|=( ),|A?B|=( )

13、,16,5.集合的證明a)證明 (A∩B)∪C=A∩(B∪C) iff C?Ab)證明 (A-B)-C=(A-C)-Bc)證明以下各式彼此等價(jià)：A∪B=U, ~A?B, ~B?A6.冪集設(shè)A,B是集合，證明以下命題成立a) ρ(A∩B)=ρ(A) ∩ρ(B)b) ρ(A) ∪ρ(B)?ρ(A∪B)c) A?B iff ρ(A) ?ρ(B)7.笛卡爾積A={0,1} B={1,2} 求A2×

14、;B,17,二元關(guān)系習(xí)題課,,18,一. 判斷題( )⒈ 設(shè)A、B、C和D是四個(gè)非空集合, 且A×C?B×D，則A?B且C?D。( )⒉ 設(shè)A、B、C和D是四個(gè)集合，則A×C=B×D，iff A=B且C=D。( ) 3. 傳遞關(guān)系的對(duì)稱閉包仍是傳遞的。( ) 4. 非空集合上的關(guān)系不是對(duì)稱的，則必是反對(duì)稱的。( ) 5. 非空集合上的自反關(guān)系必不

15、是反自反的。( ) 6. 若R和S是二個(gè)有完全相同的二元組的集合，則稱它們是相等的二元關(guān)系。( ) 7. 設(shè)A是一個(gè)非空集合，則A上的等價(jià)關(guān)系都不是偏序關(guān)系。( ) 8. 有限集上的全序關(guān)系必是良序關(guān)系。( ) 9. 有限集上的偏序關(guān)系必是全序關(guān)系。( ) 10. 是偏序集，則Ａ的任何非空子集必有極小元。( ) 11. 是偏序集，則Ａ的非空子集Ｂ的上確界必是Ｂ的最大元。(

16、 ) 12. 是全序集，則Ａ的任何非空子集必有唯一極小元。( ) 13. 是全序集，則Ａ的非空子集Ｂ的下確界必是Ｂ的最小元。,19,二、多項(xiàng)選擇題( )⒈ 下列說法中正確的有：① 任何集合都不是它自身的元素 ② 任何集合的冪集都不是空集③ 若Ａ×Ｂ＝Φ，則Ａ＝Ｂ＝Φ ④ 任意兩集合的迪卡爾積都不是空集( )⒉ {1,2,3,4,5}上的關(guān)系R={,,}是① 自反的

17、 ② 反自反的 ③ 對(duì)稱的 ④ 反對(duì)稱的 ⑤ 傳遞的( )⒊ 設(shè)R={}是Ａ＝{1,2,3}上的關(guān)系，則① rst(R)是等價(jià)關(guān)系 ② Ｒ10＝Φ ③ r(R)是偏序 ④ tr(R)是良序( )⒋ 設(shè)R和S分別是A到B和B到C的關(guān)系，且R·S=Φ，那么 ① R是空關(guān)系 ② S是空關(guān)系 ③ R和S都是空關(guān)系 ④ R和S中至少有一個(gè)是空關(guān)系 ⑤

18、 以上答案都不對(duì),20,( )⒌ 若R和S是集合A上的等價(jià)關(guān)系，則下列關(guān)系中一定是等價(jià)關(guān)系的有 ① R∪S ② R∩S ③ R－S ④ R⊕S( )⒍ 若R是集合A上的等價(jià)關(guān)系，則 ① R2＝R ② t(R)＝R ③ ＩA ? R ④ R-1＝R( )⒎ 空集上的空關(guān)系是 關(guān)系。 ① 線序 ② 等價(jià) ③ 偏序 ④ 擬序

19、⑤ 良序( ) 8. {1,2,3,4,5}上的全序關(guān)系一定是 關(guān)系。 ①等價(jià) ②偏序 ③擬序 ④良序( )9. {1,2,3,4,5}上的良序關(guān)系一定是 ① 自反的 ② 反自反的 ③ 對(duì)稱的 ④ 反對(duì)稱的 ⑤ 傳遞的( )10. 設(shè)Ｒ和Ｓ都是Ａ到Ｂ的關(guān)系，則下列關(guān)系式中正確的有： ① (Ｒ∪Ｓ)-1＝Ｒ-1∪Ｓ-1 ② (Ｒ∩Ｓ)-1＝

20、Ｒ-1∩Ｓ-1 ③ (Ｒ－Ｓ)-1＝Ｒ-1－Ｓ-1 ④ (Ｒ⊕Ｓ)-1＝Ｒ-1⊕Ｓ-1,21,三、計(jì)算與作圖1.若集合Ａ={1,2,3,4,5}上的等價(jià)關(guān)系Ｒ={,,,,,,,,}，求商集Ａ/Ｒ2.Ｒ為集合Ａ={1,2,3,4,5}上的等價(jià)關(guān)系，已知商集Ａ/Ｒ={{1,2},{3},{4,5}}，求R3.設(shè)Ａ={3,6,9,15,54,90,135,180}，｜為自然數(shù)的整除關(guān)系。畫出的Ｈasse圖，并求{

21、6,15,90}的上、下確界。四、證明題⒈ 設(shè)R是集合A上的關(guān)系。證明：R是偏序關(guān)系，iff R-1∩R=IA且Ｒ=rt(Ｒ)。⒉ 設(shè)R是集合A上的關(guān)系。證明：R是擬序關(guān)系，iff R-1∩R=Φ且Ｒ=t(Ｒ)。,22,函數(shù)習(xí)題課,,23,一、多項(xiàng)選擇( )1. 函數(shù)f：Ｒ×Ｒ→Ｒ×Ｒ，f()=是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不

22、對(duì)( )2. 函數(shù)f：Ｒ×Ｒ→Ｒ，f()=(x+y)/2是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不對(duì)( )3. 設(shè)Σ={a,b}為字母表，則f：Σ*→Σ*，f(x)=axb是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不對(duì)( )4. 函數(shù)f： [0,1]→ [0,1] ，f(x)=x/2+1/4

23、是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不對(duì)( )5. 從{0,1}2到{a,b,c,d}的二元關(guān)系R： {,a>,,b>,,c>,,b>}是 ① 函數(shù) ② 入射 ③ 滿射 ④ 雙射 ⑤ 以上答案都不對(duì)( )6. 若f、g是Ａ上的函數(shù)且g·f是雙射，則 ① f和g都是雙射

24、 ② f為滿射 ③ g為入射 ④ f有左逆 ⑤ g有右逆,24,二、填空1. 若A={a,b}，B={1,2}，則BA= 。2. 用ε表示字母表Σ={a,b}上的空串，定義f：Σ*→Σ*如下： x∈Σ* f(x)=axb 則f({ε,a,b})= 。3. 用ε表示字母表Σ={a,b}上的空串，定義f：Σ*→Σ*如下：x∈Σ*

25、 f(x)=axb 則f( )={aab,abb,ab}。設(shè)Ａ＝{1,2,4}是全集U＝{1,2,3,4,5}的子集，則Ａ的特征函數(shù)ψA＝ 。三、計(jì)算1. 設(shè)Ａ＝{a,b},Ｂ＝{1,2,3,4}，f＝{,}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如果存在的話)。2. 設(shè)Ａ＝{1,2,3,4,5},Ｂ＝{a,b}，f＝{,,,,}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如