集合論總復(fù)習(xí)習(xí)題

集合論總復(fù)習(xí)

習(xí)題第二十一講1作業(yè)講評P863-1.(9)

設(shè)某集合有101個(gè)元素，試問：

a)可構(gòu)成多少個(gè)子集？

b)其中有多少個(gè)子集元素為奇數(shù)？

c)是否有102個(gè)元素的子集？解：a)可構(gòu)成2101個(gè)子集

b)有2100個(gè)子集元素為奇數(shù)

c)不能有102個(gè)元素的子集2

(10)設(shè)S={a1,a2,...,a8},由B17和B31所表示的S的子集各是什么?應(yīng)如何表示子集{a1,a8},{a2,a6,a7}和

{a3,a8,a7}?

B17=B00010001={a4,a8} B31=B00011111={a4,a5,a6,a7,a8} {a1,a8}=B10000001=B129 {a3,a7,a8}=B00100011=B35{a2,a6,a7}=B01000110=B70作業(yè)講評P863-1.(10)解：S有28=256個(gè)不同的子集,可表示為B0,B1,B2,B3,…,B255,二進(jìn)制下標(biāo)有8位.3a)證明(1)A∩(BC)=(A∩B)(A∩C)證明:(A∩B)(A∩C)=((A∩B)∩~(A∩C))∪((A∩C)∩~(A∩B))=((A∩B)∩(~A∪~C))∪((A∩C)∩(~A∪~B))=((A∩B)∩~C))∪((A∩C)∩~B))=A∩((B∩~C)∪(C∩~B))

=A∩(BC)作業(yè)講評P953-2.(11)4作業(yè)講評P953-2.(11)a)證明(1)A∩(BC)=(A∩B)(A∩C)證明:(A∩B)(A∩C)=((A∩B)–(A∩C))∪((A∩C)–(A∩B))=(A∩(B–C))∪(A∩(C–B))=A∩((B–C)∪(C–B))=A∩(BC)注意：

A∪(B―C)≠(A∪B)―(A∪C)5(2)A∪(BC)=(A∪B)(A∪C)不一定成立。證明:設(shè)A={2,3},B={1,4,7},C={3,5},

則BC={1,3,4,5,7}

所以A∪(BC)={1,2,3,4,5,7}

但A∪B={1,2,3,4,7} A∪C={2,3,5}

故(A∪B)(A∪C)={1,4,5,7}

因此A∪(BC)=(A∪B)(A∪C)不一定成立。作業(yè)講評6作業(yè)講評P1053-4.(3)c)(AB)(CD)=(AC)(BD)解:不成立。

設(shè)A=B，C和D≠

則左邊=，右邊≠7作業(yè)講評P1053-4.(3)e)證明(1)(AB)C=(AC)(BC)證明:對于任意的<x,y>

(AB)Cx(AB)∧yC((xA∧xB)∨(xA∧xB))∧yC((xA∧xB)∧y

C)∨((xA∧x

B))∧yC)(<x,y>(AC)∧<x,y>(BC))∨(<x,y>(AC)∧<x,y>(BC))<x,y>(AC)(BC))8作業(yè)講評P1053-4.(3)e)證明(1)(AB)C=(AC)(BC)證明:(AB)C=((A-B)∪(B-A))C=((A-B)C)∪(B-A))C)=((AC)-(BC))∪((BC)-

(AC))=(AC)(BC)注意：A(B*C)=(AB)*(AC)(B*C)A=(BA)*(CA)*代表∪,∩或–運(yùn)算9作業(yè)講評P1053-4.(5)(5)證明若XY=XZ，且X≠

則Y=Z證明：1)Y=,則XY=,故

XZ=∴Z=，∴Y=Z∴yZ∴YZ

同理YZ∴

Y=Z

2)Y≠,任意yY，令xX，由已知有<x,y>XY=XZ10作業(yè)講評(5)證明若XY=XZ，且X≠

則Y=Z證明：∵XY=XZ且X≠

∴XYXZ

且XZXY∴YZ且YZ∴

Y=Z(1)AB的充分必要條件是ACBC;(2)AB的充分必要條件是CACBC是非空集合。11作業(yè)講評補(bǔ)充題90名學(xué)生，55人參加數(shù)學(xué)小組，44人參加語文小組，33人參加體育小組。36人參加數(shù)學(xué)和語文小組，29人參加數(shù)學(xué)和體育小組，25人參加語文和體育小組。問多少人3個(gè)小組都沒有參加？1.|A∪B|≤|A|+|B|2.|A∩B|≤min(|A|,|B|)3.|A–B|≥|A|–|B|4.|AB|=|A|+|B|–2|A∩B|12作業(yè)講評P1133-6.(3)舉出A={1,2,3}上的關(guān)系R的例子，使它有以下性質(zhì)：

a)既是對稱又是反對稱的

b)既不是對稱又不是反對稱的

c)R是可傳遞的解:a)RIA，如R={<1,1>}

b)部分對稱,如R={<1,2>,<2,1>,<1,3>}

c)R={<1,2>,<2,1>,<1,1>,<2,2>}13作業(yè)講評P1133-6.(6)(6)設(shè)R是X上的自反關(guān)系。證明R是對稱和傳遞的,當(dāng)且僅當(dāng)＜a,b>和<a,c>在R中時(shí)，則有<b,c>在R之中。任意元素a,b,c,若aRb,

由自反性得有aRa,

于是有bRa,

故R是對稱的；若有aRb且bRc,由對稱性得到bRa,

于是有bRa

且bRc,

故有aRc,故R傳遞14作業(yè)講評P1133-6.(6)(6)設(shè)R是X上的自反關(guān)系。證明R是對稱和傳遞的,當(dāng)且僅當(dāng)＜a,b>和<a,c>在R中時(shí)，則有<b,c>在R之中。必要性：因?yàn)镽為X上的等價(jià)關(guān)系，所以具有自反性、對稱性和傳遞性。對于集合X上的任意元素a,b,c，若aRb

且aRc,由對稱性得：bRa，再由傳遞性得bRc。15作業(yè)講評P1193-7.(3)令<x,z>SS，存在y使<x,y>S且<y,z>S∵S是傳遞的∴<x,z>S∴SSS設(shè)S為X上的關(guān)系，證明S是自反的和傳遞的，則，其逆為真嗎？令<x,y>S，由自反性知<y,y>S∴<x,y>SS∴SSS

其逆不真。例如X={1，2，3}，S={<1,2>，<2,2>，<1,1>},SS=S,但S不是自反的。

16作業(yè)講評ArelationRonasetAiscalledcircularifaRbandbRcimplycRa.ShowthatRisreflexiveandcircularifandonlyifitisanequivalencerelation.必要性：R是自反和循環(huán)的R是等價(jià)關(guān)系令<a,b>R∵R是循環(huán)的∴<b,a>R∴R對稱令<a,b>,<b,c>R，∵R是對稱的∴<a,c>R∴R傳遞∵R是自反的∴<b,b>R∵R是循環(huán)的∴<c,a>R集合A上的關(guān)系R，如果aRb且bRc蘊(yùn)含cRa，那么就稱R是循環(huán)的。證明：R是自反和循環(huán)的當(dāng)且僅當(dāng)R是等價(jià)關(guān)系17作業(yè)講評ArelationRonasetAiscalledcircularifaRbandbRcimplycRa.ShowthatRisreflexiveandcircularifandonlyifitisanequivalencerelation.充分性令<a,b>,<b,c>R，∵R是對稱的∴<c,a>R∴R循環(huán)∵R是等價(jià)關(guān)系∴R是自反,傳遞,對稱的∵R是傳遞的∴<a,c>RR是等價(jià)關(guān)系R是自反和循環(huán)的18作業(yè)講評LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/R即證：R是自反，對稱，傳遞的⑴a,bS，則<a,b>A∵a+b=b+a∴R自反⑵令<a,b>R<c,d>，即a+d=b+c∴a+f=b+e∴<a,b>R<e,f>∴R傳遞∴c+b=d+a∴R對稱∴<a,b>R<a,b>⑶令<a,b>R<c,d>，<c,d>R<e,f>

即a+d=b+c，c+f=d+e∴<c,d>R<a,b>19作業(yè)講評LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/R<1,1>,A={<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>R={<<1,1>,<2,2>>,<<1,1>,<3,3>>,<<1,1>,<1,1>>,<<1,1>,<4,4>>,<<1,2>,<1,2>>,<<1,2>,<2,3>>,<<1,2>,<3,4>>,<<1,3>,<1,3>>,<<1,4>,<1,4>>,<<2,1>,<3,2>>,<<2,1>,<2,1>>,<<2,1>,<4,3>>,<<3,1>,<3,1>>,<<3,1>,<4,2>>，<<1,3>,<2,4>>,<<4,1>,<4,1>>}}20作業(yè)講評LetS={1,2,3,4}andletA=SS.DefinethefollowingrelationRonA:<a,b>R<c,d>ifandonlyifa+d=b+c.(1)ShowthatRisanequivalencerelation.(2)ComputeA/RA/R={{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<4,3>,<3,2>,<2,1>},

{<1,3>,<2,4>},{<3,1>,<4,2>},

{<1,4>},{<4,1>}}A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}21作業(yè)講評

P1463-12(6)(6)設(shè)集合P={x1,x2,x3,x4,x5,}上的偏序關(guān)系如圖所示。找出P的最大(小)元素，極大(小)元素。找出子集{x2,x3,x4}{x3,x4,x5,}{x1,x2,x3}的上(下)(確)界最大元素x1,無最小元素

x5x1x2x3x4極大元素x1,極小元素x4,x5

集合上界下界上確界下確界{x2,x3,x4}x1x4x1x4{x3,x4,x5,}x1,x3無x3無{x1,x2,x3}x1x4x1x422作業(yè)講評

P1463-12(7)(7)下圖給出了集合{1,2,3,4}上的四個(gè)偏序關(guān)系圖,畫出它們的哈斯圖，并說明哪個(gè)是全序關(guān)系，哪個(gè)是良序關(guān)系。1243(a)先去環(huán)再去掉傳遞最后調(diào)整位置1234(a)23作業(yè)講評

P1463-12(7)(7)下圖給出了集合{1,2,3,4}上的四個(gè)偏序關(guān)系圖,畫出它們的哈斯圖，并說明哪個(gè)是全序關(guān)系，哪個(gè)是良序關(guān)系。1234(c)先去環(huán)再去掉傳遞最后調(diào)整位置421324作業(yè)講評補(bǔ)充題設(shè)f,g,h是實(shí)數(shù)集R上的函數(shù)，f(x)=x+2,g(x)=x-2,h(x)=3x，求fg、ff、gf、gg、fh、hg、hfgfg(x)=xff(x)=x+4gf(x)=xgg(x)=x-4fh(x)=3x+2hg(x)=3x-6hfg(x)=h(x)=3x25作業(yè)講評P1514-2.(6)(6)設(shè)A和B是有窮集合，有多少不同入射函數(shù)和多少不同的雙射函數(shù)。入射:X中沒有兩個(gè)元素有相同的象(1)f:A－>B為入射,必須有|A|≤|B|,即m≤n設(shè)|A|=m，|B|=n

B中任意選出m個(gè)元素的任一全排列即為所求.滿射:Y中每一個(gè)元素是X中的一個(gè)或多個(gè)元素的象點(diǎn)。

(2)f:A－>B為雙射,必須有|A|=|B|,即m=n所以，共有m!個(gè)。26集合是什么

集合是不能精確定義的基本概念。如何理解集合：由共同性質(zhì)的一些對象匯集而成的整體。集合可以是有限集，也可以是無限集集合的表示方法：

枚舉法

敘述法（列判別條件）一般用大寫字母表示集合，用小寫字母表示元素見課本P8227集合與元素的關(guān)系集合與元素的關(guān)系：xA或xA

集合元素可以是離散型數(shù)據(jù)（如整型、邏輯型、枚舉型等），也可以是非離散型數(shù)據(jù)（如實(shí)型）。

有限集一定是離散型數(shù)據(jù)，無限集可能是離散型，也可能是非離散型的數(shù)據(jù)。本書中默認(rèn)：

自然數(shù)集從0開始（見P94，習(xí)題(3)中對自然數(shù)N的子集C的定義）28集合的概念子集：ＡＢ(x)(xＡ→xＢ)（B包含A）真子集：ＡＢＡＢ∧ＡＢ(x)(xＡ→xＢ)∧(x)(xB∧xA)空集：不包含任何元素的集合

φ={x|p(x)∧┑p(x)}，

p(x)為任何謂詞全集：E={x|p(x)∨┑p(x)}，

p(x)為任何謂詞29集合的相等集合A、B相等：

A=BA,B的元素完全相同AB且BA(x,若xA，則xB)且

(x,若xB，則xA)集合A、B不等：

A≠BA,B的元素不完全相同 （不是完全不同！)not(AB)或not(BA)(x,xA且xB)或

(x,xB且xA)30冪集冪集的概念：給定集合A，由集合A的所有子集為元素組成的集合，稱為集合A的冪集，記為P(A)。若|A|=n，則|P(A)|=2n如何證明?注意

P(φ)={φ}≠φ區(qū)別：

{},但{},{}。A=BP(A)=P(B)ABP(A)P(B)31證明

AB當(dāng)且僅當(dāng)P(A)

P(B)充分性:對任意xA{x}P(A){x}P(B)

xB所以AB必要性:對任意xP(A)xAxB

xP(B)所以P(A)P(B)32集合之間的關(guān)系子集：A包含BB包含于A真子集：相等：A、B的元素完全相同不等：A、B的元素不完全相同從屬：ＡＢ （一個(gè)集合是另外一個(gè)集合的元素）33空集的性質(zhì)空集是一切集合的子集?？占俏┮坏?。空集是任何集合的冪集的元素。空集的冪集不是空集。34空集例題例判斷下列命題的真假: (1)

(2)

(3)

{} (4)

{}

(2)為假;其余均為真。35集合運(yùn)算的性質(zhì)交換律

A∩B=B∩A A∪B=B∪A

A⊕B=B⊕A

結(jié)合律

(A∩B)∩C=A∩(B∩C) (A∪B)∪C=A∪(B∪C)

(A⊕B)⊕C=A⊕(B⊕C)

注意：

A―B≠B―A (A―B)―C≠A―(B―C)36集合運(yùn)算的性質(zhì)分配律（注意證明方法是典型的，見P89，P91）

A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)

A∩(B―C)=(A∩B)―(A∩C)P91定理 但：A∪(B―C)≠(A∪B)―(A∪C)

例：B=~A,C=φ時(shí)

A∩(B⊕C)=(A∩B)⊕(A∩C)

但：A∪(B⊕C)≠(A∪B)⊕(A∪C)

例：B=C,A≠φ時(shí)37集合運(yùn)算的性質(zhì)摩根律

~(A∪B)=~A∩~B

~(A∩B)=~A∪~B

A–(B∪C)=(A–B)∩(A–C)A–(B∩C)=(A–B)∪(A–C)吸收律

A∪(A∩B)=A=A∩(A∪B)其他

A∩BAA∪B A∩BBA∪B38證明集合相等的方法

往證A=B方法一：

證明：AB且BA

（P91定理3-2.5的證明方法）方法二： 證明滿足A元素的條件邏輯等價(jià)于滿足B元素的條件 （P91定理3-2.4的證明方法）方法三： 使用集合運(yùn)算的性質(zhì) （P91定理3-2.6的證明方法）39證明集合不等的方法

往證AB：方法一：舉反例

A≠B(x,xA且xB)

或(x,xB且xA)方法二： 說明（或證明）一個(gè)是空集（或全集），另一個(gè)不是方法三： 畫文氏圖示意40證明集合是空集的方法方法一： 其邏輯判斷條件是永假方法二： 用反證法：設(shè)aA，引出矛盾的結(jié)果 （見P95習(xí)題(10)a)的證明）方法三： 利用等式，例如：A⊕A=φ41包含排斥原理│A∪B│=│A│+│B│-│A∩B││A∪B∪C│=│A│+│B│+│C│ -│A∩B│-│A∩C│-│B∩C│+│A∩B∩C│見P96-99例題1、2、342定義序偶序偶：有序的偶對序偶與集合的區(qū)別：有序/無序若x≠y，則<x,y>≠<y,x>，但{x,y}={y,x}序偶與集合的統(tǒng)一：

<x,y>={{x},{x,y}}序偶相等的定義：

<x,y>=<u,v>x=u且y=v43集合的笛卡兒乘積集合A、B的笛卡兒乘積

AB=<x,y>(xA)∧(yB)見課本P102例題1

44笛卡兒乘積的性質(zhì)ABBAABC=(AB)CA(BC)An=AAA(n個(gè)A)ABABAnAnAA45笛卡兒乘積的定理以下定理均可從序偶、集合相等的定義證明：

A(B∪C)(AB)∪(AC) (B∪C)A(BA)∪(CA) A(B∩C)(AB)∩(AC) (B∩C)A(BA)∩(CA)

若C≠，則AB(AC)(BC)(CACB)

非空集合A,B,C,D, ABCDAC且BD46關(guān)系的定義關(guān)系是兩個(gè)集合的笛卡兒乘積的子集。本質(zhì)上關(guān)系R是序偶的集合：若<x,y>R則記為xRy若<x,y>R則記為xRy

集合A到集合B的關(guān)系：AB的子集集合A上的關(guān)系：AA的子集 見課本P106例題1、2、347特殊的關(guān)系恒等關(guān)系

IA＝x,xxA是A上的關(guān)系全域關(guān)系：R＝AB空關(guān)系：R＝定理：

A到B的兩個(gè)關(guān)系的交、并、差、補(bǔ)仍是A到B的關(guān)系48關(guān)系的表示集合法：列舉集合的所有元素（序偶）或判別條件敘述法：

敘述關(guān)系定義的判別條件；P107例4矩陣法：

A到B的關(guān)系用|A|行|B|列的0、1矩陣表示圖：

A到B的關(guān)系：用有向偶圖表示（點(diǎn)表示集合元素，弧表示序偶）A上的關(guān)系：用有向圖表示（點(diǎn)表示集合元素，弧表示序偶）49關(guān)系的性質(zhì)討論非空集合A上的關(guān)系R（即RAA）自反性：aA,a,aR

關(guān)系圖中每個(gè)點(diǎn)都有環(huán)

關(guān)系矩陣是對角線元素全部為1反自反性：aA,a,aR

關(guān)系圖中每個(gè)點(diǎn)都沒環(huán)

關(guān)系矩陣是對角線元素全部為050關(guān)系的性質(zhì)對稱性：a,bA,若a,bR，則b,aR

關(guān)系圖中任意兩個(gè)不同的點(diǎn)之間要么沒有邊，要么有雙向邊；

關(guān)系矩陣是對稱矩陣反對稱性：若ab，則a,bR或b,aR；或者：a,bA,若a,bR且b,aR,則a=b；

關(guān)系圖任意兩個(gè)不同的點(diǎn)之間要么沒有邊，要么只有單向邊。關(guān)系矩陣呢？51關(guān)系的性質(zhì)傳遞性：a,b,cA,若a,bR且b,cR，則a,cR

關(guān)系圖中任意兩個(gè)點(diǎn)之間若經(jīng)過第三點(diǎn)有路接通，則必有直達(dá)邊;

關(guān)系矩陣較復(fù)雜52定義復(fù)合關(guān)系 設(shè)R是A到B的關(guān)系，S是B到C的關(guān)系，則RS稱為R和S的復(fù)合關(guān)系，表示為RS={<x,z>|xA∧zC∧ (y)(yB∧<x,y>R∧<y,z>S)}R表示關(guān)系時(shí)，Rn表示n個(gè)關(guān)系R的復(fù)合復(fù)合關(guān)系是不可交換的（沒有公共域）復(fù)合關(guān)系是可結(jié)合的。53定義逆關(guān)系 設(shè)R是A到B的關(guān)系，將R中每一序偶元素順序互換，得到的集合稱為關(guān)系R的逆關(guān)系，(inverserelation)表示為Rc={<y,x>|<x,y>R}可見，Rc是B到A的關(guān)系。逆關(guān)系保持了關(guān)系的性質(zhì)：

即保持了原關(guān)系的自反性、反自反性、對稱性、反對稱性、傳遞性（若原關(guān)系有這些性質(zhì)的話）。見課本P119習(xí)題（5）54有關(guān)定理證明兩個(gè)關(guān)系相等，實(shí)質(zhì)上是證明兩個(gè)集合（元素是序偶）相等

(R1∪R2)c=R1c∪R2c (R1∩R2)c=R1c∩R2c (R1-R2)c=R1c-R2c (AB)c=BA

(R1R2)c=R2c

R1c (R1R2)R3=R1(R2R3) R是對稱的R=Rc R是反對稱的R∩Rc

Ix

55逆關(guān)系的性質(zhì)逆關(guān)系的矩陣： 原關(guān)系矩陣轉(zhuǎn)置之后得到逆關(guān)系的矩陣逆關(guān)系的圖： 把弧的方向反轉(zhuǎn)，得到逆關(guān)系的圖逆關(guān)系保留了原來關(guān)系的自反、反自反、對稱、反對稱、傳遞等性質(zhì)。 56關(guān)系運(yùn)算后性質(zhì)的保持關(guān)系運(yùn)算后性質(zhì)的保持運(yùn)算\性質(zhì)自反性反自反性對稱性反對稱性傳遞性R∪SR∩SR–SRcR·S57關(guān)系的閉包關(guān)系R的自反（對稱、傳遞）閉包：是指包含R的、而且是自反的、最小的自反（對稱、傳遞）關(guān)系

嚴(yán)格的定義：見課本P119如果R本身是自反的（對稱的、傳遞的），則其自反的（對稱的、傳遞的）閉包就是R自反閉包：reflexiveclosure對稱閉包：symmetricclosure傳遞閉包：transitiveclosure58閉包的討論自反閉包rRR∪Ix（R是集合X上的關(guān)系）對稱閉包sRR∪Rc

傳遞閉包t(R)=R∪R2∪…∪Rn∪…

若|X|=n，則只需前m個(gè)（mn）關(guān)系的并

rsRsr(R)

rtRtr(R)

tsRst(R)Warshall算法的實(shí)質(zhì)：簡化矩陣運(yùn)算，此處不要求，“數(shù)據(jù)結(jié)構(gòu)”課程再講。59定義集合的劃分與覆蓋

A為非空集合，S={S1,S2,…,Sm}，其中（1）SiA，Si≠φ(i=1,2,…,m)（2）S1∪S2∪…∪Sm=A（3）當(dāng)i≠j時(shí)，Si∩Sj=φS是A的覆蓋S是A的劃分定義的另一種描述： 若把集合A分成若干個(gè)叫做分塊的非空子集，使得A中每一個(gè)元素至少屬于一個(gè)分塊，則這些分塊的全體叫A的一個(gè)覆蓋；若A中每一個(gè)元素屬于且只屬于一個(gè)分塊，則這些分塊的全體叫A的一個(gè)劃分（或分劃）。60習(xí)題解答P130習(xí)題(5)(1)∪(Ai

∩B)

=(A1∪A2

∪‥∪Ak)∩B=A∩Bi=1k(2)(Ai

∩B)∩(Aj

∩B)

=Ai∩Aj

∩

B=φ61定義等價(jià)關(guān)系

R是集合A上的關(guān)系，滿足自反、對稱、傳遞，則R是A上的等價(jià)關(guān)系。見課本P131例題1、例題2注意： 許多這類題目：給出某些性質(zhì)，判別是否等價(jià)關(guān)系62定義等價(jià)類R是A上的等價(jià)關(guān)系，則等價(jià)類aRxxA且aRx等價(jià)類的性質(zhì)：a,bA1）aRφ且aRA2）a,bRaRbR

3）a,bRaR∩bR=φ4）aRaA是Ａ的一個(gè)劃分，記為Ａ／Ｒ（商集）

63劃分和等價(jià)關(guān)系1）等價(jià)關(guān)系---------劃分 （P133定理3-10.2，3-10.3）2）R1=R2A/R1=A/R2

（P134定理3-10.4）決定64定義偏序關(guān)系 非空集合A上的關(guān)系R，滿足自反、反對稱、傳遞的性質(zhì)，稱R是A上的一個(gè)偏序關(guān)系，記為：序偶＜A,＞稱作偏序集。 見課本P140例題1、例題265定義“蓋住”在偏序集中的兩個(gè)元素x和y滿足以下條件： ①xy ②x≠y③x,y之間沒有z，使xz且zy

則稱y蓋住x

見課本P140例題3

對于給定的偏序集＜A,＞，其蓋住關(guān)系是確定的、唯一的。66哈斯圖Hassediagram回顧：偏序關(guān)系的關(guān)系圖的特點(diǎn)？哈斯圖： 關(guān)系圖的簡化（省略了自反性、傳遞性）使用了“蓋住”的性質(zhì)，作圖規(guī)則如下：1）每個(gè)元素用一個(gè)小圓點(diǎn)表示；2）若元素y蓋住元素x，則y畫在x上方，并用直線連接；3）若xy且x≠y，則y畫在x之上；若無關(guān)系，則兩個(gè)點(diǎn)可畫在同一水平，也可一上一下。67作業(yè)講評

P1463-12(7)(7)下圖給出了集合{1,2,3,4}上的四個(gè)偏序關(guān)系圖,畫出它們的哈斯圖，并說明哪個(gè)是全序關(guān)系，哪個(gè)是良序關(guān)系。1234(c)先去環(huán)再去掉傳遞最后調(diào)整位置421368定義鏈、反鏈 Ａ的子集稱為：

鏈：偏序集的每兩個(gè)元素都有關(guān)系；

(哈斯圖中某條鏈上的點(diǎn)集)

反鏈：偏序集的每兩個(gè)元素都沒有關(guān)系

(哈斯圖中若干個(gè)沒關(guān)系的點(diǎn)的集合)

單個(gè)元素的子集，既是鏈，又是反鏈

（注意：這是約定，不能證明）問：是否存在非鏈、非反鏈的關(guān)系？答：是。如集合{2,3,4}上的整除關(guān)系69線序關(guān)系 在偏序集＜A,＞中，如果A是一個(gè)鏈，則稱＜A,＞為全序集合或線序集合，二元關(guān)系稱為全序關(guān)系或線序關(guān)系。全序關(guān)系線序關(guān)系哈斯圖是一條“鏈” 全序關(guān)系＜A,＞中，x,yA，xy和yx至少有一個(gè)成立。

A上的線序關(guān)系A(chǔ)上的偏序關(guān)系

A上的偏序關(guān)系A(chǔ)上的關(guān)系

A上的關(guān)系A(chǔ)A70AAA上的關(guān)系A(chǔ)上的偏序關(guān)系A(chǔ)上的等價(jià)關(guān)系線序關(guān)系恒等關(guān)系的子集單個(gè)元素各概念的相互關(guān)系71極大元最大元 ＜A,＞是偏序集合，且B是A的子集，對于B中的某個(gè)元素b，若B中沒有其他元素x，滿足bx，則稱b是B的極大元。 ＜A,＞是偏序集合，且B是A的子集，對于B中的某個(gè)元素b，若對于B中每個(gè)元素x，滿足xb，則稱b是B的最大元。72上界、上確界 ＜A,＞是偏序集合，且B是A的子集，對于A中的某個(gè)元素a，若對于B中每個(gè)元素x，滿足xa，則稱a是B的上界。 注意：上界不一定是集合內(nèi)的點(diǎn)； ＜A,＞是偏序集合，且B是A的子集，a是B的某一上界，對于B中所有上界y，滿足ay，則稱a是B的最小上界，或上確界。 注意：上確界不一定是集合內(nèi)的點(diǎn)；73良序 偏序集合的每個(gè)非空子集存在最小元素，則稱為良序集。良序集合一定是全序集合（P145定理12.1)良序線序偏序關(guān)系笛卡爾乘積

有限的全序集合一定是良序集合

(P145定理12.2)無限的全序集合不一定是良序集合（例如正實(shí)數(shù)集合上的小于關(guān)系，開區(qū)間子集沒最小元素）74定義函數(shù)

函數(shù)（也叫映射mapping）的定義：f是集合X到集合Y的一個(gè)關(guān)系，對于每一個(gè)xX，有惟一的yY，使得<x,y>f，稱關(guān)系f為函數(shù)，記為：

f:X→Y或X→Y y記為f(x)f函數(shù)與關(guān)系的區(qū)別:①定義域是整個(gè)集合X；②一個(gè)aX只能對應(yīng)于惟一的一個(gè)yY，使f(x)=y；可見: 函數(shù)關(guān)系笛卡爾乘積75解(1)R1不是函數(shù),因?yàn)樵豠有兩個(gè)不同的像(2)R2不是函數(shù),因?yàn)锳中元素c沒有像。(3)R3是函數(shù),函數(shù)的定義允許多個(gè)元素共有一個(gè)像例題設(shè)A={a,b,c},B={0,1},判別下列二元關(guān)系中哪個(gè)是函數(shù)？(1)R1={?a,0?,?a,1?,?b,0?,?c,1?}。(2)R2={?a,0?,?b,1?}。(3)R3={?a,0?,?b,1?,?c,1?}。76例題證明因?yàn)槿我缓瘮?shù)f是由A中n個(gè)元素的取值所唯一確定的,A中的任一元素a,f在a處的取值都有m種可能,所以A到B可以定義m·m…m=mn

=|B||A|個(gè)不同的函數(shù)。設(shè)|A|=n,|B|=m，X到Y(jié)有多少個(gè)不同的函數(shù)？77習(xí)題解答

P1514-1(2)令f:A→B，已知CA，證明：f(A)-f(C)f(A-C)證明：任意yf(A)-f(C),xA,f(x)=y

對于zC，y≠f(z)，即x≠z

因此

xA-C

故y=f(x)f(A-C)

于是有：f(A)-f(C)f(A-C)78習(xí)題解答

P1514-1(3)

假設(shè)f和g是函數(shù)，且有fg和domgdomf，證明f=g。證明：<a,g(a)>g，有adomgdomf

故adomf，

有<a,f(a)>fg，即<a,f(a)>g

由于g是函數(shù)，因此a有惟一像點(diǎn)， 于是有：<a,g(a)>=<a,f(a)>

<a,g(a)>=<a,f(a)>f

因此gf

已知fg，得到f=g79習(xí)題解答

P1514-1(3)假設(shè)f和g是函數(shù)，且有fg和domgdomf，證明f=g。證明：用反證法：設(shè)f≠g，由已知fg得

<a,g(a)>g，但<a,g(a)>f

由<a,g(a)>g，得adomgdomf

故adomf，有<a,f(a)>fg，

即<a,f(a)>g， 由于g是函數(shù)，因此a有惟一像點(diǎn)， 于是有：<a,g(a)>=<a,f(a)>

<a,g(a)>=<a,f(a)>f與題設(shè)矛盾。

因此f=g80滿射、入射(單射)、雙射 函數(shù)f:X→Y滿射：yY，xX，使得f(x)=y；入射：x1,x2X，x1≠x2f(x1)≠f(x2)；雙射：既是入射又是滿射，也叫一一對應(yīng)

81入射入射入射入射82逆函數(shù)inversefunction問：函數(shù)的逆關(guān)系一定是函數(shù)嗎？答：只有雙射才有逆函數(shù)雙射函數(shù)f: