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

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

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

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

(1)掌握命題概念

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

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

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

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

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

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

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

判斷一個(gè)語(yǔ)句是否為命題，首先看是否為陳述句，再看其真值是否唯一。

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

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

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

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

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

將下列命題符號(hào)化．（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）分別符號(hào)化為,,.（4）是簡(jiǎn)單命題，符號(hào)化為：王教授和李教授是大學(xué)校友．

真值表

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

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

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

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

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

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

(或

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

5、“當(dāng)且僅當(dāng)”稱的等價(jià)式，記作。是的充要條件，也是的充要條件。例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é)詞與自然語(yǔ)言中聯(lián)結(jié)詞的關(guān)系。

否定——不是，沒(méi)有，非，不。

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

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

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

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

7、運(yùn)算順序

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

步驟：(1)找出各簡(jiǎn)單命題，分別符號(hào)化。

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

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

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

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

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

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

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

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

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

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

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

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

(1)解：

(2)解：

四、命題公式的分類

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

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

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

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

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

2、判定

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

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

，

解：作真值表如下：

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

(2)

，

二、重要等值式。

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

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

12、等價(jià)等值式

13、假言易位

14、等價(jià)否定等值式

15、歸謬論

10、雙重否定律

三、等值演算。

例2、驗(yàn)證下列等值式。

置換定理：如果。

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

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

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

蘊(yùn)涵等值式

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

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

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

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

分配律

排中律與同一律

分配律

排中律與同一律

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

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

例3、用兩種方法證明:

[證法一]用真值表法

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

蘊(yùn)涵等值式

雙重否定律

交換律

結(jié)合律

吸收律

例4、將下圖所示的邏輯電路簡(jiǎn)化

解：將上述邏輯電路寫(xiě)成命題公式：

利用等值式將公式化簡(jiǎn)

分配律

結(jié)合律

等冪律

所以，該電路可簡(jiǎn)化為下圖

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

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

重點(diǎn)：掌握對(duì)偶式，對(duì)偶原理。真值表

：由定義知：

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

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

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

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

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

例如：

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

三、對(duì)偶原理。

1、對(duì)偶式。

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

與互為對(duì)偶式。例如

：與，與，與2、對(duì)偶原理。

所以可得：

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

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

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

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

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

一、簡(jiǎn)單析取式，簡(jiǎn)單合取式。

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

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

例如：

為析取范式，

為合取范式。

定義：

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

為析取范式，

顯然，

為合取范式

，為合取范式。

例如：

為析取范式。

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

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

(3)利用分配律。

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

解：原式

消去

內(nèi)移

消去

上式即析取范式

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

對(duì)(分配)解：原式

消去

內(nèi)移

消去

上式即合取范式

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

(分配)對(duì)三、主范式。

1、極小項(xiàng)，極大項(xiàng)。

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

都是極大項(xiàng)，

例如，對(duì)只含變項(xiàng)的命題公式中，但不是極小項(xiàng)。但不是極大項(xiàng)。極大項(xiàng)，極小項(xiàng)

。下面分別討論，即個(gè)命題變項(xiàng)的極小項(xiàng)

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

01234567記法

極大項(xiàng)

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

01234567記法

2、主析取范式，主合取范式。主析取范式——每個(gè)簡(jiǎn)單合取式都是極小項(xiàng)的析取范式。

主合取范式——每個(gè)簡(jiǎn)單析取式都是極大項(xiàng)的合取范式。

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

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

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

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

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

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

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

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

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

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

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

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

合取范式

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

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

步驟：

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

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

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

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

由的主合取范式步驟：

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

解：的主合取范式為：

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

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

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

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

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

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

(4)求真值表。

例7、已知含3個(gè)命題變項(xiàng)的公式：

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

例7、已知含3個(gè)命題變項(xiàng)的公式：

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

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

內(nèi)容：重點(diǎn)：

(1)理解推理的概念；

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

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

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

了解：

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

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

2、判斷推理的方法。

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

1、定義：

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

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

結(jié)論：

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

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

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

所以推理正確。

[方法二]用真值表法。

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

所以推理正確。

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

主析取范式含全部最小項(xiàng)，所以推理正確。

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

結(jié)論：

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

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

其主析取范式中缺極小項(xiàng)所以推理不正確。

，[方法二]

蘊(yùn)涵等值式

吸收律

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

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

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

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

(5)析取三段論

(6)假言三段論

(7)等價(jià)三段論

(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、寫(xiě)出對(duì)應(yīng)下面推理的證明。

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

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

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

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

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

(1)附加前提證明法。

例4

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

因?yàn)榧醋C明

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

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

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

1、基本概念。

2、應(yīng)用。

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

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

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

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

，第一章

小結(jié)與例題

二、命題公式及分類。

1、基本概念。

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

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

2、應(yīng)用。

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

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

三、等值演算。

1、基本概念。

兩個(gè)公式等值的含義；等值演算。

2、應(yīng)用。

(1)靈活運(yùn)用24個(gè)重要等值式。

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

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

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

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

1、基本概念。

簡(jiǎn)單析取式，簡(jiǎn)單合取式；

析取范式，合取范式；極小項(xiàng)，極大項(xiàng)；

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

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

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

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

六、推理理論。

1、基本概念。

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

2、應(yīng)用。

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

等值演算法

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

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

例1、判斷下列各語(yǔ)句中，命題，簡(jiǎn)單命題，

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

(2)2是素?cái)?shù)或是合數(shù)，

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

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

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

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

例2、

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

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

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

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

、的真值為1，

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

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

例6、求命題公式

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

解：先求主析取范式

故主合取范式為

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

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

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

證明：設(shè)

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

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

①

③

②

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

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

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

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

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

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

問(wèn)是誰(shuí)盜竊了錄音機(jī)。

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

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

：乙的證詞正確，

：午夜燈光未滅。

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

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

或者①

前提引入

②

前提引入

③

①②拒取式

④

前提引入

⑤

③④假言推理

⑥

前提引入

⑦

⑤⑥拒取式

⑧

前提引入

⑨

⑦⑧析取三段論

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

第二章

謂詞邏輯

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

內(nèi)容：

個(gè)體詞，謂詞，量詞，命題符號(hào)化。

重點(diǎn)：

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

2、掌握在一階邏輯中的命題符號(hào)化。

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

凡人都是要死的，

蘇格拉底是人，

所以蘇格拉底是要死的。

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

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

1、個(gè)體詞，謂詞

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

是無(wú)理數(shù)。

小王比小李高2厘米。

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

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

用個(gè)體變項(xiàng)

用表示表示謂詞謂詞常項(xiàng)謂詞變項(xiàng)都用表示：小王，

：小明，

：小王比小明高。

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

小明是大學(xué)生。

一元謂詞

個(gè)體常項(xiàng)

個(gè)體常項(xiàng)

：李華

：小明

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

它們是0元謂詞。

：是大學(xué)生，

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

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

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

(2)一般，除非有特別說(shuō)明，均以全總個(gè)體域?yàn)閭€(gè)體域，(3)在引入特性謂詞后，使用全稱量詞用“使用存在量詞用“”，”，(4)個(gè)量詞，元謂詞化為命題至少需要如(5)當(dāng)個(gè)體域?yàn)橛邢藜瘯r(shí)，，則(6)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，

不能隨意顛倒順序。

三、命題符號(hào)化。

例1、在一階邏輯中將下面命題符號(hào)化。

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

解：因無(wú)指定個(gè)體域，則以全總個(gè)體域?yàn)閭€(gè)體域。：為有理數(shù)，：可表成分?jǐn)?shù)，

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

解：：為有理數(shù)，：為整數(shù)，注：若本題指定的個(gè)體域?yàn)橛欣頂?shù)集，

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

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

(2)存在著偶素?cái)?shù)。

解：

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

是偶數(shù)，：是素?cái)?shù)，(3)沒(méi)有不犯錯(cuò)誤的人。

原命題即：“每個(gè)人都犯錯(cuò)誤”。

又可符號(hào)化為：

解：

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

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

第一句為：

或

解：

：是火車，：是汽車，

：快，比第二句為：

或

例3

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

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

內(nèi)容：

合式公式，解釋，邏輯有效式，矛盾式，可滿足式。重點(diǎn)：

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

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

一階邏輯合式公式及解釋

一般：

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

(2)解釋的概念，

(3)代換實(shí)例。

了解：

(1)閉式的概念，

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

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

1、字母表。

(1)個(gè)體常項(xiàng)：

(2)個(gè)體變項(xiàng)：

(3)函數(shù)符號(hào)：

(4)謂詞符號(hào)：

(5)量詞符號(hào)：

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

(7)括號(hào)和逗號(hào)：(，)，

，

。

2、元的遞歸定義。

(1)個(gè)體常項(xiàng)和變項(xiàng)是元。

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

例如：

等都是元。

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

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

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

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

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

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

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

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

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

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

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

無(wú)自由出現(xiàn)的個(gè)體變項(xiàng)的合式公式。

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

例如：

換成

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

例如：

換成

二、合式公式的解釋。

對(duì)公式中各種變項(xiàng)(個(gè)體變項(xiàng)，函數(shù)變項(xiàng)，

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

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

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

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

邏輯有效式——

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

矛盾式——

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

可滿足式——

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

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

代換實(shí)例——

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

例如：

等都是的代換實(shí)例。

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

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

(1)解：

設(shè)。是任意的解釋，設(shè)其個(gè)體域?yàn)槿舸嬖跒榧?，為假，則，從而為真；(2)解：

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

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

(3)解：

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

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

(4)而且(矛盾式)，

所以原公式是矛盾式。

解：

原公式是命題公式的代換實(shí)例，

內(nèi)容：

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

重點(diǎn)：

掌握基本等值式，

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

一般：

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

了解：

前束范式的定義和求法。

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

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

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

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

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

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

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

前束范式：形式

例如：

，等都是前束范式，

而

等都不是前束范式。

任一合式公式都可表示為前束范式，其化歸步驟如下：（1）消去公式中出現(xiàn)的多余量詞；（2）將合式公式中出現(xiàn)的聯(lián)結(jié)詞都化為（3）利用雙重否定律，德·摩根律及量詞否定等值式將合式公式中的否定字符深入到謂詞字母前；（4）利用代替規(guī)則和換名規(guī)則，使所有約束變?cè)幌嗤?，并且使自由變?cè)c約束變?cè)煌?）利用量詞轄域收縮與擴(kuò)張等值式，擴(kuò)大量詞的轄域至整個(gè)公式．例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ī)則在推理中的正確使用。

重點(diǎn)：

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

一般：

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

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

1、概念。

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

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

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

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

要求：

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

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

要求：

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

要求：

(1)為真的特定的個(gè)體常項(xiàng)，

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

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

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

要求：

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

不能已在的：蘇格拉底。

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

結(jié)論：

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

①

前提引入

②

①

③

前提引入

④

②③假言推理

例2指出下面推理的錯(cuò)誤．

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

③UG⑤④EG解：

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

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

1、基本概念。

個(gè)體，個(gè)體域，個(gè)體詞，個(gè)體常項(xiàng)和變項(xiàng)；

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

2、應(yīng)用。

在謂詞邏輯中將命題符號(hào)化。

第二章

小結(jié)與例題

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

1、基本概念。

合式公式；轄域，約束變項(xiàng)，自由變項(xiàng)；

閉式；解釋；代換實(shí)例；邏輯有效式，

矛盾式，可滿足式。

2、應(yīng)用。

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

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

三、謂詞邏輯等值式。

基本概念。

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

四、謂詞邏輯推理理論。

1、基本概念。

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

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

例1、在一階邏輯中將下列命題符號(hào)化。

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

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

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

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

(個(gè)體域?yàn)?真值0。

真值0。

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

真值1。

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

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

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

內(nèi)容：

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

重點(diǎn)：

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

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

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

(2)常見(jiàn)的集合

和特殊集合，第三章

集合第一節(jié)

集合的基本概念

一、集合的概念。

1、集合——一些確定的對(duì)象的整體。

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

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

表示集合含有元素注意：

(1)或

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

表示同一個(gè)集合。

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

一個(gè)集合也可以作為另一個(gè)集合的元素。

例如：

2、集合的表示法。

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

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

一般，用描述法表示集合

3、常見(jiàn)的一些集合。

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

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

5、特殊的集合。

空集

(2)對(duì)任意集合有(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、子集。

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

2、集合的冪集，記的全體子集為元素的集合?！?、。，求若個(gè)元素。有個(gè)元素，則有例5、求以下集合的冪集。

(1)解：

(2)解：

(3)解：

(4)解：

(5)解：

內(nèi)容：

集合的運(yùn)算，文氏圖，運(yùn)算律。

重點(diǎn)：

(1)掌握集合的運(yùn)算

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

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

第二節(jié)

集合的運(yùn)算一、集合的運(yùn)算。

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

(其中為全集)，

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

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

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

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

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

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

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

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

(1)解：

(2)解：

三包含排斥定理

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

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

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

1、冪等律：

，2、結(jié)合律：

,3、交換律：

,4、分配律：

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

,6、零律：

,7、互否律：

(排中律)，

(矛盾律)8、吸收律：

，9、德

摩根律：

10、雙重否定律：

以上恒等式的證明思路：

欲證。，，即證對(duì)任意故

例4、證明分配律

。證明：

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

14、

15、

12、11、，，16、

17、18、

19、

20、

“

”的交換律“

”的結(jié)合律故

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

對(duì)任意，證明：

例6、證明。例7、化簡(jiǎn)

所以原式化簡(jiǎn)為

解：因?yàn)?，所以，又因?yàn)樗?，?/p>

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

1、有序?qū)?，記。特點(diǎn)：

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

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

即2、笛卡兒積。

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

，

求。

，，，，解：

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

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

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

(3)一般，。注意：

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

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

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

（1）（2）}（3）

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

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

證明：

對(duì)任意

，

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

1、基本概念。

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

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

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

第三章

小結(jié)與例題

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

1、基本概念。

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

2、應(yīng)用。

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

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

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

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

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

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

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

表示愛(ài)好體育運(yùn)動(dòng)的學(xué)生的集合，

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

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

解：

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

(2)數(shù)學(xué)系的學(xué)生或者愛(ài)好文學(xué)或者愛(ài)好體育運(yùn)動(dòng)，

解：

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

解：

(4)只有一、二年級(jí)的學(xué)生才愛(ài)好體育運(yùn)動(dòng)，

解：

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

解：

(1)解：

解：

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

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

或(4)若解：

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

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

與其中任何集合都不相等

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

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

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

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

，，，，問(wèn)上述集合中有哪些是相等的。

解：

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

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

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

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

若則有

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

由因。有知：

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

證明：設(shè)

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

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

為任意集合，證明：

(2)證明：設(shè)

，有

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

(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)系的運(yùn)算重點(diǎn)：

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

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

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

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

為二元關(guān)系。

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

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

時(shí)，稱作設(shè)

則的關(guān)系。

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

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

空關(guān)系。，恒等關(guān)系，全域關(guān)系對(duì)任意集合，空關(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)系圖表示點(diǎn)(邊(每個(gè)有序?qū)?duì)應(yīng)一條有向弧)個(gè)頂點(diǎn))二、逆關(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)系圖可將起來(lái)求得。

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

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

②

次冪規(guī)定為：

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

例7、

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

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

反對(duì)稱性，傳遞性。

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

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

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

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

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

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

關(guān)系圖的特點(diǎn)

自反性

，都有

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

，都有

主對(duì)角線元素全為0圖中每個(gè)頂點(diǎn)都無(wú)環(huán)定義

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

關(guān)系圖的特點(diǎn)

對(duì)稱性

對(duì)稱矩陣

若兩頂點(diǎn)間有

邊，必是一對(duì)方向相反的邊

反對(duì)稱性

若兩頂點(diǎn)間有邊，

必是一條有向邊

若則

，若則

，且若則

，且定義

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

關(guān)系圖的特點(diǎn)

傳遞性

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

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

解：是反自反的，反對(duì)稱的，傳遞的。

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

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

解：不是傳遞的。

是自反的，既不是對(duì)稱又不是反對(duì)稱的，

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

解：是反自反，反對(duì)稱，不是傳遞的。

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

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

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

又不是反對(duì)稱，不是傳遞的。

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

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

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

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

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

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

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

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

證明：對(duì)任意

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

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

也是所以上是對(duì)稱的。

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

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

不一定是反例：

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

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

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

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

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

3、性質(zhì)。

——

的自反閉包，

——

的對(duì)稱閉包，——

的傳遞閉包。

是自反的，是對(duì)稱的

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

1、利用以下公式。

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

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

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

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

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