集合映射與運(yùn)算

集合映射與運(yùn)算使用教材書(shū)名：離散數(shù)學(xué)（第三版）“十一五”國(guó)家規(guī)劃教材主編：鄧輝文出版社：清華大學(xué)出版社講授：第1章_第6章第2頁(yè),共76頁(yè)，2024年2月25日，星期天參考書(shū)目1、邵學(xué)才.離散數(shù)學(xué)（第二版）.清華大學(xué)出版社.(應(yīng)用型規(guī)劃教材)2、周忠榮.離散數(shù)學(xué)及其應(yīng)用.清華大學(xué)出版社.3、王禮萍.離散數(shù)學(xué)簡(jiǎn)明教程.清華大學(xué)出版社.(高職教材)4、耿素云,屈婉玲.離散數(shù)學(xué)（修訂版）.高等教育出版社.(十五規(guī)劃教材，北京大學(xué))第3頁(yè),共76頁(yè)，2024年2月25日，星期天考核方式期末成績(jī)=平時(shí)成績(jī)+期末試卷成績(jī)平時(shí)成績(jī)20分平時(shí)成績(jī)=出勤+小測(cè)驗(yàn)+作業(yè)出勤=10

小測(cè)驗(yàn)=5

作業(yè)=5（獨(dú)立、自主）期末試卷成績(jī)80分。第4頁(yè),共76頁(yè)，2024年2月25日，星期天研究對(duì)象

離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互之間關(guān)系的一門(mén)學(xué)科，它與當(dāng)今計(jì)算機(jī)所處理的對(duì)象相一致。

離散數(shù)學(xué)是研究計(jì)算機(jī)科學(xué)的基本數(shù)學(xué)工具和最合適的理論手段；是計(jì)算機(jī)類(lèi)專(zhuān)業(yè)的重要課程。第5頁(yè),共76頁(yè)，2024年2月25日，星期天學(xué)習(xí)目的

離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)的一門(mén)核心課程，不是一門(mén)純數(shù)學(xué)課程，而是計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課程。

1、為后繼課程提供必要的數(shù)學(xué)基礎(chǔ)

2、培養(yǎng)學(xué)生抽象思維能力和嚴(yán)密的邏輯推理能力。第6頁(yè),共76頁(yè)，2024年2月25日，星期天基本內(nèi)容（1）一、集合與關(guān)系：是離散數(shù)學(xué)研究的重點(diǎn)內(nèi)容

1、Chapter1集合、映射與運(yùn)算：集合是現(xiàn)代數(shù)學(xué)的最基本概念，映射是現(xiàn)代數(shù)學(xué)的基本概念，是本書(shū)的重點(diǎn)。

2、Chapter2關(guān)系：是刻畫(huà)聯(lián)系的數(shù)學(xué)模型。二、數(shù)理邏輯：研究思維形式及思維規(guī)律尤其是推理的學(xué)科。

1、Chapter3命題邏輯：研究的主要對(duì)象是命題。

2、Chapter4謂詞邏輯：研究原子命題的內(nèi)部形式結(jié)構(gòu)及其邏輯關(guān)系。第7頁(yè),共76頁(yè)，2024年2月25日，星期天基本內(nèi)容（2）三、代數(shù)結(jié)構(gòu)：研究有一般元素組成的集合上的運(yùn)算，以及運(yùn)算滿(mǎn)足一些給定的數(shù)學(xué)結(jié)構(gòu)的性質(zhì)。

1、Chapter5(1)代數(shù)結(jié)構(gòu)：計(jì)算機(jī)系統(tǒng)本身就是一種代數(shù)結(jié)構(gòu)。

2、Chapter5(2)群、環(huán)和域：在形式語(yǔ)言與自動(dòng)機(jī)理論學(xué)科中發(fā)揮作用。

3、Chapter5(3)格與布爾代數(shù)：在自動(dòng)推理和邏輯電路設(shè)計(jì)的分析和優(yōu)化等問(wèn)題中得到應(yīng)用。四、圖論：廣泛應(yīng)用與解決現(xiàn)實(shí)問(wèn)題。

1、Chapter6圖論：主要研究數(shù)據(jù)結(jié)構(gòu)中圖的相關(guān)性質(zhì)。

2、Chapter7幾類(lèi)特殊的圖：介紹生活和研究中實(shí)際的圖論的問(wèn)題。第8頁(yè),共76頁(yè)，2024年2月25日，星期天第1章集合、映射與運(yùn)算1.1集合的有關(guān)概念1.2映射的有關(guān)概念1.3運(yùn)算的定義及性質(zhì)1.4集合的運(yùn)算1.5集合的劃分與覆蓋第9頁(yè),共76頁(yè)，2024年2月25日，星期天第1章集合、映射與運(yùn)算集合是現(xiàn)代數(shù)學(xué)的最基本概念.映射又稱(chēng)為函數(shù),它是現(xiàn)代數(shù)學(xué)的基本概念,可以借助于集合下定義.運(yùn)算本質(zhì)上是映射,但有其特殊性.(關(guān)系也是集合)集合、映射、運(yùn)算及關(guān)系是貫穿于本書(shū)的一條主線(xiàn).第10頁(yè),共76頁(yè)，2024年2月25日，星期天1.1.1集合

集合（set）:是指具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體。元素（element）：集合中的每一個(gè)對(duì)象稱(chēng)為集合的元素。通常用大寫(xiě)字母表示集合，用小寫(xiě)字母表示集合中的元素。在數(shù)學(xué)中常用{}表示整體.在討論集合時(shí)，為避免出現(xiàn)某些悖論，應(yīng)指定討論范圍，這個(gè)范圍也是一個(gè)集合，稱(chēng)為全集或論域，記作U。文氏圖用矩形框表示。A第11頁(yè),共76頁(yè)，2024年2月25日，星期天隸屬關(guān)系集合與集合中元素的關(guān)系——隸屬關(guān)系給定一個(gè)集合A，（1）若x是集合A中的元素，記作x

A，讀作x屬于A(yíng)；（2）若x不是集合A中的元素，則記作x

A，讀作x不屬于A(yíng)。說(shuō)明：

讀作屬于；

讀作不屬于例:A={a,b,c,d}，則有b

A，e

A．第12頁(yè),共76頁(yè)，2024年2月25日，星期天特殊集合表示幾類(lèi)特殊集合的表示：N自然數(shù)集合,包括數(shù)0；Z整數(shù)集合；Q有理數(shù)集合；R實(shí)數(shù)集合；C復(fù)數(shù)集合.第13頁(yè),共76頁(yè)，2024年2月25日，星期天集合的表示⑴列舉法就是把集合中的所有元素一一列舉出來(lái)，或列出足夠多的元素以反映出集合中成員的特征，元素之間用逗號(hào)分開(kāi)，并用花括號(hào)括起來(lái)。如：A={a1，a2，……，an}B={0，2，4，6，……，2n，……}。第14頁(yè),共76頁(yè)，2024年2月25日，星期天集合的表示⑵描述法是指把集合中的元素所滿(mǎn)足的條件或具有的性質(zhì)描述出來(lái)，即將條件或性質(zhì)用文字或符號(hào)在花括號(hào)內(nèi)豎線(xiàn)后面表示出來(lái)。一般形式為：

A={x|x滿(mǎn)足的條件或具有的性質(zhì)}如：A={x|x–1=0，x

R}B={x|x是英文字母，x元音}第15頁(yè),共76頁(yè)，2024年2月25日，星期天集合的表示⑶遞歸法是指通過(guò)計(jì)算規(guī)則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構(gòu)造其他元素的方法；最后強(qiáng)調(diào)有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設(shè)a0=1,a1=1,an+1=an+an-1,A={a0,a1,a2,……}={ak

k

0}。第16頁(yè),共76頁(yè)，2024年2月25日，星期天集合的表示⑷巴科斯范式(BNF)表示法

BNF常用來(lái)定義高級(jí)程序設(shè)計(jì)語(yǔ)言的標(biāo)識(shí)符或表達(dá)式集合。⑸文氏圖法(JohnVenn)

首先畫(huà)一個(gè)大矩形表示全集，然后在矩形內(nèi)畫(huà)一些圓，用圓的內(nèi)部表示集合，集合之間的相互關(guān)系和有關(guān)的運(yùn)算可以用文氏圖給予形象的描述。第17頁(yè),共76頁(yè)，2024年2月25日，星期天集合的特性⑴確定性確定性是指一旦給定了集合A，對(duì)于任意元素a，我們就可以準(zhǔn)確地判定a是否在A(yíng)中。如：A={x|x是自然數(shù)，且x<100}則必有30

A，101

A⑵互異性互異性是指集合中的元素之間是彼此不同的，即集合中不允許出現(xiàn)重復(fù)的元素。如：集合A={a,b,c,c,b,d}應(yīng)為A={a,b,c,d}第18頁(yè),共76頁(yè)，2024年2月25日，星期天集合的特性⑶無(wú)序性無(wú)序性是指集合中的元素之間沒(méi)有次序關(guān)系。在不特別說(shuō)明情況下，我們所討論的集合都不是多重集。如：

A={a,{a,b},b,c}

與A={a,b,c,{a,b}}相同⑷抽象性抽象性是指集合中元素是抽象的，甚至可以是集合。如：A={a,{a,b},b,c}；第19頁(yè),共76頁(yè)，2024年2月25日，星期天相關(guān)概念有限集由有限個(gè)元素a1,…,an組成的集合稱(chēng)為有限集?；鶖?shù)（或勢(shì)）若集合A是有限集，則集合A中的元素個(gè)數(shù)稱(chēng)為集合A的基數(shù)（或勢(shì)），通常記作|A|。無(wú)限集無(wú)限集是指由無(wú)限個(gè)元素組成的集合?？占缓腥魏卧氐募鲜强占?。記

或{}。第20頁(yè),共76頁(yè)，2024年2月25日，星期天1.1.2子集子集——集合間的包含關(guān)系

給定兩個(gè)集合A和B，若A中的任意元素都屬于B，則稱(chēng)A是B的子集，或稱(chēng)A包含在B，或稱(chēng)B包含A，通常記作A

B，或B

A。（若任意a

A，必有a

B，則A

B）若A不是B的子集，則集合A中至少有一個(gè)元素不屬于B。第21頁(yè),共76頁(yè)，2024年2月25日，星期天子集定理1-1對(duì)于任意的集合A，有

A。1-2設(shè)A、B、C是任意的集合，則有⑴自反性：AA.（任意集合是其子集）⑵反對(duì)稱(chēng)性：AB,BAA=B.⑶傳遞性：AB,BCAC.1-3A=B的充要條件是AB且BA第22頁(yè),共76頁(yè)，2024年2月25日，星期天真子集若A

B，且A

B，則稱(chēng)A是B的真子集，通常記作A

B。（若A是B的真子集，則B中至少有一個(gè)元素不屬于A(yíng)）注意區(qū)別：與的不同問(wèn)題：由AB,BC可否得出AC?解：不成立,如A={a,b},B={a,b,c},C={a,{a,b,c}}.第23頁(yè),共76頁(yè)，2024年2月25日，星期天1.1.3冪集設(shè)X是一個(gè)集合，由X的所有子集作為元素構(gòu)成的集合稱(chēng)為X的冪集，記以P(X)或2X。定理

設(shè)A是一個(gè)有限集且|A|=n，則|P(A)|=2n第24頁(yè),共76頁(yè)，2024年2月25日，星期天冪集示例X={a,b}P(X)={,{a},,{a,b}}.P({})={,{}}.習(xí)題1.1(7)第25頁(yè),共76頁(yè)，2024年2月25日，星期天1.1.4n元組將n個(gè)元素x1,x2,…,xn按一定順序排列就得到一個(gè)n元(有序)組.記為：n=2n=3一般說(shuō)來(lái)(x,y)

(y,x).第26頁(yè),共76頁(yè)，2024年2月25日，星期天序偶2元組常稱(chēng)為有序?qū)蛐蚺?注意區(qū)別(a,b,c),((a,b),c),(a,(b,c))的不同.第27頁(yè),共76頁(yè)，2024年2月25日，星期天1.1.5笛卡兒積設(shè)A1，A2，…，An是集合，稱(chēng)集合為A1，A2，…，An的笛卡兒積（直積，叉積）第28頁(yè),共76頁(yè)，2024年2月25日，星期天笛卡兒積定理

A=B=例：設(shè)A={a,b},B={1,2},C={

},求A

B,B

A,A

B

C,B

C.解：A

B={(a,1),(b,1),(a,2),(b,2)}.BA={(1,a),(1,b),(2,a),(2,b)}.

A

B

C={(a,1,),(b,1,),(a,2,),(b,2,)}.B

C={(1,),(2,)}第29頁(yè),共76頁(yè)，2024年2月25日，星期天1.2映射的有關(guān)概念映射就是函數(shù)，研究的是任意兩個(gè)集合之間的一種對(duì)應(yīng)關(guān)系。映射是現(xiàn)代數(shù)學(xué)中的基本概念。函數(shù)在信息科學(xué)中得到了充分的應(yīng)用。與集合一樣，映射貫穿本書(shū)的所有內(nèi)容，深刻理解映射的有關(guān)內(nèi)容，對(duì)于其他內(nèi)容的學(xué)習(xí)是至關(guān)重要的。第30頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.1映射的定義任意給定兩個(gè)集合A和B，若存在對(duì)應(yīng)法則f

，使得對(duì)于任意x

A，均存在唯一的y

B與它對(duì)應(yīng)，則稱(chēng)f是集合A到B的一個(gè)映射，或稱(chēng)A到B的一個(gè)函數(shù)，記為f:A

B。AB第31頁(yè),共76頁(yè)，2024年2月25日，星期天映射的兩個(gè)特點(diǎn)假定f:A

B,y=f(x),通常把x稱(chēng)為自變量，其取值范圍稱(chēng)為定義域記為domf；將y稱(chēng)為因變量，其取值范圍稱(chēng)為值域，記為ranf。⑴全函數(shù).

映射f的定義域是集合A,記為domf=A；⑵唯一性.

對(duì)于任意x∈A,對(duì)應(yīng)于B中唯一的元素f(x),x為f的自變量(也稱(chēng)為原像),f(x)稱(chēng)為x在映射f下的像,通常記為y=f(x).第32頁(yè),共76頁(yè)，2024年2月25日，星期天映射的表示（1）解析表達(dá)式（2）圖示（3）表格法函數(shù)符號(hào)的選取:f,g,…,F,G,…,

,

,…,sin,exp,main,add,average,…第33頁(yè),共76頁(yè)，2024年2月25日，星期天BA

（讀作B上A）定義對(duì)于集合A和B，用BA表示A到B的所有映射組成的集合，即定理：對(duì)于集合A和B，若|A|=m，|B|=n，則|BA|=nm。教材P7例題1-5第34頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.2映射的性質(zhì)1、單射假設(shè)f:A

B,如果對(duì)任意x1,x2

A,由f(x1)=f(x2)可推出x1=x2,則稱(chēng)f是A到B的單射,或稱(chēng)f是A到B的一對(duì)一映射。例：設(shè)f:N→N，f(x)=2x,則f是N到N的單射，試證明之。第35頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.2映射的性質(zhì)2、滿(mǎn)射假設(shè)f:A

B，如果對(duì)任意y

B,均存在x

A，使得y=f(x)，則稱(chēng)f是A到B的滿(mǎn)射，或稱(chēng)f是A到B的映上(onto)的映射。例：設(shè)f:Z→N,f(x)=|x|,則f是Z到N的滿(mǎn)射。第36頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.2映射的性質(zhì)3、雙射假設(shè)f:A

B，f既是單射又是滿(mǎn)射，則稱(chēng)f是A到B的雙射,或稱(chēng)f是A到B的一一對(duì)應(yīng)。例：試建立一個(gè)Z到N的一一對(duì)應(yīng)。

2xx≥0f(x)=2|x|-1x<0習(xí)題1.2(2)第37頁(yè),共76頁(yè)，2024年2月25日，星期天置換的定義設(shè)A是有限集合,A到A的雙射稱(chēng)為A上的置換例如：寫(xiě)出A={1，2，3}上的所有置換。(個(gè)數(shù)：n!)第38頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.3逆映射定義：設(shè)f:A

B,若將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)后能得出一個(gè)B到A的映射,則稱(chēng)該映射為f的逆映射,記為f-1.定理：設(shè)f:AB

，則f的逆映射存在的充要條件是f是雙射.第39頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.4復(fù)合映射定理

設(shè)f:A

B,g:B

C，對(duì)于任意x

A，令h(x)=g(f(x))則h是集合A到集合C的映射。xy=f(x)z=g(y)=g(f(x))第40頁(yè),共76頁(yè)，2024年2月25日，星期天1.2.4復(fù)合映射定義：設(shè)f:A

B,g:B

C,對(duì)于任意x

A,h(x)=g(f(x))則稱(chēng)h為f和g的復(fù)合映射或復(fù)合函數(shù)，記為f?g重點(diǎn)：(f?g)(x)=g(f(x))abc123

第41頁(yè),共76頁(yè)，2024年2月25日，星期天復(fù)合映射例題注意：要保證復(fù)合映射有意義，必須f(A)dom(g)例2：設(shè)R到R有兩個(gè)映射f和g，定義如下：f(x)=x2,g(x)=x+2，分別計(jì)算復(fù)合映射f?g和g?f注意：一般來(lái)說(shuō)，即使復(fù)合映射均有意義，也不能保證f?g=g?f成立

第42頁(yè),共76頁(yè)，2024年2月25日，星期天恒等映射設(shè)A是集合，令f:A

A,f(x)=x，稱(chēng)f為集合A上的恒等映射(identityfunctiononA)，記為IA

顯然恒等映射是唯一存在的。【定理1-9】若f:A

B是雙射，則有f

?

f-1=IA，f-1

?

f

=IB.特別地，若f:A

A是雙射，則f

?

f-1=f-1

?

f

=IA

第43頁(yè),共76頁(yè)，2024年2月25日，星期天復(fù)合映射性質(zhì)【定理1-10】設(shè)f:A

B,g:B

C

，(1)若f和g是單射,則f?

g是單射.(2)若f和g是滿(mǎn)射,則f?

g是滿(mǎn)射.(3)若f和g是雙射,則f?

g是雙射.【定理1-11】設(shè)f:A

B,g:B

C

，(1)若f?g是單射,則f是單射,g不一定.(2)若f?g是滿(mǎn)射,則g是滿(mǎn)射,f不一定.(3)若f?g是雙射,則f是單射且g是滿(mǎn)射.【定理1-12】設(shè)f:A

B,g:B

C

，h:C

D，則(f?

g)?h=f?(g?h)第44頁(yè),共76頁(yè)，2024年2月25日，星期天1.3運(yùn)算的定義及性質(zhì)運(yùn)算是由已知對(duì)象得出新對(duì)象的一種方法。運(yùn)算是討論對(duì)象之間有何聯(lián)系的一種方法。運(yùn)算本質(zhì)上是映射，但運(yùn)算更側(cè)重于研究運(yùn)算滿(mǎn)足的一些運(yùn)算性質(zhì)。

第45頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.1運(yùn)算的定義設(shè)A1,A2,……,An和B是集合，若

f:A1×A2×……×An→B

則稱(chēng)f為A1,A2,……,An到B的n元運(yùn)算。在不需要強(qiáng)調(diào)集合A1,A2,……,An和B時(shí)，可以簡(jiǎn)稱(chēng)f為運(yùn)算，f:A×A×……×A→B稱(chēng)f為A到B的n元運(yùn)算，或稱(chēng)f為A上的n元運(yùn)算。如y=f(x1,x2,…,xn)中，x1,x2,…,xn是參加運(yùn)算的n個(gè)有順序的對(duì)象，f稱(chēng)為n元運(yùn)算，y是運(yùn)算結(jié)果，由定義知道：運(yùn)算結(jié)果一定是唯一的。第46頁(yè),共76頁(yè)，2024年2月25日，星期天運(yùn)算的特征1、封閉運(yùn)算：若對(duì)于x1,x2,…,xn

A，有f(x1,x2,…,xn)=y

A，則稱(chēng)f為A上的n元封閉運(yùn)算(closedoperation)，或稱(chēng)為A上的n元代數(shù)運(yùn)算。習(xí)題1.3(1)(2)2、運(yùn)算符號(hào)的選?。撼Ｓ梅?hào)和定義符號(hào)3、運(yùn)算符號(hào)的位置：前面、中間和后面4、運(yùn)算表：方便直觀(guān)第47頁(yè),共76頁(yè)，2024年2月25日，星期天運(yùn)算的例題例1（絕對(duì)值運(yùn)算）f:ZN,f(x)=|x|.（一元運(yùn)算）

例2(模運(yùn)算)f:ZN,f(x)=x(modk),例3（模m加法運(yùn)算和模m乘法運(yùn)算）例4（最大公因數(shù)gcd和最小公倍數(shù)lcm）第48頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)1、對(duì)合性【定義】設(shè)*是A上的1元代數(shù)運(yùn)算，若對(duì)于x

A，均有

*(*x)=x

則稱(chēng)*具有對(duì)合性，或稱(chēng)*滿(mǎn)足對(duì)合律〖例1-20〗實(shí)數(shù)集上的取反數(shù)運(yùn)算“—”具有對(duì)合性，而其上的絕對(duì)值運(yùn)算||不具有對(duì)合性。矩陣的逆運(yùn)算及轉(zhuǎn)置運(yùn)算具有對(duì)合性，因?yàn)?A-1)-1=A并且(AT)T=A第49頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)2、冪等性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于x

A，有x*x=x

則稱(chēng)x為關(guān)于*運(yùn)算的冪等元；若對(duì)于任意的x

A，x均為冪等元，則稱(chēng)*具有冪等性，或稱(chēng)*滿(mǎn)足冪等率。*

123123

132232313例1：設(shè)A={1,2,3}，A上的*運(yùn)算見(jiàn)表，指出A中的冪等元，并判斷是否滿(mǎn)足冪等率？例2：正整數(shù)集合N+上gcd和lcm是否冪等率？例3：實(shí)數(shù)集合R上乘法是否滿(mǎn)足冪等率？第50頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)3、交換性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于任意x,y

A，均有

x*y=y*x則稱(chēng)*具有交換性，或稱(chēng)*滿(mǎn)足交換律。例1：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算和減法運(yùn)算是否滿(mǎn)足交換律例2：設(shè)*是有理數(shù)集合Q上的2元運(yùn)算，定義如下：任意x1,x2

Q，x1*x2=x1x2。證明*不具有交換性。例3：說(shuō)明復(fù)合映射是否具有交換性。第51頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)4、結(jié)合性【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若對(duì)于任意的x,y,z

A

，均有(x*y)*z=x*(y*z)則稱(chēng)*具有結(jié)合性，或稱(chēng)*滿(mǎn)足結(jié)合律。

例1：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算和減法運(yùn)算是否滿(mǎn)足結(jié)合率。53145534314421213343142254321154321*例2：判定集合A={1,2,3,4,5}見(jiàn)表，是否滿(mǎn)足交換率和結(jié)合率？例3：判定映射的復(fù)合運(yùn)算是否滿(mǎn)足結(jié)合率？第52頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)5、單位元素【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若存在e

A

，對(duì)于任意的x

A

，下列條件均成立：

e*x=xx*e=x則稱(chēng)e為集合A關(guān)于*運(yùn)算的單位元素或幺元素。

例1：驗(yàn)證整數(shù)集合Z關(guān)于加法運(yùn)算+的單位元素為0，而Z關(guān)于乘法運(yùn)算的單位元素為1，Z關(guān)于減法運(yùn)算沒(méi)有單位元素。定理：若A關(guān)于*運(yùn)算有單位元素，則單位元素是唯一的。第53頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)6、零元素【定義】設(shè)*是A上的2元代數(shù)運(yùn)算，若存在θ

A

，對(duì)于任意的x

A

，下列條件均成立：

θ*x=θx*θ=θ則稱(chēng)為集合A關(guān)于*運(yùn)算的零元素。例1：驗(yàn)證整數(shù)集合Z關(guān)于加法運(yùn)算+和減法運(yùn)算-均沒(méi)有零元素。Z關(guān)于乘法運(yùn)算的零元素為0。第54頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)7、逆元素【定義1-21】設(shè)*是A上的2元代數(shù)運(yùn)算且有單位元素e，若對(duì)于x

A，存在y

A，下列條件均成立：

y*x=ex*y=e則稱(chēng)y為x的逆元素。注意：

1、一個(gè)方陣關(guān)于乘法運(yùn)算的逆元是其逆矩陣，單位元素是單位矩陣；

2、一個(gè)雙射的映射的復(fù)合運(yùn)算的逆元是其逆映射。單位元素是恒等映射。第55頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)例1：分別考察：實(shí)數(shù)集合R中各元素關(guān)于加法運(yùn)算和乘法運(yùn)算的逆元素。例2：設(shè)A={a,b,c},關(guān)于*運(yùn)算的運(yùn)算表。分析逆元。

結(jié)論：一個(gè)元素的逆元不一定存在，存在也不一定唯一。習(xí)題1.3(8)caccaabbcbaacba*【定理】設(shè)A關(guān)于*運(yùn)算的單位元素為e且*運(yùn)算滿(mǎn)足結(jié)合律，若x在A(yíng)中有左逆元y及右逆元z，則y=z。進(jìn)而，對(duì)于一個(gè)滿(mǎn)足結(jié)合律的運(yùn)算來(lái)說(shuō)，若一個(gè)元素有逆元?jiǎng)t其逆元是唯一的。第56頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)8、消去性【定義1-22】設(shè)*是A上的2元代數(shù)運(yùn)算，若A關(guān)于*運(yùn)算有零元素，如果對(duì)于任意x,y,z

A

，只要x≠θ

，則下列條件均成立：

x*y=x*z→y=zy*x=z*x→y=z則稱(chēng)*具有消去性，或稱(chēng)*滿(mǎn)足消去律。例：驗(yàn)證整數(shù)集合Z上的加法運(yùn)算+和乘法運(yùn)算均滿(mǎn)足消去律。第57頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)9、分配性【定義1-23】設(shè)*和?是A上的2元代數(shù)運(yùn)算，若對(duì)于任意x,y,z

A，下列條件均成立：x*(y?z)=(x*y)?(x*z)(y?z)*x=(y*x)?(z*x)則稱(chēng)*運(yùn)算對(duì)?運(yùn)算具有分配性，或稱(chēng)滿(mǎn)足分配律。注意：當(dāng)*運(yùn)算滿(mǎn)足交換性時(shí)，條件之一成立即可。例：實(shí)數(shù)集合R上的乘法運(yùn)算對(duì)加法運(yùn)算可分配。第58頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)10、吸收性【定義1-24】設(shè)*和?是A上的兩個(gè)2元代數(shù)運(yùn)算，若對(duì)于x,y

A，下列條件均成立：x*(x?y)=x(y?x)*x=x則稱(chēng)*運(yùn)算對(duì)運(yùn)算?可吸收。

注意：當(dāng)*和?運(yùn)算滿(mǎn)足交換性，以上公式之一成立即可。第59頁(yè),共76頁(yè)，2024年2月25日，星期天1.3.2運(yùn)算的性質(zhì)11、德·摩根（DeMorgan）律【定義】設(shè)·是集合A上的1元代數(shù)運(yùn)算，*和?是A上的兩個(gè)2元代數(shù)運(yùn)算，若對(duì)于x,y

A

，下列條件均成立：

·(x*y)=(·x)?(·y)·(x?y)=(·x)*(·y)則稱(chēng)這三種運(yùn)算滿(mǎn)足DeMorgan律第60頁(yè),共76頁(yè)，2024年2月25日，星期天1.4集合的運(yùn)算1、并運(yùn)算2、交運(yùn)算3、補(bǔ)運(yùn)算4、差運(yùn)算5、對(duì)稱(chēng)差運(yùn)算第61頁(yè),共76頁(yè)，2024年2月25日，星期天1.4.1并運(yùn)算【定義】設(shè)A和B是兩個(gè)任意集合，由所有屬于A(yíng)或?qū)儆贐的元素組成的集合稱(chēng)為集合A和B的并集，通常記作A∪B。即：A∪B={x|x

A或x

B}陰影部分為A∪BU

BA如：設(shè)A={a，b，c，d}，B={b，d，e，f}，求A∪B定理：設(shè)A和B是集合，則A∪B是包含集合A和B的最小集合。第62頁(yè),共76頁(yè)，2024年2月25日，星期天并運(yùn)算的性質(zhì)設(shè)A，B，C是集合，則1、冪等律：A∪A=A2、交換律：A∪B=B∪A3、結(jié)合律：(A∪B)∪C=A∪(B∪C)4、

∪A=A∪=A(空集

是并運(yùn)算的單位元素)5、U∪A=A∪U=U(全集U是并運(yùn)算的零元素)第63頁(yè),共76頁(yè)，2024年2月25日，星期天1.4.2交運(yùn)算【定義】設(shè)A和B是兩個(gè)任意集合，由所有屬于A(yíng)又屬于B的元素組成的集合，稱(chēng)為A和B的交集，通常記作A∩B。即A∩B={x|x

A且x

B}陰影部分為A∩BU

BA如：設(shè)A={a，b，c，d}，B={b，d，e，f}，求A∩B定理：設(shè)A和B是集合，則A∩B是包含在集合A和B中的最大集合。第64頁(yè),共76頁(yè)，2024年2月25日，星期天交運(yùn)算的性質(zhì)設(shè)A，B，C是集合，則1、冪等律：A∩A=A2、交換律：A∩B=B∩A3、結(jié)合律：(A∩B)∩C=A∩(B∩C)4、∩A=A∩

=

（空集

是交運(yùn)算的零元素）5、U∩A=A∩U=A（全集U是交運(yùn)算的單位元素）第65頁(yè),共76頁(yè)，2024年2月25日，星期天交和并運(yùn)算的性質(zhì)并、交運(yùn)算的混合性質(zhì)(吸收律)：

設(shè)A，B，C是集合，則（1）∩對(duì)∪可吸收：A∩(A∪B)=A

（2）∪對(duì)∩可吸收：A∪(A∩B)=A

（3）∩對(duì)∪可分配：A∩(B∪C)=(A∩B)∪(A∩C)

（4）∪對(duì)∩可分配：A∪(B∩C)=(A∪B)∩(A∪C)

第66頁(yè),共76頁(yè)，2024年2月25日，星期天1.4.3補(bǔ)運(yùn)算【定義】設(shè)U是全集，對(duì)于集合A，定義A的補(bǔ)集如下：

={x|x

U，但x

A}注意：一個(gè)集合的補(bǔ)集依賴(lài)于全集的選取。陰影部分為A的補(bǔ)集UA例：設(shè)集合A={a,b,c}分別取全集U={a,b,c,d}和U={a,b,c,{a,b},{b,c