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

課程教案

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

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

一、課程簡(jiǎn)介

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

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

（二）開課學(xué)期：第三學(xué)期

（三）課程類別：專業(yè)基礎(chǔ)課

（四）考核方式：考試

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

主要參考書目：

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

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

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

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

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

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

（一）教學(xué)目的與要求

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

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

必不可少的先行課程。

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

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

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

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

礎(chǔ)。

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

學(xué)時(shí)分配

教學(xué)教學(xué)重點(diǎn):難點(diǎn)

教學(xué)內(nèi)容實(shí)上其備注

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

驗(yàn)機(jī)他

第一部分?jǐn)?shù)理邏輯講授15.5

1命題邏輯的基本概念2

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

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

2命題邏輯等值演算3.5

2.1等值式B☆1

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

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

2.4可滿足性與消解法B1

3命題邏輯的推理理論2

3.1推理的形式結(jié)構(gòu)A☆1

3.2自然推理系統(tǒng)PB△1

4一階邏輯基本概念2

4.1一階邏輯命題符號(hào)化A☆1

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

5一階邏輯等值演算與推

3

理

5.1一階邏輯等值式與置

A☆1

換規(guī)則

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

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

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

3

應(yīng)用

第二部分集合論講授13

1集合代數(shù)2

1.1集合的基本概念B0.5

1.2集合的運(yùn)算A☆0.5

1.3有窮集的計(jì)數(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)系的運(yùn)算A☆1

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

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

2.6等價(jià)關(guān)系與劃分A☆A(yù)1

3函數(shù)3

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

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

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

CA1

數(shù)

3.4一個(gè)電話系統(tǒng)的描述

CA1

實(shí)例

4集合論在計(jì)算機(jī)中的應(yīng)

2

用

第三部分代數(shù)結(jié)構(gòu)講授61.5

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

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

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

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

BA1

構(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圖的運(yùn)算A☆△0.5

2歐拉圖與哈密頓圖2

2.1歐拉圖A☆0.5

2.2哈密頓圖A☆0.5

2.3最短路問題與貨郎擔(dān)

C△1

問題

3樹1.5

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

3.2生成樹A☆0.5

3.3根樹及其應(yīng)用B0.5

4平面圖3

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

4.2歐拉公式B☆0.5

4.3平面圖的判斷B1

4.4平面圖的對(duì)偶圖C1

5圖論在計(jì)算機(jī)中的應(yīng)用3

（教學(xué)要求：A一熟練掌握；B一掌握；C一了解）

三、實(shí)驗(yàn)內(nèi)容

本課程無實(shí)驗(yàn)

制訂人（簽字）：審核人（簽字）:

教學(xué)進(jìn)度表

2012-2013學(xué)年第1學(xué)期

授課教師姓名趙歡歡職稱助教周數(shù)16周計(jì)劃學(xué)時(shí)48學(xué)時(shí)

授課專業(yè)網(wǎng)絡(luò)工程班級(jí)級(jí)

2011講課48學(xué)時(shí)課堂討論_0_學(xué)時(shí)

課程名稱______________離散數(shù)學(xué)________________實(shí)驗(yàn)課—學(xué)時(shí)習(xí)題課旦學(xué)時(shí)

教材名稱_______________離散數(shù)學(xué)________________

其他環(huán)節(jié)0學(xué)時(shí)

出版社____________清華大學(xué)出版社______________

其中

周

其

課

實(shí)

習(xí)教學(xué)內(nèi)容摘要

學(xué)

他

堂

周次講

驗(yàn)

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

時(shí)

課

討

日期環(huán)

課

課等）

論

節(jié)

第一講集合、映射與運(yùn)算（一）

集合的基本概念

第一周1.1

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

月日至n

9344第二講集合、映射與運(yùn)算（二）

9月9日

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

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

第二周第三講集合、映射與運(yùn)算（三）

月日

910運(yùn)算的定義和性質(zhì)

至月221.3

916理論：運(yùn)算的定義、運(yùn)算的性質(zhì)

0

第四講集合、映射與運(yùn)算（四）

1.4集合的運(yùn)算1.5集合的劃分1.6集合的對(duì)等

第三周理論：集合的并、交、差、補(bǔ)、對(duì)稱差等基本運(yùn)算，集合的劃

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

44

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

02.1關(guān)系的概念

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

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

第四周

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

月日

924關(guān)系的運(yùn)算

至月2.1

93022理論：關(guān)系的集合運(yùn)算、逆運(yùn)算、復(fù)合運(yùn)算、關(guān)系的其他運(yùn)算

0

國(guó)慶放假

第五周

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

10月1日

2.3關(guān)系的性質(zhì)2.4關(guān)系的閉包

至月44

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

S

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

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

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

22

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

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

第七周第九講命題邏輯（-）

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

44

至10月21理論：命題的定義與真值、原子命題和復(fù)合命題、各種邏輯連

0接詞的含義，真假的判斷

第十講命題邏輯（二）

3.3命題公式及其真值表

理論：命題公式的定義、命題的符號(hào)化、命題公式的真值表、

命題公式的類型

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

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

22

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

0理

第十二講命題邏輯（四）

3.5命題公式的范式

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

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

44

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

日3.7命題邏輯中的推理

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

然推理系統(tǒng)

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

11月5日4.1個(gè)體、謂詞、量詞和函詞

22

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

H個(gè)體域，轄域，約束變?cè)妥杂勺冊(cè)暮x

第十五講謂詞邏輯（二）

4.2謂詞公式及命題的符號(hào)化4.3謂詞公式的解釋及類型

第十一周理論：謂詞公式的定義，將命題用用符號(hào)（個(gè)體，量詞，謂詞）

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

44

日至11月友中性式的概念

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

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

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

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

月日?qǐng)D的基本概念節(jié)點(diǎn)的度數(shù)子圖，圖的運(yùn)算和圖

1119226.16.26.3

至11月25同構(gòu)

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

第十八講圖論（二）

6.4路與回路6.5圖的連通性

第十三周理論內(nèi)容：路，回路，無向圖的連通性，無向連通圖的點(diǎn)連通

11月26日度與邊連通度，有向圖的連通性

44

至12月2第十九講圖論（三）

06.6圖的矩陣表示6.7賦權(quán)圖及最后藍(lán)徑

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

短路徑

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

12月3日7.1歐拉圖

22

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

0Hamilton圖

第二十一講圖論（五）

7.2無向樹7.3有向樹

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

12月8日達(dá)式的計(jì)算

44

至12月16第二十二講代數(shù)結(jié)構(gòu)（一）

5.1代數(shù)結(jié)構(gòu)簡(jiǎn)介

理論內(nèi)容：代數(shù)結(jié)構(gòu)的定義，半群及獨(dú)異點(diǎn)，子代數(shù)，代數(shù)結(jié)

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

第十六周

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

12月17日

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

至月5.2

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

0

第十七周

12月24日第二十四講總復(fù)習(xí)

22

至12月30

B

系主任簽名：院長(zhǎng)簽名：

年月日年月日

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

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

第一講：集合、映射和運(yùn)算（一）

一'教學(xué)目標(biāo)

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

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

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

二'重點(diǎn)與難點(diǎn)分析

1.重點(diǎn)：集合的概念，子集，累集，笛卡爾積的概念及求法

2.難點(diǎn)：幕集

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

1.進(jìn)行自我介紹（5分鐘）

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

2.進(jìn)行課程簡(jiǎn)介（10分鐘）

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

是一門專業(yè)基礎(chǔ)課，是數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計(jì)算機(jī)組成原理、數(shù)據(jù)庫(kù)原理

等課程的數(shù)學(xué)基礎(chǔ)。

特點(diǎn)：知識(shí)點(diǎn)集中，概念，定理多；方法性強(qiáng)；學(xué)數(shù)學(xué)就要做數(shù)學(xué)

成績(jī)?cè)u(píng)定：平時(shí)成績(jī)（到課情況，書面作業(yè)，平時(shí)測(cè)驗(yàn)）占30%,期末考試占

70%

3.進(jìn)入主題，開始第一講

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

①集合

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

母A,B,C,D表示。

例如：滁州學(xué)院全體學(xué)生

計(jì)算機(jī)與信息工程學(xué)院所有女生

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

②元素

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

例如：滁州學(xué)院的每個(gè)學(xué)生

計(jì)算機(jī)與信息工程學(xué)院的每個(gè)女生

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

③集合的表示方法

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

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

遞歸法

文氏圖：

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

④元素與集合

xdA或A

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

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

注：集合中的元素?zé)o順序；集合中無重復(fù)元素

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

中國(guó)人的集合；

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

1000以內(nèi)的素?cái)?shù)的集合；

26個(gè)英文字母組成的集合；

這個(gè)班里高個(gè)子學(xué)生的集合；

直線y=2x-5上的點(diǎn)的集合。

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

①子集（15分鐘）

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

含A,A^B,包括的兩層含義：包含與真包含（AWB）,Au3,A是B的真子集

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

例:A={1,2例,4},B42,4}

B=A或4=8

定理IT：0cA

定理1-2：⑴A=（自反性）

（2）AqB,BqA,則A=B

（3）A=B,8=C〃iJA=C（傳遞性）

用定義進(jìn)行證明

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

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

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

例1-2

注：A中有一個(gè)元素不屬于C,則A<zC,反證法是一種很好的方法

②幕集(15分鐘)

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

例：x={l,2}

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

Y={a,b,c)

P(X)={0,{a},,{c},{a,b},[a,c},{b,c},{a,b,c}}

例1-3

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

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

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

加法原理：圖示

乘法原理：圖示

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

證明：

加法原理：二項(xiàng)式定理：(x+y)"=￡c,Kyf

l+C；,+C；+...++C^=(1+1)"=2"

乘法原理：：2x2x...x2=2".

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

③n元組(5分鐘)

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

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

例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)是2元組；空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)是3

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

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

注：(x,y)W(y,x)

④笛卡爾積(10分鐘)

定義.設(shè)加是集合稱A.i=1,2,為

Al,A2,...An的笛卡爾積(直積，叉積)，記為：A1XA2X,...,A〃

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

例1-4

注：Ax0-0xA-0

一般來說，AXB^BXA

定理1-5：若|A|=m,|B|=n，則|A*8|=mXn

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

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

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

四'作業(yè)與實(shí)驗(yàn)（5分鐘）

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

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

第二講：集合、映射和運(yùn)算（二）

一'教學(xué)目標(biāo)

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

2.理解映射的三種性質(zhì)：?jiǎn)紊?、滿射、雙射，會(huì)判斷某個(gè)具體映射是否具有

這些性質(zhì)

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

二'重點(diǎn)與難點(diǎn)分析

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

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

三'教學(xué)內(nèi)容與教學(xué)過程

1.習(xí)題講解（10分鐘）

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

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

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

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

定義：對(duì)于A,B,若存在對(duì)應(yīng)法則f,對(duì)于^^人，三唯一的丁€8與它對(duì)應(yīng),

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

例：Ceilingfunctionfg=gf

Floorfunction］司

取整函數(shù)［H

定義域：自變量X的取值范圍do時(shí)

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

像:/（*）="（幻|"€乂｝為乂在映射￡下的像

原像：尸（X）=｛x"（x）U｝為Y在映射f下的原像

注：全函數(shù)即而何1=A；丁=/*）為x在映射f下的像

A

B=｛f\f-.A^B｝：A到B的所有映射組成的集合

定理1-6：|A|=m,|B|=n,則=（證明）

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

①單射（一對(duì)一映射）（10分鐘）

定義：Vxl,x2eA,/（xl）=/（x2）可推出xl=x2

或2GA,若xlWx2,可得出了（xl）w/（%2）

例1-6：設(shè)廣NrNJ（x）=2x,則f是N到N的單射，試證明之。

證：對(duì)于―eN,由/（只）=/（%2）得出2H=2X2,進(jìn)而xl=x2

（使用定義證明）

②滿射（10分鐘）

定義：對(duì)于VycBJxeA,使得丫=￡6）

充要條件：ranf=B

例1-7：設(shè)/:ZfNJ（x）=兇，則f是Z到N的滿射，試證明之。

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

(使用定義證明)

③雙射(——對(duì)應(yīng))(5分鐘)

定義:既單射又滿射

例1-8

例1-9：建立一個(gè)(0,1)到R的——對(duì)應(yīng)

解：/:(O,1)-R,/(x)=tan(x—1/2)萬(wàn)

置換：A到A的雙射

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

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

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

(加以說明解釋)

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

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

①f:R^R,f(x)=x2

②g:RrR,f(x)=x3

解：①?.?f(2)=f(-2)=4,

.??根據(jù)單射定義知f不是單射，進(jìn)而其不是雙射，根據(jù)定理廠7知

其不存在逆映射

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

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

定義:設(shè)廠Af8,g：8fC,對(duì)于VxeA,令〃(幻=g(/*)),則h是A

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

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

條件：f(A)工dom(g)

例1-12

例1-13

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

恒等映射(h)：/：A-A,/(幻=x

定理1-9：若是雙射，則/f-'=IA.f'f=IB

定理ITO：f:AiB,g:BfC

若f和g是單射，貝g是單射（證明）

若f和g是滿射，貝Mg是滿射（證明）

若f和g是雙射，則/g是雙射且（/g）T=gT廣'

定理1T1：設(shè)f8,g:8-C

若/g是單射，則f是單射，但g不一定（證明）

定理1T2設(shè)/：Af-〃：C一°,則(/g)h=f(gk)

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

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

接著介紹了映射的三種性質(zhì)：?jiǎn)紊洌瑵M射，雙射；最后介紹了逆映射的定義及復(fù)

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

四、作業(yè)與實(shí)驗(yàn)（2分鐘）

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

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

第三講：集合、映射和運(yùn)算（三）

一'教學(xué)目標(biāo)

1.理解運(yùn)算的定義

2.掌握運(yùn)算的表示及常用運(yùn)算

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

二'重點(diǎn)與難點(diǎn)分析

1.重點(diǎn)：運(yùn)算的定義，運(yùn)算的性質(zhì)

2.難點(diǎn)：運(yùn)算性質(zhì)的判定

三'教學(xué)內(nèi)容與教學(xué)過程

1.習(xí)題講解(5分鐘)

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

映射的定義

映射的性質(zhì)：?jiǎn)紊洌瑵M射，雙射

逆映射

復(fù)合映射

3.進(jìn)入主題，開始第二講。

本講知識(shí)點(diǎn)概括

(1)運(yùn)算的定義(25分鐘)

①定義：設(shè)4，A2,“.,A〃和B是集合，若/：AlxA2x...xA〃-8,稱f為

Ai,A2,...,An至B的n元運(yùn)算。

n

A到B的n元運(yùn)算，或A上的n元運(yùn)孽彳黑屋…_>B

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

f-AxAxxAfA，Vxl，x2,...x〃eA^/(xl,x2,...,x")=yeA

例,：判定M絕對(duì)值運(yùn)算II、加法運(yùn)算+、取大運(yùn)算max是否是自然數(shù)集合N(Z)

上的代數(shù)運(yùn)算。

解：VxeN=W=xeN

Vx,yeNnx+ywN

\fx\,x2,...xneNnmax(xl,x2,…GN

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

解：

例：判斷數(shù)的加法運(yùn)算是否是集合人={2"|nSN}上的代數(shù)運(yùn)算？

解：21+2?=6e2"

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

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

n273=34x8+1=((4x8)+2)x8+l

=4X82+2X8+1

273=(421)8

②模運(yùn)算

定義：/:ZfN,/(x)=x(mod〃z)x(modm)是使x=q/w+r,O4廠＜〃？成立

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

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

模m加法，模m乘法

x+吁=(x+y)(modm)

x?my=(x?y)(modm)

例：m=5,3+5（—5）=3,3?5（-5）=0

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

Vm,"eZ,若d|m且d|n,則d是m,n的公約數(shù)，用gcd（m,n）表示m,n的最大

公約數(shù)

Vm,"eZ,若皿d且n|d,則d是m,n的公倍數(shù)，用lcm（m,n）表示m,n的最

小公倍數(shù)。

注：Gcd與1cm分別記為［,］和（，）

gcd（，〃，〃）=gcd（|m|,|川）且1cm（加,〃）=lcm（依

素因數(shù)分解：（對(duì)于大于1的正整數(shù)n都可以分解成一些素?cái)?shù)乘積）

m=p；P2PkGZ+i,n=p：P2PkGZ+'

（見為素?cái)?shù)，為非負(fù)整數(shù)）

gcd（m,ri）=琢必力）.產(chǎn).）...球訕“風(fēng)）

（一）「廣（3）…戊風(fēng)小外）

Euclid算法

機(jī)=4〃+{,0<。<n,n=q2rx+r2,Q<r2<4<n,...rt_2+*〃Tf

rk=gcd（m,ri）=mx+ny

例1-19

若gcd（m,n）=l,稱m和n互素。

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

④運(yùn)算表

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

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

*abc

abca

babc

cbca

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

3339327

（2）運(yùn)算的性質(zhì)

①對(duì)合性（5分鐘）

定義：設(shè)*是A上的一元代數(shù)運(yùn)算，*（*x）=x，VxeA

例：Vxe:-（—%）=x

（A-I）T=AW），=A

②幕等性（5分鐘）

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

定義：A中的每個(gè)元素對(duì)于*都是嘉等元

例：

*123

1123

2232

3313

例：R,,?

③交換性（5分鐘）

定義：對(duì)于A上的二元運(yùn)算*,Vx,yeA,均有％*，=）'*

例：R上的+具有交換性

R上的映射的復(fù)合運(yùn)算/g?

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

定義：Vx,y,zeA:（x*y）*z=x*（y*z）.

例:映射的復(fù)合運(yùn)算（/g）h=f（g/i）具有結(jié)合性

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

R上的-?

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

定義：對(duì)于A上的二元運(yùn)算*,3e,使得對(duì)于Vx

x*e-x.e*x—x.

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

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

R關(guān)于減法運(yùn)算-的單位元素是？

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

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

⑥零元素（5分鐘）

定義：對(duì)于A上的二元運(yùn)算*,三。，使得對(duì)于Vx

e*x=0.x*e=e.

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

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

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

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

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

⑦逆元素（5分鐘）

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

定義：xeAJyeA,使得：

x*y=e.y*x—e.

例：R上的加法運(yùn)算+：x+(-x)=O=(-x)+x

R上的乘法運(yùn)算?：X—=1=—x

XX

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

定理1-5：若A關(guān)于*運(yùn)算有單位元素為e且*運(yùn)算滿足結(jié)合律，若對(duì)于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,對(duì)于Vx,y,zeA,若xw。

x*y=x*z=y=z.

y*x=z*x=y=z.

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

⑨分配性(5分鐘)

定義：*,是A上的兩個(gè)二元運(yùn)算，對(duì)于Vx,y,zeA

x*(yoz)=(x*y)o(x*z).(y°z)*x=(y*x)o(z*x).

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

⑩吸收性(2分鐘)

定義：*，是A上的兩個(gè)二元運(yùn)算，對(duì)于V%y，zeA

x*(xoy)=x.(y。冗)*工=x.

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

?德摩根律(3分鐘)

定義：?是A上的一元運(yùn)算，*，是A上的兩個(gè)二元運(yùn)算，對(duì)于Vx，y，zeA

?(x*y)=(?%)。(?y).?(%。y)=(7)*(?y).

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

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

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

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

四、作業(yè)與實(shí)驗(yàn)(2分鐘)

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

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

第四講：集合、映射和運(yùn)算（四）

一'教學(xué)目標(biāo)

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

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

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

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

二'重點(diǎn)與難點(diǎn)分析

1.重點(diǎn)：集合的運(yùn)算一一并、交、補(bǔ)、差、對(duì)稱差

集合運(yùn)算性質(zhì)

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

三'教學(xué)內(nèi)容與教學(xué)過程

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

運(yùn)算的定義

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

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

2.進(jìn)入主題、開始第四講

本講知識(shí)點(diǎn)概括

（1）集合的運(yùn)算

①并運(yùn)算（15分鐘）

定義：=A或％eB}.

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

VC

定理1-17：并運(yùn)算滿足的性質(zhì)：

（交換律）

（AuB）uC=A<J（8DC）（結(jié)合律）

=A（基等律）

AD0=0DA=A（。是u運(yùn)算的單位元素）

A<JU=U<JA=U（。是u運(yùn)算的零元素）

例1-38:設(shè)f:A->B,X,YcA,則證明：/（XuF）=/（X）u/（y）

XqXuyn/（x）1/（xuy）

證明：ycxuy=>f（Y）c/（XuY）

V/?e/(Xuy)^3ae(Xuy):/j=/(a)

aeX=>/>=/(a)e/(X)

agYnb=f(a)wf(Y)

：.bwf(X)2f(Y)

/(Xuy)c/(X)u/(D

②交運(yùn)算(15分鐘)

定義：A(~\B-{X\XE：AUxeB}

定理1T8：AcB是包含在1和8的最大集合

VCcA,C￡B=>CcAnB

定理1T9：交運(yùn)算滿足的性質(zhì)：

Ar>A=A(嘉等律)

AryB=Br\A(交換律)

(Ac6)cC=Ac(3cC)(結(jié)合律)

Ac0=0cA=0(。是c運(yùn)算的零元素)

AcU=UcA=A(U是c運(yùn)算的單位元素)

例：

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

Au(AcB)=A(u對(duì)c可吸收)

An(AoB)=A(c對(duì)口可吸收)

4口(3門。)=(4。8)門(4口。)(口對(duì)門可分配)

AC(8UC)=(AC8)D(4CC)(C對(duì)?？煞?/p>