模糊數(shù)學(xué)第一章

遼寧大學(xué)信息學(xué)院研究生課程模糊數(shù)學(xué)及其應(yīng)用主講:尹鳳杰什么是模糊數(shù)學(xué)？模糊數(shù)學(xué)概念

FuzzyMathematics

研究和處理模糊概念的數(shù)學(xué)方法。

模糊概念：難以精確表達(dá)的概念。

例：高個(gè)子長(zhǎng)頭發(fā)戴寬邊眼鏡的中年男人1禿子悖論:天下所有的人都是禿子設(shè)頭發(fā)根數(shù)nn=1顯然若n=k

為禿子n=k+1亦為禿子模糊概念模糊概念：從屬于該概念到不屬于該概念之間無(wú)明顯分界線年輕、重、熱、美、厚、薄、快、慢、大、小、高、低、長(zhǎng)、短、貴、賤、強(qiáng)、弱、軟、硬、陰天、多云、暴雨、清晨等。2共同特點(diǎn)：模糊概念的外延不清楚。模糊概念導(dǎo)致模糊現(xiàn)象模糊數(shù)學(xué)就是用數(shù)學(xué)方法研究模糊現(xiàn)象。3模糊概念模糊數(shù)學(xué)的產(chǎn)生與基本思想

產(chǎn)生1965年，L.A.Zadeh（扎德）發(fā)表了文章《模糊集》(FuzzySets，InformationandControl,8,338-353)

基本思想用屬于程度代替屬于或不屬于。描述差異的中間過(guò)渡。是精確性對(duì)模糊性的一種逼近。某個(gè)人屬于禿子的程度為0.8,另一個(gè)人屬于禿子的程度為0.3等.4首次成功的用數(shù)學(xué)方法描述了模糊概念。課程認(rèn)識(shí)

在日常生活中，我們遇到的概念不外乎兩類。一類是清晰的概念，對(duì)象是否屬于這個(gè)概念是明確的。例如人、自然數(shù)、正方形等。

要么是人，要么不是人。要么是自然數(shù)，要么不是自然數(shù)。要么是正方形，要么不是正方形。另一類對(duì)象概念從屬的界限是模糊的，隨判斷人的思維而定。例如:好不好?快不快？快樂(lè)的很，好得很等等。

在客觀世界中，諸如上述的模糊概念要比清晰概念多得多。對(duì)于這類模糊現(xiàn)象，過(guò)去已有的數(shù)學(xué)模型難以適用，需要形成新的理論和方法，即在數(shù)學(xué)和模糊現(xiàn)象之間架起一座橋梁。它，就是我們要講的“模糊數(shù)學(xué)”。2課程認(rèn)識(shí)

本課程為計(jì)算機(jī)專業(yè)的研究生專業(yè)基礎(chǔ)課

教學(xué)目的

通過(guò)本課程的學(xué)習(xí)，掌握模糊數(shù)學(xué)的基本思想，基礎(chǔ)理論；從而進(jìn)一步了解模糊理論的基本應(yīng)用，能夠應(yīng)用模糊理論解決信息領(lǐng)域與工程技術(shù)中的實(shí)際問(wèn)題。

教學(xué)要求模糊數(shù)學(xué)基礎(chǔ)部分包括：模糊集合及其運(yùn)算；分解定理和擴(kuò)張?jiān)?；模糊度量；模糊關(guān)系；模糊矩陣等。應(yīng)用方法包括：聚類分析；模式識(shí)別；模糊決策等。3用數(shù)學(xué)的眼光看世界，可把我們身邊的現(xiàn)象劃分為：數(shù)學(xué)經(jīng)典（精確）數(shù)學(xué)確定性不確定性隨機(jī)性模糊性隨機(jī)數(shù)學(xué)模糊數(shù)學(xué)4第一章模糊理論的數(shù)學(xué)基礎(chǔ)普通集合與普通關(guān)系一、集合二、關(guān)系模糊理論的數(shù)學(xué)基礎(chǔ)普通集合與普通關(guān)系

集合的有關(guān)概念集合的運(yùn)算集合運(yùn)算的性質(zhì)映射與擴(kuò)張集合的特征函數(shù)

直積關(guān)系的概念關(guān)系的運(yùn)算特征關(guān)系等價(jià)關(guān)系與劃分偏序集格概念、內(nèi)涵、外延每一個(gè)概念都有一定的外延和內(nèi)涵概念的外延就是適合這個(gè)概念的一切對(duì)象的范圍概念的內(nèi)涵就是這個(gè)概念所反映的對(duì)象的本質(zhì)屬性的總和一、集合一、集合概念、內(nèi)涵、外延概念：青菜內(nèi)涵：一種植物，綠色，一般葉子直立，可食用外延：韭菜、芹菜、芥蘭、白菜、蔥等等概念與集合概念可以用集合來(lái)表示我們討論具體問(wèn)題時(shí)，要有論域（議題限制在一定范圍內(nèi)）例如：在論域“人”上，討論概念“男子”一、集合概念與集合從集合“人”中挑出所有男子，構(gòu)成一個(gè)子集AA是概念“男子”的外延是概念“男子”的集合表現(xiàn)概念可以用集合來(lái)表示一、集合一、集合經(jīng)典集合的回顧

十九世紀(jì)末，康托（Contort）建立了經(jīng)典集合論。經(jīng)典集合論是現(xiàn)代數(shù)學(xué)各個(gè)分支的基礎(chǔ)，其本身也是一門(mén)嚴(yán)格體系的數(shù)學(xué)分支。我們可以從常見(jiàn)事物中，抽象出集合這一概念：具有某種特定屬性的，彼此可以區(qū)別的對(duì)象的全體，叫做集合。每個(gè)集合里通常包含有若干個(gè)體，集合里的每個(gè)個(gè)體，成為集合中的一個(gè)元素。同一集合中的元素都具有某種共性，該集合被討論的全體對(duì)象，稱為論域。一、集合1.集合的有關(guān)概念相等:空集:不含任何元素的集合,子集:真子集:則稱冪集:U的所有子集的集合稱為U的冪集,記為P(U)例如：1.集合的有關(guān)概念定理:如果有限集合U有n個(gè)元素，則其冪集P(U)有2n個(gè)元素。例：P()={}P(P())={,{}}注意點(diǎn)：

和

，

A={},則有

A,

A，{

}A,{}A

例題：A={a,,c}

則a

A,b

A,c

A{a}

A,

A,{c}

A2.集合的運(yùn)算(set-theoreticoperations)表“或”表“且”表“非”差A(yù)BEA∩B=

ABEA∩BA?BABEA∪BABEA-BAE~A３.集合運(yùn)算的性質(zhì)(1)冪等律(idempotence)(2)交換律(commutativity)(3)結(jié)合律(associativity)(4)吸收律(absorptionlaws)(5)分配律(distributivity)(6)存在最大最小元(7)還原律(involution)３.集合運(yùn)算的性質(zhì)(8)DeMorgan德.摩根律（對(duì)偶律）(9)補(bǔ)余律(complementation)推廣：分配律、對(duì)偶律等可推廣３.集合運(yùn)算的性質(zhì)4.集合中元素的計(jì)數(shù)集合A＝{1，2，…，n}，它含有n個(gè)元素,可以說(shuō)這個(gè)集合的基數(shù)是n，記作cardA＝n也可以記為｜A｜＝n，空集的基數(shù)是即｜

｜＝0．有窮集、無(wú)窮集定義:設(shè)A為集合，若存在自然數(shù)n（0也是自然數(shù)），使得｜A｜＝cardA＝n，則稱A為有窮集，否則稱A為無(wú)窮集。例如，{a,b,c}是有窮集，而N，Z，Q，R都是無(wú)窮集。5.映射與擴(kuò)張（1）映射(mapping):實(shí)際是函數(shù)概念的推廣記號(hào)：例1：設(shè)都是集合，若存在對(duì)應(yīng)關(guān)系f,使都有唯一的與之相對(duì)應(yīng)，則稱f

是映X入Y的映射。讀作f映X入Y（映入），y稱為x在影射f下的像，x稱為原像。（2）特殊映射5.映射與擴(kuò)張單射(injection)：且對(duì)任意也稱f為一一的。滿射(surjection)：且對(duì)任意都有使得則稱f為滿射。也稱f映X到Y(jié)上（映上）。f為從X到Y(jié)的滿射當(dāng)且僅當(dāng)f(X)=Y.雙射(bijection)：注1.單射或滿射的概念與集合有關(guān).例如:注2.雙射為1-1對(duì)應(yīng).5.映射與擴(kuò)張（3）擴(kuò)張：點(diǎn)集映射集合變換書(shū)例1-1合成映射：P3P56.集合的特征函數(shù)(characteristicfunctionofaset)證：取大運(yùn)算,如2∨3=3故稱集合A的特征函數(shù)。6.集合的特征函數(shù)(characteristicfunctionofaset)例題:則則類似可得：證：取小運(yùn)算,如2∧3=2推廣：6.集合的特征函數(shù)(characteristicfunctionofaset)定義：設(shè)A和B是任意兩個(gè)集合，用A中的元素為第一元素,B中的元素為第二元素構(gòu)成的有序?qū)Γ羞@樣的有序?qū)M成的集合稱為集合A和B的笛卡兒積，也稱集合A和B的直乘積，記做A×B一種集合合成的方法，把集合A，B合成集合A×B，規(guī)定A×B＝{<x,y>

x

A,y

B}，不能寫(xiě)作B×A。二、關(guān)系(Relations)1.直積(Descartesproduct)n階笛卡兒積將兩個(gè)集合的笛卡兒積推廣到n個(gè)集合1.直積(Descartesproduct)稱為例1例2R表示實(shí)數(shù)集，例3設(shè)集合A={a,b},B={1,2,3},C=zhp5rft,

求A×B×C，B×A。解:先計(jì)算A×B＝{{a,1},{a,2},{a,3},{{b,1},{b,2},{b,3}} A×B×C＝

{{a,1},{a,2},{a,3},{{b,1},{b,2},{b,3}}×fjzdbpb

＝{<{a,1},d>,<{a,2},d>,<{a,3},d>,<{b,1},d>,<{b,2},d>,<{b,3},d>} B×A＝{<1,a>,<2,a>,<3,a>,<1,b>,<2,b>,<3,b>}

例4設(shè)集合A＝{1,2},求A×P(A)。解:P(A)={

,{1},{2},{1,2}} A×P(A)＝{1,2}×{

,{1},}{2},{1,2} ={<1,

>,<2,

>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,<1,{1,2}>,<2,{1,2}>}1.直積(Descartesproduct)注意點(diǎn)：或(1)(2)(3)直積不適合交換律和結(jié)合律例1設(shè)一旅館有n個(gè)房間，每個(gè)房間可住兩個(gè)旅客，所以一共可住2n個(gè)旅客，在旅館內(nèi)，旅客與房間有一定關(guān)系，用R表示“某旅客住在某房間”這種關(guān)系。設(shè)n=3表示旅館共有3個(gè)房間,分別記以1,2,3可住6個(gè)旅客分別記以a,b,c,d,e,f,這些旅客住的房間如右下圖所示123abcdef

滿足R的所有關(guān)系可看成是一個(gè)有序偶的集合，這個(gè)集合可叫RR={<a,1>,<b,1>,<c,2>,<d,2>,<e,3>,<f,3>}

若令

A={a,b,c,d,e,f}B={1,2,3}則例中關(guān)系的每一元素均屬于A×B亦即R是A×B的子集，并稱此關(guān)系為從A到B的關(guān)系R。關(guān)系的引入2.關(guān)系的概念2.關(guān)系的概念注1.關(guān)系就是集合，注2.從X到Y(jié)的關(guān)系與從Y到X關(guān)系不同。例22.關(guān)系的概念若(x,y)R，則稱x與y有關(guān)系，記為R(x,y)=1；若(x,y)R，則稱x與y沒(méi)有關(guān)系，記為R(x,y)=0.

映射R:X

Y{0,1}實(shí)際上是X

Y的子集R上的特征函數(shù).3.關(guān)系的運(yùn)算例33.關(guān)系的運(yùn)算3.關(guān)系的運(yùn)算關(guān)系的矩陣表示法

設(shè)X={x1,x2,…,xm},Y={y1,y2,…,yn}，R為從X到Y(jié)的二元關(guān)系，記rij=R(xi,yj)，R=(rij)m×n，則R為布爾矩陣(Boole)，稱為R的關(guān)系矩陣.

布爾矩陣(Boole)是元素只取0或1的矩陣.3.關(guān)系的運(yùn)算關(guān)系合成的矩陣表示法

設(shè)X={x1,x2,…,xm},Y={y1,y2,…,ys},Z={z1,z2,…,zn}，且X到Y(jié)的關(guān)系R1=(aik)m×s，Y到Z的關(guān)系R2=(bkj)s×n，則X到Z的關(guān)系可表示為矩陣的合成：R1°

R2=(cij)m×n，其中cij=∨{(aik∧bkj)|1≤k≤s}.例4設(shè)X={1,2,3,4},Y={2,3,4},Z={1,2,3},R1是X到Y(jié)的關(guān)系,R2是Y到Z的關(guān)系,R1={(x,y)|x+y=6}={(2,4),(3,3),(4,2)},R2={(y,z)|y–z=1}={(2,1),(3,2),(4,3)},則R1與R2的合成R1°

R2={(x,z)|x+z=5}={(2,3),(3,2),(4,1)}.3.關(guān)系的運(yùn)算合成(°

)運(yùn)算的性質(zhì)：性質(zhì)1：(A°B)°C=A°(B°C)；滿足結(jié)合律（舉例)性質(zhì)2：Ak

°Al

=Ak+l，(Am)n=Amn；性質(zhì)3：A°

(B∪C)

=(A°B)∪(A°C)；

(B∪C)°

A=(B°

A)∪(C°

A)；

分配律（對(duì)∪分配）性質(zhì)4：O°A=A°O=O，I°A=A°I=A；0-1律

性質(zhì)5：A

B，C

D

A°C

B°D.O為零矩陣，I為n階單位方陣.3.關(guān)系的運(yùn)算例設(shè)A={1,2,3,4}，B={2,3,4}，C={1,2,3}，D={4,5,6}A到B的關(guān)系R1={(2,4),(2,3),(4,2)},B到C的關(guān)系R2={(2,1),(3,2),(4,3)},C到D的關(guān)系R3={(2,4),(1,5),(2,6),(3,6)}則A到C的關(guān)系R1。R2={(2,3),(2,2),(4,1)}.(R1。R2)。R3={(2,6),(2,4),(4,5)}.則B到D的關(guān)系R2。R3={(2,5),(3,4),(3,6),(4,6)}.R1。(R2。R3)={(2,6),(2,4),(4,5)}.滿足結(jié)合律注意合成運(yùn)算的交運(yùn)算的分配律不成立！舉例4.特征關(guān)系稱為R的特征關(guān)系。4.特征關(guān)系5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)

在我們的周?chē)斜姸嗟氖虑橐覀內(nèi)ヌ幚?怎么高效率的處理這些問(wèn)題呢?一個(gè)簡(jiǎn)單的方法就是分門(mén)別類地去處理,而分門(mén)別類地去處理事情的數(shù)學(xué)基礎(chǔ)是利用等價(jià)關(guān)系去分類.5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)則稱R是一個(gè)X上的等價(jià)關(guān)系。例15.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)例2：在非空集A的冪集P(A)上給定包含關(guān)系R1，真包含關(guān)系R2，以及不相交關(guān)系R3：判斷是否自反、傳遞、對(duì)稱？5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)R1具有自反性，傳遞性，但不具備對(duì)稱性。R2具有傳遞性，但不具備對(duì)稱性，也不具備自反性。R3具有對(duì)稱性，但不具備自反性和傳遞性，例3：設(shè)P是正整數(shù)，在所有整數(shù)的集合Z上給定關(guān)系R：5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)R具備自反性、對(duì)稱性及傳遞性嗎？5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)幾點(diǎn)說(shuō)明：

對(duì)稱關(guān)系不是反對(duì)稱關(guān)系（aRb且bRa得到b=a)的反義。有些關(guān)系既是對(duì)稱的又是反對(duì)稱的，比如“等于”。有些關(guān)系既不是對(duì)稱的也不是反對(duì)稱的，比如整數(shù)的“整除”。有些關(guān)系既是對(duì)稱的但不是反對(duì)稱的，比如“模n同余。有些關(guān)系不是對(duì)稱的，但是反對(duì)稱的，比如“小于”。5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)

練習(xí)：

任何非空集合上的空關(guān)系都是對(duì)稱的、傳遞的、非自反的。其上的相等關(guān)系是自反的、對(duì)稱的、傳遞的。三角形的相似關(guān)系、全等關(guān)系是自反的、對(duì)稱的、傳遞的。正整數(shù)集合上的整除關(guān)系是自反的、傳遞的、不對(duì)稱的。但整數(shù)集合上的整除關(guān)系只有傳遞性。（注意零點(diǎn)）實(shí)數(shù)集上的等于關(guān)系為自反的、對(duì)稱的、傳遞的。小于等于關(guān)系為自反的、傳遞的，但非對(duì)稱的。小于關(guān)系是傳遞的、非對(duì)稱的、非自反的。判斷一個(gè)關(guān)系是否具有某種性質(zhì)，除直接用定義外，還有以下充要條件：

設(shè)R為X={x1,x2,…,xn}

上的關(guān)系，則其關(guān)系矩陣R=(rij)n×n

為n階方陣.(1)R具有自反性

IR；(2)R具有對(duì)稱性

RT

=R

；(3)R具有傳遞性

R2

R

.

若R具有自反性，則

I

R

R2

R3

…5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)下面證明：R具有傳遞性

R2

R.R=(rij)n×n

設(shè)R具有傳遞性,即對(duì)任意的i,j,s，若有ris=1，

rsj=1，則有rij=1.

對(duì)任意的i,j，若∨{(rik∧rkj)|1≤k≤n}=0，則∨{(rik∧rkj)|1≤k≤n}≤rij.

若∨{(rik∧rkj)|1≤k≤n}=1，則存在1≤s≤n，使得:(ris∧rsj)=1，5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)即ris=1,rsj=1.

由于R具有傳遞性，則rij=1，所以∨{(rik∧rkj)|1≤k≤n}=rij.綜上所述

R2

R.

設(shè)R2

R，則對(duì)任意的i,j,k，若有

rik=1，rkj=1，即(rik∧rkj)=1，因此∨{(ris∧rsj)|1≤s≤n}=1，

由R2

R，得rij=1，所以R具有傳遞性.5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)集合表達(dá)式關(guān)系性質(zhì)關(guān)系圖特征關(guān)系矩陣特性自反性反自反性反對(duì)稱性傳遞性對(duì)稱性每一個(gè)結(jié)點(diǎn)有一環(huán)每一結(jié)點(diǎn)均無(wú)環(huán)若有邊則有雙邊（方向相反）若有邊則單邊（沒(méi)有邊成對(duì)出現(xiàn)）若有雙邊則必有雙環(huán)，有三角形必是向量三角形，且如果結(jié)點(diǎn)v1,v2…vm間有邊，則必有邊v1,vm主對(duì)角線元素為1主對(duì)角線元素為0矩陣為對(duì)稱矩陣5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)

存在既不是自反的也不是反自反的二元關(guān)系如：設(shè)A={1,2,3}，R是A上的關(guān)系，

R={<1,1>,<2,2>},缺少<3,3>,則R既不是自反的，也不是反自反的。判斷一個(gè)關(guān)系是否是反對(duì)稱，通俗的講就是對(duì)于所有的a,b∈A，若a≠b,則序偶<a,b>,<b,a>至多只有一個(gè)出現(xiàn)在關(guān)系R中，如

R={<1,2>,<1,1>,<3,1>}.5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)例1.設(shè)A={a,b,c},以下各關(guān)系Ri(i=1,2,…8)均為A上二元關(guān)系。是否自反？是否對(duì)稱？是否傳遞？5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)例2：集合A={1,2,…,8}上的關(guān)系R={{x,y}︱x≡y(mod3)},其中x≡y(mod3)表示x-y可被3整除，對(duì)任意的x,y,z∈A，x-x可被3整除;若x-y可被3整除，則y-x也可被3整除；若x-y和y-z可被3整除，則x-z=(x-y)+(y-z)可被3整除，所以，R具有自反性、對(duì)稱性和傳遞性，R是A上的等價(jià)關(guān)系。練習(xí)題：設(shè)A={1,2,3,4,5},A上關(guān)系R為R={<a,b>︱a-b是偶數(shù)}，問(wèn)R是否具有自反性、對(duì)稱性、傳遞性？5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)例3.{紅，白，黃三色球若干}，球x與球y相同顏色。證明：R是等價(jià)關(guān)系。結(jié)論：R是等價(jià)關(guān)系。5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)設(shè)R是集合A上的等價(jià)關(guān)系，對(duì)任意x∈A，在A中一切與x有等價(jià)關(guān)系R的元素組成的集合，稱為“由x產(chǎn)生關(guān)于R的等價(jià)類”。簡(jiǎn)稱“x的等價(jià)類”，記為[x]R.等價(jià)類：5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)例5.考慮自然數(shù)集N上的同余關(guān)系的等價(jià)類。因?yàn)槿魏巫匀粩?shù)除以3，其余數(shù)只能是0，1，2，所以在集合N上只有由0，1，2產(chǎn)生關(guān)于的3個(gè)等價(jià)類（約定）：這三個(gè)等價(jià)類滿足:稱這三個(gè)子集為集合N的一個(gè)劃分。5.等價(jià)關(guān)系與劃分（EquivalencyrelationsandPartition)定理：若R

是集合上的等價(jià)關(guān)系，則等價(jià)類的集合稱集合{Ai

}是集合A的一個(gè)劃分.每個(gè)集合Ai叫做這個(gè)劃分的一個(gè)類。定義：設(shè)A是一個(gè)非空集，而Ai，（指標(biāo)集K可以是有限的，也可以是無(wú)限的）是集合A的某些非空子集，如果構(gòu)成A的一個(gè)劃分。6.偏序集(partiallyorderedset或poset)定義1:設(shè)R是非空集合A上的關(guān)系。若R是自反的、反對(duì)稱的和傳遞的，則稱R是A上的偏序關(guān)系，記作≤。若<x,y>∈≤,則記作x≤y,讀作“x小于等于y”.這里的小于等于不是指數(shù)的大小，而是指它們?cè)谄蛑形恢玫南群蟆?意即:依據(jù)這個(gè)序,x排在y的前面)等價(jià)關(guān)系和偏序關(guān)系是具有不同性質(zhì)的兩個(gè)關(guān)系

6.偏序集(partiallyorderedset或poset)說(shuō)明：

1.學(xué)過(guò)離散數(shù)學(xué)的人都知道，關(guān)系是有序?qū)Φ募?，?dāng)我們面對(duì)一個(gè)集合S，集合S上的關(guān)系是一個(gè)有序?qū)Φ募蟈，其中X中的每個(gè)元素都是有序?qū)Γ?，每個(gè)有序?qū)χ械脑囟紒?lái)自于集合S.2.若給定集合S上的關(guān)系R是一個(gè)偏序關(guān)系，則說(shuō)集合S在關(guān)系R下是一個(gè)偏序集。

3.偏序集是和關(guān)系密切相連的一個(gè)概念，當(dāng)面對(duì)一個(gè)集合，外加一個(gè)關(guān)系時(shí)，才可以判斷此集合在這種關(guān)系下是否是偏序集。例1:集合A={1,2,3},偏序≤是A上的大于等于關(guān)系,

則≤={<3,3>,<3,2>,<3,1>,<2,2>,<2,1>,<1,1>}

那么有3≤2,2

≤2,3≤1。它們分別表示

<3,2>,<2,2>和<3,1>屬于偏序≤，因?yàn)椤苁莧1,2,3}上的大于等于關(guān)系,在≤前邊的數(shù)恰好是比較大的數(shù)。6.偏序集解：

∵<2,2>,<3,3>,<6,6>,<8,8>R

∴R是自反的又∵<2,6>,<2,8>,<3,6>R

而<6,2>,<8,2>,<6,3>R∴R是反對(duì)稱的

x,y,z

A,若<x,y>R且<y,z>R,則

<x,z>R

由<x,y>

R

有y|x=n

由<y,z>

R

有z|y=m

將y=z|m代入y|x=n得z|x=mn

即<x,z>R(∵z|x=mn)

∴

R是可傳遞的.(事實(shí)上∵<3,3>,<3,6>,<2,2>,<2,6>,<2,8>R

則<3,6>,<2,6>,<2,8>R∴R是可傳遞的）綜上所述：R是偏序關(guān)系6.偏序集例2集合A={2,3,6,8}上的“整除”關(guān)系RR={<2,2>,<3,3>,<6,6>,<8,8>,<2,6>,<2,8>,<3,6>}

(x整除y）那么R有哪些關(guān)系？定義2:一個(gè)集合A與A上的偏序關(guān)系R一起叫做偏序集，記作<A,≤>。如：集合A={2,3,6,8}上的“整除”關(guān)系——<A,≤>

整數(shù)集合上的小于等于關(guān)系——<Z,≤>

R={<x,y>|x,yZ∧x≤y}∵xZ<x,x>R∴R是自反的又∵

<x,y>R

而<y,x>R(∵<y,x>表示y≥x與關(guān)系R矛盾）

∴R是反對(duì)稱的又∵x,y,tZ,若<x,y>R且<y,t>R

則

<x,t>R∴R是可傳遞的R是偏序關(guān)系6.偏序集6.偏序集說(shuō)明：①

記Z+是正整數(shù)集合，a整除b記作b︱a,例如：4︱2、

12︱3、21︱7等等，則這種整除關(guān)系“︱”是Z+上的偏序關(guān)系。②整除關(guān)系“︱”不是整數(shù)集合Z上的偏序關(guān)系，特別地，“︱”在Z上不是反對(duì)稱的。例如有2︱-2和-2︱2，但2≠-2。③在整數(shù)集合Z上，定義關(guān)系：aRb,當(dāng)且僅當(dāng)存在正整數(shù)r使b=ar.例如因?yàn)?=23所以2R8.則R是Z上的偏序關(guān)系，<Z,R>是偏序集。哈斯圖的畫(huà)法：設(shè)<X,≤>是偏序集，X中的每個(gè)元素用節(jié)點(diǎn)表示，x,y∈X偏序關(guān)系關(guān)系圖的簡(jiǎn)化——哈斯圖(Hassediagram)分以下兩步:(其中≤表示偏序關(guān)系)①若x≤y，且x≠y，則將x畫(huà)在y的下面。②若x≤y，x≠y，并且沒(méi)有不同于x，y的z

使得x≤z≤y，則在x，y之間用直線連結(jié)。為了直觀地研究偏序關(guān)系和偏序集，可借助于哈斯(Hass)圖。它是關(guān)系圖的簡(jiǎn)化，根據(jù)偏序關(guān)系中的自反和傳遞特性去掉了關(guān)系圖中所有環(huán)和某些線段后的簡(jiǎn)化圖。6.偏序集例3A={1,2,3,4,6}上的整除關(guān)系為R,畫(huà)出<A,R>的哈斯圖1346在畫(huà)偏序集<A,≤>的哈斯圖時(shí)，首先適當(dāng)排列頂點(diǎn)的順序使得：

x,y∈A，若x<y，則將x畫(huà)在y的下方。對(duì)于A中的兩個(gè)不同元素x和y,如果y蓋住x,就用一條線段連接x和y。26.偏序集

a

b

a,b

a,b,c

a,b,c,d

a,b,c,e

例4設(shè)A＝

a

,

b

,

a,b

,

a,b,c

,

a,b,c,d

,

a,b,c,e

，畫(huà)出<A,>的哈斯圖。例5A={1,2},畫(huà)出A的冪集P(A)上的包含關(guān)系的哈斯圖∵P(A)={

,{1},{2},{1,2}}例6

A={2,3,6,12,24,36},畫(huà)出“整除”R的偏序集

<A,≤>的哈斯圖。定義3設(shè)<A,≤>為偏序集,若對(duì)任意的x,y∈A,x和y都可比,(即x≤y或y≤x)則稱R為A上的全序關(guān)系,且稱<A,≤>為全序集。例如，A={1,2,3,4,5}上的小于等于關(guān)系是全序關(guān)系,因?yàn)橛汕袄螦上的小于等于關(guān)系是偏序關(guān)系,所以<A,≤>為偏序集。又因?yàn)閷?duì)任意的x,y∈A,x,y均可比較大小,即x≤y或y≤x所以是全序關(guān)系。而整除關(guān)系<A,≤>亦為偏序集，但對(duì)任意的

x,y∈A,x,y相互不能整除,所以不是全序關(guān)系。對(duì)于集合A上的任一全序,集合

A中任意兩個(gè)元素都是可比的6.偏序集注意點(diǎn)：

“偏”是用來(lái)定義偏序集X的，因?yàn)榧蟈上某些元素是不可比較的；若X的每一對(duì)元素都是可以比較的，則稱X為全序集，相應(yīng)的偏序就稱為全序。全序集也叫做線性序集或叫做鏈。雖然偏序集可能不是全序集，但它的子集仍可能是全序集，很明顯，全序集的每一個(gè)子集都是全序集。典型示例

考慮偏序集<Z+,︱>。21和7可比較，因?yàn)?1︱7，但

3和5不可以比較，因?yàn)榧葲](méi)有3︱5也沒(méi)有5︱3。因此<Z+,︱>不是全序集，但S={2,6,12,36}是Z+在整除關(guān)系下的全序子集。對(duì)于含有兩個(gè)或兩個(gè)以上元素的集合S，偏序集

<P(S),>不是全序集。例如，假設(shè)a和b屬于S，那么P(S)中的{a}與是不可能比較的，而A={Φ,{a},S}

是P(S)在偏序關(guān)系下的全序子集。定義4

設(shè)<A,≤>為偏序集①若存在一個(gè)元素使得所有均有,則稱為偏序集A的最大元。②若對(duì)于所有均有,則稱為偏序集A的最小元。若存在一個(gè)元素，在A中不存在這樣的元素，使得而有，稱為偏序集A的極大元。若A中不存在這樣的元素，使得而有，稱為偏序集A的極小元。6.偏序集

最小(大)元與極小(大)元的區(qū)別：最小元是A中最小的元素，它與A中其它元素都可比極小元不一定與A中其它元素都可比，只要沒(méi)有比它小的元素即可。極大元是指在該集合中沒(méi)有比它更大的,這是一種“局部”性質(zhì),并不意味著它是最大的。最大元?jiǎng)t指比所有的都大(可以發(fā)生相等),這是一種“全局”性質(zhì),故最大元必定是極大元。對(duì)于有窮集合A，最小(大)元不一定存在，但若存在則一定唯一存在；而極小(大)元一定存在，并且可能存在多個(gè)。若A中只有一個(gè)極小(大)元,則它一定是A的最小(大)元。6.偏序集例7上述兩個(gè)偏序集都有最小元,分別是1和。整除關(guān)系的偏序集沒(méi)有最大元,包含關(guān)系的偏序集有最大元{a,b,c}。凡是在哈斯圖中向上路徑的每一個(gè)終點(diǎn)都是極大元。上圖中整除關(guān)系的偏序集有極大元7,8,9,10,11和12,包含關(guān)系的偏序集有唯一極大元{a,b,c}。兩個(gè)偏序集都有極小元,分別是1和。187112451036129{a,b,c}{b,c}{c}<{1,2,…,12},R整除>{a,b}{a}{a,c}{

}<{P({a,b,c

}),R

>6.偏序集6.偏序集定義5

設(shè)A是偏序集<X,≤>的子集，①若對(duì)于一切a

A有a≤x成立，則稱x為A的一個(gè)上界。②若對(duì)于一切a

A均有x≤a成立，則稱x為A的一個(gè)下界。③如果x

X是A的上界，且對(duì)每個(gè)A的上界x’

X

均有x≤x’(上界集的最小元），則稱x為A的上確界。記為x=SupA。④如果x

X是A的下界，且對(duì)每個(gè)A的下界x’

X

均有x’≤x(下界中的最大元），則稱x為A的下確界。記為x=infA。6.偏序集例8

在上圖整除關(guān)系的偏序集里,如果A={2,3,6},

那么A的上界是6和12,最小上界是6。A的下界是

1,最大下界也是1。在右上圖中,令A(yù)={c,d,e},則A的上界和最小上界都是e,A的下界為a,b,但A沒(méi)有最大下界817241151036129<{1,2,…,12},R整除>fbcdagheA={2,3,6},

A={c,d,e},由本定義可知：（1）A的最小元一定是A的下界，并且也是A的最大下界；但反之不一定正確，A的下界不一定是

A的最小元，因?yàn)樗赡懿皇茿中的元素；（2）類似地可以討論A的最大元與其上界的關(guān)系。（3）A的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。6.偏序集6.偏序集最小元∈A，小于A中其它元最大元∈A，大于A中其它元不一定存在，若存在必唯一極小元∈A，A中沒(méi)有比它小的元極大元∈A，A中沒(méi)有比它大的元一定存在，可能多個(gè)上界∈X，大于A中其它元下界∈X，小于A中其它元不一定存在，若存在不一定唯一上確界∈X，最小的上界下確界∈X，最大的下界不一定存在，若存在必唯一

解:B1

中極小元、最小元都是1

極大元是4、5、6,無(wú)最大元；

B1的下界是1,下確界也是1，沒(méi)有上界和上確界。

B2

中因?yàn)?和3不可比，故極小元是2和3，極大元也是2和3

但都沒(méi)有最小元和最大元；下界是1,下確界也是1，上界是6和12，上確界都是6。

B3

中極小元、極大元、最小元和最大元都是5。下界1,5和下確界5，上界是5和10，上確界都是5。

123546例9

求偏序集<{1,2,…,12},R整除>中，對(duì)于B1={1,2,3,4,5,6},B2={2,3},B3={5}的各極小元、極大元、最小元和最大元。例10：設(shè)集合A＝{a,b,c,d,e}，偏序關(guān)系R的哈斯圖如圖所示，若A的子集B={c,d,e}，求：（1）用列舉法寫(xiě)出偏序關(guān)系R的集合表達(dá)式；（2）寫(xiě)出集合B的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界。解：（1）R={<d,b>,<d,c>,<d,a>,<b,a>,<c,a>,<e,c>,<e,a>}（2）集合B的極大元：c，極小元：d、e，最大元：c，最小元：無(wú)，上界：c、a，上確界：c，下界：無(wú)，下確界：無(wú)。

6.偏序集例11:6.偏序集證：例12例13注一個(gè)集合的上、下界可能有多個(gè)，也可能不存在.6.偏序集為最小上界

1.格的定義<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，則稱<A,≤>是格。右圖的三個(gè)偏序集,哪個(gè)是格？６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。<A,≤><B,≤>3。4。1。2。<C,≤><A,≤>不是格，因?yàn)閧24,36}無(wú)最小上界。<B,≤>和<C,≤>是格。7.格

(Lattices)這三個(gè)偏序集，都不是格，

第一個(gè)與第三個(gè)是同構(gòu)的。因?yàn)閐和e無(wú)下界，也無(wú)最小上界；b,c雖有下界，但無(wú)最大下界。

第二個(gè)圖：2,3無(wú)最大下界，4,5無(wú)最小上界。d

a

b

ce

1

2

34