第一篇：02324離散數(shù)學201404
絕密★考試結束前
全國2014年4月高等教育自學考試
離散數(shù)學試題
課程代碼：02324 本試卷共5頁，滿分l00分，考試時間l50分鐘。考生答題注意事項：
1．本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對應試卷上的題號使用28鉛筆將“答題卡”的相應代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號。使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間。超出答題區(qū)域無效
選擇題部分
一、單項選項題（本大題共15小題，每小題1分，共15分）
在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均不得分。
1.設P：我在家，Q：天下雨，命題“只要天下雨，我就在家”的符號化正確的是 A.P?Q C.?P??Q
2.下列命題公式為永真式的是
B.?P??Q D.Q?P
（P?Q）?Q A.C.(P?Q)?P 3.下列等價式不正確的是 ．．．
B.(P?Q)?P D.P?(?P?Q)
A.(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
（?x）B(x)?(?x)(A?B(x))B.A?（?x）A(x)?B?(?x)(A(x)?B)C.D.?（?x）A(x)?(?x)?A(x)
（x）（x）4.設A：x是鳥，B：x會飛，命題“沒有不會飛的鳥”符號化為
(A(x)?B(x))A.?（?x）(A(x)?B(x))C.?（?x）B.??x(A(x)??B(x))
（?x）(A(x)?B(x))D.5.設X?，則下列陳述正確的是 ｛｛?｝｛,a｝｛,b｝｝A.{a,b}?X
｛｛a｝,｛b｝｝?X B.｛?｝?X C.6.設AA.A｛｛a｝｝?X D.B=A，則 B=A
B.AB=B
C.B?A?? D.B?A
（A）7.設A?，則其冪集P的元素總個數(shù)為 ｛a,b｛,a,b｝｝A.2 C.4
B.3 D.8 8.在整數(shù)集Z上，下列定義的運算滿足結合律的是 A.a*b?min{a,b} C.a*b?|a?b|
9.設?G,*?是群，是下列陳述不正確的是 ．．．
B.a*b?2a?b D.a*b?a?b
（ab）?ab A.（a）?aC.nmnmnnn（aba）?aba B.D.aa?anmn?m-1n?1n
10.f：X?Y，g：Y?Z是函數(shù)，則下列陳述正確的是 A.若gf不是滿射的，則f不是滿射的
f不是滿射的 f是滿射的 f是滿射的
B.若g不是滿射的，則gC.若f是滿射的，則gD.若g是滿射的，則g11.設簡單圖G所有結點的度數(shù)之和為36，則G的邊數(shù)為 A.12 C.36 12.下列無向圖不一定是樹的是 ．．．A.有n個結點，n?1條邊的圖 B.無回路的連通圖
C.連通但刪去一條邊則不連通的圖
D.無回路但添加一條邊則有一個回路的連通圖
B.18 D.72
13.設R是A上的二元關系，r、s、t分別指關系的自反閉包、對稱閉包、傳遞閉包、則下列描述不正確的是 ．．．
A.r(R)?RC.t(R)?RIA
B.s(R)?R-1-1R?1
R2（R）?R D.14.不列必為歐拉圖的是 A.不可以一筆畫的圖 C.存在歐拉回路的圖
B.結點度數(shù)都是偶數(shù)的圖 D.奇數(shù)度結點有3個的連通圖
15.設X=｛0，1｝，冪集為?，下列關于代數(shù)系統(tǒng)??(X),（X）A.｛0｝是幺元 C.｛0，1｝是幺元
B.｛1｝是幺元 D.?是幺元
?的陳述正確的是
非選擇題部分
注意事項：
用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。
二、填空題（本大題共10小題，每小題2分，共20分）16.命題公式P?Q的成真指派為______,成假指派為______。
17.設R=｛<1,2>,<3,4>,<5,5>｝和S=｛<2,1>,<3,3>,<3,5>｝是集合A=｛1,2,3,4,5｝上的兩個關系，則RS=_______, SR=______。18.設A=｛<1,4>,<2,3>,<4,4>｝,B?{<1,3>,<2,3>,<5,2>},那么dom(Aran(AB)=______, B)=______。
19.整數(shù)集Z中的運算*定義如下：?a,b?z,a*b?a?b?4ab，則Z中關于*運算的幺元為______；設a有逆元，則其逆元a為______。?1（f20.設f(x)?x?1,g(x)?2x2?1，那么復合函數(shù)
g）(x)=______.(gf)(x)=______。
（?x）P(x,z)?(?y)(Q(y)?R(x,y))的約束變元有______,自由變元有______。21.公式22.如題22圖所示的格中，b的補元是______，c的補元是______。23.設A?｛a,b｝,B?{a,b,c}，則A?B=______，A??=______。24.
25.Kn是n個結點的完全圖,則K7的邊數(shù)為______,每個結點的度數(shù)為______。
三、計算題（本大題共4小題，每小題7分，共28分）
（P?Q）??（P?R）26.構造命題公式的真值表。
27.設R=｛是A=｛1,2,3,4｝上的二元關系，<1,4>,<2,1>,<2,3>,<3,1>,<4,2>,<4,3>｝（1）畫出R的關系圖；（2）寫出R的關系矩陣；
（3）說明在A上R是否具有自反、反自反、對稱、反對稱性質。
（P?Q）??（Q?R）28.求公式的主析取范式和主合取范式。
29.設集合A=｛1,2,4,7,14,28｝，≤為A上的整除關系，（1）畫出＜Ａ，≤＞的哈斯圖;（2）求子集B=｛2，7，14｝的極大元、極小元、最大元、最小元。
四、證明題（本大題共3小題，每小題7分，共21分）
*>是一個群，?a,b?G，30.設 31.設A?，在A上定義二元關系～如下： ｛?a,b?|a,b為正整數(shù)｝?a,b?~?c,d?，當且僅當a?d?c?b。 證明：～是一個等價關系。 32.設G是有n個結點、n?1條邊的圖，且每個結點的度數(shù)都不超過3，證明：G中至少有2個度數(shù)等于3的結點。 五、綜合應用題（本大題共2小題，每小題8分，共16分）33.構造下列推理的證明。 如果他訓練刻苦，他必贏得比賽；如果他贏得比賽，他必得到總理的接見；總理沒有接見他；所以他訓練不刻苦。34.今有a,b,c,d,e,f,g共7人，已知下列事實：（1）a會講意大利語和韓語；（2）b會講漢語；（3）c會講韓語和英語；（4）d會講英語、法語和俄語；（5）e會講漢語、俄語和意大利語；（6）f會講英語；（7）g會講漢語和法語。 試問這7個人應如何排座位（圓桌），才能使每個人和坐在他身邊的人交談？ 離散數(shù)學課件作業(yè) 第一部分 集合論 第一章集合的基本概念和運算 1-1 設集合 A ={1，{2}，a，4，3}，下面命題為真是[ B ] A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ? A。 1-2 A,B,C 為任意集合，則他們的共同子集是[ D ] A．C；B．A；C．B；D．?。 1-3 設 S = {N，Z，Q，R}，判斷下列命題是否成立 ？ （1）N ? Q，Q ∈S，則 N ? S［不成立］ （2）-1 ∈Z，Z ∈S，則-1 ∈S［不成立］ 1-4 設集合 A ={3，4}，B = {4，3} ∩ ?，C = {4，3} ∩{ ? }，D ={ 3，4，? }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F(xiàn) = { 4，?，3，3}，試問哪兩個集合之間可用等號表示 ？ 答：A = E；B = C；D = F 1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 } （2）A = { x│x ∈N 且 3－x 〈 3 } 答：（1）A = { 0，1，2，3 }； （2）A = { 1，2，3，4，……} = Z+； 第二章二元關系 2-1 給定 X =（3, 2，1），R 是 X 上的二元關系，其表達式如下： R = {〈x，y〉x，y ∈X 且 x≤ y } 求：(1)domR =?;(2)ranR =?;(3)R 的性質。 答：R = {<2，3>，<1,2>，<1,3>}； DomR={R中所有有序對的x}={2,1,1}={2,1}; RanR={R中所有有序對的y}={3,2,3}={3,2}； R 的性質:反自反,反對稱,傳遞性質.2-2 設 R 是正整數(shù)集合上的關系，由方程 x + 3y = 12 決定，即 R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求： （1）R 的列元表達式；（2）給出 dom（R。R）。 答：根據(jù)方程式有：y=4-x/3，x 只能取 3，6,9。 （1）R = {〈3，3〉,〈6，2〉,〈9，1〉}； 至于(2),望大家認真完成合成運算 R。R={<3,3>}.然后,給出 R。R 的定義域,即 （2）dom（R。R）= {3}。 2-3 判斷下列映射 f 是否是 A 到 B 的函數(shù)；并對其中的 f：A→B 指出他的性質，即 是否單射、滿射和雙射，并說明為什么。 （1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。 （2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。 （3）A = B = R，f=x。 （4）A = B = N，f=x2。 （5）A = B = N，f = x + 1。 答：（1）是 A 到 B 的函數(shù)，是滿射而不是單射； （2）是雙射； （3）是雙射； （4）是單射，而不是滿射； （5）是單射而不是滿射。 2-4 設 A ={1，2，3，4}，A 上的二元關系 R ={〈x，y〉︱（x-y）能被3整除}，則自然映射 g：A→A/R使 g(1)=[C] A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。 2-5 設 A ={1，2，3}，則商集A/IA =[D] A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。 2-6．設ｆ(x)＝x+1，ｇ(x)＝x-1 都是從實數(shù)集合Ｒ到Ｒ的函數(shù)，則ｆ。ｇ＝[C] A．x+1；B．x-1；C．x；D．x2。 第三章 結構代數(shù)(群論初步) 3-1 給出集合及二元運算，闡述是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？ （1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元運算 *是普通乘法。 （2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ； 二元運算。定義如下：對于所有 ai，aj ∈S2，都有 ai。aj = ai。 （3）S3 = {0，1}，二元運算 * 是普通乘法。 答：（1）二元運算*在S1上不封閉．所以，＂S1，*＂不能構成代數(shù)系統(tǒng)。 （2）由二元運算的定義不難知道。在 S2 內是封閉的，所以，〈S2。〉構成代數(shù) 系統(tǒng)；然后看該代數(shù)系統(tǒng)的類型：該代數(shù)系統(tǒng)只是半群。 （3）很明顯，〈{0，1}，*〉構成代數(shù)系統(tǒng)；滿足結合律，為半群；1是幺元，為獨異 點；而 0 為零元；結論：僅為獨異點，而不是群。 3-2 在自然數(shù)集合上，下列那種運算是可結合的［A］ A．x*y = max(x,y)；B．x*y = 2x+y ； C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 設 Z 為整數(shù)集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有 x。y=x + y，試問〈Z。〉能否構成群，為什麼 ？ 答：由題已知，集合Z滿足封閉性；二元運算滿足結合律，依此集合Z為半群；有幺元為 －5，為獨異點.假設代數(shù)系統(tǒng)的幺元是集合中的元素 e,則一個方程來自于二元運算定義, 即e。x= e + x，一個方程來自該特殊元素的定義的性質,即e。x = x.由此而來的兩個方程聯(lián)立結果就有: e+x=x 成立.削去 x,e=0 的結果不是就有了嗎!；每個元素都有逆.求每個元素的逆元素,也要解聯(lián)方程,如同求幺元一樣的道理；結論是：代數(shù)系統(tǒng)〈 Z。〉構成群。 第二部分圖論方法 第四章 圖 4-1 10 個頂點的簡單圖 G 中有 4 個奇度頂點，問 G 的補圖中有幾個偶數(shù)度頂點 ？ 答：因為10階完全圖的每個頂點的度數(shù)都是n-1=9――為奇數(shù)。這樣一來，一個無向簡單圖 G 的某頂點的度數(shù)是奇數(shù)，其補圖的相應頂點必偶數(shù)，因為一個偶數(shù)與一個奇數(shù)之和才是奇數(shù)．所以，Ｇ的補圖中應有 10-4＝6 個奇數(shù)度頂點。 4-2 是非判斷：無向圖G中有10條邊,4個3度頂點,其余頂點度數(shù)全是2,共有 8 個頂點.[是] 4-3 填空補缺：1條邊的圖 G 中，所有頂點的度數(shù)之和為[2] 第五章樹 5-1握手定理的應用（指無向樹） （1）在一棵樹中有 7 片樹葉，3 個 3 度頂點，其余都是 4 度頂點，問有(有1個4度頂點)個？ （2）一棵樹有兩個 4 度頂點，3 個 3 度頂點，其余都是樹葉，問有(9個1度頂點)片？ 5-2 一棵樹中有 i 個頂點的度數(shù)為 i（i=2，…k），其余頂點都是樹葉(即一度頂點)，問樹葉多少片？設有x片,則 x= 答：假設有 x 片樹葉，根據(jù)握手定理和樹的頂點與邊數(shù)的關系，有關于樹葉的方程，解方程得到樹葉數(shù) x = Σi（i—2）i + 2，（i = 2，3，……k）。 5-3 求最優(yōu) 2 元樹：用 Huffman 算法求帶權為 1，2，3，5，7，8 的最優(yōu) 2 元樹 T。試問：（1）T 的權 W（T）？（2）樹高幾層 ？ 答：用 Huffman 算法，以 1，2，3，5，7，8 為權，最優(yōu) 2 元樹 T ；然后，計算并回答所求問題：（1）T 的權 W（T）= 61；（2）樹高幾層：4 層樹高。 5-4以下給出的符號串集合中，那些是前綴碼？將結果填入[]內.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非] 5-5(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非] 5-6(是非判斷題)二元正則樹有奇數(shù)個頂點。[是] 5-7 在某次通信中 a，b，c，d，e 出現(xiàn)的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。 1、最優(yōu)二元樹 T；2.每個字母的碼字； 答：每個字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號 出現(xiàn)次數(shù)即為權，如右下圖).。100（近似）7.。563..4。282..2..2。..1..14141414111 1所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。 第三部分邏輯推理理論 第六章 命題邏輯 6-1 判斷下列語句是否命題，簡單命題或復合命題。 （1）2月 17 號新學期開始。[真命題] （2）離散數(shù)學很重要。[真命題] （3）離散數(shù)學難學嗎 ？[真命題] （4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。[復合命題] （5）x + 5 大于 2。[真命題] （6）今天沒有下雨，也沒有太陽，是陰天。[復合命題] 6-2 將下列命題符號化.（1）2 是偶素數(shù)。 （2）小李不是不聰明，而是不好學。 （3）明天考試英語或考數(shù)學。（兼容或） （4）你明天不去上海，就去北京。（排斥或） 答：（1）符號化為： p ∧ q。 （2）符號化為：p ∧ ﹃q。 （3）符號化為：p ∨ q。 （4）符號化為：（﹃p ∧ q）∨（p ∧ ﹃q）。 6-3分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0； （2）Σ（0，1，2，3）； （3）Σ（1，3）。 以下兩題(6-4;6-5)為選擇題,將正確者填入[]內.6-4 令 p：經(jīng)一塹；q：長一智。命題’’只有經(jīng)一塹，才能長一智’’符號化為[B] A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p 6-5 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號化為［B］ A． p→q；B．q→p；C．p∧q；D．﹁q→p 6-6證明題:用不同方法(必須有構造證明法)判斷推理結果是否正確。 如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。答：將公式分成前提及結論。 前提：（p→﹃q），p； 結論：﹃q； 證明：（1）（p→﹃q）前提引入 （2）p前提引入 （3）（p→﹃q）∧p（1）（2）假言推理 （4）﹃q 要證明的結論與證明結果一致，所以推理正確。 第七章謂詞邏輯 7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號化 （1）這臺機器不能用。 （2）如果 2 ＞ 3，則 2 ＞ 5。 答：（1）﹃F（a）。 （2）L（a，b）→ H（a，z）。 7-2 填空補缺題：設域為整數(shù)集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0） 7-3在謂詞邏輯中將下列命題符號化 （1）有的馬比所有的牛跑得慢。 （2）人固有一死。 答：（1）符號化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。 （2）與（1）相仿，要注意量詞、聯(lián)結詞間的搭配： x（F（x）→y（G（y）→ H（x，y）））。 《附錄》習題符號集 ? 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, ÷ 普通除法, ㏑ 自然對數(shù), ㏒ 對數(shù)，﹃ 非，?量詞 ”所有”，”每個”，∨ 析取聯(lián)結詞，∧ 合取聯(lián)結詞，彐 量詞”存在”，”有的”。 2010年8月12號。 淺談離散數(shù)學 【摘要】離散數(shù)學是一門理論性強,知識點多,概念抽象的基礎課程,學生學習起來普遍感到難度很高。本文從離散數(shù)學內容、學生學習興趣的激發(fā)、教學內容的安排、教學方式方法的使用等方面,探討了如何上好、學好離散數(shù)學課。 【關鍵詞】離散數(shù)學教學方法教師 學生 離散數(shù)學研究的是離散量，是計算機科學與技術系各專業(yè)的核心課程。課程內容具有知識點多、散、抽象等特點,加之學生不能認識到該課程的重要性,缺乏學習興趣和學習主動性,不僅忽視該課程的學習,甚至害怕這門課程。因此,創(chuàng)新教學方法,提高學生自主學習的積極性,對提高學生的能力、提升教學質量和水平具有重要的意義。通過一學期的學習和專研,我積累了少許經(jīng)驗,總結了一些關于離散數(shù)學的教學方法，僅供大家參考。 一、離散數(shù)學的特點 本課程介紹計算機科學與技術系各專業(yè)所需要的離散數(shù)學基礎知識,主要有以下兩點特點： 1、知識點集中，概念和定理多：《離散數(shù)學》是建立在大量概念之上的邏輯推理學科，概念的理解是我們學習這門學科的核心。掌握、理解和運用這些概念和定理是學好這門課的關鍵。要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的則是定理和性質。 2、方法性強：離散數(shù)學的特點是抽象思維能力的要求較高。培養(yǎng)學生抽象思維能力、邏輯推理能力、縝密概括能力以及分析和解決實際問題能力的主干課程,對學習其他諸多課程,具有重要的指導作用。《離散數(shù)學》的證明題多，不同的題型會需要不同的證明方法，同一個題也可能有幾種方法，具有很強的方法性。 二、教學困難所在1、離散數(shù)學是一門理論性強,知識點多,概念抽象的基礎課程, 內容具有知 識點多、散、抽象等特點，學生學者困難； 2、學生不能認識到該課程的重要性,缺乏學習興趣和學習主動性,不僅忽視該課程的學習,甚至害怕這門課程。 3、離散數(shù)學課程在課堂教學難度、教學時間等方面的原因,很多學校都出現(xiàn)師生、學生之間的交流較少，從而使學生學習困難。 三、離散數(shù)學的教學方法引導學生提高對離散數(shù)學課程應用性的認識,激發(fā)學生學習的興趣和愛好,增強汲取知識的自主性 離散數(shù)學課程是一門基礎性課程,學習離散數(shù)學課程對學生今后的學習和工作,具有重要的作用,例如培養(yǎng)學生的抽象思維能力和縝密的邏輯推理能力,為學生今后處理離散信息,提高專業(yè)理論水平,從事計算機的實際工作提供必備的數(shù)學工具;通過學習,可以掌握數(shù)理邏輯,集合論,代數(shù)結構和圖論的基本概念和原理,并會運用離散數(shù)學的方法,分析和解決計算機理論和應用中的一些問題等。學習主動性是學生的力量之源,因此,引導學生充分認識學習離散數(shù)學課程的作用,能夠激發(fā)學生學習的愛好和熱情,提升學生學習的積極性和主動性,從而使學生學有成效。認真?zhèn)湔n,合理準備教學內容和安排教學環(huán)節(jié),優(yōu)化教學方式方法 備好課是教學取得預期效果的前提和基礎,針對學生學習具體情況,合理準備教學內容和安排教學環(huán)節(jié),使用恰當?shù)慕虒W方法,在教學中可以起到事半功倍的效果。 (1)合理地準備教學內容。根據(jù)課程教學大綱和離散數(shù)學課程定理定義比較多、知識比較抽象的特點以及學生的實際情況,準備深度和廣度適合學生特點的教學內容。 (2)合理地講解課程內容,重難點突出講解,注意輕重緩急。對于離散數(shù)學中比較重要、比較抽象的概念和定理,如邏輯的推理理論、關系的性質、群、圖等,認真分析,用多種方式和方法深入 講解,可以使用解析法、圖示法、矩陣法舉實例等多種方法講解。對于比較容易理解和掌握的內容,可以一筆帶過。這樣,學生對所學內容就會有重點地學習,主次分明,學生不僅可以對所學內容掌握透徹,更能熟練把握離散數(shù)學中分析問題和解決問題的思路、方式和方法。 (3)啟發(fā)式教學和教師講授相結合。很多人認為,大學教學課時緊,內容多,關鍵靠學生自主學習,我卻認為并不完全是這樣的。如果教師不顧學生的理解情況,只顧在講臺上講授知識,課堂氛圍會很沉悶,很多同學不能專注于該門課程的學習,經(jīng)常走神,教學很難達到預期的效果。因此,有針對性地提問和展開討論,不僅能夠培養(yǎng)學生的思考能力,更能調動學生學習的興趣和積極性,從而使教學達到最佳效果。也可以引進有趣生動的例子說明概念，既活躍課堂，又鞏固了學生的記憶。3 合理布置作業(yè),認真批改作業(yè),有針對性地安排習題課和課后答疑 學數(shù)學就要做數(shù)學，《離散數(shù)學》的學習也不例外。學習數(shù)學不僅限于學習數(shù)學知識，更重要的還在于學習數(shù)學思維方法。為了強化學生能力的訓練,培養(yǎng)學生的抽象思維能力、邏輯推理能力、實際問題的解決能力等,在保證作業(yè)數(shù)量的同時,更要提高布置作業(yè)的質量,增加典型簡答題、討論題、推理題、實際應用題等習題在作業(yè)中的分量,使學生在掌握各種基本知識和基本技能的同時,提高自身的綜合能力。 認真檢查和批改作業(yè),是督促學生學習的主要途徑,也是教師了解學生理解和掌握所學課程情況的主渠道。必要時,教師可以批改一部分作業(yè),其他作業(yè)讓同學們之間互相檢查和批改,不僅可以督促學生學習,更能讓學生在批改其他同學作業(yè)時逐步認識到自身的缺陷和不足,以備今后更有針對性地學習。 教師在作業(yè)檢查和批改過程中發(fā)現(xiàn)的主要問題和疑難以及學生提出的有代表性的問題,有必要安排習題課進行講解,幫助學生對解決疑難,加深對所知識的理解。對于學生比較爭論的問題,可以展開討論,鼓勵學生大膽發(fā)言,培養(yǎng)學生探索未知的精神和創(chuàng)造性解決實際問題的能力。 四、總結 從此上看，上好離散數(shù)學課,關鍵是根據(jù)學生具體實際,有針 對性地安排教學內容,合理使用教學方式方法,最大限度地激發(fā)學生的學習興趣,充分發(fā)揮教師的主導作用和學生的主體作用,達到教與學和諧。 參考文獻 [1] 屈婉玲,耿素云,張立昂.離散數(shù)學[M].北京:高等教育出版社.2008.[2] 黃巍,金國祥.”離散數(shù)學”課程教學改革的探討[J].中國電力教育,2009(8):82-83.[3] 周小燕,胡豐華.對提高離散數(shù)學教學質量的探討[J].浙江科技學院學報,2007,19(2):156-158.[4] 龍浩,張佳佳.怎樣教好《離散數(shù)學》課[J].貴陽學院學報,2007,2(1):53-57.[5] 廖仲春.離散數(shù)學的教學探討[J].湖南工業(yè)職業(yè)技術學院學報,2008,8(5)http:// 離散數(shù)學試題（A卷答案） 一、（10分） （1）證明(P?Q)∧(Q?R)?(P?R)（2）求(P∨Q)?R的主析取范式與主合取范式，并寫出其相應的成真賦值和成假賦值。解：（1）因為((P?Q)∧(Q?R))?(P?R)??((?P∨Q)∧(?Q∨R))∨(?P∨R)?(P∧?Q)∨(Q∧?R)∨?P∨R ?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R))?(P∧?Q)∨(Q∨?P∨R)?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R)?T 所以，(P?Q)∧(Q?R)?(P?R)。 （2）(P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R ?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R)?M2∧M4∧M6 ?m0∨m1∨m3∨m5 所以，其相應的成真賦值為000、001、011、101、111：成假賦值為：010、100、110。 二、（10分）分別找出使公式?x(P(x)??y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。 解：設論域為{1，2}。 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((F∧F)∨(F∧F)))∧(T?((F∧F)∨(F∧F)))?(T?F)∧(T?F)?F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 ?x(P(x)??y(Q(y)∧R(x，y)))??x(P(x)?((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))?(P(1)?((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)?((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))?(T?((T∧T)∨(T∧T)))∧(T?((T∧T)∨(T∧T)))?(T?T)∧(T?T)?T 三、（10分） 在謂詞邏輯中構造下面推理的證明：每個喜歡步行的人都不喜歡做汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。 解 論域：所有人的集合。A(x)：x喜歡步行；B(x)：x喜歡坐汽車；C(x)：x喜歡騎自行車；則推理化形式為： ?x(A(x)??B(x))，?x(B(x)∨C(x))，??xC(x)?x?A(x)下面給出證明：(1)??xC(x) P(2)?x?C(x) T(1)，E(3)?C(c) T(2)，ES(4)?x(B(x)∨C(x)) P(5)B(c)∨C(c) T(4)，US(6)B(c) T(3)(5)，I(7)?x(A(x)??B(x)) P(8)A(c)??B(c) T(7)，US(9)?A(c) T(6)(8)，I(10)?x?A(x) T(9)，EG 四、（10分） 下列論斷是否正確？為什么？(1)若A∪B＝A∪C，則B＝C。(2)若A∩B＝A∩C，則B＝C。(3)若A?B＝A?C，則B＝C。 解(1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，則A∪B＝A∪C，但B＝C不成立。(2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，則A∩B＝A∩C，但B＝C不成立。(3)成立。因為若A?B＝A?C，對任意的x∈B，當x∈A時，有x∈A∩B?x?A?B?x?A?C＝(A∪C)－(A∩C)?x∈A∩C?x∈C，所以B?C；當x?A時，有x?A∩B，而x∈B?x∈A∪B，所以x∈A∪B－A∩B＝A?B?x∈A?C，但x? A，于是x∈C，所以B?C。 同理可證，C ?B。 因此，當A?B＝A?C時，必有B＝C。 五、（10分）若R是集合A上的自反和傳遞關系，則對任意的正整數(shù)n，R＝R。 證明 當n＝1時，結論顯然成立。設n＝k時，Rk＝R。當n＝k＋1時，Rk+1＝Rk*R＝R*R。下面由R是自反和傳遞的推導出R*R＝R即可。 由傳遞性得R*R?R。另一方面，對任意的 由數(shù)學歸納法知，對任意的正整數(shù)n，Rn＝R。 n 六、（15分）設函數(shù)f：R×R?R×R，f定義為：f( (1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f。 (4)求復合函數(shù)f－1?f和f?f。 證明(1)對任意的x，y，x1，y1∈R，若f( (2)對任意的 1，y＝ u?w2，則f( u?w2＋ u?w2，u?w2－>＝ u?w2－1(3)f( x?y?x?y2x?y?(x?y)2(4)f?f( 七、（15分）設X＝{1，2，3，4}，R是X上的二元關系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關系圖。(2)寫出R的關系矩陣。 (3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關系圖如圖所示：(2)R的關系矩陣為： ?1??0M(R)??1??1?101110110??0? 0??0??(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的； 經(jīng)過計算可得 ?1??02M(R)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0?? 八、（10分）若 對于任意的a、b∈H，有a*b＝a*(b)∈H，即a*b∈H。又因為H是G非空子集，所以*在H上滿足結合律。綜上可知， 九、（10分）給定二部圖G＝ 證明 設|V1|＝m1，則|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m22 2－ 1－1 －1 m12。因為(m2?m1)2?0，即4?mm1?m1，所以n≤m2/4。離散數(shù)學試題（B卷答案） 一、（20分）用公式法判斷下列公式的類型：(1)(?P∨?Q)?(P??Q)(2)(P?Q)?(P∧?(Q∨?R))解：（1）因為(?P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q) ?(P∧Q)∨(P∧?Q)∨(?P∧Q)?m1∨m2∨m3 ?M0 所以，公式(?P∨?Q)?(P??Q)為可滿足式。 （2）因為(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1 ?m2∨m3∨m4∨m5∨m6∨m7 所以，公式(P?Q)?(P∧?(Q∨?R))為可滿足式。 二、（15分）在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業(yè)中都會獲得成功。存在著身體健康的科學家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。 Q(x)：x是勤奮的；x是科學家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為： ?x(S(x)?Q(x))，?x(Q(x)∧H(x)?C(x))，?x(S(x)∧H(x)) ?x(C(x)∨F(x))下面給出證明： (1)?x(S(x)∧H(x)) P(2)S(a)∧H(a) T(1)，ES(3)?x(S(x)?Q(x)) P(4)S(a)?Q(a) T(1)，US(5)S(a) T(2)，I(6)Q(a) T(4)(5)，I(7)H(a) T(2)，I(8)Q(a)∧H(a) T(6)(7)，I(9)?x(Q(x)∧H(x)?C(x)) P(10)Q(a)∧H(a)?C(a) T(9)，Us(11)C(a) T(8)(10)，I(12)?xC(x) T(11)，EG(13)?x(C(x)∨F(x)) T(12)，I 三、（10分）設A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}} 四、（15分）設R和S是集合A上的任意關系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。(2)若R和S是反自反的，則R*S也是反自反的。(3)若R和S是對稱的，則R*S也是對稱的。(4)若R和S是傳遞的，則R*S也是傳遞的。(5)若R和S是自反的，則R∩S是自反的。(6)若R和S是傳遞的，則R∪S是傳遞的。 解 (1)成立。對任意的a∈A，因為R和S是自反的，則 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，則R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，則R和S是對稱的，但R*S＝{<1，3>，<3，2>}不是對稱的。 (4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，則R和S是傳遞的，但R*S＝{<1，3>，<1，1>，<2，1>}不是傳遞的。 (5)成立。對任意的a∈A，因為R和S是自反的，則 五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。問(1)有多少個不同的由X到Y的函數(shù)？ (2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射？(3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射？ 解 (1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數(shù)共n個。 (2)顯然當|m|≤|n|時，存在單射。由于在Y中任選m個元素的任一全排列都形成X到Y的不同的單射，故不同的單射有Cnm!＝n(n－1)(n―m―1)個。 (3)顯然當|m|＝|n|時，才存在雙射。此時Y中元素的任一不同的全排列都形成X到Y的不同的雙射，mm故不同的雙射有m!個。 六、（5分）集合X上有m個元素，集合Y上有n個元素，問X到Y的二元關系總共有多少個？ 解 X到Y的不同的二元關系對應X×Y的不同的子集，而X×Y的不同的子集共有個2mn，所以X到Y的二元關系總共有2mn個。 七、（10分）若 證明 設e是群 若x?∈G也是a*x＝b的解，則x?＝e*x?＝(a*a)*x?＝a*(a*x?)＝a*b＝x。所以，x＝a*b是a*x － 1－1 －1 －1＝b的惟一解。 八、（10分）給定連通簡單平面圖G＝ 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝24。若存在f∈ f?FF，使得d(f)＞3，則3|F|＜2|E|＝24，于是|F|＜8，與|F|＝8矛盾。故對任意f∈F，d(f)＝3。 第一章 數(shù)學語言與證明方法 例1 設E={ x | x是北京某大學學生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數(shù)學系學生}，D= { x | x是喜歡聽音樂的學生}.試描述下列各集合中學生的特征: (A?D)? ~ C={ x | x是北京人或喜歡聽音樂,但不是數(shù)學系學生} ~ A?B={ x | x是外地走讀生}(A-B)? D={ x | x是北京住校生, 并且喜歡聽音樂} ~ D ? ~ B={ x | x是不喜歡聽音樂的住校生} 例3 證明:(1)A?B=B?A(交換律)證 ?x x?A?B ? x?A?x?B (并的定義) ?x?B?x?A (邏輯演算的交換律) ?x?B?A (并的定義)(2)A?(B?C)=(A?B)?(A?C)(分配律)證 ?x x?A?(B?C) ? x?A?(x?B? x?C) (并,交的定義) ?(x?A?x?B)?(x?A?x?C) (邏輯演算的分配律) ?x?(A?B)?(A?C) (并,交的定義)(3)A?E=E(零律)證 ?x x?A?E ? x?A?x?E (并的定義) ? x?A?1 (全集E的定義) ?1 (邏輯演算的零律) ?x?E (全集E的定義)(4)A?E=A(同一律)證 ?x x?A?E ? x?A?x?E (交的定義) ? x?A?1 (全集E的定義) ? x?A (邏輯演算的同一律)例4 證明 A?(A?B)=A（吸收律）證 利用例3證明的4條等式證明 A?(A?B) =(A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交換律) = A?E (零律) = A (同一律)例5 證明(A-B)-C=(A-C)-(B-C)證 (A-C)-(B-C) =(A ? ~C)? ~(B ? ~C) (補交轉換律) =(A ? ~C)?(~B ? ~~C) (德摩根律) =(A ? ~C)?(~B ? C) (雙重否定律) =(A ? ~C ? ~B)?(A ? ~C ? C) (分配律) =(A ? ~C ? ~B)?(A ? ?) (矛盾律) = A ? ~C ? ~B (零律,同一律) =(A ? ~B)? ~C (交換律,結合律) =(A – B)– C (補交轉換律)例6 證明(A?B)?(A?C)=(B?C)(A?C))?((A?C)A 例7 設A,B為任意集合, 證明:(1)A?A?B 證 ?x x?A ? x?A?x?B (附加律) ? x?A?B (2)A?B?A 證 ?x x?A?B ? x?A?x?B ? x?A (化簡律)(3)A-B?A 證 ?x x?A-B ? x?A?x?B ? x?A (化簡律)(4)若A?B, 則P(A)?P(B)證 ?x x?P(A)? x?A ? x?B (已知A?B) ? x?P(B)例8 證明 A?B=A?B-A?B.證 A?B=(A?~B)?(~A?B) =(A?~A)?(A?B)?(~B?~A)?(~B?B) =(A?B)?(~B?~A) =(A?B)?~(A?B) =A?B-A?B 例3 若A-B=A, 則A?B=? 證 用歸謬法, 假設A?B??, 則存在x,使得 x?A?B ? x?A?x?B ? x?A-B?x?B (A-B=A) ? x?A?x?B?x?B ? x?B?x?B，矛盾 例4 證明 是無理數(shù) 證 假設 是有理數(shù), 存在正整數(shù)n,m, 使得 =m/n,不妨設m/n為既約分數(shù).于是m=n, m2=2n2, m2是偶數(shù), 從而m是偶數(shù).設m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數(shù), 與m/n為既約分數(shù)矛盾.例6 對于每個正整數(shù)n, 存在n個連續(xù)的正合數(shù).證 令x=(n+1)! 則 x+2, x+3,…, x+n+1是n個連續(xù)的正合數(shù): i | x+i，i=2,3,…,n+1 例7 判斷下述命題是真是假: 若A?B=A?C, 則B=C.解 反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有 A?B=A?C = {a,b} 但B?C, 故命題為假.例8 證明:對所有n?1, 1+2+ … +n=n(n+1)/2 證 歸納基礎.當n=1時, 1=1?(1+1)/2, 結論成立.歸納步驟.假設對n?1結論成立, 則有 1+2+ … +n +(n+1)=n(n+1)/2 +(n+1) (歸納假設) =(n+1)(n+2)/2 得證當n+1時結論也成立.例9 任何大于等于2的整數(shù)均可表成素數(shù)的乘積 證 歸納基礎.對于2, 結論顯然成立.歸納步驟.假設對所有的k(2?k?n)結論成立, 要證結論 對n+1也成立.若n+1是素數(shù), 則結論成立;否則n+1=ab, 2?a,b 命題邏輯 例1 下列句子中那些是命題？ (1)北京是中華人民共和國的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你會開車嗎？ (5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請關上門！(8)我正在說謊話.(1),(2),(5)是命題,(3),(4),(6)~(8)都不是命題 例2 將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.解 (1)p∧q (2)p∧q (3)p∧?q(4)記 r:張輝是三好生, s:王麗是三好生，r∧s(5)簡單命題，記 t:張輝與王麗是同學 例3 將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.解 (1)p∨r, 真值:1(2) p∨q, 真值: 1(3)r∨s,真值: 0(4)記t:元元拿一個蘋果,u:元元拿一個梨 (t∧?u)∨(?t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年 (v∧?w)∨(?v∧w)又可形式化為 v∨w 例4 設p:天冷, q:小王穿羽絨服，將下列命題符號化 (1)只要天冷，小王就穿羽絨服.p?q(2)因為天冷，所以小王穿羽絨服.p?q (3)若小王不穿羽絨服，則天不冷.?q??p 或 p?q(4)只有天冷，小王才穿羽絨服.q?p(5)除非天冷，小王才穿羽絨服.q?p(6)除非小王穿羽絨服，否則天不冷.p?q (7)如果天不冷，則小王不穿羽絨服.?p??q 或 q?p(8)小王穿羽絨服僅當天冷的時候.q?p 例5 求下列復合命題的真值 (1)2+2＝4 當且僅當 3+3＝6.(2)2+2＝4 當且僅當 3是偶數(shù).0(3)2+2＝4 當且僅當 太陽從東方升起.(4)2+2＝5 當且僅當 美國位于非洲.(5)f(x)在x0處可導的充要條件是它在 x0處連續(xù).0 例6 公式A=(? p1? ? p2? ? p3)?(p1? p2) 000是成真賦值，001是成假賦值 公式B=(p?q)?r 000是成假賦值，001是成真賦值 例3 證明 p?(q?r)?(p?q)?r 證 p?(q?r) ? ?p?(?q?r) （蘊涵等值式） ?(?p??q)?r （結合律） ? ?(p?q)?r （德摩根律） ?(p?q)?r （蘊涵等值式 例4 證明: p?(q?r) (p?q)?r 方法一 真值表法（見例2） 方法二 觀察法.容易看出000使左邊成真, 使右邊成假.方法三 先用等值演算化簡公式, 再觀察.例5 用等值演算法判斷下列公式的類型(1)q??(p?q)解 q??(p?q) ? q??(?p?q) （蘊涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交換律，結合律） ? p?0 （矛盾律） ? 0 （零律）該式為矛盾式.(2)(p?q)?(?q??p)解 (p?q)?(?q??p) ?(?p?q)?(q??p) （蘊涵等值式） ?(?p?q)?(?p?q) （交換律） ? 1 該式為重言式.(3)((p?q)?(p??q))?r) 解 ((p?q)?(p??q))?r) ?(p?(q??q))?r （分配律） ? p?1?r （排中律） ? p?r （同一律） 非重言式的可滿足式.如101是它的成真賦值,000是它的 成假賦值.例1 求?(p?q)??r 的析取范式與合取范式 解 ?(p?q)??r ? ?(?p?q)??r ?(p??q)??r 析取范式 ?(p??r)?(?q??r) 合取范式 注意: 公式的析取范式與合取范式不惟一.例1(續(xù))求?(p?q)??r 的主析取范式與主合取范式 解(1)?(p?q)??r ?(p??q)??r p??q ?(p??q)?1 同一律 ?(p??q)?(?r?r) 排中律 ?(p??q??r)?(p??q?r) 分配律 ? m4?m5 ?r ?(?p?p)?(?q?q)??r 同一律, 排中律 ?(?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r) ? m0? m2? m4? m6 得 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6 可記作 ? ?(0,2,4,5,6)(2)?(p?q)??r ?(p??r)?(?q??r) p??r ? p?0??r 同一律 ? p?(q??q)??r 矛盾律 分配律 ?(p?q??r)?(p??q??r) 分配律 ? M1?M3 ?q??r ?(p??p)??q??r 同一律, 矛盾律 ?(p??q??r)?(?p??q??r) 分配律 ? M3?M7 得 ?(p?q)??r ? M1?M3?M7 可記作 ? ?(1,3,7)例2(1)求 A ?(?p?q)?(?p??q?r)?r的主析取范式 解 用快速求法 (1)?p?q ?(?p?q??r)?(?p?q?r)? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7 得 A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7)(2)求 B? ?p?(p?q??r)的主合取范式 解 ?p ?(?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1 得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7)例3 用主析取范式判斷公式的類型:(1)A? ?(p?q)?q (2)B? p?(p?q) (3)C?(p?q)?r 解(1)A ? ?(? p?q)?q ?(p??q)?q ? 0 矛盾式(2)B ? ? p?(p?q)? 1 ? m0?m1?m2?m3 重言式(3)C ? ?(p?q)?r ?(?p??q)?r ?(?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r) ? m0?m1?m3? m5?m7 非重言式的可滿足式 例4 用主析取范式判斷下面2組公式是否等值:(1)p與(?p?q)?(p?q)解 p ? p?(?q?q)?(p??q)?(p?q)? m2?m3 (?p?q)?(p?q)? ?(?p?q)?(p?q) ?(p??q)?(p?q)? m2?m3 故 p ?(?p?q)?(p?q)(2)(p?q)?r 與 p?(q?r)解(p?q)?r ?(p?q??r)?(p?q?r) ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5? m6?m7 p?(q?r)?(p?q)?(p? r) ?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r) ? m5? m6?m7 故 (p?q)?r p?(q?r)例5 某單位要從A,B,C三人中選派若干人出國考察, 需滿 足下述條件:(1)若A去, 則C必須去;(2)若B去, 則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案? 解 記p:派A去, q:派B去, r:派C去 (1)p?r，(2)q??r，(3)(p??q)?(?p?q)求下式的成真賦值 A=(p?r)?(q??r)?((p??q)?(?p?q))例6 求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式 解 A ? m1?m3?m7 ? M0?M2?M4?M5?M6 例1 判斷下面推理是否正確:(1)若今天是1號, 則明天是5號.今天是1號.所以, 明天是5號.解 設 p: 今天是1號, q: 明天是5號 推理的形式結構為 (p?q)ùp?q 證明 用等值演算法 (p?q)ùp?q ? ?((?púq)ùp)úq ?((pù?q)ú?p)úq ? ?pú?qúq ? 1 得證推理正確 (2)若今天是1號, 則明天是5號.明天是5號.所以, 今天是1號.解 設p: 今天是1號, q: 明天是5號.推理的形式結構為 (p?q)ùq?p 證明 用主析取范式法 (p?q)ùq?p ?(?púq)ùq?p ? ?((?púq)ùq)úp ? ?qúp ?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq) ? m0úm2úm3 01是成假賦值, 所以推理不正確.例2 在自然推理系統(tǒng)P中構造下面推理的證明: 前提: púq, q?r, p?s, ?s 結論: rù(púq)證明 ① p?s 前提引入 ② ? s 前提引入 ③ ? p ①②拒取式 ④ púq 前提引入 ⑤ q ③④析取三段論 ⑥ q?r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rù(púq) ⑦④合取 推理正確, rù(púq)是有效結論 例3 構造推理的證明: 若明天是星期一或星期三, 我就有 課.若有課, 今天必需備課.我今天下午沒備課.所以, 明天 不是星期一和星期三.解 設 p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(púq)?r, r?s, ?s 結論: ?pù?q 例4 構造下面推理的證明: 前提: ?púq, ?qúr, r?s 結論: p?s 證明 ① p 附加前提引入 ② ?púq 前提引入 ③ q ①②析取三段論 ④ ?qúr 前提引入 ⑤ r ③④析取三段論 ⑥ r?s 前提引入 ⑦ s ⑤⑥假言推理 推理正確, p?s是有效結論 例5 構造下面推理的證明 前提: ?(pùq)úr, r?s, ?s, p 結論: ?q 證明 用歸繆法 ① q 結論否定引入 ② r?s 前提引入 ③ ?s 前提引入 ④ ?r ②③拒取式 ⑤ ?(pùq)úr 前提引入 ⑥ ?(pùq) ④⑤析取三段論 ⑦ ?pú?q ⑥置換 ⑧ ?p ①⑦析取三段論 ⑨ p 前提引入 ⑩ ?pùp ⑧⑨合取 推理正確, ?q是有效結論 例6 用歸結證明法構造下面推理的證明: 前提:(p?q)?r, r?s, ?s 結論:(p?q)?(pùs)解 (p?q)?r ? ?(?púq)úr ?(pù?q)úr ?(púr)ù(?qúr) r?s ? ?rús ? (p?q)?(pùs)? ?(?púq)ú(pùs)?(pù?q)ú(pùs)? ? pù(?qús)推理可表成 前提: púr, ?qúr, ?rús, ?s 結論: pù(?qús) 第3章 一階邏輯 例1(1)4是偶數(shù) 4是個體常項, “是偶數(shù)”是謂詞常項, 符號化為: F(4)(2)小王和小李同歲 小王, 小李是個體常項, 同歲是謂詞常項.記a:小王，b: 小李, G(x,y): x與y同歲, 符號化為: G(a,b)(3)x< y x,y是命題變項, < 是謂詞常項, 符號化為: L(x,y)(4)x具有某種性質P x是命題變項, P是謂詞變項, 符號化為: P(x)例2 將下述命題用0元謂詞符號化, 并討論它們的真值:(1) 是無理數(shù), 而 是有理數(shù)(2)如果2>3，則3<4 解 (1)設F(x): x是無理數(shù), G(x): x是有理數(shù) 符號化為 真值為0(2)設 F(x,y): x>y, G(x,y): x 個體域分別取(a)人類集合,(b)全總個體域.解:(a)(1)設F(x): x愛美，符號化為 ?x F(x) (2)設G(x): x用左手寫字，符號化為 ?x G(x) (b)設M(x): x為人，F(xiàn)(x), G(x)同(a)中 (1)?x(M(x)?F(x)) (2)? x(M(x)?G(x))M(x)稱作特性謂詞 例4 將下列命題符號化, 并討論其真值:(1)對任意的x, 均有x2-3x+2=(x-1)(x-2)(2)存在x, 使得x+5=3 分別取(a)個體域D1=N,(b)個體域D2=R 解 記F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a)(1)?x F(x) 真值為1 (2)?x G(x) 真值為0(b)(1)?x F(x) 真值為1 (2)?x G(x) 真值為1 例5 將下面命題符號化:(1)兔子比烏龜跑得快 (2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得一樣快的兔子和烏龜 解 用全總個體域，令F(x): x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)?x?y(F(x)?G(y)?H(x,y))(2)?x(F(x)?(?y(G(y)?H(x,y)))(3)? ?x?y(F(x)?G(y)?H(x,y))(4)? ?x?y(F(x)?G(y)?L(x,y))例6 公式 ?x(F(x,y)??yG(x,y,z))?x的轄域:(F(x,y)??yG(x,y,z))，指導變元為x ?y的轄域:G(x,y,z)，指導變元為y x的兩次出現(xiàn)均為約束出現(xiàn) y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn) z為自由出現(xiàn).例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導變元為x ?x的轄域:G(x)，指導變元為x x的兩次出現(xiàn)均為約束出現(xiàn).但是, 第一次出現(xiàn)的x是?x中 的x, 第二次出現(xiàn)的x是?x中的x.例8 給定解釋I 如下: (a)個體域 D=N (b) (c) (d)謂詞 說明下列公式在 I 下的含義, 并討論其真值 (1)?xF(g(x,a),x)?x(2x=x) 假命題 (2)?x?y(F(f(x,a),y)?F(f(y,a),x))?x?y(x+2=y?y+2=x) 假命題(3)?x?y?zF(f(x,y),z) ?x?y?z(x+y=z) 真命題 (4)?xF(f(x,x),g(x,x)) ?x(2x=x2) 真命題(5)F(f(x,a), g(x,a))x+2=2x 不是命題 (6)?x(F(x,y)?F(f(x,a), f(y,a)))?x(x=y?x+2=y+2) 真命題 例8(1)~(4)都是閉式, 在I下全是命題.(5)和(6)不是閉式, 在I下(5)不是命題,(6)是命題 例9 判斷下列公式的類型:(1)?x(F(x)?G(x))取解釋I1, D1=R，:x是整數(shù)，:x是有理數(shù), 取解釋I2, D2=R，:x是整數(shù)，:x是自然數(shù), 非永真式的可滿足式(2)?(?xF(x))?(?xF(x)) 這是 ?p?p 的代換實例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實例, ?(p?q)?q是矛盾式 矛盾式 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項 真命題 假命題 (1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z) 換名規(guī)則 ? ?uF(u,y,z)? ?vG(x,v,z) 換名規(guī)則 或者 ? ?xF(x,u,z)? ?yG(x,y,z) 代替規(guī)則 ? ?xF(x,u,z)? ?yG(v,y,z) 代替規(guī)則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z)) 換名規(guī)則 或者 ? ?x(F(x,t)? ?yG(x,y,z)) 代替規(guī)則 例2 設個體域D={a,b,c}, 消去下面公式中的量詞:(1)?x(F(x)?G(x))?(F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c))(2)?x(F(x)??yG(y))? ?xF(x)??yG(y) 量詞轄域收縮 ?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))(3)?x?yF(x,y)? ?x(F(x,a)?F(x,b)?F(x,c))?(F(a,a)?F(a,b)?F(a,c))?(F(b,a)?F(b,b)?F(b,c)) ?(F(c,a)?F(c,b)?F(c,c))例3 給定解釋I:(a)D={2,3},(b) (c) :x是奇數(shù)，: x=2 ? y=2，: x=y.在I下求下列各式的真值:(1)?x(F(f(x))?G(x, f(x))) 解 (F(f(2))?G(2, f(2)))?(F(f(3))?G(3, f(3)))?(1?1)?(0?1)? 1(2)?x?yL(x,y)解 ?yL(2,y)??yL(3,y)?(L(2,2)?L(2,3))?(L(3,2)?L(3,3))?(1?0)?(0?1)? 0 例4 證明下列等值式: ? ?x(M(x)?F(x))? ?x(M(x)? ?F(x))證 左邊 ? ?x ?(M(x)?F(x)) 量詞否定等值式 ? ?x(?M(x)??F(x))? ?x(M(x)? ?F(x))例5 求公式的前束范式(1)?xF(x)???xG(x)解 ? ?xF(x)??x?G(x) 量詞否定等值式 ? ?x(F(x)??G(x)) 量詞分配等值式 解2 ? ?xF(x)???yG(y) 換名規(guī)則 ? ?xF(x)??y?G(y) 量詞否定等值式 ? ?x(F(x)??y?G(y)) 量詞轄域擴張 ? ?x?y(F(x)??G(y)) 量詞轄域擴張 第4章 關系 例1 <2,x+5>=<3y?4,y>，求 x, y.解 3y?4=2, x+5=y ? y=2, x= ?3 例2 A={0, 1}, B={a, b, c} A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} B?A ={ A = {?}, B = ? P(A)?A = {, <{?},?>} P(A)?B = ? 例3 (1)R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2)C={ R={ |A|=n, |B|=m, |A×B|=nm, A×B 的子集有 個.所以從A到B有 元關系.|A|=n, A上有 不同的二元關系.例如 |A|=3, 則 A上有512個不同的二元關系.例 5A={a, b, c, d}, R={ ??1110??1000???0000???0100??例1 R={ domR = ranR = fldR = 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R?1 = R°S = S°R = 個不同的二 例3 設A = {a, b, c, d}, R = { ?0100??0100??01 ???1010??1010102???M?? M???0001??0001??00 ?????00000000???00?? 例1 A = {a, b, c}, R1, R2, R3 是 A上的關系, 其中 R1 = { 00??1?010????01??0??00??0010?101??000??000?R2自反, R3 反自反, R1既不自反也不反自反.例2 設A＝{a,b,c}, R1, R2, R3和R4都是A上的關系, 其中 R1＝{ R1＝{ R2＝{ R3＝{ 證明若 IA ?R，則 R 在 A 上自反.證 任取x，x?A ? 因此 R 在 A 上是自反的.例5 證明若 R=R?1 , 則 R 在A上對稱.證 任取 因此 R 在 A 上是對稱的.例6 證明若 R∩R?1?IA , 則 R 在 A 上反對稱.證 任取 ? 因此 R 在 A 上是反對稱的.例7 證明若 R°R?R , 則 R 在 A 上傳遞.證 任取 因此 R 在 A 上是傳遞的.例8 判斷下圖中關系的性質, 并說明理由 (1)不自反也不反自反；對稱, 不反對稱；不傳遞.(2)反自反, 不是自反；反對稱, 不是對稱；傳遞.(3)自反，不是反自反；反對稱，不是對稱；不傳遞.例1 設A={a,b,c,d}, R={ 例1 設 A={1, 2, …, 8}, 如下定義 A上的關系R： R={ ?x?A, 有x≡x(mod 3) ?x,y?A, 若x≡y(mod 3), 則有y≡x(mod 3) ?x,y,z?A, 若x≡y(mod 3), y≡z(mod 3), 則有 x≡z(mod 3)例2 令A={1, 2, …, 8}，A關于模 3 等價關系R 的商集為 A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A關于恒等關系和全域關系的商集為： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} } 例3 設A＝{a, b, c, d}, 給定? 1, ? 2, ? 3, ? 4, ? 5, ? 6如下： ? 1={{a, b, c},jdb3l39rxn9}，? 2={{a, b},{c},jdb3l39rxn9} ? 3={{a},{a, b, c, d}}，? 4={{a, b},{c}} ? 5={?,{a, b},{c, d}}，? 6={{a,{a}},{b, c, d}} 則? 1和? 2是A的劃分, 其他都不是A的劃分.例4 給出A＝{1,2,3}上所有的等價關系 求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫出 對應的等價關系.A上的等價關系與劃 分之間的對應： ? 4對應于全域關系EA ? 5對應于恒等關系IA ? 1, ? 2和? 3分別對應于等價關系 R1, R2和R3.其中 R1={<2,3>,<3,2>}∪IA R2={<1,3>,<3,1>}∪IA R3={<1,2>,<2,1>}∪IA 例5 設A={1,2,3,4}，在A?A上定義二元關系 R： < A?A={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>} 根據(jù)有序對 例6 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> 例7 已知偏序集 R={ 例8 設偏序集 例1 設A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中 f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2 判斷下面函數(shù)是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數(shù)集（3）f : R→Z, f(x)=?x?（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+為正實數(shù)集.解(1)f : R→R, f(x)= ?x2+2x?1 在x=1取得極大值0.既不是單射也不是滿射的.(2)f : Z+→R, f(x)=lnx 單調上升, 是單射的.但不滿射, ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= ?x? 是滿射的, 但不是單射的, 例如 f(1.5)=f(1.2)=1.(4)f : R→R, f(x)=2x+1 是滿射、單射、雙射的, 因為它是單調函數(shù)并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有極小值f(1)=2.該函數(shù)既不是單射的也不是滿射的.例3 A=P({1,2,3}), B={0,1}{1,2,3} 解 A={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f0, f1, … , f7 }, 其中 f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令 f : A→B，f(?)=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4 A=[0,1] B=[1/4,1/2] 構造雙射 f : A→B解 令 f : [0,1]→[1/4,1/2] f(x)=(x+1)/4 例5 A=Z, B=N，構造雙射 f : A→B 將Z中元素以下列順序排列并與N中元素對應： Z：0?11 ?22?33 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 則這種對應所表示的函數(shù)是： x?0?2xf:Z?N,f(x)????2x?1x?0例1 設 f : R→R, g : R→R ?x2x?3f(x)?? x?3??2 g(x)?x?2 求 f °g, g°f.如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù).解 f?g:R?R?x2?2x?3f?g(x)??x?3?0g?f:R?R?(x?2)2g?f(x)????2x?1x?1 f : R→R不存在反函數(shù)；g : R→R的反函數(shù)是 g?1: R→R, g?1(x)=x?2 第6章 圖 例1 下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇數(shù)個奇數(shù).(2)能 例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小 于等于2, 問G至少有多少個頂點? 解 設G有n個頂點.由握手定理，4?3+2?(n-4)?2?10 解得 n?8 例3 已知5階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的 多面體.證 用反證法.假設存在這樣的多面體, 作無向圖G= 討論所有可能的情況.設有a個5度頂點和b個6度頂點(1)a=0, b=9; (2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)~(3)至少5個6度頂點,(4)和(5)至少6個5度頂點 方法二 假設b<5, 則a>9-5=4.由握手定理的推論, a ? 6 例6 畫出4階3條邊的所有非同構的無向簡單圖 解 總度數(shù)為6, 分配給4個頂點, 最大度為3, 且奇度頂點數(shù) 為偶數(shù), 有下述3個度數(shù)列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2 例7 畫出3個以1,1,1,2,2,3為度數(shù)列的非同構的無向簡單圖 0,2,2,2 例1 右圖有 個面 R1的邊界:a R2的邊界:bce R3的邊界:fg R0的邊界:abcdde, fg deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右邊2個圖是同一平面圖的平面嵌入.R1在(1)中是外部面, 在(2)中是內部面;R2在(1)中是內部面, 在(2)中是外部面.R3 R1 R3 R2(1) R2 R1(2) 說明:(1)一個平面圖可以有多個不同形式的平面嵌入, 它們都同構.(2)可以通過變換(測地投影法)把平面圖的任何一面作為外部面 例3 證明 K5 和 K3,3不是平面圖 證 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4 不滿足定理6.15的條件 例 5證明下面2個圖均為非平面圖.與K3,3同胚也可收縮到K3,3 與K5同胚也可收縮到K5 例6 畫出所有非同構的6階11條邊的簡單連通非平面圖 解 在K5(5階10條邊)上加一個頂點和一條邊 在K3,3(6階9條邊)上加2條邊 例1 某中學有3個課外活動小組:數(shù)學組, 計算機組和生物組.有趙,錢,孫,李,周5名學生, 問分別在下述3種情況下, 能否選出3人各任一個組的組長?(1)趙, 錢為數(shù)學組成員, 趙,孫,李為計算機組成員, 孫,李,周為生物組成員.(2)趙為數(shù)學組成員, 錢,孫,李為計算機組成員, 錢,孫,李,周為生物組成員.(3)趙為數(shù)學組和計算機組成員, 錢,孫,李,周為生物組成員.解 數(shù) 計 生 數(shù) 計 生 趙 錢 孫 李 周 趙 錢 孫 李 周 (1(數(shù) 計 生 趙 錢 孫 李 周 (3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖: (a(b(c) (c)中存在哈密頓通路 例3 證明右圖不是哈密頓圖 證 假設存在一條哈密頓回路, a,f,g是2度頂點, 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點c出現(xiàn)3次, 矛盾.a b c f d e g 此外, 該圖滿足定理6.10的條件, 這表明此條件是必要、而不充分的.又, 該圖有哈密頓通路.例4 有7個人, A會講英語, B會講英語和漢語, C會講英語、意大利語和俄語, D會講日語和漢語, E會講德語和意大利語, F會講法語、日語和俄語, G會講法語和德語.問能否將他們沿圓桌安排就坐成一圈, 使得每個人都能與兩旁的人交談? 解 作無向圖, 每人是一個頂點, 2人之間有邊?他們有共同的語言.G F E D A B C ACEGFDBA是一條哈密頓回路,按此順序就坐即可.第二篇：離散數(shù)學
第三篇：淺談離散數(shù)學專題
第四篇：離散數(shù)學
第五篇：離散數(shù)學
點擊咨詢 