離散數(shù)學期末復習指導（?？疲?/h1>

上傳人：窩***

認證信息

認證類型：個人認證

認證主體：沃**（實名認證）

IP屬地：安徽

IP屬地：安徽 上傳時間：2020-12-24 格式：DOC 頁數(shù)：16 大小：239.03KB 積分：20 舉報 版權申訴

1、離散數(shù)學期末復習指導（?？疲┲醒腚姶罄砉げ坑嬎銠C教研室 離散數(shù)學是中央電大計算機應用專業(yè)信息管理方向開設的必修統(tǒng)設課。該課程使用新的教學大綱，在原有離散數(shù)學課程的基礎上削減了教學內(nèi)容（主要是群與環(huán)、格與布爾代數(shù)這兩章及圖論的后三節(jié)內(nèi)容），使所學的知識達到必需、夠用，更加適合大學?？茖哟蔚慕逃?。目前該課程沒有新教材，借用原教材。使用的教材為中央電大出版的離散數(shù)學（劉敘華等編）和離散數(shù)學學習指導書（虞恩蔚等編）。離散數(shù)學主要研究離散量結構及相互關系，使學生得到良好的數(shù)學訓練，提高學生抽象思維和邏輯推理能力，為從事計算機的應用提供必要的描述工具和理論基礎。其先修課程為：高等數(shù)學、線性代數(shù)；后續(xù)課程為

2、：數(shù)據(jù)結構、數(shù)據(jù)庫、操作系統(tǒng)、計算機網(wǎng)絡等。 課程的主要內(nèi)容本課程分為三部分：集合論、數(shù)理邏輯和圖論。1、 集合論部分（集合的基本概念和運算、關系及其性質）；2、 數(shù)理邏輯部分（命題邏輯、謂詞邏輯）；3、 圖論部分（圖的基本概念、樹及其性質）。 學習建議離散數(shù)學是理論性較強的學科，學習離散數(shù)學的關鍵是對離散數(shù)學（集合論、數(shù)理邏輯和圖論）有關基本概念的準確掌握，對基本原理及基本運算的運用，并要多做練習。一、各章復習示例與解析第一章 集 合例1，將“大于3而小于或等于7的整數(shù)集合”用集合表示出來。解析 集合的表示方法一般有兩種，一種稱為列舉法，一種稱為描述法。 列舉法將集合的元素按任意順序逐一列在

3、花括號內(nèi)，并用逗號分開?！按笥?而小于或等于7的整數(shù)”有4、5、6、7，用列舉法表示為4、5、6、7； 描述法是利用集合中的元素滿足某種條件或性質用文字或符號在花括號內(nèi)豎線后面表示出來。上例用描述法表示為x| xZ并且3x7，其中Z為整數(shù)集合。答：4、5、6、7或x| xZ并且35。 在解釋I下求公式$x（F（x）G（x）的真值。5、 化簡下式：（ABC）（AB）-（A（B-C）A）6、 已知A=1，2，3，4，5，B=1，2，3，R是A到B的二元關系，并且R=（x，y）|xA且yB且2 x+y 4，畫出R的關系圖，并寫出關系矩陣。7、 畫出下面偏序集（A，）的哈斯圖，并指出集合A的最小元、最

4、大元、極大元和極小元。其中A=a，b，c，d，e，=（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）IA。8、 求命題公式的析取范式與合取范式。9、給定解釋I如下： 定義域D=2，3； f（2） f（3） F（2，2） F（2，3） F（3，2） F（3，3） 3 2 0 0 1 1求。10、求下面帶權圖的最優(yōu)支撐樹，并計算它的權。 4 7 8 20 12 8 9 10 15（四）證明題1、證明等價式。 2、 利用形式演繹法證明：蘊涵Q。3、 A，B，C為任意的集合，證明：4、 利用一階邏輯的基本等價式，證明： 練習題參考解答（一）填空題1、列舉；描述；2、5

5、；5，2，5，3，5，2，3，5；83、s1=（a，1），（b，1）；s2=（a，2），（b，2）；s3=（a，1），（b，2）；s4=（a，2），（b，1）4、（1，0，1）； （1，1，1）； （1，0，0）5、 28； 76、5；f，5；1，3，47、笛卡爾積（或直乘積）；（x，y）|xA且yB；二元關系8、并且（或合?。换蛘撸ɑ蛭鋈。?；蘊涵9、（L（a，a）L（a，b）L（a，c）（L（b，a）L（b，b）L（b，c）（L（c，a）L（c，b）L（c，c）10、點；連接某些不同點對的邊；一對不同點之間最多有一條邊（二）選擇題（選擇一個正確答案的代號，填入括號中）1、C 2、A 3、C

6、 4、A 5、C6、A 7、B 8、D 9、C 10、A（三）計算題1、解：（1） （2）=（1，2），（3，4） =（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4） =（1，1），（3，1），（3，2），（4，3） =（2，1），（4，3） 2、解： R1和R2的關系圖如下： R1的關系圖 R2的關系圖由關系圖可知，R1是等價關系。R1不同的等價類有兩個，即a，b和c，d。由于R2不是自反的，所以R2不是等價關系。3、解 ：（1） 真值表P QP PP （PP）Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）為可滿足。（2

7、） 真值表P QPQ （PQ） （PQ）Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）為恒假。 （3） 真值表P Q RPQ QR PR （PQ）（QR）（PR）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0 11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1 因此公式（3）為恒真。 4、解： $x（F（x）G（x） （F（-2）G（-2）（F（3）G（3）（F（6）G（6） （10）（10）（01） 1 5、解： （ABC）（AB）-（A（B-C）

8、A）=（AB）- A （利用兩次吸收律） =（AB） A =（A A）（B A） = f（B A）= B- A 6、解： R=（1，1），（1，2），（1，3），（2，1），（2，2），（3，1） 1 1 2 2 3 34 5 R的關系圖為關系矩陣7、解： （A，）的哈斯圖為： e b c d a a為A的極小元，也是最小元； e為A的極大元，也是最大元。 8、解： （PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）上面結果為合取范式。利用對分配得：（PQ）（PQ） （PP）（PQ）（QP）（QQ） （PQ）（QP）上面結果為析取范式。9、解： x

9、y（F（x，y）F（f（x），f（y） x（F（x，2）F（f（x），f（2）（F（x，3）F（f（x），f（3） （F（2，2）F（f（2），f（2）（F（2，3）F（f（2），f（3）（F（3，2）F（f（3），f（2）（F（3，3）F（f（3），f（3） （01）（01）（10）（10） 0 10、解： 帶權圖的最優(yōu)支撐樹如下，權和為28。 4 7 8 9（四）證明題1、 證明： 2、證明： （1） 規(guī)則P（2） 規(guī)則P（3） 規(guī)則Q，根據(jù)（1）、（2）和基本蘊涵式（12）（4） 規(guī)則P（5） 規(guī)則Q，根據(jù)（3）、（4）和基本蘊涵式（11） （6） 規(guī)則P（7） 規(guī)則Q，根據(jù)（5）、（6）和基本蘊涵式（12）（8） 規(guī)則P（9） 規(guī)則Q，根據(jù)（7）、（8）和基本