離散數(shù)學習題匯總

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

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

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

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

5、攜帶數(shù)量最少工具箱，而所包含的工具種類齊全。,8,(4) 設(shè)計一個樓上、樓下開關(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) 請根據(jù)下面事實，找出兇手：1. 清潔工或者秘書謀害了經(jīng)理。2.

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

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

8、一的后繼數(shù)（9）沒有一個自然數(shù)使數(shù)1是它的后繼數(shù)（10）每個不等于1的自然數(shù)都有唯一的一個數(shù)是它的直接先行者,12,2.變元的約束（1）對下列謂詞公式中的約束變元換名?x(P(x)→(R(x)∨Q(x)))∧ ?xR(x)→?zS(x,z)（2）對下列謂詞公式中的自由變元代入(?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）任何人如果他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行（4）每個大學

11、生不是文科生就是理工科生，有的大學生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學生，他就是文科生,14,集合論習題課,,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.集合計算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)證明以下各式彼此等價：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)系習題課,,18,一. 判斷題( )⒈ 設(shè)A、B、C和D是四個非空集合, 且A×C?B×D，則A?B且C?D。( )⒉ 設(shè)A、B、C和D是四個集合，則A×C=B×D，iff A=B且C=D。( ) 3. 傳遞關(guān)系的對稱閉包仍是傳遞的。( ) 4. 非空集合上的關(guān)系不是對稱的，則必是反對稱的。( ) 5. 非空集合上的自反關(guān)系必不

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

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

17、 ② 反自反的 ③ 對稱的 ④ 反對稱的 ⑤ 傳遞的( )⒊ 設(shè)R={}是Ａ＝{1,2,3}上的關(guān)系，則① rst(R)是等價關(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中至少有一個是空關(guān)系 ⑤

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

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

20、Ｒ-1∩Ｓ-1 ③ (Ｒ－Ｓ)-1＝Ｒ-1－Ｓ-1 ④ (Ｒ⊕Ｓ)-1＝Ｒ-1⊕Ｓ-1,21,三、計算與作圖1.若集合Ａ={1,2,3,4,5}上的等價關(guān)系Ｒ={,,,,,,,,}，求商集Ａ/Ｒ2.Ｒ為集合Ａ={1,2,3,4,5}上的等價關(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ù)習題課,,23,一、多項選擇( )1. 函數(shù)f：Ｒ×Ｒ→Ｒ×Ｒ，f()=是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不

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

23、是 ① 入射 ② 滿射 ③ 雙射 ④ 以上答案都不對( )5. 從{0,1}2到{a,b,c,d}的二元關(guān)系R： {,a>,,b>,,c>,,b>}是 ① 函數(shù) ② 入射 ③ 滿射 ④ 雙射 ⑤ 以上答案都不對( )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＝ 。三、計算1. 設(shè)Ａ＝{a,b},Ｂ＝{1,2,3,4}，f＝{,}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如果存在的話)。2. 設(shè)Ａ＝{1,2,3,4,5},Ｂ＝{a,b}，f＝{,,,,}是Ａ到Ｂ的函數(shù)，試找出f的所有左逆和右逆(如