離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)

離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:離散數(shù)學(xué)期末復(fù)習(xí)指導(dǎo)（?？疲┥綎|廣播電視大學(xué)計算機(jī)與通信學(xué)院2008年6月離散數(shù)學(xué)是中央電大計算機(jī)應(yīng)用專業(yè)信息管理方向開設(shè)的必修統(tǒng)設(shè)課。該課程使用新的教學(xué)大綱，在原有離散數(shù)學(xué)課程的基礎(chǔ)上削減了教學(xué)內(nèi)容（主要是群與環(huán)、格與布爾代數(shù)這兩章及圖論的后三節(jié)內(nèi)容），使所學(xué)的知識達(dá)到必需、夠用，更加適合大學(xué)?？茖哟蔚慕逃?。目前該課程沒有新教材，借用原教材。使用的教材為中央電大出版的《離散數(shù)學(xué)》（劉敘華等編）和《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書》（虞恩蔚等編）。離散數(shù)學(xué)主要研究離散量結(jié)構(gòu)及相互關(guān)系，使學(xué)生得到良好的數(shù)學(xué)訓(xùn)練，提高學(xué)生抽象思維和邏輯推理能力，為從事計算機(jī)的應(yīng)用提供必要的描述工具和理論基礎(chǔ)。其先修課程為：高等數(shù)學(xué)、線性代數(shù)；后續(xù)課程為：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、操作系統(tǒng)、計算機(jī)網(wǎng)絡(luò)等。課程的主要內(nèi)容本課程分為三部分：集合論、數(shù)理邏輯和圖論。集合論部分（集合的基本概念和運(yùn)算、關(guān)系及其性質(zhì)）；數(shù)理邏輯部分（命題邏輯、謂詞邏輯）；圖論部分（圖的基本概念、樹及其性質(zhì)）。學(xué)習(xí)建議離散數(shù)學(xué)是理論性較強(qiáng)的學(xué)科，學(xué)習(xí)離散數(shù)學(xué)的關(guān)鍵是對離散數(shù)學(xué)（集合論、數(shù)理邏輯和圖論）有關(guān)基本概念的準(zhǔn)確掌握，對基本原理及基本運(yùn)算的運(yùn)用，并要多做練習(xí)。一、各章復(fù)習(xí)示例與解析第一章集合例1，將“大于3而小于或等于7的整數(shù)集合”用集合表示出來。[解析]集合的表示方法一般有兩種，一種稱為列舉法，一種稱為描述法。列舉法將集合的元素按任意順序逐一列在花括號內(nèi)，并用逗號分開?！按笥?而小于或等于7的整數(shù)”有4、5、6、7，用列舉法表示為{4、5、6、7}；描述法是利用集合中的元素滿足某種條件或性質(zhì)用文字或符號在花括號內(nèi)豎線后面表示出來。上例用描述法表示為{x|xZ并且3x7}，其中Z為整數(shù)集合。答：{4、5、6、7}或{x|xZ并且3x7}。例2，判定下列各題的正確與錯誤：（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}}；（6）{{a}，1，3，4}{{a}，3，4，1}；（7）{a，b}{a，b，{a，b}}；（8）如果AB=B，則A=E。[解析]此題涉及到集合中子集的概念，集合的包含關(guān)系，空集與集合的關(guān)系。解題時要注意區(qū)分兩個集合之間的關(guān)系以及集合中元素與集合之間的關(guān)系的不同。集合之間的關(guān)系分為包含關(guān)系（子集、真子集）、相等關(guān)系、冪集等，判斷時要準(zhǔn)確理解這些概念，才能正確地運(yùn)用這些知識。集合與它的元素之間的關(guān)系有兩種：一個元素a屬于一個集合A，記為aA；一個元素A不屬于一個集合A，記為aA。要注意符號的記法（）與集合包含符號記法（，）的不同。答：正確的是（2）、（4）、（5）、（7）；其余的都是錯誤的。例3，設(shè)A，B是兩個集合，A={1，2，3}，B={1，2}，請計算（A）–（B）。[解析]集合的概念一般在中學(xué)階段已經(jīng)學(xué)過，這里只多了一個冪集概念，重點(diǎn)對冪集加以掌握，一是掌握冪集的構(gòu)成，由集合A的所有子集組成的集合，稱為A的冪集，記作（A）或2A；一是掌握冪集元數(shù)為2n，n為集合A的元數(shù)。集合的基本運(yùn)算有交、并、差、補(bǔ)。答：（A）={，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}（B）={，{1}，{2}，{1，2}}于是（A）–（B）={{3}，{1，3}，{2，3}，{1，2，3}}例4，試證明（A~B）（~AB）=（AB）（~A~B）[解析]證明集合恒等式要熟練運(yùn)用教材15頁集合的10個基本運(yùn)算。一般來說，欲證P=Q，即證PQ并且QP，也就是要證明，對于任意的x，有下式成立。xPxQ和xQxP證明集合恒等式的另一種方法是利用已知的恒等式來代入。本題就是用的這個方法。通過對集合恒等式證明的練習(xí)，既可以加深對集合性質(zhì)的理解與掌握；又可以為第三章命題邏輯中公式的基本等價式的應(yīng)用打下良好的基礎(chǔ)。實際上，本章做題是一種基本功訓(xùn)練，尤其要求學(xué)生重視吸收律和重要等價式在A–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表示出來，先要清楚“模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)系圖了。答：R的關(guān)系矩陣為：R的關(guān)系圖為：例2，設(shè)集合A={1，2，3，，10}，A上的關(guān)系R={（x，y）|x，yA，且x+y=10}，試判斷R具有哪幾種性質(zhì)？

[解析]關(guān)系的性質(zhì)既是對關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價關(guān)系、半序關(guān)系的基礎(chǔ)。對于四種性質(zhì)（自反性、對稱性、反對稱性、傳遞性）的判定，可以依據(jù)其定義，也可以依據(jù)教材中49頁上總結(jié)的關(guān)于關(guān)系矩陣和關(guān)系圖的規(guī)律。對于傳遞性的判定，難度稍大一點(diǎn)，這里要提及兩點(diǎn)：一是不破壞傳遞性定義，可認(rèn)為具有傳遞性。如空關(guān)系具有傳遞性，同時空關(guān)系具有對稱性與反對稱性，但是不具有自反性。另一點(diǎn)是介紹一種判定傳遞性的“跟蹤法”，即若（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的關(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)系的對稱性。例3，設(shè)集合，判定下列關(guān)系，哪些是自反的，對稱的，反對稱的和傳遞的：解：均不是自反的；R4是對稱的；R1，R2，R3，R4，R5是反對稱的；R1，R2，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的自反閉包，對稱閉包和傳遞閉包。[解析]在理解掌握關(guān)系閉包概念的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個定理的結(jié)論：定理2，自反閉包；定理3，對稱閉包；定理4的推論，傳遞閉包。答：r（R1）=R1IA={（a，b），（b，c），（c，a），（a，a），（b，b），（c，c）}s（R1）=R1R1-1={（a，b），（b，c），（c，a），（b，a），（c，b），（a，c）}R12={（a，c），（b，a），（c，b）}R13={（a，a），（b，b），（c，c）}t（R1）=R1R12R13={（a，b），（b，c），（c，a），（a，c），（b，a），（c，b），（a，a），（b，b），（c，c）}空關(guān)系R2的自反閉包，對稱閉包和傳遞閉包均為。例5，設(shè)集合，A上的二元關(guān)系R為：（１）寫出R的關(guān)系矩陣，畫出R的關(guān)系圖；（２）證明R是A上的半序關(guān)系，畫出其哈斯圖；（３）若，且，求B的最大元，最小元，極大元，極小元，最小上界和最大下界。[解析]理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對于確定任一子集的最大（?。┰?，極大（?。┰簿腿菀琢恕＿@里要注意，最大（?。┰c極大（小）元只能在子集內(nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。解：（1）R的關(guān)系矩陣為R的關(guān)系圖為（2）因為R是自反的，反對稱的和傳遞的，所以R是A上的半序關(guān)系。（A，R）為半序集，（A，R）的哈斯圖如下：441325（3）當(dāng)B={2，3，4，5}，B的極大元為2，4；極小元為2，5；B無最大元與最小元；B也無上界與下界，更無最小上界與最大下界。例6，下列映射中哪些是滿射，哪些是單射，哪些是雙射？（1）（2）（3）（4）[解析]映射的概念與映射種類的判定：映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對各種初等函數(shù)。答：（1），（3）是非單非滿射；（2）是滿射；（4）是雙射。第三章命題邏輯例1，試證明公式為恒真公式。[解析]判定公式的恒真性，包括判定公式是恒真的或是恒假的。具體方法有兩種：一是真值表法，對于任給一個公式，主要列出該公式的真值表，觀察真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿足的。二是推導(dǎo)法，即利用基本等價式推導(dǎo)出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）當(dāng)且僅當(dāng)?shù)葍r于它的合取范式（析取范式）中，每個子句（短語）均至少包含一個原子及其否定。這里要求的析取范式中所含有的每個短語不是極小項，一定要與求主析取范式相區(qū)別，對于合取范式也同樣。證明：證法一：真值表法，見《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書》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，求的主析取范式與主合取范式。[解析]求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價式中的分配律、同一律和互補(bǔ)律，結(jié)果的前一步適當(dāng)使用等冪律，使相同的短語（或子句）只保留一個。另外，由已經(jīng)得到的主析?。ê先。┓妒?，根據(jù)原理，參閱《離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)書》71頁例15，也可以求得主合?。ㄎ鋈。┓妒?。解：（1）求主析取范式，[方法1]利用真值表求解G000001010011100101110111000000111010101101011111因此[方法2]推導(dǎo)法（2）求主合取范式[方法1]利用上面的真值表，為0的有兩行，它們對應(yīng)的極大項分別為，因此，[方法2]利用已求出的主析取范式求主合取范式，已用去6個極小項，尚有2個極小項，即與，于是，例3，利用形式演繹法證明{P（QR），SP，Q}蘊(yùn)涵SR。[解析]利用形式演繹進(jìn)行邏輯推理時，一是要理解并掌握14個基本蘊(yùn)涵式，二是會使用三個規(guī)則：規(guī)則P、規(guī)則Q和規(guī)則D，需要進(jìn)行一定的練習(xí)。證明：（1）SP規(guī)則P（2）S規(guī)則D（3）P規(guī)則Q，根據(jù)（1），（2）（4）P（QR）規(guī)則P（5）QR規(guī)則Q，根據(jù)（3），（4）（6）Q規(guī)則P（7）R規(guī)則 Q，根據(jù)（5），（6）（8）SR規(guī)則D，根據(jù)（2），（7）第四章謂詞邏輯例1，在謂詞邏輯中將下列命題符號化：（1）凡正數(shù)都大于0；（2）存在小于3的素數(shù)；（3）沒有不能表示成分?jǐn)?shù)的有理數(shù)；（4）參加考試的人未必都能取得好成績。[解析]反復(fù)理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與改名規(guī)則。解：（1），其中F（x）：x是正數(shù)，G（x）：x大于0；（2），其中F（x）：x大于3，G（x）：x是素數(shù)；（3），其中F（x）：x為有理數(shù)，G（x）：x能表示成分?jǐn)?shù)?！皼]有不能表示成分?jǐn)?shù)的有理數(shù)”與“所有的有理數(shù)都能表示成分?jǐn)?shù)”是同一個命題的不同的敘述方法，因此本命題也可以符號化為。（4），其中F（x）：x是參加考試的人，G（x）：x取得好成績。與（3）類似，本命題可以符號化為。這個例子中幾個命題的符號化均有典型性，請同學(xué)們注意分析。例2，設(shè)I是如下一個解釋：F(2)F(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)32011101求的真值。[解析]將一階邏輯公式表達(dá)式中的量詞消除，寫成與之等價的公式，然后將解釋I中的數(shù)值代入公式，求出真值。解：例3，試將一階邏輯公式化成前束范式。[解析]在充分理解掌握前束范式概念的基礎(chǔ)上，利用改名規(guī)則、基本等價式與蘊(yùn)涵式（一階邏輯中），將給定公式中量詞提到母式之前稱為首標(biāo)。解：第五章圖論例1，在具有n個頂點(diǎn)的完全圖Kn中刪去多少條邊才能得到樹？

[解析]本章的概念較多，學(xué)習(xí)時需要認(rèn)真比較各概念的含義，如：圖、子圖、有向圖、權(quán)圖；樹、支撐樹、二叉樹、有向樹；路、簡單路、回路等，這些都是圖的基本概念，今后將在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、計算機(jī)網(wǎng)絡(luò)等課程中用到。解：n個頂點(diǎn)的完全圖Kn中共有條邊，n個頂點(diǎn)的樹應(yīng)有條邊，于是，刪去的邊有：。例2，求下面有限圖中點(diǎn)u到各點(diǎn)間的最短路。（圖上數(shù)字見教材231頁第3題。左側(cè)一列的四個點(diǎn)為u1到u4，右側(cè)一列的四個點(diǎn)為u5到u8）uv[解析]計算權(quán)圖中的最短路要格執(zhí)行迪克斯特拉（Dijkstra）算法的驟，從起點(diǎn)起，到每一點(diǎn)求出最短路，然后進(jìn)行仔細(xì)比較，最后到達(dá)終點(diǎn)，算出最小權(quán)和。解：uu1，d(u,u1)=1，路(u,u1)uu2，d(u,u2)=9，路(u,u4,u3,u7,u2)uu3，d(u,u3)=5，路(u,u4,u3,)uu4，d(u,u4)=3，路(u,u4)uu5，d(u,u5)=11，路(u,u1,u5)或路(u,u4,u3,u7,u2,u5)uu6，d(u,u6)=13，路(u,u1,u5,u6)uu7，d(u,u7)=8，路(u,u4,u3,u7)uu8，d(u,u8)=11，路(u,u4,u8)uv，d(u,v)=15，路(u,u1,u5,u6,v)或路(u,u4,u3,u7,u6,v)例3，利用克魯斯卡爾（Kruskal）算法求一棵最優(yōu)支撐樹。A3B2C11242D3E321F2G2H[解析]權(quán)圖中的最優(yōu)支撐樹是圖中所帶權(quán)和最小的支撐樹，使用克魯斯卡爾（Kruskal）算法。解：按照Kruskal給出的在權(quán)圖中求最優(yōu)支撐樹的算法，可生成下面的最優(yōu)支撐樹：（權(quán)和為11）生成的最優(yōu)支撐樹結(jié)果不是唯一的，又如下圖（權(quán)和為11）也是一種最優(yōu)支撐樹。例4，一棵樹有兩個節(jié)點(diǎn)度數(shù)為2，一個節(jié)點(diǎn)度數(shù)為3，三個節(jié)點(diǎn)度數(shù)為4，問它有幾個度數(shù)為1的節(jié)點(diǎn)？解：我們知道一個有限圖中，各點(diǎn)的度數(shù)總和是邊數(shù)的2倍；而樹中的邊數(shù)為點(diǎn)數(shù)減1。根據(jù)這兩點(diǎn)，可知樹中各點(diǎn)的度數(shù)總和=2（樹中點(diǎn)數(shù)1），設(shè)樹葉有x個，于是，22+3+34+x=2（2+1+3+x-1）得x=9。上例可推廣為“一棵樹有n2個節(jié)點(diǎn)度數(shù)為2，n3個節(jié)點(diǎn)度數(shù)為3，…，nk個節(jié)點(diǎn)度數(shù)為k，問它有幾個度數(shù)為1的節(jié)點(diǎn)？”請同學(xué)們思考。三、綜合練習(xí)及參考解答（一）填空題1、集合的表示方法有兩種：法和法。請把“奇整數(shù)集合”表示出來{}。A，B是兩個集合，A={1，2，3，4}，B={2，3，5}，則B-A=，（B）（A）=，（B）的元素個數(shù)為。設(shè)，則從A到B的所有映射是。設(shè)命題公式，則使公式G為假的解釋是、和。5、設(shè)G是完全二叉樹，G有15個點(diǎn)，其中8個葉結(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}，求AB=，（A）（C）=，C=。7、設(shè)A和B是任意兩個集合，若序偶的第一個元素是A的一個元素，第二個元素是B的一個元素，則所有這樣的序偶集合稱為集合A和B的，記作AB，即AB=。AB的子集R稱為A，B上的。8、將幾個命題聯(lián)結(jié)起來，形成一個復(fù)合命題的邏輯聯(lián)結(jié)詞主要有否定、、、和等值。9、表達(dá)式xyL（x，y）中謂詞的定義域是{a，b，c}，將其中的量詞消除，寫成與之等價的命題公式為。10、一個無向圖表示為G=（P，L），其中P是的集合，L是的集合，并且要求。（二）選擇題（選擇一個正確答案的代號，填入括號中）設(shè)命題公式，則G是（）。A.恒真的B.恒假的C.可滿足的D.析取范式2、設(shè)集合，A上的關(guān)系，則=（）。3、一個公式在等價意義下，下面哪個寫法是唯一的（）。A．析取范式B．合取范式C．主析取范式D．以上答案都不對4、設(shè)命題公式G=（PQ），H=P（QP），則G與H的關(guān)系是（）。A．GHB．HGC．G=HD．以上都不是5、已知圖G的相鄰矩陣為，則G有（）。點(diǎn)，8邊B.6點(diǎn)，7邊C.5點(diǎn)，7邊D.6點(diǎn)，8邊6、下列命題正確的是（）。A．{}=B．{}=C．{a}{a，b，c}D．{a，b，c}7、設(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)系的（）性質(zhì)。A．自反B．對稱C．傳遞D．反對稱8、設(shè)R為實數(shù)集，映射=RR，（x）=-x2+2x-1，則是（）。A．單射而非滿射B．滿射而非單射C．雙射D．既不是單射，也不是滿射9、下列語句中，（）是命題。A．下午有會嗎B．這朵花多好看呀！C．2是常數(shù)。D．請把門關(guān)上。10、下面給出的一階邏輯等價式中，（）是錯的。x（A（x）B（x））=xA（x）xB（x）AxB（x）=x（AB（x））x（A（x）B（x））=xA（x）xB（x）xA（x）=x（A（x））（三）計算題1、設(shè)R和S是集合上的關(guān)系，其中，試求：（1）寫出R和S的關(guān)系矩陣；（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）}。畫出R1和R2的關(guān)系圖；判斷它們是否為等價關(guān)系，是等價關(guān)系的求A中各元素的等價類。用真值表判斷下列公式是恒真恒假可滿足（1）（PP）Q（2）（PQ）Q（3）（（PQ）（QR））（PR）設(shè)解釋I為：定義域D={-2，3，6}；F（x）：x3；G（x）：x5。在解釋I下求公式x（F（x）G（x））的真值?；喯率剑海ǎˋBC）（AB））（（A（BC））A）已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元關(guān)系，并且R={（x，y）|xA且yB且2x+y4}，畫出R的關(guān)系圖，并寫出關(guān)系矩陣。畫出下面偏序集（A，）的哈斯圖，并指出集合A的最小元、最大元、極大元和極小元。其中A={a，b，c，d，e}，={（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）}IA。求命題公式的析取范式與合取范式。9、給定解釋I如下：定義域D={2，3}；f（2）f（3）F（2，2）F（2，3）F（3，2）F（3，3）320011求。10、求下面帶權(quán)圖的最優(yōu)支撐樹，并計算它的權(quán)。4782012891015（四）證明題1、證明等價式。利用形式演繹法證明：蘊(yùn)涵Q。A，B，C為任意的集合，證明：利用一階邏輯的基本等價式，證明：練習(xí)題參考解答（一）填空題1、列舉；描述；2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；83、1={（a，1），（b，1）}；2={（a，2），（b，2）}；3={（a，1），（b，2）}；4={（a，2），（b，1）}4、（1，0，1）；（1，1，1）；（1，0，0）28；76、{5}；{，{5}}；{1，3，4}7、笛卡爾積（或直乘積）；{（x，y）|xA且yB}；二元關(guān)系8、并且（或合?。?；或者（或析?。?；蘊(yùn)涵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、點(diǎn)；連接某些不同點(diǎn)對的邊；一對不同點(diǎn)之間最多有一條邊（二）選擇題（選擇一個正確答案的代號，填入括號中）1、C2、A3、C4、A5、C6、A7、B8、D9、C10、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的關(guān)系圖如下：R1的關(guān)系圖R2的關(guān)系圖由關(guān)系圖可知，R1是等價關(guān)系。R1不同的等價類有兩個，即{a，b}和{c，d}。由于R2不是自反的，所以R2不是等價關(guān)系。3、解：真值表PQPPP（PP）Q00101011001000111000因此公式（1）為可滿足。真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（2）為恒假。真值表PQRPQQRPR（（PQ）（QR））（PR）00011110011111010101101111111000101101011111010011111111因此公式（3）為恒真。4、解：x（F（x）G（x））（F（-2）G（-2））（F（3）G（3））（F（6）G（6））（10）（10）（01）15、解：（（ABC）（AB））（（A（BC））A）=（AB）A（利用兩次吸收律）=（AB）~A=（A~A）（B~A）=（B~A）=BA6、解：R={（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）}11