山東廣播電視大學計算機與通訊學院
2023年6月
離散數學是**電大計算機應用專業資訊管理方向開設的必修統設課。該課程使用新的教學大綱，在原有離散數學課程的基礎上削減了教學內容（主要是群與環、格與布林代數這兩章及圖論的後三節內容），使所學的知識達到必需、夠用，更加適合大學專科層次的教育。目前該課程沒有新教材，借用原教材。
使用的教材為**電大出版的《離散數學》（劉敘華等編）和《離散數學學習指導書》（虞恩蔚等編）。
離散數學主要研究離散量結構及相互關係，使學生得到良好的數學訓練，提高學生抽象思維和邏輯推理能力，為從事計算機的應用提供必要的描述工具和理論基礎。其先修課程為：高等數學、線性代數；後續課程為：
資料結構、資料庫、作業系統、計算機網路等。
課程的主要內容
本課程分為三部分：集合論、數理邏輯和圖論。
1、 集合論部分（集合的基本概念和運算、關係及其性質）；
2、 數理邏輯部分（命題邏輯、謂詞邏輯）；
3、 圖論部分（圖的基本概念、樹及其性質）。
學習建議
離散數學是理論性較強的學科，學習離散數學的關鍵是對離散數學（集合論、數理邏輯和圖論）有關基本概念的準確掌握，對基本原理及基本運算的運用，並要多做練習。
一、各章複習示例與解析
第一章集合
例1，將「大於3而小於或等於7的整數集合」用集合表示出來。
[解析]
集合的表示方法一般有兩種，一種稱為列舉法，一種稱為描述法。
列舉法將集合的元素按任意順序逐一列在花括號內，並用逗號分開。「大於3而小於或等於7的整數」有4、5、6、7，用列舉法表示為；
描述法是利用集合中的元素滿足某種條件或性質用文字或符號在花括號內豎線後面表示出來。上例用描述法表示為，其中z為整數集合。
答：或。
例2，判定下列各題的正確與錯誤：
（1）a}；
（2）；
（3）；
（4）；
（5）}；
（6），1，3，4}，3，4，1}；
（7）}；
（8）如果ab=b，則a=e。
[解析]
此題涉及到集合中子集的概念，集合的包含關係，空集與集合的關係。解題時要注意區分兩個集合之間的關係以及集合中元素與集合之間的關係的不同。
集合之間的關係分為包含關係（子集、真子集）、相等關係、冪集等，判斷時要準確理解這些概念，才能正確地運用這些知識。
集合與它的元素之間的關係有兩種：乙個元素a屬於乙個集合a，記為aa；乙個元素a不屬於乙個集合a，記為aa。要注意符號的記法（）與集合包含符號記法（，）的不同。
答：正確的是（2）、（4）、（5）、（7）；其餘的都是錯誤的。
例3，設a，b是兩個集合，a=，b=，請計算（a）–（b）。
[解析]
集合的概念一般在中學階段已經學過，這裡只多了乙個冪集概念，重點對冪集加以掌握，一是掌握冪集的構成，由集合a的所有子集組成的集合，稱為a的冪集，記作（a）或2a；一是掌握冪集元數為2n，n為集合a的元數。
集合的基本運算有交、並、差、補。
答：（a）=，，，，，，}
（b）=，，}
於是（a）–（b）=，，，}
例4，試證明（a~b）（~ab）=（ab）（~a~b）
[解析]
證明集合恒等式要熟練運用教材15頁集合的10個基本運算。一般來說，欲證p=q，即證pq並且qp，也就是要證明，對於任意的x，有下式成立。
xp x q 和 xq x p
證明集合恒等式的另一種方法是利用已知的恒等式來代入。本題就是用的這個方法。
通過對集合恒等式證明的練習，既可以加深對集合性質的理解與掌握；又可以為第三章命題邏輯中公式的基本等價式的應用打下良好的基礎。實際上，本章做題是一種基本功訓練，尤其要求學生重視吸收律和重要等價式在a–b=a~b證明中的特殊作用。
證明：第二章關係與對映
例1，設集合a=，試求a上的模2同餘關係r的關係矩陣和關係圖。
[解析]
關係的概念是第二章的基礎，又是第一章集合概念的應用。因此應該真正理解並熟練掌握二元關係的概念及關係矩陣、關係圖表示。
這道題要把r表示出來，先要清楚「模2同餘關係」的概念，如果x，y模2同餘，就是指x，y除以2的餘數相同。於是，
r= 求出了關係r的表示式，就可以進一步求出關係矩陣和關係圖了。
答：r的關係矩陣為：
r的關係圖為：
例2，設集合a=，a上的關係r=，試判斷r具有哪幾種性質？
[解析]
關係的性質既是對關係概念的加深理解與掌握，又是關係的閉包、等價關係、半序關係的基礎。對於四種性質（自反性、對稱性、反對稱性、傳遞性）的判定，可以依據其定義，也可以依據教材中49頁上總結的關於關係矩陣和關係圖的規律。
對於傳遞性的判定，難度稍大一點，這裡要提及兩點：一是不破壞傳遞性定義，可認為具有傳遞性。如空關係具有傳遞性，同時空關係具有對稱性與反對稱性，但是不具有自反性。
另一點是介紹一種判定傳遞性的「跟蹤法」，即若（a1，a2）r，（a2，a3）r，，（ai-1，ai）r，則（a1，ai）r；如若（a，b）r，（b，a）r，則有（a，a）r，且（b，b）r。
先寫出r的關係式，r=，並在此基礎上判斷r是否具有四種關係的性質。
答：r只具有關係的對稱性。
例3，設集合，判定下列關係，哪些是自反的，對稱的，反對稱的和傳遞的：
解：均不是自反的；r4是對稱的；r1，r2，r3，r4，r5是反對稱的；r1，r2，r3，r4，r5是傳遞的。
例4，設集合a=，r1，r2都是a上的二元關係，r1=，r2=，試求r1和r2的自反閉包，對稱閉包和傳遞閉包。
[解析]
在理解掌握關係閉包概念的基礎上，主要掌握閉包的求法。關鍵是熟記三個定理的結論：定理2，自反閉包；定理3，對稱閉包；定理4的推論，傳遞閉包。
答：r（r1）= r1ia=
s（r1）= r1 r1-1 =
r12 =
r13 =
t（r1）= r1 r12 r13 =
空關係r2的自反閉包，對稱閉包和傳遞閉包均為。
例5，設集合，a上的二元關係r為：
（１）寫出r的關係矩陣，畫出r的關係圖；
（２）證明r是a上的半序關係，畫出其哈斯圖；
（３）若，且，求b的最大元，最小元，極大元，極小元，最小上界和最大下界。
[解析]
理解與掌握半序關係與半序集概念的關鍵是哈斯圖。哈斯圖畫法掌握了，對於確定任一子集的最大（小）元，極大（小）元也就容易了。這裡要注意，最大（小）元與極大（小）元只能在子集內確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小於子集中的任一元素，可以與某一元素相等，最大下界也同樣。
解：（1）r的關係矩陣為
r的關係圖為
（2）因為r是自反的，反對稱的和傳遞的，所以r是a上的半序關係。（a，r）為半序集，（a，r）的哈斯圖如下：
（3）當b=，b的極大元為2，4；極小元為2，5；b無最大元與最小元；b也無上界與下界，更無最小上界與最大下界。
例6，下列對映中哪些是滿射，哪些是單射，哪些是雙射？
（1）（2）（3）（4）[解析]
對映的概念與對映種類的判定：對映的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助於關係圖，而實數集的子集上的對映也可以利用直角座標系表示進行，尤其是對各種初等函式。
答：（1），（3）是非單非滿射；（2）是滿射；（4）是雙射。
第三章命題邏輯
例1，試證明公式為恆真公式。
[解析]
判定公式的恆真性，包括判定公式是恆真的或是恆假的。具體方法有兩種：
一是真值表法，對於任給乙個公式，主要列出該公式的真值表，觀察真值表的最後一列是否全為1（或全為0），就可以判定該公式是否恆真（或恆假），若不全為0，則為可滿足的。
二是推導法，即利用基本等價式推導出結果為1，或者利用恆真（恆假）判定定理：公式g是恆真的（恆假的）當且僅當等價於它的合取正規化（析取正規化）中，每個子句（短語）均至少包含乙個原子及其否定。
這裡要求的析取正規化中所含有的每個短語不是極小項，一定要與求主析取正規化相區別，對於合取正規化也同樣。
證明：證法一：真值表法，見《離散數學學習指導書》60頁例6（4）的解答。
證法二 ：
g=（（pq）（qr））（pr）
=（pq）（qr）pr
=（（（pq）（pr）（qq）（qr））p）r
=（（pqp）（prp）（qrp））r
=（1（qrp））r
=qrpr
=1故g為恆真公式。
例2，求的主析取正規化與主合取正規化。
[解析]
求正規化，包括求析取正規化、合取正規化、主析取正規化和主合取正規化。關鍵有兩點：一是準確理解掌握定義；另一是巧妙使用基本等價式中的分配律、同一律和互補律，結果的前一步適當使用等冪律，使相同的短語（或子句）只保留乙個。
離散數學期末複習指導
2 3 4 5 6 1，3，4 3，4，1 7 8 如果ab b，則a e。解析 此題涉及到集合中子集的概念，集合的包含關係，空集與集合的關係。解題時要注意區分兩個集合之間的關係以及集合中元素與集合之間的關係的不同。集合之間的關係分為包含關係 子集 真子集 相等關係 冪集等，判斷時要準確理解這些概念...
離散數學期末複習指導
瀏水浮芸qq632069015 山東廣播電視大學計算機與通訊學院 2008年6月 離散數學是 電大計算機應用專業資訊管理方向開設的必修統設課。該課程使用新的教學大綱，在原有離散數學課程的基礎上削減了教學內容 主要是群與環 格與布林代數這兩章及圖論的後三節內容 使所學的知識達到必需 夠用，更加適合大學...
離散數學期末複習指導 遠端
浙江電大機電系基礎部 離散數學是浙江電大計算機應用專業資訊管理方向開設的必修統設課。該課程使用新的教學大綱，在原有離散數學課程的基礎上削減了教學內容 主要是群與環 格與布林代數這兩章及圖論的後三節內容 使所學的知識達到必需 夠用，更加適合大學專科層次的教育。目前該課程沒有新教材，借用原教材。使用的教...