1、離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)（專(zhuān)科）中央電大理工部計(jì)算機(jī)教研室 離散數(shù)學(xué)是中央電大計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)信息管理方向開(kāi)設(shè)的必修統(tǒng)設(shè)課。該課程使用新的教學(xué)大綱，在原有離散數(shù)學(xué)課程的基礎(chǔ)上削減了教學(xué)內(nèi)容（主要是群與環(huán)、格與布爾代數(shù)這兩章及圖論的后三節(jié)內(nèi)容），使所學(xué)的知識(shí)達(dá)到必需、夠用，更加適合大學(xué)專(zhuān)科層次的教育。目前該課程沒(méi)有新教材，借用原教材。使用的教材為中央電大出版的離散數(shù)學(xué)（劉敘華等編）和離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書(shū)（虞恩蔚等編）。離散數(shù)學(xué)主要研究離散量結(jié)構(gòu)及相互關(guān)系，使學(xué)生得到良好的數(shù)學(xué)訓(xùn)練，提高學(xué)生抽象思維和邏輯推理能力，為從事計(jì)算機(jī)的應(yīng)用提供必要的描述工具和理論基礎(chǔ)。其先修課程為：高等數(shù)學(xué)、線(xiàn)性代數(shù)；后續(xù)課程為

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

3、花括號(hào)內(nèi)，并用逗號(hào)分開(kāi)。“大于3而小于或等于7的整數(shù)”有4、5、6、7，用列舉法表示為4、5、6、7； 描述法是利用集合中的元素滿(mǎn)足某種條件或性質(zhì)用文字或符號(hào)在花括號(hào)內(nèi)豎線(xiàn)后面表示出來(lái)。上例用描述法表示為x| xÎZ并且3<x£7，其中Z為整數(shù)集合。答：4、5、6、7或x| xÎZ并且3<x£7。例2，判定下列各題的正確與錯(cuò)誤： （1）aÎa； （2）aÍ a，b，c ； （3）ÆÎ a，b，c ； （4）ÆÍ a，b，c ； （5）a，bÍa，b，c， a，b，c ； （

4、6）a，1，3，4Ìa，3，4，1； （7）a，bÍa，b， a，b ； （8）如果AÇB=B，則A=E。解析 此題涉及到集合中子集的概念，集合的包含關(guān)系，空集與集合的關(guān)系。解題時(shí)要注意區(qū)分兩個(gè)集合之間的關(guān)系以及集合中元素與集合之間的關(guān)系的不同。 集合之間的關(guān)系分為包含關(guān)系（子集、真子集）、相等關(guān)系、冪集等，判斷時(shí)要準(zhǔn)確理解這些概念，才能正確地運(yùn)用這些知識(shí)。 集合與它的元素之間的關(guān)系有兩種：一個(gè)元素a屬于一個(gè)集合A，記為aÎA；一個(gè)元素A不屬于一個(gè)集合A，記為aÏA。要注意符號(hào)的記法（Î）與集合包含符號(hào)記法（Í，Ì

5、）的不同。答：正確的是（2）、（4）、（5）、（7）；其余的都是錯(cuò)誤的。例3，設(shè)A，B是兩個(gè)集合，A=1，2，3，B=1，2，請(qǐng)計(jì)算r（A）r（B）。解析集合的概念一般在中學(xué)階段已經(jīng)學(xué)過(guò)，這里只多了一個(gè)冪集概念，重點(diǎn)對(duì)冪集加以掌握，一是掌握冪集的構(gòu)成，由集合A的所有子集組成的集合，稱(chēng)為A的冪集，記作r（A）或2A；一是掌握冪集元數(shù)為2n，n為集合A的元數(shù)。 集合的基本運(yùn)算有交、并、差、補(bǔ)。答：r（A）=Æ，1，2，3，1，2，1，3，2，3，1，2，3r（B）=Æ，1，2，1，2于是r（A）r（B）=3，1，3，2，3，1，2，3例4，試證明（AÈB）Ç

6、（AÈB）=（AÇB）È（AÇB）解析 證明集合恒等式要熟練運(yùn)用教材15頁(yè)集合的10個(gè)基本運(yùn)算。一般來(lái)說(shuō)，欲證P=Q，即證PÍQ并且QÍP，也就是要證明，對(duì)于任意的x，有下式成立。xÎPÞ x ÎQ 和 xÎQÞ x ÎP證明集合恒等式的另一種方法是利用已知的恒等式來(lái)代入。本題就是用的這個(gè)方法。通過(guò)對(duì)集合恒等式證明的練習(xí)，既可以加深對(duì)集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價(jià)式的應(yīng)用打下良好的基礎(chǔ)。實(shí)際上，本章做題是一種基本功訓(xùn)練，尤其要求學(xué)生重視吸收律和重

7、要等價(jià)式在A(yíng)B=AÇB證明中的特殊作用。證明： 第二章 關(guān)系與映射例1，設(shè)集合A=1，2，3，4，5，試求A上的模2同余關(guān)系R的關(guān)系矩陣和關(guān)系圖。解析關(guān)系的概念是第二章的基礎(chǔ)，又是第一章集合概念的應(yīng)用。因此應(yīng)該真正理解并熟練掌握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示。 這道題要把R表示出來(lái)，先要清楚“模2同余關(guān)系”的概念，如果x，y模2同余，就是指x，y除以2的余數(shù)相同。于是，R=（1，1），（1，3），（1，5），（2，2），（2，4），（3，1），（3，3），（3，5），（4，2），（4，4），（5，1），（5，3），（5，5） 求出了關(guān)系R的表達(dá)式，就可以進(jìn)一步求出關(guān)系矩陣和關(guān)系

8、圖了。答：R的關(guān)系矩陣為：R的關(guān)系圖為：例2，設(shè)集合A=1，2，3，¼，10，A上的關(guān)系R=（x，y）|x，yÎA，且x+y=10，試判斷R具有哪幾種性質(zhì)？解析 關(guān)系的性質(zhì)既是對(duì)關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、半序關(guān)系的基礎(chǔ)。對(duì)于四種性質(zhì)（自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性、傳遞性）的判定，可以依據(jù)其定義，也可以依據(jù)教材中49頁(yè)上總結(jié)的關(guān)于關(guān)系矩陣和關(guān)系圖的規(guī)律。對(duì)于傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時(shí)空關(guān)系具有對(duì)稱(chēng)性與反對(duì)稱(chēng)性，但是不具有自反性。另一點(diǎn)是介紹一種判定傳遞性的“跟蹤法”，即若（

9、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。 先寫(xiě)出R的關(guān)系式，R=（1，9），（2，8），（3，7），（4，6），（5，5），（6，4），（7，3），（8，2），（9，1），并在此基礎(chǔ)上判斷R是否具有四種關(guān)系的性質(zhì)。答：R只具有關(guān)系的對(duì)稱(chēng)性。例3，設(shè)集合，判定下列關(guān)系，哪些是自反的，對(duì)稱(chēng)的，反對(duì)稱(chēng)的和傳遞的：解：均不是自反的；R4是對(duì)稱(chēng)的；R1，R2，R3，R4，R5是反對(duì)稱(chēng)的；R1，R

10、2，R3，R4，R5是傳遞的。例4，設(shè)集合A=a，b，c，d，R1，R2都是A上的二元關(guān)系，R1=（a，b），（b，c），（c，a），R2=Æ，試求R1和R2的自反閉包，對(duì)稱(chēng)閉包和傳遞閉包。解析在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)論：定理2，自反閉包；定理3，對(duì)稱(chēng)閉包；定理4的推論，傳遞閉包。答：r（R1）= R1ÈIA=（a，b），（b，c），（c，a），（a，a），（b，b），（c，c） s（R1）= R1È R1-1 =（a，b），（b，c），（c，a），（b，a），（c，b），（a，c） R12 =（a，c），（b，a

11、），（c，b）R13 =（a，a），（b，b），（c，c）t（R1）= R1È R12È R13 =（a，b），（b，c），（c，a），（a，c），（b，a），（c，b），（a，a），（b，b），（c，c） 空關(guān)系R2的自反閉包，對(duì)稱(chēng)閉包和傳遞閉包均為Æ。例5，設(shè)集合，A上的二元關(guān)系R為： （）寫(xiě)出R的關(guān)系矩陣，畫(huà)出R的關(guān)系圖；（）證明R是A上的半序關(guān)系，畫(huà)出其哈斯圖；（）若，且，求B的最大元，最小元，極大元，極小元，最小上界和最大下界。解析理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫(huà)法掌握了，對(duì)于確定任一子集的最大（小）元，極大（小）元也就容易了。這里

12、要注意，最大（小）元與極大（小）元只能在子集內(nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。解：（1）R的關(guān)系矩陣為 R的關(guān)系圖為 （2）因?yàn)镽是自反的，反對(duì)稱(chēng)的和傳遞的，所以R是A上的半序關(guān)系。（A，R）為半序集，（A，R）的哈斯圖如下： 4· 1 3· 2 5 （3）當(dāng)B=2，3，4，5，B的極大元為2，4；極小元為2，5；B無(wú)最大元與最小元；B也無(wú)上界與下界，更無(wú)最小上界與最大下界。例6，下列映射中哪些是滿(mǎn)射，哪些是單射，哪些是雙射？ （1） （2） （3） （4）解析

13、映射的概念與映射種類(lèi)的判定：映射的種類(lèi)主要指單射、滿(mǎn)射、雙射與非單非滿(mǎn)射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函數(shù)。答：（1），（3）是非單非滿(mǎn)射；（2）是滿(mǎn)射；（4）是雙射。第三章命題邏輯例1，試證明公式為恒真公式。解析判定公式的恒真性，包括判定公式是恒真的或是恒假的。具體方法有兩種：一是真值表法，對(duì)于任給一個(gè)公式，主要列出該公式的真值表，觀(guān)察真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿(mǎn)足的。二是推導(dǎo)法，即利用基本等價(jià)式推導(dǎo)出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G是

14、恒真的（恒假的）當(dāng)且僅當(dāng)?shù)葍r(jià)于它的合取范式（析取范式）中，每個(gè)子句（短語(yǔ)）均至少包含一個(gè)原子及其否定。這里要求的析取范式中所含有的每個(gè)短語(yǔ)不是極小項(xiàng)，一定要與求主析取范式相區(qū)別，對(duì)于合取范式也同樣。證明：證法一：真值表法，見(jiàn)離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書(shū)60頁(yè)例6（4）的解答。證法二 ： G=Ø（ØPÚQ）Ù（ØQÚR）Ú（ØPÚR） =（PÙØQ）Ú（QÙØR）ÚØPÚR =（PÚQ）Ù（PÚØR

15、）Ù（ØQÚQ）Ù（ØQÚØR）ÚØP）ÚR =（PÚQÚØP）Ù（PÚØRÚØP）Ù（ØQÚØRÚØP）ÚR =（1Ù（ØQÚØRÚØP）ÚR =ØQÚØRÚØPÚR =1故G為恒真公式。例2，求的主析取范式與主合取范

16、式。解析求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價(jià)式中的分配律、同一律和互補(bǔ)律，結(jié)果的前一步適當(dāng)使用等冪律，使相同的短語(yǔ)（或子句）只保留一個(gè)。另外，由已經(jīng)得到的主析取（合取）范式，根據(jù)原理，參閱離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書(shū)71頁(yè)例15，也可以求得主合取（析取）范式。解：（1）求主析取范式， 方法1 利用真值表求解G0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111因此方法2 推導(dǎo)法（2）求主合取范式方法1 利用上面的真值表，為0的有兩行，它們對(duì)應(yīng)的極大項(xiàng)分

17、別為，因此， 方法2 利用已求出的主析取范式求主合取范式，已用去6個(gè)極小項(xiàng)，尚有2個(gè)極小項(xiàng)，即與，于是， 例3，利用形式演繹法證明 P®（Q®R），ØSÚP，Q蘊(yùn)涵S®R。解析利用形式演繹進(jìn)行邏輯推理時(shí)，一是要理解并掌握14個(gè)基本蘊(yùn)涵式，二是會(huì)使用三個(gè)規(guī)則：規(guī)則P、規(guī)則Q和規(guī)則D，需要進(jìn)行一定的練習(xí)。證明：（1）ØSÚP 規(guī)則P（2）S 規(guī)則D（3）P 規(guī)則Q，根據(jù)（1），（2） （4）P®（Q®R） 規(guī)則P （5）Q®R 規(guī)則Q，根據(jù)（3），（4） （6）Q 規(guī)則P （7）R 規(guī)則Q，根據(jù)（5

18、），（6） （8）S®R 規(guī)則D，根據(jù)（2），（7）第四章 謂詞邏輯例1，在謂詞邏輯中將下列命題符號(hào)化： （1）凡正數(shù)都大于0； （2）存在小于3的素?cái)?shù)； （3）沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù)； （4）參加考試的人未必都能取得好成績(jī)。解析反復(fù)理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則。解： （1），其中F（x）：x是正數(shù)，G（x）：x大于0； （2），其中F（x）：x大于3，G（x）：x是素?cái)?shù)； （3），其中F（x）：x為有理數(shù)，G（x）：x能表示成分?jǐn)?shù)。 “沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù)”與“所有的有理數(shù)都能表示成分?jǐn)?shù)”是同一個(gè)命題的不同的敘述方

19、法，因此本命題也可以符號(hào)化為。 （4），其中F（x）：x是參加考試的人，G（x）：x取得好成績(jī)。與（3）類(lèi)似，本命題可以符號(hào)化為。 這個(gè)例子中幾個(gè)命題的符號(hào)化均有典型性，請(qǐng)同學(xué)們注意分析。例2，設(shè)I是如下一個(gè)解釋?zhuān)?F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1求的真值。解析將一階邏輯公式表達(dá)式中的量詞消除，寫(xiě)成與之等價(jià)的公式，然后將解釋I中的數(shù)值代入公式，求出真值。解： 例3，試將一階邏輯公式化成前束范式。解析在充分理解掌握前束范式概念的基礎(chǔ)上，利用改名規(guī)則、基本等價(jià)式與蘊(yùn)涵式（一階邏輯中），將給定公式中量詞提到

20、母式之前稱(chēng)為首標(biāo)。解： 第五章 圖論例1，在具有n個(gè)頂點(diǎn)的完全圖Kn中刪去多少條邊才能得到樹(shù)？解析 本章的概念較多，學(xué)習(xí)時(shí)需要認(rèn)真比較各概念的含義，如：圖、子圖、有向圖、權(quán)圖；樹(shù)、支撐樹(shù)、二叉樹(shù)、有向樹(shù)；路、簡(jiǎn)單路、回路等，這些都是圖的基本概念，今后將在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、計(jì)算機(jī)網(wǎng)絡(luò)等課程中用到。解：n個(gè)頂點(diǎn)的完全圖Kn中共有條邊，n個(gè)頂點(diǎn)的樹(shù)應(yīng)有條邊，于是，刪去的邊有：。例2，求下面有限圖中點(diǎn)u到各點(diǎn)間的最短路。（圖上數(shù)字見(jiàn)教材231頁(yè)第3題。左側(cè)一列的四個(gè)點(diǎn)為u1到u4，右側(cè)一列的四個(gè)點(diǎn)為u5到u8） u v解析計(jì)算權(quán)圖中的最短路要格執(zhí)行迪克斯特拉（Dijkstra）算法的驟，從起點(diǎn)起，到每

21、一點(diǎn)求出最短路，然后進(jìn)行仔細(xì)比較，最后到達(dá)終點(diǎn)，算出最小權(quán)和。解：u®u1， d(u, u1)=1，路(u, u1) u® u2，d(u, u2)=9，路(u, u4, u3, u7, u2)u® u3，d(u, u3)=5，路(u, u4, u3 ,)u® u4，d(u, u4)=3，路(u, u4 )u® u5，d(u, u5)=11，路(u, u1, u5)或路 (u, u4, u3 , u7 , u2 , u5)u® u6，d(u, u6)=13，路(u, u1, u5, u6)u® u7，d(u, u7)=8，路(

22、u, u4 , u3 , u7)u® u8，d(u, u8)=11，路(u, u4, u8)u®v， d(u, v)=15，路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)例3，利用克魯斯卡爾（Kruskal）算法求一棵最優(yōu)支撐樹(shù)。 A 3 B 2 C 1 1 2 4 2 D 3 E 3 2 1 F 2 G 2 H解析 權(quán)圖中的最優(yōu)支撐樹(shù)是圖中所帶權(quán)和最小的支撐樹(shù)，使用克魯斯卡爾（Kruskal）算法。解：按照Kruskal給出的在權(quán)圖中求最優(yōu)支撐樹(shù)的算法，可生成下面的最優(yōu)支撐樹(shù)：（權(quán)和為11） 生成的最優(yōu)支撐樹(shù)結(jié)果不是唯一的

23、，又如下圖（權(quán)和為11）也是一種最優(yōu)支撐樹(shù)。例4，一棵樹(shù)有兩個(gè)節(jié)點(diǎn)度數(shù)為2，一個(gè)節(jié)點(diǎn)度數(shù)為3，三個(gè)節(jié)點(diǎn)度數(shù)為4，問(wèn)它有幾個(gè)度數(shù)為1的節(jié)點(diǎn)？解：我們知道一個(gè)有限圖中，各點(diǎn)的度數(shù)總和是邊數(shù)的2倍；而樹(shù)中的邊數(shù)為點(diǎn)數(shù)減1。根據(jù)這兩點(diǎn)，可知樹(shù)中各點(diǎn)的度數(shù)總和=2´（樹(shù)中點(diǎn)數(shù)-1），設(shè)樹(shù)葉有x個(gè)，于是，2´2+3+3´4+x=2´（2+1+3+x-1）得x=9。上例可推廣為“一棵樹(shù)有n2個(gè)節(jié)點(diǎn)度數(shù)為2，n3個(gè)節(jié)點(diǎn)度數(shù)為3，nk個(gè)節(jié)點(diǎn)度數(shù)為k，問(wèn)它有幾個(gè)度數(shù)為1的節(jié)點(diǎn)？”請(qǐng)同學(xué)們思考。三、 綜合練習(xí)及參考解答（一）填空題1、集合的表示方法有兩種： 法和 法。請(qǐng)把“奇

24、整數(shù)集合”表示出來(lái) 。2、 A，B是兩個(gè)集合，A=1，2，3，4，B=2，3，5，則B-A= ，r（B）-r（A）= ，r（B）的元素個(gè)數(shù)為 。3、 設(shè)，則從A到B的所有映射是 。4、 設(shè)命題公式，則使公式G為假的解釋是 、 和 。5、設(shè)G是完全二叉樹(shù)，G有15個(gè)點(diǎn)，其中8個(gè)葉結(jié)點(diǎn)，則G的總度數(shù)為 ，分枝點(diǎn)數(shù)為 。6、全集E=1，2，3，4，5，A=1，5，B=1，2，3，4，C=2，5， 求AÇB= ，r（A）Çr（C）= ，C= 。7、設(shè)A和B是任意兩個(gè)集合，若序偶的第一個(gè)元素是A的一個(gè)元素，第二個(gè)元素是B的一個(gè)元素，則所有這樣的序偶集合稱(chēng)為集合A和B的 ，記作A

25、80;B，即A´B= 。A´B的子集R稱(chēng)為A，B上的 。8、將幾個(gè)命題聯(lián)結(jié)起來(lái)，形成一個(gè)復(fù)合命題的邏輯聯(lián)結(jié)詞主要有否定、 、 、 和等值。9、表達(dá)式"x$yL（x，y）中謂詞的定義域是a，b，c，將其中的量詞消除，寫(xiě)成與之等價(jià)的命題公式為 。10、一個(gè)無(wú)向圖表示為G=（P，L），其中P是 的集合，L是 的集合，并且要求 。（二）選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1. 設(shè)命題公式，則G是（ ）。A.恒真的 B.恒假的 C.可滿(mǎn)足的 D.析取范式2、設(shè)集合，A上的關(guān)系，則=（ ）。 3、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫(xiě)法是唯一的（ ）。A析取范式 B合取范式

26、 C主析取范式 D以上答案都不對(duì)4、設(shè)命題公式G=Ø（P®Q），H=P®（Q®ØP），則G與H的關(guān)系是（ ）。AGÞH BHÞG CG=H D以上都不是5、已知圖G的相鄰矩陣為，則G有（ ）。 A.5點(diǎn)，8邊 B. 6點(diǎn)，7邊 C. 5點(diǎn)，7邊 D. 6點(diǎn)，8邊6、下列命題正確的是（ ）。AfÇf=f BfÈf=f CaÎa，b，c DfÎa，b，c7、設(shè)集合A=a，b，c，A上的關(guān)系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），則R具有關(guān)系的

27、（ ）性質(zhì)。A自反 B對(duì)稱(chēng) C傳遞 D反對(duì)稱(chēng)8、設(shè)R為實(shí)數(shù)集，映射s=R®R，s（x）= -x2+2x-1，則s是（ ）。A單射而非滿(mǎn)射 B滿(mǎn)射而非單射 C雙射 D既不是單射，也不是滿(mǎn)射9、下列語(yǔ)句中，（ ）是命題。A下午有會(huì)嗎？ B這朵花多好看呀！ C2是常數(shù)。 D請(qǐng)把門(mén)關(guān)上。10、下面給出的一階邏輯等價(jià)式中，（ ）是錯(cuò)的。A "x（A（x）ÚB（x）="xA（x）Ú"xB（x）B A®"xB（x）="x （A®B（x）C $x（A（x）ÚB（x）=$xA（x）Ú$xB（x

28、）D Ø"xA（x）=$x（ØA（x）（三）計(jì)算題1、設(shè)R和S是集合上的關(guān)系，其中，試求： （1）寫(xiě)出R和S 的關(guān)系矩陣；（2）計(jì)算。2、 設(shè)A=a，b，c，d，R1，R2是A上的關(guān)系，其中R1=（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）。（1） 畫(huà)出R1和R2的關(guān)系圖；（2） 判斷它們是否為等價(jià)關(guān)系，是等價(jià)關(guān)系的求A中各元素的等價(jià)類(lèi)。3、 用真值表判斷下列公式是恒真？恒假？可滿(mǎn)足？（1）（P

29、7;ØP）«Q（2）Ø（P®Q）ÙQ（3）（P®Q）Ù（Q®R）®（P®R）4、 設(shè)解釋I為：（1） 定義域D=-2，3，6；（2） F（x）：x£3；G（x）：x>5。 在解釋I下求公式$x（F（x）ÚG（x）的真值。5、 化簡(jiǎn)下式：（AÈBÈC）Ç（AÈB）-（AÈ（B-C）ÇA）6、 已知A=1，2，3，4，5，B=1，2，3，R是A到B的二元關(guān)系，并且R=（x，y）|xÎA且yÎB且

30、2£ x+y £4，畫(huà)出R的關(guān)系圖，并寫(xiě)出關(guān)系矩陣。7、 畫(huà)出下面偏序集（A，£）的哈斯圖，并指出集合A的最小元、最大元、極大元和極小元。其中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、求下面帶權(quán)圖的最優(yōu)支撐樹(shù)，并計(jì)算它的權(quán)。 4 7 8 20 12 8 9 10 15（四）證明題1、證

31、明等價(jià)式。 2、 利用形式演繹法證明：蘊(yùn)涵Q。3、 A，B，C為任意的集合，證明：4、 利用一階邏輯的基本等價(jià)式，證明： 練習(xí)題參考解答（一）填空題1、列舉；描述；2、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）|xÎA且yÎB；二元關(guān)系8、并且（或合取）；或者（或析取）；蘊(yùn)涵9、（L（a，a）ÚL（a，b）Ú

32、L（a，c）Ù（L（b，a）ÚL（b，b）ÚL（b，c）Ù（L（c，a）ÚL（c，b）ÚL（c，c）10、點(diǎn)；連接某些不同點(diǎn)對(duì)的邊；一對(duì)不同點(diǎn)之間最多有一條邊（二）選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）1、C 2、A 3、C 4、A 5、C6、A 7、B 8、D 9、C 10、A（三）計(jì)算題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的關(guān)系圖如

33、下： R1的關(guān)系圖 R2的關(guān)系圖由關(guān)系圖可知，R1是等價(jià)關(guān)系。R1不同的等價(jià)類(lèi)有兩個(gè)，即a，b和c，d。由于R2不是自反的，所以R2不是等價(jià)關(guān)系。3、解 ：（1） 真值表P QØP PÙØP （PÙØP）«Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）為可滿(mǎn)足。（2） 真值表P QP®Q Ø（P®Q） Ø（P®Q）ÙQ0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）為恒假。 （3） 真值表P Q RP

34、4;Q Q®R P®R （P®Q）Ù（Q®R）®（P®R）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） Û （1Ú0）Ú（1

35、8;0）Ú（0Ú1） Û 1 5、解： （AÈBÈC）Ç（AÈB）-（AÈ（B-C）ÇA）=（AÈB）- A （利用兩次吸收律） =（AÈB）Ç 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的關(guān)系圖為關(guān)系矩陣7、解： （A，£）的哈斯圖為： e b c d a a為A的極小元，也是最小元； e為A的極大元，也是最大元。 8、解： Ø（PÚQ）«（PÙQ）Û（Ø（PÚQ）®（P