教學(xué)課件-離散數(shù)學(xué)(第二版)王宗傳

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支,是計算機(jī)科學(xué)中基礎(chǔ)理論的核心課程，為計算機(jī)科學(xué)提供了有力的理論基礎(chǔ)和工具。離散數(shù)學(xué)的基本思想、概念和方法廣泛地滲透到計算機(jī)科學(xué)與技術(shù)發(fā)展的各個領(lǐng)域，而且其基本理論和研究成果更是全面而系統(tǒng)地影響和推動著其發(fā)展。離散數(shù)學(xué)的內(nèi)容十分豐富，最重要，最核心的是：數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論。本課程主要講授以上四個方面的內(nèi)容。

數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科，它與數(shù)學(xué)的其它分支、計算機(jī)科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切的聯(lián)系。命題邏輯和一階謂詞邏輯是數(shù)理邏輯中最成熟的部分，在計算機(jī)科學(xué)中應(yīng)用最為廣泛，其中命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分，謂詞邏輯是在它的基礎(chǔ)上發(fā)展起來的。本課程在第一，二兩章中介紹數(shù)理邏輯的內(nèi)容。數(shù)理邏輯簡介

內(nèi)容：命題，邏輯聯(lián)結(jié)詞，命題符號化

(1)掌握命題概念

(2)掌握聯(lián)結(jié)詞含義及真值表

(3)掌握命題符號化方法

重點：第一章命題邏輯第一節(jié)命題與邏輯聯(lián)結(jié)詞一、命題的概念

命題：能判斷真假的陳述句。

注：(1)命題必須是一個完整的陳述句．

（2）命題的真值具有唯一性，確定性．

（3）真值的唯一性并不一定要求現(xiàn)在就能判斷出命題的真假，要是在將來某時候能判斷出真假也行，真值是否唯一與是否知道其真值是兩回事．真值真（記為T或1）假（記為F或0）例1、判斷下列語句中哪些是命題．（1）人的血液是白色的．（2）x+y>5．（3）你的大學(xué)英語四級考試通過了嗎？（4）明年六一兒童節(jié)是晴天．（5）2+3=5．（6）地球之外的星球上也有人類．（7）請講普通話?。?）很多人喜歡中央3臺的星光大道節(jié)目．（9）12是素數(shù)．（10）九寨溝的風(fēng)景真是美麗?。?/p>

判斷一個語句是否為命題，首先看是否為陳述句，再看其真值是否唯一。

表示。命題常項，命題變項均用二、邏輯聯(lián)結(jié)詞。

這五種常用的聯(lián)結(jié)詞有命題簡單命題（不能再分解成更簡單的命題）復(fù)合命題（由簡單命題用聯(lián)接詞聯(lián)接而成的命題）真值表

1、“非”稱為的否定式，記作例如：：11是素數(shù)；：11不是素數(shù)取值1，取值0。真值表

2、“并且”稱為的合取式，記作。

在例1．（2）中，設(shè)表示“2是素數(shù)”，表示“2是偶數(shù)”，則表示“2是素數(shù)和偶數(shù)”，由于的真值都是1，所以的真值也是1．例2、

將下列命題符號化．（1）王教授不僅研究經(jīng)濟(jì)學(xué)而且研究管理學(xué)．（2）王教授雖然研究經(jīng)濟(jì)學(xué)但不研究管理學(xué)．（3）王教授研究經(jīng)濟(jì)學(xué)及管理學(xué)．（4）王教授和李教授是大學(xué)校友．解：設(shè)：王教授研究經(jīng)濟(jì)學(xué)，：王教授研究管理學(xué)，則（1）（2）（3）分別符號化為,,.（4）是簡單命題，符號化為：王教授和李教授是大學(xué)校友．

真值表

3、“或者”稱的析取式，記作。例如，：小明學(xué)過英語，：小明學(xué)過日語，則小明學(xué)過英語或日語可表示為真值表：

4、“如果那么”稱的蘊(yùn)涵式，記作其中為前件，為后件。(1)如果天不下雨，我就騎車上班。

(2)只要天不下雨，我就騎車上班。

(3)只有天不下雨，我才騎車上班。

(4)除非天下雨，否則我就騎車上班。

(5)如果天下雨，我就不騎車上班。

(或

)例3、：天下雨，：我騎車上班。真值表：

5、“當(dāng)且僅當(dāng)”稱的等價式，記作。是的充要條件，也是的充要條件。例4、：，：3是奇數(shù)(1)當(dāng)且僅當(dāng)3是奇數(shù)。(2)當(dāng)且僅當(dāng)3不是奇數(shù)。(3)當(dāng)且僅當(dāng)3是奇數(shù)。(4)當(dāng)且僅當(dāng)3不是奇數(shù)。6、邏輯聯(lián)結(jié)詞與自然語言中聯(lián)結(jié)詞的關(guān)系。

否定——不是，沒有，非，不。

合取——并且，同時，和，既…又…，不但…而且…，雖然…但是…。

析取——或者，或許，可能。

蘊(yùn)涵——若…則…，假如…那么…，既然…那就…，倘若…就…。

等價——當(dāng)且僅當(dāng)，充分必要，相同，一樣。

7、運算順序

邏輯聯(lián)結(jié)詞也稱邏輯運算符，規(guī)定優(yōu)先級的順，若有括號時，先進(jìn)行括號序為內(nèi)運算。例如：三、命題符號化。

步驟：(1)找出各簡單命題，分別符號化。

(2)找出各聯(lián)結(jié)詞，把簡單命題逐個聯(lián)結(jié)起來。例5、

將下列命題符號化．（1）小王不富有但很快樂．（2）小王現(xiàn)在乘坐公共汽車或坐飛機(jī)．（3）如果明天有霧，他就不能坐輪船而是乘車過江．（4）這個材料有趣，意味著這些習(xí)題很難，并且反之亦然．（5）如果這個材料無趣或者習(xí)題不是很難，那么這門課程就不會讓人喜歡．（6）這門課程會讓人喜歡，除非這個材料無趣并且習(xí)題很難．解：（1）設(shè)：小王富有，：小王很快樂，符號化為（2）設(shè)：小王現(xiàn)在乘坐公共汽車，：小王現(xiàn)在坐飛機(jī)，符號化為（3）設(shè)：明天有霧，：他坐輪船過江，：他乘車過江，符號化為對于（4）、（5）、（6），設(shè)：這個材料有趣，：這些習(xí)題很難，：這門課程會讓人喜歡，則符號化分別為，，，．內(nèi)容：命題公式，重言式，矛盾式，可滿足公式。

重點：(1)掌握命題公式的定義及公式的真值表。

(2)掌握重言式和矛盾式的定義及使用真值表進(jìn)行判斷。

第二節(jié)命題公式與解釋一、命題公式

通俗地說，命題公式是由命題常項，命題變項，聯(lián)結(jié)詞，括號等組成的字符串。

規(guī)定：公式中最外層的括號，及的括號可省略。

例1、判斷以下字符串中哪些是命題公式。

(1)(2)(3)(4)(5)(6)解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。

二、，如公式，110(按字典序)為的成假賦值，111，011，010……等是的成真賦值。個命題變項的命題公式，共有含組不同賦值。公式的解釋或賦值賦值成真賦值（使A為真的賦值）成假賦值（使A為假的賦值）三、真值表。

的真值表——指在所有賦值之下取值列成的表。

構(gòu)造命題公式的真值表的具體步驟如下：（1）找出公式中包含的所有命題變項（若無下角標(biāo)就按字典順序給出），列出所有可能的賦值（個）；（2）按照優(yōu)先級的運算順序：，，，，，進(jìn)行運算．如果出現(xiàn)括號，先進(jìn)行括號中的運算，直到計算出公式的真值．例2、求下列命題公式的真值表。

(1)解：

(2)解：

四、命題公式的分類

2、判定方法:真值表法。1、定義：設(shè)是任意一個命題公式．（1）若在它的各種賦值下取值均為假，則稱為永假式或矛盾式；（2）若在它的各種賦值下取值均為真，則稱為永真式或重言式；（3）若至少存在一組賦值是成真賦值，則稱為可滿足式；例3、給定命題公式如下，請判斷哪些是重言式，哪些是矛盾式，哪些是可滿足式？

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)解：列出各題真值表如下(步驟簡略)(1)、(2)、(5)、(6)、(9)為重言式；(3)、(8)為矛盾式；(4)、(7)、(10)及以上的重言式均為可滿足式。內(nèi)容：等值關(guān)系，24個重要等值式，等值演算。

重點：(1)掌握兩公式等值的定義。

(2)掌握24個重要等值式，并能利用其進(jìn)行等值演算。

第三節(jié)公式的等值演算一、兩命題公式間的等值關(guān)系。

2、判定

。1、定義：設(shè)為兩命題公式，若等價式是重言式，則稱與是等值的，記作。是否重言式

。是否等值，即判斷判斷兩公式(1)

，

解：作真值表如下：

例1、判斷兩公式是否等值。解：作真值表如下：

(2)

，

二、重要等值式。

2、結(jié)合律，3、分配律，1、交換律，4、德

摩根律，6、吸收律，5、等冪律，7、零律，8、同一律，9、互否律(矛盾律)(排中律)，11、蘊(yùn)涵等值式

12、等價等值式

13、假言易位

14、等價否定等值式

15、歸謬論

10、雙重否定律

三、等值演算。

例2、驗證下列等值式。

置換定理：如果。

，則（1）（2）（3）（1）解：

蘊(yùn)涵等值式分配律

蘊(yùn)涵等值式（2）

蘊(yùn)涵等值式

蘊(yùn)涵等值式德·摩根律雙重否定律與分配律

蘊(yùn)涵等值式解：（3）解：

蘊(yùn)涵等值式等價等值式

蘊(yùn)涵等值式德·摩根律交換律

分配律

排中律與同一律

分配律

排中律與同一律

考慮問題:能否利用等值式來化簡，或判斷公式的類型(重言，矛盾，可滿足)。

判斷一個公式是否重言式，矛盾式，可滿足式，或者判斷兩個命題公式是否等值。有兩種方法，即真值表法和等值演算法。

例3、用兩種方法證明:

[證法一]用真值表法

由最后兩列真值完全相同，于是命題成立。[證法二]用等值式法

蘊(yùn)涵等值式

雙重否定律

交換律

結(jié)合律

吸收律

例4、將下圖所示的邏輯電路簡化

解：將上述邏輯電路寫成命題公式：

利用等值式將公式化簡

分配律

結(jié)合律

等冪律

所以，該電路可簡化為下圖

：內(nèi)容：聯(lián)結(jié)詞的全功能集，極小功能集,對偶原理。了解：全功能集，極小功能集。

第四節(jié)聯(lián)結(jié)詞全功能集與對偶原理

重點：掌握對偶式，對偶原理。真值表

：由定義知：

一、聯(lián)結(jié)詞。記作1、“的排斥或(異或)，之間恰有一個成立”稱。真值表

：的與非式，記作并且2、“的否定”稱。真值表：

的或非式，記作3、“或者的否定”稱。二、全功能集，極小功能集。

全功能集：若干個聯(lián)結(jié)詞的集合，其余的聯(lián)結(jié)詞均可由它們表示。

最小全功能集：不含冗余聯(lián)結(jié)詞的全功能集。

例如：

等都是全功能集。等都是極小全功能集。

三、對偶原理。

1、對偶式。

定義：設(shè)公式僅含聯(lián)結(jié)詞，則將分別用替代，所得的公式稱的對偶式。

與互為對偶式。例如

：與，與，與2、對偶原理。

所以可得：

若。，則例如：已知(分配律)，與均為相互對偶式，

且，與內(nèi)容：命題公式的范式。

(2)掌握析取范式和合取范式的定義和求法步驟。

(3)掌握極小項，極大項的概念及主范式的求法。

第五節(jié)命題公式的范式重點：（1）掌握簡單合取式和簡單析取式的概念。

一、簡單析取式，簡單合取式。

簡單析取式:由有限個命題變項或其否定構(gòu)成的析取式簡單合取式:由有限個命題變項或其否定構(gòu)成的合取式例如：等都是簡單析取式。，，，例如：等都是簡單合取式。

，，，二、析取范式，合取范式。

例如：

為析取范式，

為合取范式。

定義：

由有限個簡單合取式構(gòu)成的析取式稱作析取范式。由有限個簡單析取式構(gòu)成的合取式稱作合取范式。例如：

為析取范式，

顯然，

為合取范式

，為合取范式。

例如：

為析取范式。

范式存在定理：任一命題公式都存在與之等值的析取范式和合取范式。求范式步驟：

(2)否定消去或內(nèi)移。

(3)利用分配律。

(1)消去聯(lián)結(jié)詞

解：原式

消去

內(nèi)移

消去

上式即析取范式

例1、求公式的析取范式。分配律

對(分配)解：原式

消去

內(nèi)移

消去

上式即合取范式

例2、求公式的合取范式。分配律

(分配)對三、主范式。

1、極小項，極大項。

定義：設(shè)命題公式含這個命題變項，則和分別稱為極小項和極大項，其中為或。都是極小項，

都是極大項，

例如，對只含變項的命題公式中，但不是極小項。但不是極大項。極大項，極小項

。下面分別討論，即個命題變項的極小項

成真賦值(二進(jìn)制數(shù))000001010011100101110111對應(yīng)十進(jìn)制數(shù)

01234567記法

極大項

成假賦值(二進(jìn)制數(shù))000001010011100101110111對應(yīng)十進(jìn)制數(shù)

01234567記法

2、主析取范式，主合取范式。主析取范式——每個簡單合取式都是極小項的析取范式。

主合取范式——每個簡單析取式都是極大項的合取范式。

兩種求法，等值式法和真值表法。

定理：任何命題公式的主析取范式、主合取范式

都存在且都是唯一的。步驟：

(3)消去重復(fù)的及永假項。2.1、利用等值式法求命題公式的主析取范式。(1)求，的析取范式(2)利用

補(bǔ)充變元，(4)按角碼順序排序，并用“”表示。解：由例1的析取范式為

例3、求公式的主析取范式。(吸收律)步驟：

(3)求每個成真賦值對應(yīng)的十進(jìn)制數(shù)，即極小項的角碼，將極小項按序析取即成。2.2、利用真值表求命題公式的主析取范式。(1)列出的真值表，(2)找出的所有成真賦值，解：(1)列真值表

例4、用真值表求的主析取范式。(2)的成真賦值有010，100，101，110，111(3)對應(yīng)的十進(jìn)制數(shù)為2，4，5，6，7所以的主析取范式為

步驟：(3)消去重復(fù)的及永真項；

2.3、利用等值式法求命題公式的主合取范式。

(1)求；的合取范式(2)利用

補(bǔ)充變元；(4)按角碼順序排序，并用符號“”表示；如。記為解：由例2，

合取范式

例4、求公式的主合取范式。

2.4、利用真值表求命題公式的主合取范式。

步驟：

(3)求每個成假賦值對應(yīng)的十進(jìn)制數(shù)，即極大項的角碼，將極大項按序合取即成。(1)列出的真值表，(2)找出的所有成假賦值，例5、用真值表求的主合取范式。解：(1)由例3知真值表，的(3)對應(yīng)的十進(jìn)制數(shù)為0，1，3。

(2)的成假賦值有000，001，011，所以的主合取范式：思考：命題公式間有什么聯(lián)系，能否通過其中一個求另一個？(觀察例3，例5)的主合取范式，主析取范式由例3、例5知：2.5、已知命題公式的主析取范式(主合取范式)，

求主合取范式(主析取范式)。

(2)寫出與(1)中極小項角碼相同的極大項，

由的主合取范式步驟：

的主析取范式求(1)寫出的主析取范式未出現(xiàn)的極小項，(3)由以上極大項合取即成的主合取范式。例6、(1)已知命題公式的主合取范式。(主析取范式為：求含3個命題變項)

解：的主合取范式為：

例6、(2)已知命題公式主合取范式為：的主析取范式。(求含2個命題變項)解：的主析取范式為：3、主范式的用途。

(1)判斷兩命題公式是否等值。

(2)判斷命題公式的類型。

重言式主析取范式含全部的極小項主合取范式不含任何極大項(主合取范式記為1)矛盾式主析取范式不含任何極小項(主析取范式記為0)主合取范式含全部的極大項3、主范式的用途。

(2)判斷命題公式的類型。

可滿足式主析取范式至少含一個極小項主合取范式至少缺一個極大項(3)求成真(假)賦值。

(4)求真值表。

例7、已知含3個命題變項的公式：

和(1)判斷的類型。解：為矛盾式。為可滿足式，(2)判斷是否等值。解：不等值。的成假賦值有010，011，100，101。

例7、已知含3個命題變項的公式：

和(3)求的成真賦值和成假賦值。的成真賦值有000，001，110，111。

解：(4)求的真值表。解：真值表

內(nèi)容：重點：

(1)理解推理的概念；

(2)掌握8條推理定律；

(3)掌握推理規(guī)則；

(4)掌握構(gòu)造證明法。

了解：

附加前提證明法和歸謬法。

推理規(guī)則，構(gòu)造證明法。推理的概念，推理定律，第六節(jié)命題邏輯中的推理一、推理的形式結(jié)構(gòu)。

2、判斷推理的方法。

等值演算法，真值表法，主析取范式法。

1、定義：

記作則稱前提若為重言式，推結(jié)論的推理正確，為的邏輯結(jié)論或有效結(jié)論。。例1、判斷下面各推理是否正確。

(1)如果天氣涼快，小王就不去游泳，天氣涼快，所以小王沒去游泳。

結(jié)論：

推理形式結(jié)構(gòu)為：

判斷此蘊(yùn)涵式是否為重言式。

前提：，解：設(shè)小王去游泳。：：天氣涼快，[方法一]用等值式法。

所以推理正確。

[方法二]用真值表法。

其真值表中最后一列全為1，

所以推理正確。

[方法三]用主析取范式法。

主析取范式含全部最小項，所以推理正確。

(2)如果我上街，我一定去新華書店，我沒上街，所以我沒去新華書店。前提：

結(jié)論：

推理的形式結(jié)構(gòu)為：

解：設(shè)：我去新華書店，：我上街，[方法一]

其主析取范式中缺極小項所以推理不正確。

，[方法二]

蘊(yùn)涵等值式

吸收律

[方法三]所以推理不正確。

列出真值表，其最后一列不全為1,由于01是推理不正確。的成假賦值，并非重言式，二、構(gòu)造證明法。

1、推理定律有以下8條：

(1)附加(2)化簡(3)假言推理(4)拒取式

(5)析取三段論

(6)假言三段論

(7)等價三段論

(8)構(gòu)造性二難

2、推理規(guī)則。

(1)前提引入規(guī)則

(3)置換規(guī)則

3、構(gòu)造證明法。

依照推理規(guī)則，應(yīng)用推理規(guī)律。

(2)結(jié)論引入規(guī)則

例2、構(gòu)造下列推理的證明。

(1)前提：

結(jié)論：

證明：前提引入

②

前提引入

前提引入

③

④

①②③構(gòu)造性二難

①(2)前提：

結(jié)論：

證明：

①

前提引入

前提引入

②

③

①②拒取式

④

前提引入

⑤

③④假言推理

⑥

前提引入

⑦

⑤⑥拒取式

⑧

前提引入

⑨

⑦⑧析取三段論

例3、寫出對應(yīng)下面推理的證明。

(1)張三說李四在說謊，李四說王五在說謊，王五說張三、李四都在說謊．問張三、李四、王五3人，到底誰說真話，誰說假話？解：先將命題符號化．設(shè)：張三說真話；：李四說真話；：王五說真話前提：，，，,,推理過程：①前提引入②前提引入③①②假言三段論④前提引入⑤

③④假言三段論⑥⑤置換⑦⑥置換⑧前提引入⑨⑦⑧假言推理⑩

前提引入⑾⑨⑩假言推理⑿⑦⑨⑾合取引入因此，由上述推理可知：張三說假話，王五說假話，只有李四說真話．(2)如果小王是理科生，他的數(shù)學(xué)成績必好．如果小王不是文科生，他必是理科生．小王數(shù)學(xué)成績確實不好．所以小王是文科生．解：先將命題符號化．設(shè)：小王是理科生；：小王是文科生；：小王數(shù)學(xué)成績好．

前提：；；結(jié)論：證明：①前提引入②前提引入③①②拒取式④前提引入⑤③④拒取式⑥

⑤置換3、附加前提證明法和歸謬法。

(1)附加前提證明法。

例4

用附加前提證明法證明下面推理．前提：，，結(jié)論：證明：①前提引入②附加前提引入③①②析取三段論④前提引入⑤③④假言推理⑥前提引入⑦⑤⑥假言推理(2)歸謬法。

因為即證明

(其中為任意命題公式)例5

構(gòu)造下面推理的證明．前提：，，結(jié)論：證明:①否定結(jié)論引入

②①置換③②化簡④前提引入⑤③④拒取式⑥前提引入⑦⑤⑥析取三段論⑧前提引入⑨⑦⑧假言推理⑩②化簡⑾⑨⑩合取由⑾得出了矛盾，根據(jù)歸謬法說明推理正確．一、命題與聯(lián)結(jié)詞。

1、基本概念。

2、應(yīng)用。

(1)選擇適當(dāng)?shù)穆?lián)結(jié)詞將命題符號化。

(2)判斷命題(簡單或復(fù)合)的真假。

命題與真值；簡單命題和復(fù)合命題；

命題常項和變項；五個聯(lián)結(jié)詞真值表。

，第一章

小結(jié)與例題

二、命題公式及分類。

1、基本概念。

命題公式的定義；公式的賦值；

重言式，矛盾式，可滿足式。

2、應(yīng)用。

(1)求給定公式的真值表，及成真賦值，成假賦值。

(2)用真值表判斷給定公式的類型。

三、等值演算。

1、基本概念。

兩個公式等值的含義；等值演算。

2、應(yīng)用。

(1)靈活運用24個重要等值式。

(2)用等值演算判斷公式的類型及兩個公式

是否等值(也可用真值表)。

四、聯(lián)結(jié)詞全功能集與對偶原理

基本概念聯(lián)結(jié)詞的全功能集，極小全功能集對偶原理五、命題公式的范式

1、基本概念。

簡單析取式，簡單合取式；

析取范式，合取范式；極小項，極大項；

主析取范式，主合取范式。

2、應(yīng)用。(1)求給定公式的主析取范式和主合取范式。

(2)用主析取范式或主合取范式判斷兩公式是否等值。(3)用主析取范式或主合取范式求公式的成真或成假賦值。

(4)用主析取范式或主合取范式判斷公式的類型。

六、推理理論。

1、基本概念。

推理，推理規(guī)則，推理定律；構(gòu)造證明法。

2、應(yīng)用。

(1)判斷推理是否正確：真值表法

等值演算法

主析取范式法(主合取范式法)。

(2)用8條推理定律構(gòu)造推理的證明。

例1、判斷下列各語句中，命題，簡單命題，

復(fù)合命題，真命題，假命題，真值待定的命題各有哪些？

(2)2是素數(shù)或是合數(shù)，

(4)只有4是奇數(shù)，5才能被3整除。

(5)明年5月1日是晴天。

(1)，(3)若，則5是偶數(shù)，解：命題有(2)－(5)，其中(5)是簡單命題，(2)，(3)，(4)是復(fù)合命題，

(2)，(4)為真命題，(3)為假命題，(5)真值待定。

例2、

設(shè)：天正在下雪；：我將進(jìn)城；：我有空。用自然語言寫出下列命題。

(1)解：我將進(jìn)城去當(dāng)且僅當(dāng)我有空且天不下雪。

(2)解：雖然天正在下雪，但我將進(jìn)城去。(3)解：我進(jìn)城當(dāng)且僅當(dāng)我有空。(4)解：天不下雪且我沒空。例3、

設(shè)試求下列命題的真值。的真值為0，

、的真值為1，

、(1)解：(2)解：(3)解：(4)解：例4、簡化下列命題公式。(1)解：(2)解：(3)解：(4)解：例5、判斷下列各命題公式，哪些是重言式，矛盾式，可滿足式？(1)(2)(3)解：可用真值表法，等值演算法，主析取(主合取)范式等方法判斷公式的類型，

(2)為重言式，(3)為矛盾式，(1)，(2)均為可滿足式。

例6、求命題公式

的主析取范式，主合取范式，成真賦值和成假賦值。

解：先求主析取范式

故主合取范式為

成真賦值為極小項角碼對應(yīng)的二進(jìn)制數(shù)，00，10，11。

成假賦值為極大項角碼對應(yīng)的二進(jìn)制數(shù)，即01

例7、設(shè)(1)求的真值表。(2)求的主析取范式、主合取范式。解：例8、寫出對應(yīng)下面推理的證明。有紅、黃、藍(lán)、白四隊參加足球聯(lián)賽。如果紅隊第三，則當(dāng)黃隊第二時，藍(lán)隊第四；或者白隊不是第一，或者紅隊第三；事實上，黃隊第二。因此，如果白隊第一，那么藍(lán)隊第四。

證明：設(shè)

：紅隊第三，：黃隊第二，：藍(lán)隊第四，：白隊第一。前提：結(jié)論：前提：結(jié)論：前提引入

附加前提引入①②析取三段論前提引入④

①

③

②

⑤③④假言推理前提引入⑤⑥假言推理⑦⑥由附加前提證明法知推理正確。

例9、一公安人員審查一件盜竊案，已知的事實如下：

(1)甲或乙盜竊了錄音機(jī)；

(2)若甲盜竊了錄音機(jī)，則作案時間不能發(fā)生在午夜前；(3)若乙的證詞正確，則午夜時屋里燈光未滅；

(4)若乙的證詞不正確，則作案時間發(fā)生在午夜之前；

(5)午夜時屋里燈光滅了。

問是誰盜竊了錄音機(jī)。

：乙盜竊了錄音機(jī)，

：作案時間發(fā)生在午夜前，

：乙的證詞正確，

：午夜燈光未滅。

解：設(shè)：甲盜竊了錄音機(jī)，

前提：，，，，結(jié)論：

或者①

前提引入

②

前提引入

③

①②拒取式

④

前提引入

⑤

③④假言推理

⑥

前提引入

⑦

⑤⑥拒取式

⑧

前提引入

⑨

⑦⑧析取三段論

所以是乙盜竊了錄音機(jī)。

第二章

謂詞邏輯

第一節(jié)謂詞邏輯基本概念

內(nèi)容：

個體詞，謂詞，量詞，命題符號化。

重點：

1、掌握個體詞，謂詞，量詞的有關(guān)概念，

2、掌握在一階邏輯中的命題符號化。

一、謂詞邏輯研究的內(nèi)容。例如：判斷以下推理是否正確：

凡人都是要死的，

蘇格拉底是人，

所以蘇格拉底是要死的。

這是著名的“蘇格拉底三段論”，

若用推理形式為分別表示以上3個命題，，不是重言式。二、個體詞，謂詞，量詞。

1、個體詞，謂詞

。例如：陳景潤是數(shù)學(xué)家．。

是無理數(shù)。

小王比小李高2厘米。

(1)個體詞——簡單命題中表示主體或客體的詞(由名詞組成)。個體域(或稱論域)——個體變項取值的范圍。

(2)謂詞——刻畫個體詞的性質(zhì)或個體詞之間關(guān)系的詞。個體詞個體常項

用個體變項

用表示表示謂詞謂詞常項謂詞變項都用表示：小王，

：小明，

：小王比小明高。

元謂詞(用表示)如高。比：其中為個體詞。是二元謂詞，例如：李華是大學(xué)生，

小明是大學(xué)生。

一元謂詞

個體常項

個體常項

：李華

：小明

分別表示李華，小明是大學(xué)生，

它們是0元謂詞。

：是大學(xué)生，

2、量詞——表示數(shù)量的詞。

全稱量詞量詞存在量詞使用量詞時，應(yīng)注意以下6點：

(1)在不同個體域中，命題符號化的形式可能不一樣，

(2)一般，除非有特別說明，均以全總個體域為個體域，(3)在引入特性謂詞后，使用全稱量詞用“使用存在量詞用“”，”，(4)個量詞，元謂詞化為命題至少需要如(5)當(dāng)個體域為有限集時，，則(6)多個量詞同時出現(xiàn)時，

不能隨意顛倒順序。

三、命題符號化。

例1、在一階邏輯中將下面命題符號化。

(1)所有的有理數(shù)均可表成分?jǐn)?shù)。

解：因無指定個體域，則以全總個體域為個體域。：為有理數(shù)，：可表成分?jǐn)?shù)，

(2)有的有理數(shù)是整數(shù)。

解：：為有理數(shù)，：為整數(shù)，注：若本題指定的個體域為有理數(shù)集，

則(1)，(2)分別符號化為和。例2、在一階邏輯中將下列命題符號化。

(1)凡偶數(shù)均能被2整除。

(2)存在著偶素數(shù)。

解：

：是偶數(shù)，：能被2整除，：解：

是偶數(shù)，：是素數(shù)，(3)沒有不犯錯誤的人。

原命題即：“每個人都犯錯誤”。

又可符號化為：

解：

：是人，：犯錯誤，(4)每列火車都比某些汽車快。

某些汽車比所有的火車慢。

第一句為：

或

解：

：是火車，：是汽車，

：快，比第二句為：

或

例3

設(shè)個體域為實數(shù)集，令是整數(shù)．是有理數(shù)．．．試用日常語言敘述下列命題，并指出其真值．（1）（2）（3）（4）

（2）存在著實數(shù)，使得對于任意實數(shù)，都有．該命題真值為0．（3）存在著實數(shù)和,使得且．該命題真值為1．（4）對于任意實數(shù)，存在著實數(shù)，使得且，解：（1）對于任意實數(shù)，存在著實數(shù)，使得．該命題真值為1．該命題真值為0．

內(nèi)容：

合式公式，解釋，邏輯有效式，矛盾式，可滿足式。重點：

(1)掌握合式公式的概念，

(2)掌握量詞的轄域，約束變項，自由變項的概念，(3)掌握邏輯有效式，矛盾式，可滿足式的概念。第二節(jié)

一階邏輯合式公式及解釋

一般：

(1)換名規(guī)則，代替規(guī)則，

(2)解釋的概念，

(3)代換實例。

了解：

(1)閉式的概念，

(2)判斷合式公式的類型。

一、一階邏輯中的合式公式。

1、字母表。

(1)個體常項：

(2)個體變項：

(3)函數(shù)符號：

(4)謂詞符號：

(5)量詞符號：

(6)聯(lián)結(jié)詞符：

(7)括號和逗號：(，)，

，

。

2、元的遞歸定義。

(1)個體常項和變項是元。

(3)只有有限次地使用(1)、(2)生成的符號串才是元。

例如：

等都是元。

(2)若是元，則元函數(shù)，是任意是元。3、原子公式。

4、合式公式的遞歸定義。

(1)原子公式是合式公式；

設(shè)是項，則稱為原子公式。元謂詞，是任意(3)若也是合式公式；

是合式公式，則是合式公式，則也是合式公式；(2)若(5)只有有限次地應(yīng)用(1)－(4)構(gòu)成的符號串

才是合式公式(也稱謂詞公式)，簡稱公式。

(4)若也是合式公式；是合式公式，則5、約束出現(xiàn)，自由出現(xiàn)。

在合式公式中，稱為指導(dǎo)變項，稱為相應(yīng)量詞的轄域，

約束出現(xiàn)，自由出現(xiàn)

例1、指出下列各合式公式中的指導(dǎo)變項，量詞的轄域，個體變項的自由出現(xiàn)和約束出現(xiàn)。

（1）（2）（3）閉式(封閉的合式公式)——

無自由出現(xiàn)的個體變項的合式公式。

換名規(guī)則——指導(dǎo)變項，約束變項換名

例如：

換成

代替規(guī)則——自由變項代替

例如：

換成

二、合式公式的解釋。

對公式中各種變項(個體變項，函數(shù)變項，

謂詞變項)，指定特殊的常項去代替，就構(gòu)成了公式的一個解釋。

(1)非空個體域；(2)中一部分特定元素；1、解釋由以下4部分組成：(3)上一些特定的函數(shù)；(4)上一些特定的謂詞；例2給定解釋如下：中特定元素；

(1);(2)函數(shù)為；(3)謂詞為；(4)為為

．；在解釋下，求下列各式的真值．（1）；（2）；（3）；（4）．解：設(shè)（1）、（2）、（3）、（4）中公式分別為．在解釋下，．2、邏輯有效式(永真式)，矛盾式(永假式)，可滿足式。

邏輯有效式——

在任何解釋下都取值為真的合式公式。

矛盾式——

在任何解釋下都取值為假的合式公式。

可滿足式——

至少存在一種解釋使其取值為真的合式公式。

有一些公式，可以利用命題公式的結(jié)論。

代換實例——

個命題變項將詞公式稱為設(shè)是含的命題公式，所得的謂取代個謂詞的代換實例。

例如：

等都是的代換實例。

命題公式中重言式，矛盾式的代換實例在謂詞公式中仍是重言式(邏輯有效式)，矛盾式。

例3、判斷下列公式中哪些是邏輯有效式，哪些是矛盾式。

(1)解：

設(shè)。是任意的解釋，設(shè)其個體域為若存在為假，為假，則，從而為真；(2)解：

原公式是命題公式的代換實例，(重言式)，

而且所以原公式是邏輯有效的。

(3)解：

原公式是命題公式的代換實例，(重言式)，

而且所以原公式是邏輯有效的。

(4)而且(矛盾式)，

所以原公式是矛盾式。

解：

原公式是命題公式的代換實例，

內(nèi)容：

一階邏輯等值式，前束范式。

重點：

掌握基本等值式，

(量詞否定等值式，量詞轄域收縮與擴(kuò)張等值式，量詞分配等值式)的內(nèi)容。

一般：

使用基本等值式進(jìn)行等值演算。

了解：

前束范式的定義和求法。

第三節(jié)謂詞邏輯等值式一、一階邏輯等值式。

已有的等值式命題公式中的24個等值式及代換實例由換名規(guī)則及代替規(guī)則所得公式與原公式等值定義：

若為邏輯有效式，記定理2．1量詞否定等值式。

(1)(2)定理2．2量詞分配等值式。

(1)(2)定理2．3量詞轄域收縮與擴(kuò)張等值式。

(1)(2)(4)(3)(5)(6)(7)(8)定理2．4多個量詞間的次序排列等值式。

(1)(2)二、前束范式。

前束范式：形式

例如：

，等都是前束范式，

而

等都不是前束范式。

任一合式公式都可表示為前束范式，其化歸步驟如下：（1）消去公式中出現(xiàn)的多余量詞；（2）將合式公式中出現(xiàn)的聯(lián)結(jié)詞都化為（3）利用雙重否定律，德·摩根律及量詞否定等值式將合式公式中的否定字符深入到謂詞字母前；（4）利用代替規(guī)則和換名規(guī)則，使所有約束變元均不相同，并且使自由變元與約束變元不同．（5）利用量詞轄域收縮與擴(kuò)張等值式，擴(kuò)大量詞的轄域至整個公式．例2、求下列公式的前束范式。

解：

(1)（定理2．1（2））（換名規(guī)則）（定理2．3

（1）①）（定理2．3

（1）①）(2)解：

（代替規(guī)則）（換名規(guī)則）（定理2．3（2）③）（定理2．3（2）④）（定理2．3（1）③）（定理2．3（1）④）內(nèi)容：

謂詞邏輯推理理論。

了解：

推理規(guī)則在推理中的正確使用。

重點：

掌握謂詞邏輯推理的概念。

一般：

全稱量詞消去規(guī)則，全稱量詞引入規(guī)則，存在量詞引入規(guī)則，存在量詞消去規(guī)則。第四節(jié)謂詞邏輯中的推理

一、謂詞邏輯推理的概念。

1、概念。

已有的推理定律命題公式中的重言蘊(yùn)涵式及代換實例一階邏輯中的等值式(每個等值式可產(chǎn)生兩條推理定律)若則稱推理正確，記為

為邏輯有效式，2、量詞分配定律。

(1)(2)(3)(4)二、推理規(guī)則。

1、全稱量詞消去規(guī)則

要求：

(1)中自由出現(xiàn)的個體變項，是(2)中約束出現(xiàn)的個體變項，

為任意的不在(3)為任意的個體常項。2、全稱量詞引入規(guī)則

要求：

(1)中自由出現(xiàn)，且在均為真，(2)取代中約束出現(xiàn)。不能在的取任何值時3、存在量詞消去規(guī)則

要求：

(1)為真的特定的個體常項，

是使(2)中出現(xiàn)過，不曾在(3)個體變項時，不能用此規(guī)則。

外還有其他自由出現(xiàn)的

中除4、存在量詞引入規(guī)則

要求：

(1)是特定的個體常項，(2)取代中出現(xiàn)過。

不能已在的：蘇格拉底。

解：設(shè)：是人，：是要死的，前提：

結(jié)論：

例1證明蘇格拉底三段論“凡人都是要死的．蘇格拉底是人．所以蘇格拉底是要死的．”證明：

①

前提引入

②

①

③

前提引入

④

②③假言推理

例2指出下面推理的錯誤．

①前提引入②①UI③②EI④

③UG⑤④EG解：

因中存在自由出現(xiàn)的個體變項，因而不能使用EI規(guī)則，所以②～③錯誤．例3構(gòu)造下面推理的證明．前提：結(jié)論：證明：①前提引入②前提引入③①UI④②UI⑤④假言易位⑥

③⑤假言三段論⑦⑥假言易位⑧⑦UG一、謂詞邏輯的基本概念。

1、基本概念。

個體，個體域，個體詞，個體常項和變項；

謂詞；量詞，全稱量詞和存在量詞。

2、應(yīng)用。

在謂詞邏輯中將命題符號化。

第二章

小結(jié)與例題

二、謂詞邏輯合式公式及解釋。

1、基本概念。

合式公式；轄域，約束變項，自由變項；

閉式；解釋；代換實例；邏輯有效式，

矛盾式，可滿足式。

2、應(yīng)用。

(1)求某些公式在給定解釋下的真值。

(2)判斷某些簡單公式的類型。

三、謂詞邏輯等值式。

基本概念。

等值式，常用等值式；前束范式。

四、謂詞邏輯推理理論。

1、基本概念。

推理；全稱量詞消去規(guī)則全稱量詞引入規(guī)則存在量詞引入規(guī)則，，存在量詞消去規(guī)則。，2、應(yīng)用。

用構(gòu)造法證明某些簡單的推理。

例1、在一階邏輯中將下列命題符號化。

(1)至少有一個實數(shù)不是自然數(shù)

(2)任何金屬均可溶解于某種液體中。

：解：：是液體，：是金屬，，符號化為溶解設(shè)是實數(shù)，是自然數(shù)，符號化為

解：例2、將下列命題譯成自然語言，并確定其真值。

(個體域為)真值0。

真值0。

(1)，其中解：對任意正整數(shù)使得，，存在正整數(shù)。(2)，其中解：存在正整數(shù)滿足，，使得對任意的正整數(shù)。真值0。

真值1。

(3)，其中解：對任意正整數(shù)使得，，存在正整數(shù)。(4)，其中解：對任意正整數(shù)使得，，存在正整數(shù)。設(shè)解釋I為：個體域為，謂詞例3根據(jù)解釋I，求下列各式的真值：（1）；（2）；（3）．解：（1）（2）（3）例4

航海家都教育自己的孩子成為航海家，有一個人教育他的孩子去做飛行員，證明這個人一定不是航海家．證明：設(shè)個體域是人的集合．謂詞是航海家；教育他的孩子成為航海家．前提：結(jié)論：證明：①

前提引入②①EI③前提引入④③UI⑤②④拒取式⑥②⑤合取⑦⑥EG現(xiàn)代數(shù)學(xué)中，每個對象(如數(shù)，函數(shù)等)本質(zhì)上都是集合，都可以用某種集合來定義，數(shù)學(xué)的各個分支，本質(zhì)上都是在研究某一種對象集合的性質(zhì)。集合論的特點是研究對象的廣泛性，它也是計算機(jī)科學(xué)與工程的基礎(chǔ)理論和表達(dá)工具，而且在程序設(shè)計，數(shù)據(jù)結(jié)構(gòu)，形式語言，關(guān)系數(shù)據(jù)庫，操作系統(tǒng)等都有重要應(yīng)用。集合論是研究集合一般性質(zhì)的數(shù)學(xué)分支，它的創(chuàng)始人是康托爾(，1845－1918)。在集合論簡介

內(nèi)容：

集合，元素，子集，冪集等。

重點：

(1)掌握集合的概念及兩種表示法，

(3)掌握子集及兩集合相等的概念，

(4)掌握冪集的概念及求法。

(2)常見的集合

和特殊集合，第三章

集合第一節(jié)

集合的基本概念

一、集合的概念。

1、集合——一些確定的對象的整體。

集合用大寫的字母標(biāo)記

其中的對象稱元素，用小寫字母標(biāo)記

表示集合含有元素注意：

(1)或

(2)集合中的元素均不相同

表示同一個集合。

(3)集合的元素可以是任何類型的事物，

一個集合也可以作為另一個集合的元素。

例如：

2、集合的表示法。

(1)列舉法(將元素一一列出)例如：

(2)描述法(用謂詞概括元素的屬性)例如：

一般，用描述法表示集合

3、常見的一些集合。

4、集合間的關(guān)系。

(1)的子集，記為為的真子集，記

5、特殊的集合。

空集

(2)對任意集合有(3)兩集合相等，記作全集)(或(為任一集合)例1、選擇適當(dāng)?shù)闹^詞表示下列集合。

(1)小于5的非負(fù)整數(shù)集

(2)奇整數(shù)集合

(3)10的整倍數(shù)集合，

(4)例2、確定下面命題的真值：

(1)真值

真值

(2)(3)真值

(4)真值

(5)真值

(6)真值

(7)真值

(8)真值

例3、有可能，且為集合，若嗎？嗎，有可能解：兩種情形都有可能。

設(shè)，則。，有又設(shè)，則。，但二、冪集。

1、子集。

元個元素的集合)的元集(例如：為3元集。0元子集：(只有一個)，1元子集：個)，(共2元子集：個)，(共3元子集：個)。(共一般，個。元集共有子集解：

2、集合的冪集，記的全體子集為元素的集合。——例4、。，求若個元素。有個元素，則有例5、求以下集合的冪集。

(1)解：

(2)解：

(3)解：

(4)解：

(5)解：

內(nèi)容：

集合的運算，文氏圖，運算律。

重點：

(1)掌握集合的運算

(2)用文氏圖表示集合間的相互關(guān)系和運算，

(3)掌握基本運算律的內(nèi)容及運用。

第二節(jié)

集合的運算一、集合的運算。

，相對補(bǔ)集集合，的并集交集，對稱差。絕對補(bǔ)集，(當(dāng)不交)時，稱以上定義加以推廣，

(其中為全集)，

(1)(2)(3)(4)，求出以下集合。

，例1、設(shè)，，(5)(6)(7)(8)1、文氏圖。

(2)矩形內(nèi)的圓表示集合，

(1)用大矩形表示全集，二、文氏圖。(3)除特殊情形外，一般表示兩個集合的圓是相交的，

(4)圓中的陰影的區(qū)域表示新組成的集合。

2、用文氏圖表示集合的有關(guān)運算。

例2、用文氏圖表示下列集合。

(1)(2)(3)(4)例3、用集合公式表示下列文氏圖中的陰影部分。

(1)解：

(2)解：

三包含排斥定理

設(shè)和是兩個有限集合，則，其中分別表示、的元數(shù)．

把包含排斥定理推廣到個集合的情況可用如下定理表述：

設(shè)為有限集合，其元數(shù)分別為，則例4求從1到500之間能被2,3,7任何一個數(shù)整除的整數(shù)的個數(shù)．例5有100名程序員，其中47名熟悉FORTRAN語言，35名熟悉PASCAL語言，23名熟悉這兩種語言．問有多少人對這兩種語言都不熟悉？

1、冪等律：

，2、結(jié)合律：

,3、交換律：

,4、分配律：

,第三節(jié)集合的運算性質(zhì)5、同一律：

,6、零律：

,7、互否律：

(排中律)，

(矛盾律)8、吸收律：

，9、德

摩根律：

10、雙重否定律：

以上恒等式的證明思路：

欲證。，，即證對任意故

例4、證明分配律

。證明：

對任意，除基本運算外，還有以下一些常用性質(zhì)(證明略)13、

14、

15、

12、11、，，16、

17、18、

19、

20、

“

”的交換律“

”的結(jié)合律故

例5、證明：(第14條)證明：

對任意，證明：

例6、證明。例7、化簡

所以原式化簡為

解：因為，所以，又因為所以，又

最后，原式化簡為。例8、設(shè)為假的各有哪些？（1）（2）（3）的子集，以下命題中為真，均為真命題假命題真命題一、笛卡兒積。

1、有序?qū)?，記。特點：

(1)，時，(2)。有序。，記元組第四節(jié)序偶與笛卡兒積2、有序元組

是一個有序?qū)?，其中第一個元素是一個有序元組，一個有序元組記作

即2、笛卡兒積。

定義：集合。的笛卡兒積，記作和例1、

，

求。

，，，，解：

當(dāng)且僅當(dāng)

例2、設(shè)。，求解：

(2)笛卡兒積是集合，有關(guān)集合的運算都適合。

(3)一般，。注意：

(1)若則元集，是元集，是元集。為3、笛卡兒積。

階特別，當(dāng)記為時，。如，例3設(shè)

試求：（1）；（2）；（3）。解：

（1）（2）}（3）

笛卡兒積運算具有以下性質(zhì)：

1．若中有一個空集，則它們的笛卡兒積是空集，即2．當(dāng)且都不是空集時，有3．當(dāng)都不是空集時，有4．笛卡兒積運算對或運算滿足分配律，即(1)(2)(3)(4)例4、證明：

證明：

對任意

，

故。一、集合的基本概念。

1、基本概念。

元素和集合的屬于關(guān)系；有限集和無限集；子集和真子集；集合的相等；空集和全集；冪集。2、應(yīng)用。

(1)用集合的兩種表示法表示集合。

(2)求給定集合的冪集。

第三章

小結(jié)與例題

二、集合的基本運算與性質(zhì)。

1、基本概念。

交集，并集，差集，補(bǔ)集，對稱差集；文氏圖；基本運算律。

2、應(yīng)用。

(1)用文氏圖表示集合間的相互關(guān)系和運算。

(2)運用基本運算律進(jìn)行證明，化簡等。

三序偶與笛卡兒積表示計算機(jī)科學(xué)系學(xué)生的集合，

表示二年級大學(xué)生的集合，

表示數(shù)學(xué)系學(xué)生的集合，

表示選修離散數(shù)學(xué)的學(xué)生的集合，

表示愛好文學(xué)的學(xué)生的集合，

表示愛好體育運動的學(xué)生的集合，

用集合交集，并集和包含關(guān)系表示：

(1)所有計算機(jī)科學(xué)系二年級的學(xué)生都選修離散數(shù)學(xué)，

解：

例1、設(shè)表示一年級大學(xué)生的集合，

(2)數(shù)學(xué)系的學(xué)生或者愛好文學(xué)或者愛好體育運動，

解：

(3)數(shù)學(xué)系一年級的學(xué)生都沒有選修離散數(shù)學(xué)，

解：

(4)只有一、二年級的學(xué)生才愛好體育運動，

解：

(5)除去數(shù)學(xué)系和計算機(jī)科學(xué)系二年級的學(xué)生外都不選修離散數(shù)學(xué)。

解：

(1)解：

解：

例2、設(shè)，，確定在以下條件下集合相等？

中哪個可能與，，(2)，但解：

或(4)若解：

或例2、設(shè)，，確定在以下條件下集合相等？

中哪個可能與，，(3)且解：

與其中任何集合都不相等

例2、設(shè)，，確定在以下條件下集合相等？

中哪個可能與，，(5)若且例3、簡要說明：舉出它們的元素和子集。

的區(qū)別，與子集有解：是無任何元素的集合，，是以集合為元素的集合，

元素為。，子集有例4、設(shè)

，，，，問上述集合中有哪些是相等的。

解：

(1)解：結(jié)論不一定成立。

例5、設(shè)是集合，證明或反駁下列斷言。

若則有，，，，，但若則有，，，。(2)解：結(jié)論不一定成立。

例5、設(shè)是集合，證明或反駁下列斷言。

若則有

，，，，，但若則有，，，。(3)解：結(jié)論成立。

由因。有知：

故。例5、設(shè)是集合，證明或反駁下列斷言。(1)，有

證明：設(shè)

例6、設(shè)為任意集合，證明：

又，，即有，故所以。例6、設(shè)

為任意集合，證明：

(2)證明：設(shè)

，有

又，，故即，所以。例7、求下列集合的基數(shù)和每個集合的冪集。

(1)解：基數(shù)2，

冪集為：

(2)解：基數(shù)3，

冪集為：

(1){2，4，6，8}解：例8、設(shè)試用其中：表示下述集合。(2){3，6，9}解：例8、設(shè)試用其中：表示下述集合。(3){10}解：例8、設(shè)試用其中：表示下述集合。解：例8、設(shè)試用其中：表示下述集合。(4)是偶數(shù)例8、設(shè)試用其中：表示下述集合。(5)是奇數(shù))是正偶數(shù))解：例8、設(shè)試用其中：表示下述集合。(1)所有奇數(shù)的集合；

解：

(2)解：

例9、

都是表示下列集合。

和的子集，試用(3)解：

(4)解：

例9、

都是表示下列集合。

和的子集，試用內(nèi)容：

二元關(guān)系，關(guān)系圖，關(guān)系矩陣，關(guān)系的運算重點：

(1)二元關(guān)系的定義及三種表示法，

(2)一些特殊的二元關(guān)系。

第四章二元關(guān)系和函數(shù)第一節(jié)二元關(guān)系及其運算（3）二元關(guān)系的逆、復(fù)合、冪運算了解：關(guān)系的復(fù)合運算性質(zhì)，矩陣法求冪運算一、二元關(guān)系。

1、定義：(1)若集合則稱為空集或它的元素都是有序?qū)Γ?/p>

為二元關(guān)系。

若否則，記作，，則記作。

(2)的關(guān)系，到的任何子集都稱作從特別，當(dāng)上關(guān)系。

時，稱作設(shè)

則的關(guān)系。

到都是從例1、，2、上不同關(guān)系的數(shù)目。

若則，元集，記為，的子集共有個，元集個。上不同的關(guān)系共有3、特殊的關(guān)系。

空關(guān)系。，恒等關(guān)系，全域關(guān)系對任意集合，空關(guān)系，全域關(guān)系，恒等關(guān)系。4、常用關(guān)系。

(1)設(shè)上小于等于關(guān)系：

，(2)設(shè)上整除關(guān)系：

，(3)冪集：上的包含關(guān)系解：

例2、。，，求解：

，

例3、。上的包含關(guān)系，求有三種集合表示法矩陣表示法圖形表示法5、上二元關(guān)系的表示法。

解：

關(guān)系圖：

例4、已知求，上關(guān)系

，和關(guān)系圖。的關(guān)系矩陣一般：設(shè)

，其中

關(guān)系圖表示點(邊(每個有序?qū)?yīng)一條有向弧)個頂點)二、逆關(guān)系，復(fù)合關(guān)系。

1、關(guān)系的逆。

(1)定義：關(guān)系的逆關(guān)系定義為解：

例5、為上小于等于關(guān)系，

為，。，上整除關(guān)系，分別求出即上大于等于關(guān)系。

為即上的倍數(shù)關(guān)系。

為2、關(guān)系的(復(fù)合

。(1)定義，關(guān)系R和S的合成關(guān)系定義為：

(2)，的關(guān)系矩陣與的關(guān)系矩陣滿足的轉(zhuǎn)置。的關(guān)系圖只需將改向即得。

的關(guān)系圖中的有向弧(3)。例6、設(shè)

求

，，，，，。解：

邏輯加法：

，，，。(2)滿足的關(guān)系矩陣

與的關(guān)系矩陣。的關(guān)系圖可將起來求得。

的關(guān)系圖連接次冪的運算滿足：

，(3)合成關(guān)系滿足結(jié)合律：。(4)關(guān)系次冪。的定義：設(shè)的①

②

次冪規(guī)定為：

，上關(guān)系，為[解法一]用集合表示。

例7、

求。，[解法二]用關(guān)系圖表示。

內(nèi)容：關(guān)系的自反性，反自反性，對稱性，

反對稱性，傳遞性。

重點：(1)掌握自反性，反自反性，對稱性，反對稱性，傳遞性的定義及關(guān)系矩陣和關(guān)系圖的特征，

(2)掌握關(guān)系五種性質(zhì)的判斷和驗證。

第二節(jié)關(guān)系的性質(zhì)和閉包關(guān)系的自反，對稱，傳遞閉包（3）掌握關(guān)系的自反，對稱，傳遞閉包的概念及求法。

一、關(guān)系的五種性質(zhì)(自反，反自反，對稱，反對稱，傳遞)。

1、定義及關(guān)系矩陣，關(guān)系圖特征由下表給出(上關(guān)系)為定義

關(guān)系矩陣的特點

關(guān)系圖的特點

自反性

，都有

主對角線元素全為1圖中每個頂點都有環(huán)反自反性

，都有

主對角線元素全為0圖中每個頂點都無環(huán)定義

關(guān)系矩陣的特點

關(guān)系圖的特點

對稱性

對稱矩陣

若兩頂點間有

邊，必是一對方向相反的邊

反對稱性

若兩頂點間有邊，

必是一條有向邊

若則

，若則

，且若則

，且定義

關(guān)系矩陣的特點

關(guān)系圖的特點

傳遞性

若，則且若頂點則有邊，到有邊，到必有邊到(1)(2)解：是對稱的，不是傳遞的。

既不是自反又不是反自反，

解：是反自反的，反對稱的，傳遞的。

例1、如下所示，判斷各有哪些性質(zhì)。上關(guān)系，(3)(4)解：既是對稱又是反對稱的，傳遞的。

既不是自反又不是反自反的，

解：不是傳遞的。

是自反的，既不是對稱又不是反對稱的，

例2、判斷下圖中的關(guān)系分別具有哪些性質(zhì)。

解：是反自反，反對稱，不是傳遞的。

既是對稱又是反對稱的，傳遞的。是空關(guān)系，是反自反，既是對稱又是反對稱的，傳遞的。

是恒等關(guān)系，是自反的，傳遞的。是全域關(guān)系，是自反的，對稱的，反對稱的，傳遞的。

既不是自反也不是反自反的，

又不是反對稱，不是傳遞的。

是反自反的，既不是對稱則有以下文氏圖。

2、若把上所有關(guān)系看成一個全集，

二、五種性質(zhì)的其它判斷方法。

設(shè)上恒等關(guān)系，則

為上關(guān)系，是1、，是自反的當(dāng)且僅當(dāng)2、，是反自反的當(dāng)且僅當(dāng)3、，是對稱的當(dāng)且僅當(dāng)4、，是反對稱的當(dāng)且僅當(dāng)5、。是傳遞的當(dāng)且僅當(dāng)例3、設(shè)判斷是否傳遞的。

上關(guān)系，，解：因是傳遞的。

，所以因所以，不是傳遞的。

三、關(guān)系在各種運算下保持原有特性問題。

證明：對任意

例如：設(shè)證明上的對稱關(guān)系，

為上的對稱關(guān)系。

也是所以上是對稱的。

在又如：設(shè)證明上反對稱關(guān)系，

為上的反對稱關(guān)系。

不一定是反例：

都是上的反對稱關(guān)系，但的反對稱關(guān)系。上不是四、閉包的定義。

(2)1、定義：設(shè)的自反閉包(對稱閉包，傳遞閉包)也是上的關(guān)系，

是非空集合上關(guān)系，且滿足：

(1)是自反的(對稱的，傳遞的)，

(3)對傳遞關(guān)系)的自反關(guān)系(對稱關(guān)系，上的任何包含。，都有2、記號。

3、性質(zhì)。

——

的自反閉包，

——

的對稱閉包，——

的傳遞閉包。

是自反的，是對稱的

，是傳遞的。五、閉包的求法。

1、利用以下公式。

(1)，(2)，(3)。2、利用關(guān)系圖。

(1)的關(guān)系圖：在沒有環(huán)的結(jié)點上加上環(huán)，

(2)的關(guān)系圖：把單向邊改為雙向邊，

(3)以到達(dá)的終點添加一條有向邊，直到添加完畢。

，分別找出可的關(guān)系圖：對每個結(jié)點沒有有向邊，則到，若[解法一