離散數(shù)學的教學案

滁州學院計算機與信息工程學院

課程教案

課程名稱：離散數(shù)學

授課教師：趙歡歡

授課對象：11級網(wǎng)絡工程專業(yè)3、4班

授課時間：2012年9月-2012年12月

滁州學院計算機科學與信息工程學院

2012年8月

《離散數(shù)學》教學大綱

（DiscreteMathematic）

課程代碼：學時：48學分：3

一、課程簡介

本大綱根據(jù)2009版應用型人才培養(yǎng)方案制訂。

（一）教學對象：網(wǎng)絡工程、計算機科學與技術(shù)專業(yè)本科學生

（二）開課學期：第三學期

（三）課程類別：專業(yè)根基課

（四）考核方式：考試

（五）參考教材：《離散數(shù)學》第2版鄧輝文清華大學出版社2010.

主要參考書目：

[1]邵學才，葉秀明.離散數(shù)學[M].北京電子工業(yè)出版社，2009.

[2]邵志清，虞慧群.離散數(shù)學[M].北京電子工業(yè)出版社，2003.

[3]屈婉玲.離散數(shù)學習題解析[M].北京大學出版社，2008.

本課程的先修課程是高等數(shù)學、線性代數(shù)，后續(xù)課程包含數(shù)據(jù)構(gòu)造、數(shù)據(jù)庫原理

及應用、操作系統(tǒng)、數(shù)字邏輯、人工智能、算法分析與設計等。

二、教學基本要求與內(nèi)容安排

(一)教學目的與要求

離散數(shù)學是研究離散量的構(gòu)造及其相互關(guān)系的學科，它在各學科領(lǐng)域特別在

計算機科學領(lǐng)域有著廣泛的應用，同時離散數(shù)學也是計算機專業(yè)的許多專業(yè)課程

必不可少的先行課程。

本課程的教學目的旨在通過對離散數(shù)學的教學，讓學生不但可以掌握處理如

集合、代數(shù)構(gòu)造和圖等離散構(gòu)造的描述工具和方法，為后續(xù)課程的學習創(chuàng)造條件,

而且為學生今后提高專業(yè)理論水平，從事計算機行業(yè)的實際工作提供必備的抽象

思維和嚴格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的根

基。

(二)教學內(nèi)容安排

學時分配

教學教學重點難點

教學內(nèi)容實上其備注

要求方法(☆)(A)講課

險機他

第一局部數(shù)理邏輯講授15.5

1命題邏輯的基本概念2

1.1命題與聯(lián)接詞B☆1

1.2命題公式及其賦值A(chǔ)☆A1

2命題邏輯等值演算3.5

2.1等值式B☆1

2.2析取范式與合取范式A☆△1

2.3聯(lián)接詞的完備集C0.5

2.4可滿足性與消解法B1

3命題邏輯的推理理論2

3.1推理的形式構(gòu)造A☆1

3.2自然推理系統(tǒng)PBA1

4一階邏輯基本概念2

4.1一階邏輯命題符號化A☆1

4.2一階邏輯公式及解釋A☆A1

5一階邏輯等值演算與推

3

理

5.1一階邏輯等值式與置

A☆1

換規(guī)則

5.2一階邏輯前束范式A☆1

5.3一階邏輯的推理理論A☆△1

6數(shù)理邏輯在計算機中的

3

應用

第二局部集合論講授13

1集合代數(shù)2

1.1集合的基本概念B0.5

1.2集合的運算A☆0.5

1.3有窮集的計數(shù)C0.5

1.4集合恒等式A☆0.5

2二元關(guān)系6

2.1有序?qū)εc笛卡爾積A☆1

2.2二元關(guān)系A(chǔ)☆1

2.3關(guān)系的運算A☆1

2.4關(guān)系的性質(zhì)A☆△1

2.5關(guān)系的閉包A☆1

2.6等價關(guān)系與劃分A☆A1

3函數(shù)3

3.1函數(shù)的定義與性質(zhì)A☆0.5

3.2函數(shù)的復合與反函數(shù)A☆0.5

3.3雙射函數(shù)與集合的基

CA1

數(shù)

3.4一個系統(tǒng)的描述實

CA1

例

4集合論在計算機中的應

2

用

第三局部代數(shù)構(gòu)造講授61.5

1代數(shù)系統(tǒng)3

1.1二元運算及其性質(zhì)A☆1

1.2代數(shù)系統(tǒng)A☆1

1.3代數(shù)系統(tǒng)的同態(tài)與同

B△1

構(gòu)

2群與環(huán)3

2.1群的定義及其性質(zhì)A☆1

2.2循環(huán)群與置換群A☆△2

第四局部圖論講授12

1圖的基本概念2.5

1.1圖A☆0.5

1.2連通與回路A☆0.5

1.3圖的連通性A☆0.5

1.4圖的矩陣表示A☆0.5

1.5圖的運算A☆△0.5

2歐拉圖與哈密頓圖2

2.1歐拉圖A☆0.5

2.2哈密頓圖A☆0.5

2.3最短路問題與貨郎擔

C△1

問題

3樹1.5

3.1無向樹及其性質(zhì)A☆0.5

3.2生成樹A☆0.5

3.3根樹及其應用B0.5

4平面圖3

4.1平面圖的基本概念B0.5

4.2歐拉公式B☆0.5

4.3平面圖的判斷B1

4.4平面圖的對偶圖C1

5圖論在計算機中的應用3

（教學要求：A一熟練掌握；B一掌握；C—了解）

三、實驗內(nèi)容

本課程無實驗

制訂人〔簽字）：審核人［簽字）:

教學進度表

2012—2013學年第1學期

授課教師姓名_趙歡歡職稱助教周數(shù)16周方案學時48學時

授課專業(yè)_____網(wǎng)絡工程班級2011級講課48學時課堂討論上學時

課程名稱—離散數(shù)學實驗課_2_學時習題課_Q_學時

教材名稱_____離散數(shù)學其他環(huán)節(jié)0學時

出版社______清華大學出版社___________

其中

周

其

課

實

習教學內(nèi)容摘要

學

他

堂

周次講

驗

題（章節(jié)名稱、講述的內(nèi)容提要、實驗的名稱、課堂討論的題目

時

環(huán)

課

日期討

課

課等）

節(jié)

論

第一講集合、映射與運算（-）

1.1集合的基本概念

第一周

理論：集合、子集、號集、n元組、笛卡爾積

9月3日至44第二講集合、映射與運算（二）

9月9日

1.2映射的有關(guān)概念

理論：映射的定義、映射的性質(zhì)、逆映射、復合映射

第二周

第三講集合、映射與運算（三）

9月10日

221.3運算的定義和性質(zhì)

至9月16

理論：運算的定義、運算的性質(zhì)

日

第四講集合、映射與運算（四）

1.4集合的運算1.5集合的劃分1.6集合的對等

第三周理論：集合的并、交、差、補、對稱差等基本運算，集合的

9月17日劃分與覆蓋、集合對等、可數(shù)集合、不可數(shù)集合

44

至9月23第五講關(guān)系（-）

B2.1關(guān)系的概念

理論：n元關(guān)系的定義、2元關(guān)系、關(guān)系的定義域和值域、關(guān)

系的表示、函數(shù)的關(guān)系定義

第四周

第六講關(guān)系（二）

9月24日

2.1關(guān)系的運算

22

至9月30理論：關(guān)系的集合運算、逆運算、復合運算、關(guān)系的其他運算

0

國慶放假

第五周

第七講關(guān)系（三）

10月1日442.3關(guān)系的性質(zhì)2.4關(guān)系的閉包

至10月7

理論：關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性、

0

傳遞性；自反閉包r（R）、對稱閉包s（R）、傳遞閉包t（R）

第六周第八講關(guān)系（四）

10月8日2.5等價關(guān)系2.6相容關(guān)系2.7偏序關(guān)系

22

至10月14理論：等價關(guān)系的定義、等價類；相容關(guān)系的定義；偏序關(guān)系

日的定義、哈斯圖的、偏序集中的特殊元素

第九講命題邏輯（一）

3.1命題的有關(guān)概念3.2邏輯聯(lián)接詞

第七周理論：命題的定義與真值、原子命題和復合命題、各種邏輯連

10月15日接詞的含義，真假的判斷

44

至10月21第十講命題邏輯（二）

日3.3命題公式及其真宿表

理論：命題公式的定義、命題的符號化、命題公式的真值表、

命題公式的類型

第八周第十一講命題邏輯（三）

10月22日3.4邏輯等值的命題公式

22

至10月28理論：邏輯等值的定義、基本等值式、等值演算法、對偶

B原理

第十二講命題邏輯（四）

3.5命題公式的范式

第九周理論：命題公式的析取范式和合取范式的定義域求法

10月29日命題公式的主析取范式及主合取范式的定義和求法

44

至11月4第十三講命題邏輯（五）

03.7命題邏輯中的推理

理論：推理形式有效性的定義；基本推理規(guī)則；命題邏輯的

自然推理系統(tǒng)

第十周第十四講謂詞邏輯（一）

11月5日4.1個體、謂詞、量詞和函詞

22

至11月11理論：謂詞邏輯概念，謂詞的概念與表示，量詞的概念與表示，

日個體域，轄域，約束變元和自由變元的含義

第十五講謂詞邏輯（二）

4.2謂詞公式及命題的符號化4.3謂詞公式的解釋及類型

第十一周理論：謂詞公式的定義，將命題用用符號（個體，量詞，謂詞）

11月12來表示，消去量詞的邏輯等值式，永真式，科滿足式，永假式

44

日至11月友中性式的概念

18日第十六講謂詞邏輯（三）

4.4邏輯等值的謂詞公式4.5謂詞公式的前束范式

理論：謂詞公式等值的定義，基本等值式，前束范式

第十二周第十七講圖論［一）

11月19日6.1圖的基本概念6.2節(jié)點的度數(shù)6.3子圖，圖的運算和

22

至11月25圖同構(gòu)

0理論：圖的定義，鄰接，關(guān)聯(lián)，簡單圖，節(jié)點的度數(shù)，子圖

第十八講圖論（二）

第十三周

6.4路與回路6.5圖的連通性

11月26日

44理論內(nèi)容：路，回路，無向圖的連通性，無向連通圖的點連通

至12月2

度與邊連通度，有向圖的連通性

0第十九講圖論（三）

6.6圖的矩陣表示6.7賦權(quán)圖及最短路徑

理論內(nèi)容：圖的鄰接矩陣，可達矩陣，關(guān)聯(lián)矩陣，賦權(quán)圖，最

短路徑

第十四周第二十講圖論（四）

12月3日7.1歐拉圖

22

至12月9理論內(nèi)容：歐拉圖的有關(guān)概念，歐拉定理，中國郵遞員問題、

0Hami1ton圖

第二十一講圖論（五）

7.2無向樹7.3有向樹

第十五周理論內(nèi)容：樹的基本概念，最小生成樹，二叉樹的遍歷與

12月8日表達式的計算

44

至12月16第二十二講代數(shù)構(gòu)造（-）

5.1代數(shù)構(gòu)造簡介

理論內(nèi)容：代數(shù)構(gòu)造的定義，半群及獨異點，子代數(shù)，代數(shù)構(gòu)

造的同態(tài)與同構(gòu)

第十六周

第二十三講代數(shù)構(gòu)造（二）

月日

1217群的定義及性質(zhì)

至月225.2

1223理論內(nèi)容：群的有關(guān)概念，子群，群的同態(tài)

0

第十七周

12月24日第二十四講總復習

22

至12月30

H

系主任簽名：院長簽名：

年月日年月日

說明：1.本教學進度表由主講教師負責填寫，于每學期開學第一周內(nèi)送交教師所在系，經(jīng)領(lǐng)導審定、簽字后備查。

2.此表一式三份，其中，任課教師一份，教師所在系一份，教務處一份。

第一講：集合、映射和運算〔一〕

一、教學目標

1.掌握集合的概念與表示

2.理解子集、器集、n元組與笛卡兒積的概念

3.掌握子集，暴集，笛卡爾積的求法

二、重點與難點分析

1.重點：集合的概念，子集，幕集，笛卡爾積的概念及求法

2.難點：暴集

三、教學內(nèi)容與教學過程

L進展自我介紹（5分鐘）

姓名，聯(lián)系方式，專業(yè)方向。建議學生用電子郵件方式聯(lián)系。

2.進展課程簡介（10分鐘）

離散數(shù)學是研究離散量的構(gòu)造及相互之間關(guān)系的學科

是一門專業(yè)根基課，是數(shù)據(jù)構(gòu)造、操作系統(tǒng)、計算機組成原理、數(shù)據(jù)庫原理

等課程的數(shù)學根基。

特點：知識點集中，概念，定理多；方法性強；學數(shù)學就要做數(shù)學

成績評定：平時成績（到課情況，書面作業(yè)，平時測驗）占30%,期末考試占

70%

3.進入主題，開場第一講

(1)集合的有關(guān)概念(20分鐘)

①集合

定義：集合是具有某種特定性質(zhì)的對象聚集成的一個整體，通常用大寫字

母A,B,C,D表示。

例如：滁州學院全體學生

計算機與信息工程學院所有女生

常見的數(shù)的集合：N,N+,Z,Q,R,C

②元素

集合中的每一個對象稱為該集合的元素，通常用小寫字母a,b,c,d,x,等表示

例如：滁州學院的每個學生

計算機與信息工程學院的每個女生

N：0、1、2、3...

③集合的表示方法

列舉法:Z={...,-2,-1,0,1,2,…}

描述法：{x|x是自然數(shù)且x小于10}

遞歸法

U

文氏圖:

特殊集合：全集U,空集0

④元素與集合

xWA或％eA

|A|表示集合A中的元素個數(shù)

注意:集合中的元素可以是集合，如A={a,{a,b},b,c},|A|=4,{a,b}WA

注：集合中的元素無順序；集合中無重復元素

例：指出以下哪些是集合，哪些不是集合

中國人的集合；

百貨商店里好看的花布的集合；

1000以內(nèi)的素數(shù)的集合；

26個英文字母組成的集合；

這個班里高個子學生的集合；

直線y=2x-5上的點的集合。

(2)集合之間的關(guān)系

①子集115分鐘)

定義：假設A中的任意元素都屬于B,則A是B的子集，稱A包含于B或B

包含A,A^B,包括的兩層含義：包含與真包含AuB,A是B的真子

集

注意：屬于(元素與集合的關(guān)系)與包含于(集合與集合的關(guān)系)的區(qū)別

例：A={1,2例,4},B={2,4}

B^A或A衛(wèi)8

定理IT：0GA

定理1-2：⑴AcA;(自反性)

則A=B

(3)A.-8tC,則《qC(傳遞性)

用定義進展證明

定理1-3：A=B的充要條件是4=8,8=A

注：該定理是證明兩個集合相等的基本方法

該定理與定理1-2中的(2)的區(qū)別

例1-2

注：A中有一個元素不屬于C,則AzC,反證法是一種很好的方法

②累集(15分鐘)

定義：由X的所有子集組成的集合，P(X)={A|AqX}

例:x={l,2}

P(X)={0,{1},{2},{1,2}},

Y={a,b,c)

例1-3

注：假設|X|=n,P(x)的元素有：°；由一個元素構(gòu)成的子集；由兩個元素構(gòu)成的

子集；…由n個元素構(gòu)成的子集

計數(shù)的基本原理：

加法原理：圖示

乘法原理：圖示

定理1-4：假設|X|=n,|P(X)|=2n

證明：

加法原理：二項式定理：。+乃"=￡。"？?

乘法原理：“°

注：每個元素的參與與否構(gòu)成不同的子集

③n元組(5分鐘)

定義：論域U中選取的n個元素按照一定的順序排列，得到n元有序組，稱

n元組，記為：（xl,x2,x3,…,xn）或<xl,x2,x3,…,xn>

例：平面直角坐標系中點的坐標是2元組；空間直角坐標系中點的坐標是3元

組；n元組在數(shù)據(jù)構(gòu)造中是一個表

有序?qū)?，序偶?元組

注：（x,y）#（y,x）

④笛卡爾積（10分鐘）

定義:設ALA2,...,A”是集合，稱{（xl,x2,...,x〃）=1,2,為A1,A2,…An

的笛卡爾積（直積，叉積），記為：A1XA2X,...,A〃

例:A={a,b},B={l,2},

例1-4

注：Ax0=0xA=0

一般來說，AXB^BXA

定理1-5：假設|A|=m,|B|=n，則|AxB|=mXn

4.教學小結(jié)（5分鐘）

本講首先介紹了集合的概念與表示方法，接著介紹了集合之間的關(guān)系一一子

集與基集，n元組，笛卡爾積的概念及相關(guān)定理。

四'作業(yè)與實驗〔5分鐘〕

1.書面作業(yè)：習題1.11、2,3、7、10

2.上機作業(yè)：無

第二講：集合、映射和運算〔二〕

一'教學目標

1.掌握映射的概念與表示

2.理解映射的三種性質(zhì)：單射、滿射、雙射，會判斷某個具體映射是否具有

這些性質(zhì)

3.掌握逆映射的含義，復合映射的定義及性質(zhì)

二、重點與難點分析

1.重點：理解和判斷映射的三種性質(zhì)，逆映射，復合映射

2.難點：映射三種性質(zhì)的判斷，復合映射的性質(zhì)

三、教學內(nèi)容與教學過程

1.習題講解（10分鐘〕

2.上講內(nèi)容回憶（3分鐘）

集合的概念：集合、元素、集合的表示方法

集合間的關(guān)系：子集、募集、n元組、笛卡爾積

（1）映射的定義（15分鐘）

定義：對于A,B,假設存在對應法則f,對于VxeA,三唯一的B與它對應,

稱f是A到B的一個映射或一個函數(shù)。記為：f:A-B1圖示）

例：Ceilingfunction/g=gf

Floorfunction^」

取整函數(shù)［可

定義域：自變量X的取值范圍do時

值域：函數(shù)值y的取值范圍ranf

像：/(*)={/(幻次6*}為乂在映射￡下的像

原像：尸(X)=UI/W」W為Y在映射f下的原像

注：全函數(shù)即"°時=八；丁=/(幻為x在映射f下的像

8"=""：A-團：A到B的所有映射組成的集合

定理『6：|A|=m,|B|=n,則忸［=心(證明)

(2)映射的性質(zhì)

①單射(一對一映射)(10分鐘)

定義：Vxl,x2eA,/(xl)=/(x2)可推出xl=x2

或Vxl,x2eA,假設xlWx2,可得出/(xl)W/(X2)

例1-6：設廣NfN,/(x)=2x,則f是N到N的單射，試證明之。

證：對于Vxl,x2eN,由/(砌=/。2)得出2月=2X2,進而xl=x2

(使用定義證明)

②滿射(10分鐘)

定義：對于使得丫=￡a)

充要條件：ranf

例1-7：設/:ZfN,/(X)=N,則f是Z到N的滿射，試證明之。

證：對于VyeN,Wx=yeZ,顯然有y=/(x)

(使用定義證明)

③雙射(一一對應)(5分鐘)

定義:既單射又滿射

例1-8

例1-9：建設一個(0,1)到R的一一對應

解：/:(0,1)-R,/(x)=tan(x—1/2)乃

置換：A到A的雙射

(3)逆映射(逆函數(shù)，反函數(shù))(10分鐘)

定義：f:A-B,將f的方向逆轉(zhuǎn)后，得到的集合B到集合A的映射/一

定理1-7：f的逆映射存在的充要條件是f是雙射

(加以說明解釋)

注：假設f是雙射，則廣’也是雙射，且(廣|尸=/

例1T1：判斷所給出的映射是否有逆射，假設有，求出其逆映射

①f:R.R,于(x)=x?

②g:RfRJ(X)=%3

解:①?f(2)=f(-2)=4,

根據(jù)單射定義知f不是單射，進而其不是雙射，根據(jù)定理1-7知其不存

在逆映射

②顯然g是雙射，其逆映射為-R,gT(y)=V7

(4)復合映射(20分鐘)

定義:設廣A-8,g:8fC,對于VxeA,令〃(x)=g(/(x)),則h是A到C的

映射，h為f和g的復合映射或復合函數(shù)，記為/g(圖示)

注：(/g)(x)=g(/(x))

條件：f(A)=do/n(g)

例1-12

例1-13

注：一般來說即使/g和g/都有意義，也不能保證/g=g/成立

恒等映射(L)：f:A^A,f(x)=x

定理1-9：假設是雙射，則/f=【B

假設了:A-A是雙射，則/尸=廣f=IA

定理1-10：f:A^B,g:B^C

假設f和g是單射，則/g是單射(證明)

假設f和g是滿射，則/g是滿射1證明)

假設f和g是雙射，則/g是雙射且(/g)T=gi

定理1TL設/：Af8,g:B->C

假設/g是單射，則f是單射，但g不一定1證明)

假設/g是滿射，則g是滿射，而f不一定(證明)

定理1T2設—則(/g)h=f(gh)

4.教學小結(jié)(5分鐘)

本講首先介紹了映射(函數(shù))的定義及定義域、值域、像、原像等相關(guān)概念;

接著介紹了映射的三種性質(zhì)：單射，滿射，雙射；最后介紹了逆映射的定義及復

合映射的定義及其具有的相關(guān)性質(zhì)。

四'作業(yè)與實驗〔2分鐘〕

1.書面作業(yè)：習題1.21、2、6、11、14.

2.上機作業(yè)：無

第三講：集合、映射和運算〔三〕

一'教學目標

1.理解運算的定義

2.掌握運算的表示及常用運算

3.理解運算的性質(zhì)并能判斷具體運算是否具有某些性質(zhì)

二'重點與難點分析

1.重點：運算的定義，運算的性質(zhì)

2.難點：運算性質(zhì)的判定

三、教學內(nèi)容與教學過程

1.習題講解(5分鐘)

2.上講內(nèi)容回憶(5分鐘)

映射的定義

映射的性質(zhì)：單射，滿射，雙射

逆映射

復合映射

3.進入主題，開場第二講。

本講知識點概括

(1)運算的定義(25分鐘)

①定義：設4,A2,…,A”和B是集合，假設/：A1XA2X...XA〃->8,稱f為

Al,A2,...,An到B的n元運算。

A到B的n元運算，或A上的n元運考.AXAX...XA->B

A上的n元封閉運算(代數(shù)運算)：

n

/?AxAxxA->A*Vxl,x2,...x〃eA,有/(xl,x2,.,x〃)=yGA

例】判定最絕對值運算II、加法運算+、取大運算max是否是自然數(shù)集合N(Z)

上的代數(shù)運算。

解：=

例：判定減法運算-,取小運算min是否是自然數(shù)集合N上的代數(shù)運算。

解：

例：判斷數(shù)的加法運算是否是集上的代數(shù)運算

解:2'+22=6^2n

例：將十進制數(shù)273轉(zhuǎn)換成八進制

解：273=34x8+1,34=4x8+2,

②模運算

定義.f:ZN,f(x)-%(modm)x(mod/〃)是使x=q/n+r,0Wr成立

的整數(shù)r,即x除以m的余數(shù)。

例：16(mod3)、-8(mod5)>9(mod2)

模m加法，模m乘法

例：m=5,3+5(-5)=3,3?s(-5)=0

③最大公約數(shù)，最小公倍數(shù)

ViwZ,假設d仙且d|n,則d是m,n的公約數(shù),用gcd(m,n)表示m,n的最

大公約數(shù)

假設m|d且n|d,則d是m,n的公倍數(shù)，用lcm(m,n)表示m,n的

最小公倍數(shù)。

注：Ged與1cm分別記為［,］和(,)

gcd(/n,n)=gcd(|/7/|,|/?|)Hlcm(m,〃)=Icm(|〃z|,|〃|)

素因數(shù)分解：(對于大于1的正整數(shù)n都可以分解成一些素數(shù)乘積)

Euclid算法

例］-1/=彷〃+不0<4<〃，〃=%4+出0〈與V〃，…*=%-第-1+〃，〃_1=%”

假設g斯闔御鄰廂相才更素。

歐拉函數(shù)0(〃)：表示小于等于n且與n互素的正整數(shù)的個數(shù)

④運算表

給定集合A,則集合A上的1元或2元運算可以用運算表來表示

例:A={a,b,c},*

*abc

abca

babc

cbca

思考：A上的封閉的1元，2元，3元運算的個數(shù)是多少

3339327

⑵運算的性質(zhì)

①對合性〔5分鐘)

定義：設*是A上的一元代數(shù)運算，*(*x)=x，VxwA

例：VxGR:-(-x)=x

②幕等性(5分鐘)

幕等元：x*x-x,x&A

定義：A中的每個元素對于*都是基等元

例：

*123

1123

2232

3313

例：R,?？

③交換性(5分鐘)

定義：對于A上的二元運算*,Vx,yeA,均有％*丁=y*樂

例：R上的+具有交換性

R上的映射的復合運算/g?

④結(jié)合性(5分鐘)

定義:Vx,y,zeA:(x*y)*z=x*(y*z).

例:映射的復合運算(/g)h=f(g〃)具有結(jié)合性

R上的+具有結(jié)合性

R上的-

⑤單位元素（幺元素）（5分鐘）

定義：對于A上的二元運算*,He,使得對于Vx

例：R關(guān)于加法運算+的單位元素是0

R關(guān)于乘法運算?的單位元素是1

R關(guān)于減法運算■?的單位元素是

定理1-3：假設A關(guān)于*有單位元素，則單位元素是唯一的

證明:設el,e2是A關(guān)于*的單位元素，則el=el*e2=e2

⑥零元素（5分鐘）

定義：對于A上的二元運算*,me,使得對于V》

例:R關(guān)于乘法運算?的零元素是0

R關(guān)于減法運算-的零元素是

R關(guān)于加法運算?的零元素是

定理1-4：假設A關(guān)于*有零元素，則零元素是唯一的

證明：設el,e2是A關(guān)于*的零元素，則el=el*e2=e2

⑦逆元素（5分鐘）

前提：A關(guān)于二元運算*有單位元素e

定義：使得：

例：R上的加法運算+：x+（-x）=O=（-x）+x

R上的乘法運算?：X—=1=—x

XX

注：逆元不一定存在，存在不一定唯一，參見表1-5

定理1-5：假設A關(guān)于*運算有單位元素為e且*運算滿足結(jié)合律，假設對

于A中的x有左逆元y與右逆元z,則y=z,此逆元唯一

證明：y*x=e,x*z=e

y=y*e=y*（x*z）=（y*x）*z=e*z=z

⑧消去性（分鐘）

定義：假設A關(guān)于*有零元，則記為6,對于Vx,y,zeA,假設x。。

例1-31Z上的加法運算+和乘法運算.均滿足消去律.

⑨分配性（5分鐘）

定義：*,是A上的兩個二元運算，對于Vx,y,zeA

則稱*關(guān)于是可分配的

⑩吸收性（2分鐘）

定義：*，是A上的兩個二元運算，對于V%y，zeA

則稱*關(guān)于是可吸收的

?德摩根律（3分鐘）

定義：?是A上的一元運算，'是A上的兩個二元運算，對于Vx，y，zeA

4.教學小結(jié)（3分鐘）

本講首先介紹了運算的定義并介紹了幾種常用的運算，接著介紹了運算的性

質(zhì)：對合性、暴等性、交換性、結(jié)合性、單位元素、零元素、逆元素、消去性、

分配性、吸收性、德?摩根律，并結(jié)合之前所學知識講解運算的性質(zhì)。

四'作業(yè)與實驗〔2分鐘〕

1.書面作業(yè)：習題1.3：1、3、5、6、8

2.上機作業(yè)：無

第四講：集合、映射和運算〔四〕

一、教學目標

1.掌握集合的各種運算

2.理解各種集合運算所滿足的性質(zhì)

3.掌握集合的劃分與覆蓋的概念

4.了解集合的對等，集合的基數(shù)，可數(shù)集合等概念

二、重點與難點分析

1.重點：集合的運算一一并、交、補、差、對稱差

集合運算性質(zhì)

2.難點：集合運算等值式的證明，集合的對等、基數(shù)

三、教學內(nèi)容與教學過程

1.上講內(nèi)容回憶（5分鐘）

運算的定義

運算的性質(zhì)：對合性、幕等性、交換性、結(jié)合性、單位元素、零元

素、逆元素、消去性、分配性、吸收性、德?摩根律

2.進入主題、開場第四講

本講知識點概括

（1）集合的運算

①并運算（15分鐘）

定義：={%|A或％e8}.

定理1-16：AuB是包含A和B的最小集合

定理1T7：并運算滿足的性質(zhì)：

=（交換律）

（AuB）C=Au（BuC）（結(jié)合律）

AuA=A（幕等律）

AD0=0DA=A（0是u運算的單位元素）

A^JU=U<JA=U（U是u運算的零元素）

例1-38:設f:A->B,X,YcA,則證明：/（Xur）=/（X）u/（y）

X=X3n/(X)=/(XuY)

證明：rcxuy=>y(r)c/(Xuy)

.-./(x)u/(y)c/(xuy)

②交運算（15分鐘）

定義：AnB={x|%eAELXGB）

定理1-18：AcB是包含在4和6的最大集合

定理1-19：交運算滿足的性質(zhì)：

AnA=A（幕等律）

AryB=BryA（交換律）

（AcB）cC=Ac（BcC）（結(jié)合律）

Ac0=0cA=0（0是c運算的零元素）

AcU=UcA=A（U是c運算的單位元素）

例：

定理1-20：并運算與交運算之間滿足的性質(zhì)：

例1-41：AqBoAc3=AoAu3=3

證：AcB<=>A<JB=B

③補運算（10分鐘）

定義：A=Q（A）

例1-42：（A的補集依賴于全集U的選?。?/p>

A={a,b,c）

U={a,b,c,d}nA=uhdoe91

定理1-21：4°d="

AnA=0

定理1-22：德?摩根律:

P25：u,c「運算的重要性質(zhì)

④差運算(10分鐘)

定義：A-3={x|xeA&xeB}

有，s{a,b,c}-{b,c,d,e,f}^[a]

例1-43：

{b,c,d,e,f}-{a,b,c}=[d,e,f]

定理1-23：A-B=Ar>B

證明：VxeA-BoxwA,xe3<=>無GA,xeB<=>xeAcB

例1-45：證明：(A-B)-C=A-(BuC)

(A-B)-C=(AnB)-C=(AnB)nC

證：一一

=An(BnC)=A-(BuC)

例1-46：3=0

147.(A-B)u(A-C)=(AnB)u(AnC)

=Ac(、uO=AcBcC=A—(3cC)

⑤對稱差運算(10分鐘)

定義：A0B=(A-B)u(B-A)

例{a,b,c}?{b,c,d,e,f}=［a,d,e,f}

A③8=B③A(交換律)

定理1-24.A③0=0③A=A(0是③的單位元素)

'"(A?B)?C=A?(B?C)(結(jié)合律)

A0A=0

容斥原理

形式：|AuB|=|A|+|8|-|Ac8|.

或：|AnB|=|t7|-|A|-|B|+|AnB|

例：求1到1000之間［包含1和1000在內(nèi))既不能被5和6整

除數(shù)有多少個

解：|S|=1000

|A|=L1000/5j=200,|B|41000/6J=166

|AnB|=L1000/lcm(5,6)J=11000/33」=33

(2)集合的劃分與覆蓋(12分鐘)

①劃分

定義：乃={4|A,vA,ie/}

4w0,Vie/

其中：AcAj=0,Vzj

UA=A

iel

例1-53：設八={a,b,c},則A的所有不同的劃分分別為：

②覆蓋

設A是集合，由A的假設干非空子集構(gòu)成的集合稱為A的覆蓋，如果這些非空

子集的并等于A.

(3)集合的對等門0分鐘)

定義：/?存在雙射f:ATB.

例：(0,1)?R

集合的基數(shù)|山：無限集合A

假設集合力和8對等，則稱這兩個集合的基數(shù)一樣.例：|(0,1)|=因

可數(shù)集合：能與自然數(shù)集合N對等的集合

3.教學小結(jié)(2分鐘)