第一篇：離散數學習題集
離散數學習題集——圖論分冊 耿素云 北京大學出版社 定價：8元
數理邏輯(離散數學一分冊)王捍貧 北京大學出版社 定價：15元
集合論與圖論(離散數學二分冊)耿素云 北京大學出版社 定價：19元
代數結構與組合數學(離散數學三分冊)屈婉玲 北京大學出版社 定價：21元
離散數學習題集——數理邏輯與集合論分冊 耿素云 北京大學出版社 定價：11.5元
離散數學習題集——圖論分冊 耿素云 北京大學出版社 定價：8元
離散數學習題集——抽象代數分冊 張立昂 北京大學出版社 定價：8.8元
離散數學 左孝凌 劉永才 上海科學技術文獻出版社 定價：16元
離散數學(理論·分析·題解)左孝凌 劉永才 上海科學技術文獻出版社 定價：22元
第二篇：離散數學
離散數學課件作業
第一部分 集合論
第一章集合的基本概念和運算
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 = { 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 是正整數集合上的關系，由方程 x + 3y = 12 決定，即
R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求：
（1）R 的列元表達式；（2）給出 dom（R。R）。
答：根據方程式有：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 的函數；并對其中的 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 的函數，是滿射而不是單射；
（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 都是從實數集合Ｒ到Ｒ的函數，則ｆ。ｇ＝[C]
A．x+1；B．x-1；C．x；D．x2。
第三章 結構代數(群論初步)
3-1 給出集合及二元運算，闡述是否代數系統，何種代數系統 ？
（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，*＂不能構成代數系統。
（2）由二元運算的定義不難知道。在 S2 內是封閉的，所以，〈S2。〉構成代數
系統；然后看該代數系統的類型：該代數系統只是半群。
（3）很明顯，〈{0，1}，*〉構成代數系統；滿足結合律，為半群；1是幺元，為獨異
點；而 0 為零元；結論：僅為獨異點，而不是群。
3-2 在自然數集合上，下列那種運算是可結合的［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 為整數集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有
x。y=x + y，試問〈Z。〉能否構成群，為什麼 ？
答：由題已知，集合Z滿足封閉性；二元運算滿足結合律，依此集合Z為半群；有幺元為 －5，為獨異點.假設代數系統的幺元是集合中的元素 e,則一個方程來自于二元運算定義, 即e。x= e + x，一個方程來自該特殊元素的定義的性質,即e。x = x.由此而來的兩個方程聯立結果就有: e+x=x 成立.削去 x,e=0 的結果不是就有了嗎!；每個元素都有逆.求每個元素的逆元素,也要解聯方程,如同求幺元一樣的道理；結論是：代數系統〈 Z。〉構成群。
第二部分圖論方法
第四章 圖
4-1 10 個頂點的簡單圖 G 中有 4 個奇度頂點，問 G 的補圖中有幾個偶數度頂點 ？ 答：因為10階完全圖的每個頂點的度數都是n-1=9――為奇數。這樣一來，一個無向簡單圖 G 的某頂點的度數是奇數，其補圖的相應頂點必偶數，因為一個偶數與一個奇數之和才是奇數．所以，Ｇ的補圖中應有 10-4＝6 個奇數度頂點。
4-2 是非判斷：無向圖G中有10條邊,4個3度頂點,其余頂點度數全是2,共有 8 個頂點.[是]
4-3 填空補缺：1條邊的圖 G 中，所有頂點的度數之和為[2]
第五章樹
5-1握手定理的應用（指無向樹）
（1）在一棵樹中有 7 片樹葉，3 個 3 度頂點，其余都是 4 度頂點，問有(有1個4度頂點)個？
（2）一棵樹有兩個 4 度頂點，3 個 3 度頂點，其余都是樹葉，問有(9個1度頂點)片？
5-2 一棵樹中有 i 個頂點的度數為 i（i=2，…k），其余頂點都是樹葉(即一度頂點)，問樹葉多少片？設有x片,則 x=
答：假設有 x 片樹葉，根據握手定理和樹的頂點與邊數的關系，有關于樹葉的方程，解方程得到樹葉數 x = Σi（i—2）i + 2，（i = 2，3，……k）。
5-3 求最優 2 元樹：用 Huffman 算法求帶權為 1，2，3，5，7，8 的最優 2 元樹 T。試問：（1）T 的權 W（T）？（2）樹高幾層 ？
答：用 Huffman 算法，以 1，2，3，5，7，8 為權，最優 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(是非判斷題)二元正則樹有奇數個頂點。[是]
5-7 在某次通信中 a，b，c，d，e 出現的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。
1、最優二元樹 T；2.每個字母的碼字；
答：每個字母出現頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號
出現次數即為權，如右下圖).。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）離散數學很重要。[真命題]
（3）離散數學難學嗎 ？[真命題]
（4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。[復合命題]
（5）x + 5 大于 2。[真命題]
（6）今天沒有下雨，也沒有太陽，是陰天。[復合命題]
6-2 將下列命題符號化.（1）2 是偶素數。
（2）小李不是不聰明，而是不好學。
（3）明天考試英語或考數學。（兼容或）
（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：經一塹；q：長一智。命題’’只有經一塹，才能長一智’’符號化為[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 填空補缺題：設域為整數集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0）
7-3在謂詞邏輯中將下列命題符號化
（1）有的馬比所有的牛跑得慢。
（2）人固有一死。
答：（1）符號化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。
（2）與（1）相仿，要注意量詞、聯結詞間的搭配：
x（F（x）→y（G（y）→ H（x，y）））。
《附錄》習題符號集
? 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, ÷ 普通除法, ㏑ 自然對數, ㏒ 對數，﹃ 非，?量詞 ”所有”，”每個”，∨ 析取聯結詞，∧ 合取聯結詞，彐 量詞”存在”，”有的”。
2010年8月12號。
第三篇：淺談離散數學專題
淺談離散數學
【摘要】離散數學是一門理論性強,知識點多,概念抽象的基礎課程,學生學習起來普遍感到難度很高。本文從離散數學內容、學生學習興趣的激發、教學內容的安排、教學方式方法的使用等方面,探討了如何上好、學好離散數學課。
【關鍵詞】離散數學教學方法教師 學生
離散數學研究的是離散量，是計算機科學與技術系各專業的核心課程。課程內容具有知識點多、散、抽象等特點,加之學生不能認識到該課程的重要性,缺乏學習興趣和學習主動性,不僅忽視該課程的學習,甚至害怕這門課程。因此,創新教學方法,提高學生自主學習的積極性,對提高學生的能力、提升教學質量和水平具有重要的意義。通過一學期的學習和專研,我積累了少許經驗,總結了一些關于離散數學的教學方法，僅供大家參考。
一、離散數學的特點
本課程介紹計算機科學與技術系各專業所需要的離散數學基礎知識,主要有以下兩點特點：
1、知識點集中，概念和定理多：《離散數學》是建立在大量概念之上的邏輯推理學科，概念的理解是我們學習這門學科的核心。掌握、理解和運用這些概念和定理是學好這門課的關鍵。要特別注意概念之間的聯系，而描述這些聯系的則是定理和性質。
2、方法性強：離散數學的特點是抽象思維能力的要求較高。培養學生抽象思維能力、邏輯推理能力、縝密概括能力以及分析和解決實際問題能力的主干課程,對學習其他諸多課程,具有重要的指導作用。《離散數學》的證明題多，不同的題型會需要不同的證明方法，同一個題也可能有幾種方法，具有很強的方法性。
二、教學困難所在1、離散數學是一門理論性強,知識點多,概念抽象的基礎課程, 內容具有知
識點多、散、抽象等特點，學生學者困難；
2、學生不能認識到該課程的重要性,缺乏學習興趣和學習主動性,不僅忽視該課程的學習,甚至害怕這門課程。
3、離散數學課程在課堂教學難度、教學時間等方面的原因,很多學校都出現師生、學生之間的交流較少，從而使學生學習困難。
三、離散數學的教學方法引導學生提高對離散數學課程應用性的認識,激發學生學習的興趣和愛好,增強汲取知識的自主性
離散數學課程是一門基礎性課程,學習離散數學課程對學生今后的學習和工作,具有重要的作用,例如培養學生的抽象思維能力和縝密的邏輯推理能力,為學生今后處理離散信息,提高專業理論水平,從事計算機的實際工作提供必備的數學工具;通過學習,可以掌握數理邏輯,集合論,代數結構和圖論的基本概念和原理,并會運用離散數學的方法,分析和解決計算機理論和應用中的一些問題等。學習主動性是學生的力量之源,因此,引導學生充分認識學習離散數學課程的作用,能夠激發學生學習的愛好和熱情,提升學生學習的積極性和主動性,從而使學生學有成效。認真備課,合理準備教學內容和安排教學環節,優化教學方式方法
備好課是教學取得預期效果的前提和基礎,針對學生學習具體情況,合理準備教學內容和安排教學環節,使用恰當的教學方法,在教學中可以起到事半功倍的效果。
(1)合理地準備教學內容。根據課程教學大綱和離散數學課程定理定義比較多、知識比較抽象的特點以及學生的實際情況,準備深度和廣度適合學生特點的教學內容。
(2)合理地講解課程內容,重難點突出講解,注意輕重緩急。對于離散數學中比較重要、比較抽象的概念和定理,如邏輯的推理理論、關系的性質、群、圖等,認真分析,用多種方式和方法深入
講解,可以使用解析法、圖示法、矩陣法舉實例等多種方法講解。對于比較容易理解和掌握的內容,可以一筆帶過。這樣,學生對所學內容就會有重點地學習,主次分明,學生不僅可以對所學內容掌握透徹,更能熟練把握離散數學中分析問題和解決問題的思路、方式和方法。
(3)啟發式教學和教師講授相結合。很多人認為,大學教學課時緊,內容多,關鍵靠學生自主學習,我卻認為并不完全是這樣的。如果教師不顧學生的理解情況,只顧在講臺上講授知識,課堂氛圍會很沉悶,很多同學不能專注于該門課程的學習,經常走神,教學很難達到預期的效果。因此,有針對性地提問和展開討論,不僅能夠培養學生的思考能力,更能調動學生學習的興趣和積極性,從而使教學達到最佳效果。也可以引進有趣生動的例子說明概念，既活躍課堂，又鞏固了學生的記憶。3 合理布置作業,認真批改作業,有針對性地安排習題課和課后答疑
學數學就要做數學，《離散數學》的學習也不例外。學習數學不僅限于學習數學知識，更重要的還在于學習數學思維方法。為了強化學生能力的訓練,培養學生的抽象思維能力、邏輯推理能力、實際問題的解決能力等,在保證作業數量的同時,更要提高布置作業的質量,增加典型簡答題、討論題、推理題、實際應用題等習題在作業中的分量,使學生在掌握各種基本知識和基本技能的同時,提高自身的綜合能力。
認真檢查和批改作業,是督促學生學習的主要途徑,也是教師了解學生理解和掌握所學課程情況的主渠道。必要時,教師可以批改一部分作業,其他作業讓同學們之間互相檢查和批改,不僅可以督促學生學習,更能讓學生在批改其他同學作業時逐步認識到自身的缺陷和不足,以備今后更有針對性地學習。
教師在作業檢查和批改過程中發現的主要問題和疑難以及學生提出的有代表性的問題,有必要安排習題課進行講解,幫助學生對解決疑難,加深對所知識的理解。對于學生比較爭論的問題,可以展開討論,鼓勵學生大膽發言,培養學生探索未知的精神和創造性解決實際問題的能力。
四、總結
從此上看，上好離散數學課,關鍵是根據學生具體實際,有針
對性地安排教學內容,合理使用教學方式方法,最大限度地激發學生的學習興趣,充分發揮教師的主導作用和學生的主體作用,達到教與學和諧。
參考文獻
[1] 屈婉玲,耿素云,張立昂.離散數學[M].北京:高等教育出版社.2008.[2] 黃巍,金國祥.”離散數學”課程教學改革的探討[J].中國電力教育,2009(8):82-83.[3] 周小燕,胡豐華.對提高離散數學教學質量的探討[J].浙江科技學院學報,2007,19(2):156-158.[4] 龍浩,張佳佳.怎樣教好《離散數學》課[J].貴陽學院學報,2007,2(1):53-57.[5] 廖仲春.離散數學的教學探討[J].湖南工業職業技術學院學報,2008,8(5)http://
第四篇：離散數學
離散數學試題（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上的自反和傳遞關系，則對任意的正整數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。另一方面，對任意的
由數學歸納法知，對任意的正整數n，Rn＝R。
n
六、（15分）設函數f：R×R?R×R，f定義為：f(
(1)證明f是單射。(2)證明f是滿射。(3)求逆函數f。
(4)求復合函數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不是對稱的；
經過計算可得 ?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。離散數學試題（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分）在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業中都會獲得成功。存在著身體健康的科學家。所以，存在著事業獲得成功的人或事業半途而廢的人。
Q(x)：x是勤奮的；x是科學家；C(x)：解：論域：所有人的集合。H(x)：x是身體健康的；S(x)：x是事業獲得成功的人；F(x)：x是事業半途而廢的人；則推理化形式為：
?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的函數？
(2)當n、m滿足什么條件時，存在單射，且有多少個不同的單射？(3)當n、m滿足什么條件時，存在雙射，且有多少個不同的雙射？
解
(1)由于對X中每個元素可以取Y中任一元素與其對應，每個元素有n種取法，所以不同的函數共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。
第五篇：離散數學
第一章
數學語言與證明方法
例1 設E={ x | x是北京某大學學生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走讀生}, C= { x | x是數學系學生}，D= { x | x是喜歡聽音樂的學生}.試描述下列各集合中學生的特征:
(A?D)? ~ C={ x | x是北京人或喜歡聽音樂,但不是數學系學生} ~ 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 證明
是無理數
證
假設
是有理數, 存在正整數n,m, 使得
=m/n,不妨設m/n為既約分數.于是m=n, m2=2n2, m2是偶數, 從而m是偶數.設m=2k, 得(2k)2=2n2, n2=2k2, 這又得到n也 是偶數, 與m/n為既約分數矛盾.例6 對于每個正整數n, 存在n個連續的正合數.證
令x=(n+1)!
則 x+2, x+3,…, x+n+1是n個連續的正合數:
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的整數均可表成素數的乘積 證 歸納基礎.對于2, 結論顯然成立.歸納步驟.假設對所有的k(2?k?n)結論成立, 要證結論 對n+1也成立.若n+1是素數, 則結論成立;否則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是素數.(2)2或3是素數.(3)4或6是素數.(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是偶數.0(3)2+2＝4 當且僅當 太陽從東方升起.(4)2+2＝5 當且僅當 美國位于非洲.(5)f(x)在x0處可導的充要條件是它在 x0處連續.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(續)求?(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 在自然推理系統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是偶數 4是個體常項, “是偶數”是謂詞常項, 符號化為: 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) 是無理數, 而 是有理數(2)如果2>3，則3<4 解 (1)設F(x): x是無理數, G(x): x是有理數 符號化為 真值為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(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的兩次出現均為約束出現 y的第一次出現為自由出現, 第二次出現為約束出現 z為自由出現.例7 公式 ?x(F(x)??xG(x))?x的轄域:(F(x)??xG(x))，指導變元為x ?x的轄域:G(x)，指導變元為x x的兩次出現均為約束出現.但是, 第一次出現的x是?x中 的x, 第二次出現的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是整數，:x是有理數, 取解釋I2, D2=R，:x是整數，:x是自然數, 非永真式的可滿足式(2)?(?xF(x))?(?xF(x)) 這是 ?p?p 的代換實例, ?p?p是重言式，永真式(3)?(?xF(x)??yG(y))? ?yG(y)這是?(p?q)?q的代換實例, ?(p?q)?q是矛盾式 矛盾式 例1 消去公式中既約束出現、又自由出現的個體變項 真命題 假命題 (1)?xF(x,y,z)? ?yG(x,y,z)? ?uF(u,y,z)? ?yG(x,y,z) 換名規則 ? ?uF(u,y,z)? ?vG(x,v,z) 換名規則 或者 ? ?xF(x,u,z)? ?yG(x,y,z) 代替規則 ? ?xF(x,u,z)? ?yG(v,y,z) 代替規則(2)?x(F(x,y)? ?yG(x,y,z))? ?x(F(x,y)? ?tG(x,t,z)) 換名規則 或者 ? ?x(F(x,t)? ?yG(x,y,z)) 代替規則 例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是奇數，: 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) 換名規則 ? ?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的所有劃分, 然后根據劃分寫出 對應的等價關系.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>} 根據有序對 例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 判斷下面函數是否為單射, 滿射, 雙射的, 為什么?（1）f : R→R, f(x)= ?x2+2x?1（2）f : Z+→R, f(x)=lnx, Z+為正整數集（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+為正實數集.解(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 是滿射、單射、雙射的, 因為它是單調函數并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有極小值f(1)=2.該函數既不是單射的也不是滿射的.例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 … 則這種對應所表示的函數是： 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 存在反函數, 求出它們的反函數.解 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不存在反函數；g : R→R的反函數是 g?1: R→R, g?1(x)=x?2 第6章 圖 例1 下述2組數能成為無向圖的度數列嗎?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇數個奇數.(2)能 例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數均小 于等于2, 問G至少有多少個頂點? 解 設G有n個頂點.由握手定理，4?3+2?(n-4)?2?10 解得 n?8 例3 已知5階有向圖的度數列和出度列分別為3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 證明不存在具有奇數個面且每個面都具有奇數條棱的 多面體.證 用反證法.假設存在這樣的多面體, 作無向圖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條邊的所有非同構的無向簡單圖 解 總度數為6, 分配給4個頂點, 最大度為3, 且奇度頂點數 為偶數, 有下述3個度數列:(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為度數列的非同構的無向簡單圖 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個課外活動小組:數學組, 計算機組和生物組.有趙,錢,孫,李,周5名學生, 問分別在下述3種情況下, 能否選出3人各任一個組的組長?(1)趙, 錢為數學組成員, 趙,孫,李為計算機組成員, 孫,李,周為生物組成員.(2)趙為數學組成員, 錢,孫,李為計算機組成員, 錢,孫,李,周為生物組成員.(3)趙為數學組和計算機組成員, 錢,孫,李,周為生物組成員.解 數 計 生 數 計 生 趙 錢 孫 李 周 趙 錢 孫 李 周 (1(數 計 生 趙 錢 孫 李 周 (3(1),(2)有多種方案,(3)不可能 例2 證明下述各圖不是哈密頓圖: (a(b(c) (c)中存在哈密頓通路 例3 證明右圖不是哈密頓圖 證 假設存在一條哈密頓回路, a,f,g是2度頂點, 邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點c出現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是一條哈密頓回路,按此順序就坐即可.
點擊咨詢 