離散數(shù)學(xué)復(fù)習(xí)2

1、1第二章 謂詞邏輯2.1謂詞演算的基本概念謂詞演算的基本概念2.2謂詞演算的關(guān)系式謂詞演算的關(guān)系式2.3前束范式前束范式2.4謂詞演算的推理22.1.1 謂詞與個(gè)體考察以下考察以下2 2個(gè)原子命題：個(gè)原子命題：（1 1）李華是工程師。）李華是工程師。（2 2）何威是工程師。）何威是工程師。若對(duì)這兩個(gè)原子命題進(jìn)行內(nèi)部結(jié)構(gòu)分析，就若對(duì)這兩個(gè)原子命題進(jìn)行內(nèi)部結(jié)構(gòu)分析，就會(huì)發(fā)現(xiàn)它們之間既有會(huì)發(fā)現(xiàn)它們之間既有相異之處相異之處又有又有相同之處相同之處。相異之處：相異之處：主語不同主語不同相同之處：相同之處：謂語共享謂語共享將相同部分從這類命題中將相同部分從這類命題中分離分離（抽抽象象）出來進(jìn)行研究）出來進(jìn)

2、行研究并符號(hào)化并符號(hào)化。引入一個(gè)符號(hào)表示引入一個(gè)符號(hào)表示“x x是工程師是工程師”。(x) 或或( )32.1.1 謂詞與個(gè)體n像像( () ) 這樣抽象形式，實(shí)際上就是上述幾個(gè)語句中描述主語性質(zhì)的這樣抽象形式，實(shí)際上就是上述幾個(gè)語句中描述主語性質(zhì)的謂語結(jié)構(gòu)的謂語結(jié)構(gòu)的抽象形式抽象形式或描述主語所涉及或描述主語所涉及對(duì)象之間的關(guān)系對(duì)象之間的關(guān)系的抽象形式的抽象形式。n上述中的上述中的抽象形式抽象形式就是就是謂詞謂詞。語句中的。語句中的主語或?qū)ο笾髡Z或?qū)ο蠓Q為稱為個(gè)體個(gè)體。n個(gè)體個(gè)體是指可以獨(dú)立存在的。是指可以獨(dú)立存在的。謂詞謂詞是用來刻劃個(gè)體的性質(zhì)或關(guān)系的。通是用來刻劃個(gè)體的性質(zhì)或關(guān)系的。通常

3、用常用大寫字母大寫字母F F,G,HG,H等表示謂詞等表示謂詞，用，用小寫字母小寫字母a,b,ca,b,c等表示個(gè)體等表示個(gè)體。n在原子命題中引進(jìn)謂詞和個(gè)體的概念，這種以命題中的謂詞為基礎(chǔ)的在原子命題中引進(jìn)謂詞和個(gè)體的概念，這種以命題中的謂詞為基礎(chǔ)的分析研究，稱為分析研究，稱為謂詞邏輯謂詞邏輯( (或稱或稱謂詞演算謂詞演算) )。42.1.1 謂詞與個(gè)體 個(gè)體的變化范圍，稱為個(gè)體的變化范圍，稱為個(gè)體域個(gè)體域。 將宇宙間一切事物（所有個(gè)體）所組成的個(gè)體域?qū)⒂钪骈g一切事物（所有個(gè)體）所組成的個(gè)體域稱為稱為全總個(gè)體域全總個(gè)體域。 以某一個(gè)個(gè)體域?yàn)樽冇虻淖冊(cè)?，稱為以某一個(gè)個(gè)體域?yàn)樽冇虻淖冊(cè)?，稱為個(gè)體變

4、元個(gè)體變?cè)Ａ?xí)慣用小寫的習(xí)慣用小寫的x,y,zx,y,z等表示。等表示。 與個(gè)體變?cè)鄬?duì)的是與個(gè)體變?cè)鄬?duì)的是個(gè)體常元個(gè)體常元，它指某個(gè)確定的，它指某個(gè)確定的個(gè)體，習(xí)慣用小寫的個(gè)體，習(xí)慣用小寫的a,b,ca,b,c等表示。等表示。52.1.1 謂詞與個(gè)體n僅含一個(gè)個(gè)體變?cè)闹^詞，稱為一元謂詞。n含有n個(gè)個(gè)體變?cè)闹^詞，稱為n元謂詞。n含有0個(gè)個(gè)體變?cè)闹^詞（但可能包含多個(gè)個(gè)體常元），稱為0元謂詞。 n一般地，一元謂詞刻畫了個(gè)體的性質(zhì)，多元謂詞刻畫了個(gè)體之間的關(guān)系。n注意：謂詞不是命題，只有當(dāng)確定的個(gè)體“填入”后，才成為命題。 (x)(x)(x(x，y)y)(a,b,c)(a,b,c)“張華張華

5、是大學(xué)生是大學(xué)生”可表示為可表示為F(a)62.1.2 量詞)(xxF 全稱量詞記作 “ x ”，其含意是：“所有的x ”、“每一個(gè)x ”、“凡是x ”、“任意的x ”等等。表示表示對(duì)個(gè)體域中的所有個(gè)體其對(duì)個(gè)體域中的所有個(gè)體其謂詞謂詞F(x)F(x)均為真均為真。72.1.2 量詞)(xxF 存在量詞記作 “ ”，其含意是：“存在著x ”、“有些x ” 等等。表示表示個(gè)體域中存在個(gè)體域中存在某些個(gè)體某些個(gè)體其其謂詞謂詞F(x)F(x)均為真均為真。x8函數(shù) 在謂詞邏輯中，在謂詞邏輯中，個(gè)體與個(gè)體間有一定的關(guān)系個(gè)體與個(gè)體間有一定的關(guān)系，這種關(guān)這種關(guān)系稱為函數(shù)系稱為函數(shù)。)(xf),(yxf),(

6、21nxxxf一元函數(shù)一元函數(shù)二元函數(shù)二元函數(shù) 多元函數(shù)多元函數(shù)例：李平的媽媽是醫(yī)生。D(x)：x是醫(yī)生；a：李平；f(a)：李平的媽媽；句子符號(hào)化為：D(f(a)9用謂詞和量詞表示句子的步驟：n參考題目給出的個(gè)體域，如果沒有指明，假設(shè)為全總個(gè)體域；n確定句子中的謂詞和個(gè)體變?cè)辉谌倐€(gè)體域下，句子中的名詞（人、數(shù)、動(dòng)物等）都需要使用特性謂詞表示；多元謂詞使用多個(gè)不同的個(gè)體變?cè)?。n根據(jù)句子中特性謂詞前的修飾詞選擇量詞； ：“所有的”、“凡是”、“一切”、“任意”、“每一個(gè)”等詞，或省略的情況 ：“存在”、“有些”、“某些”、“幾個(gè)”等詞n根據(jù)量詞確定謂詞之間的關(guān)系； 所限定的個(gè)體變?cè)诘奶匦?/p>

7、謂詞和其他謂詞之間使用條件連接詞。 所限定的個(gè)體變?cè)诘奶匦灾^詞和其他謂詞之間使用合取連接詞。10例1.沒有不犯錯(cuò)的人)()(xWxMxnM(x)：x是人nW(x)：x犯錯(cuò)11例2.對(duì)于所有的正實(shí)數(shù)x,y，都有x+yx。),()()(yxPySxSyxnS(x)：x是正實(shí)數(shù)nP(x，y)：x+yx12練習(xí)n課后題1.29（8）（9）（10）132.1.3 謂詞邏輯公式（公式 ）謂詞邏輯公式中所使用的符號(hào)有以下七種:(1)個(gè)體常量符:(2)個(gè)體變量符:(3)函數(shù)符:(4)謂詞符:(5)聯(lián)結(jié)詞符:(7)括號(hào)(,)(6)量詞符:, 一個(gè)謂詞邏輯公式中是由上述符號(hào)按一定上述符號(hào)按一定規(guī)則規(guī)則所組成的

8、所組成的符號(hào)串符號(hào)串。a,b,c, x,y,z f,g,h F,G,H142.1.3 謂詞公式（續(xù)）例如，下列各式是謂詞公式。但下列各式不是謂詞公式。)()(yRxQy)P(x,y)x)()y)y)Q(x,()x(P(x)(y)x,P(y)x)(E(y)x)()x(x)P()z, y(RQ(x)z, y,x(P)(z(y)x)(15練習(xí)：n下列哪些是謂詞公式：)()(.(7)()(. 6)(. 5)(),(. 4)()(. 3),(),),(. 2),(. 1xPxxyPxPxZPyxzxPxyxPxyyQxPxyxQzyyxpAyxyxP162.1.4 自由變?cè)图s束變?cè)捎谌Q量詞的作用，

9、使得命題函數(shù)中的x不再起變?cè)淖饔?，或者說，量詞約束了x的變?cè)饔茫谶@種情況下，稱變量x為“約束出現(xiàn)”，并稱x為約束變?cè)?。又如在這個(gè)謂詞公式中，易見，x是約束元，但y不是約束元，稱y是“自由出現(xiàn)”，并稱y為自由變?cè)?。量詞后括號(hào)括號(hào)中的內(nèi)容中的內(nèi)容稱為量詞的作用域或轄域。Q(x)x)(P(x)()Q(x)y),(P(xx)(x)Q(x)y),(P(xx17換名規(guī)則 在對(duì)約束元換名時(shí)，應(yīng)遵循以下兩種規(guī)則（約束元換名規(guī)則）：（1）對(duì)約束元（如x）換名時(shí)，更改的名稱范圍是 或中的x以及量詞作用域中所出現(xiàn)的所有x，在量詞作用域外的部分不換名。（2）換名時(shí)一定要更改為作用域中沒有出現(xiàn)的變量名稱xx18例

10、1解：在這個(gè)謂詞公式中，x既是約束元又是自由元，y也是約束元又是自由元。若把約束元x換名為u，約束元y換名為v，經(jīng)換名后，謂詞公式可寫成為于是可知，u，v是約束元，x，y是自由元。y)R(x,(Q(y)y)(Q(x)y)(P(x,x)()R(x,)(Q()()Q(y),(P()(vvvuuu19代入規(guī)則n對(duì)于謂詞公式中的自由變?cè)?，也可以更改，這種更改稱為代入，代入時(shí)應(yīng)對(duì)謂詞公式中出現(xiàn)該自由變?cè)拿恳惶幎歼M(jìn)行。這稱為自由元代入規(guī)則n例如， 可更改為y)R(x,P(x)x)(y)R(z,P(x)x)(20例1（續(xù)）n對(duì)下列謂詞公式中自由元進(jìn)行代入，使得一個(gè)變量在謂詞公式中只呈一種形式（約束元或自由

11、元）出現(xiàn)。 y)R(x,(Q(y)y)(Q(x)y)(P(x,x)(21謂詞關(guān)系式n將命題公式的等價(jià)關(guān)系命題公式的等價(jià)關(guān)系可以推廣為謂詞公式的等價(jià)關(guān)系謂詞公式的等價(jià)關(guān)系：QPQP)(),(xxQxxP)()()()(xxQxxPxxQxxP例如：命題公式將P和Q分別替換為：公式就可變?yōu)椋?2謂詞公式（等價(jià)或蘊(yùn)含）關(guān)系式n由于量詞的引入，謂詞公式多了如下公式：)()(.8)()(.7)()(.6)()(.5)()()(.4)()()(.3)()()()(.2)()()()(.1xxBAxBAxxxBAxBAxxxBAxBAxxxBAxBAxxAxxAxxAxxAxxxBxxAxBxAxxxBxx

12、AxBxAx存在服從對(duì)的分配律全稱服從對(duì)的分配律全稱量詞變?yōu)榇嬖诹吭~存在量詞變?yōu)槿Q量詞否定否定深入深入5、6、7、8其中的A是沒有出現(xiàn)約束變?cè)獂的謂詞公式。量詞作用域的擴(kuò)張和收縮23關(guān)系式)()(.14)()(.13)()(.12)()(.11)()()()(.10)()()()(. 9xBAxxxBAxBAxxxBABxAxBxxABxAxBxxAxxBxxAxBxAxxBxAxxxBxxA全稱對(duì)不服從分配律存在對(duì)不服從分配律24對(duì)偶定義 設(shè)A是命題公式，且A中僅有聯(lián)結(jié)詞 ， ，量詞 ， 。在A中把，F(xiàn)，T， ， ，分別換成，T，F(xiàn)， ， 后所得的命題公式稱為A的對(duì)偶公式。25對(duì)偶n例：

13、的對(duì)偶式：)(BxAx)(BxAx26練習(xí)：寫出對(duì)偶式)()(xyyRxP)()(xyyRxP272.3 前束范式定義定義:一個(gè)公式，如果量詞均非否定地在全式的開頭，且公式除量詞外，最多只含，則稱此公式叫前前束范式。束范式。例： xyz( Q(x,y) R(z) (前束范式)(x) P(x)(y)Q(y), (x)(P(x)(y)Q(x,y)(),()()()(zRyxQzxy)(),()()(yQyxPyxXXXX28前束范式n求解的一般步驟（不唯一）：n1.運(yùn)用基本等價(jià)公式，把各種聯(lián)結(jié)詞轉(zhuǎn)換成基本聯(lián)結(jié)詞： 、和n2.運(yùn)用E1、E8、E9、E24、E25、E26等將公式中的深入到各謂詞變?cè)?/p>

14、前面。n3.利用換名、代入規(guī)則，使所有的約束變?cè)煌易杂勺冊(cè)c約束變?cè)膊煌?。n4.利用E27、E28 、E29 、E30 、E31 、E32擴(kuò)大量詞的作用域至整個(gè)公式。29前束范式n例：把xP(x) R(x)變成前束范式n xP(x) R(x) yP(y) R(x) y(P(y) R(x)n例：把xP(x) xQ(x) 變成前束范式。 xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x) 30前束范式n例. 將公式(x)P(x)(y)Q(y)(x)R(x)化歸為前束范式 原式 (x)P(x)(y)Q(y)(x)R(x) (x)P(x)(y)Q

15、(y)(x)R(x) (x)P(x)(y)Q(y)(z)R(z) (x)(y)(z)(P(x)Q(y)R(z) 量詞前移31練習(xí)n課后題 1.32（2）32第三章 集合n3.1集合的基本概念n3.2集合的運(yùn)算及基本公式n3.3冪集n3.4包含排斥原理n3.5集合的直積333.1.1 集合的表示n一般用大寫的英文字母A, B, C, 來代表集合，|A|表示集合中元素的個(gè)數(shù)；n用小寫的英文字母a , b , c, 來代表集合中的元素。n一些特殊集合的表示：n代表自然數(shù)集合，n代表整數(shù)集合，n代表有理數(shù)集合，n代表實(shí)數(shù)集合，n代表復(fù)數(shù)集合343.1.1 元素與集合的關(guān)系n如果b是集合A中的元素，稱b

16、屬于屬于A，并記作n如果b不是集合A中的元素，稱b不屬于不屬于A，并記作AbAbn例如：QNZZN2,1,1,5,135練習(xí)：列出下列集合的元素n(1) x,|xN t (t2,3 x=2t)n(2) x,|xN ts (t0,1 s 3,4 txs)n(3) x,|xN t (t整除整除2 xt)4,64,61,2,31,2,3N-1,2N-1,236空集和全集空集和全集n不含有任何元素的集合稱為空集，記作n研究對(duì)象的全體稱為全集，記作E。nE=x|P(x) P(x)n注意：全集是個(gè)相對(duì)性的概念，由于研究的問題不同，所取的全集也不同，即使是同一個(gè)問題也可以有不同的全集37【例】確定下列命題是

17、否正確？n(1)n(2)n(3)n(4) n(5)n(6)n(7)n(8) ,cbacbaba,b, a, c,b, aba,b, a, b, aba,b, a,b, aba,XX383.2 集合的運(yùn)算及其基本公式n1.并運(yùn)算n2.交運(yùn)算交運(yùn)算n3.差集差集n4.補(bǔ)集補(bǔ)集n5.布爾和布爾和393.2 集合的運(yùn)算及其基本公式3.差集：設(shè)A，B是集合，由所有屬于屬于A但不屬于不屬于B的元素構(gòu)成的集合稱為A對(duì)B的差集差集，記作：A-B 例如: A = 1，2，3，4，B = 3，4，5 差集 A B = 1 , 2 , B AAB=5403.2 集合的運(yùn)算及其基本公式n4.補(bǔ)集n集合A的補(bǔ)集補(bǔ)集 A

18、可定義為 A=E A =x| (xA)A413.2 集合的運(yùn)算及其基本公式n5.布爾和（對(duì)稱差）n集合A,B的布爾和（對(duì)稱差）A+B 定義為： A+B=(A - B) (B - A)AB A+B=(A B) -(A B)42練習(xí)：n3.E=0,1,2,3,4,5,6,7,8,9,A=2,4,5,6,8,B=1,4,5,9,C=x|xZ+,2x5求：AB,C-B,(CB)A0,1,2,3,6,7,8,90,1,2,3,6,7,8,92,32,30,1,3,4,5,7,90,1,3,4,5,7,9433.3 冪集定義：設(shè)A是集合，由A的所有子集作為元素構(gòu)成的集合稱為A的冪集，記作AA2)(或冪集的

19、符號(hào)化表示冪集的符號(hào)化表示 = x| )(AAx 例：設(shè)集合例：設(shè)集合 A = 1, 2A = 1, 2，則其冪集，則其冪集2,1,2,1,)(A例：設(shè)集合例：設(shè)集合 A = aA = a，b b，c c ，則其冪集，則其冪集 ,)(AcbcabacbaA44練習(xí)練習(xí):1,1)3(,)2(,) 1 (,)() 1 (1 ,1,1 ,1,)1 ,1()3( 分別求下列集合的冪集分別求下列集合的冪集解：它們的冪集分別為解：它們的冪集分別為 ,)()2(45冪集n2定理定理： 設(shè)集合設(shè)集合A A是由是由n n個(gè)元素個(gè)元素所組成的有所組成的有限集，則限集，則A A的冪集的冪集是有限集是有限集，且由，且

20、由個(gè)元素組成。也即個(gè)元素組成。也即|(A)|=n2將集合中元素的個(gè)數(shù)稱為將集合中元素的個(gè)數(shù)稱為基數(shù)基數(shù)。463.5 笛卡爾乘積n1.有序?qū)?有序偶)和有序n元組定義定義：由兩個(gè)客體由兩個(gè)客體a和和b(允許允許a=b）按一定的順序排）按一定的順序排列成的列成的二元組二元組稱為一個(gè)稱為一個(gè)有序?qū)τ行驅(qū)?，記作，記作（a , b）,其中其中a稱為有序?qū)Φ姆Q為有序?qū)Φ牡谝豢腕w第一客體，b稱為有序?qū)Φ姆Q為有序?qū)Φ牡诙腕w第二客體如：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)如：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)(x,y)就是有序?qū)褪怯行驅(qū)Χx定義：有序偶有序偶(a(a，b)b)與與(c(c，d) d) ，如果有，如果有a = ca

21、 = c，b = db = d，則稱，則稱(a(a，b)b)與與(c(c，d)d)是是相等相等的的。 47笛卡兒乘積笛卡兒乘積定義定義：設(shè)設(shè)A, B A, B 是集合，由是集合，由所有所有以以A A中元素為中元素為第一客體，第一客體，B B中元素為第二客體的中元素為第二客體的有序?qū)τ行驅(qū)?gòu)構(gòu)成的成的集合集合稱為稱為A A到到B B的的笛卡兒乘積笛卡兒乘積( (直積直積) )，記，記作作A AB B，即，即BbA,ab)(a,BA48笛卡兒乘積笛卡兒乘積例如例如: :設(shè)設(shè)A = a, b , B = x, y,z,A = a, b , B = x, y,z,則則 A A到到B B的笛卡兒乘積的笛

22、卡兒乘積A AB =(a, x),(a,y),(a, z),(b, B =(a, x),(a,y),(a, z),(b, x),(b, y), (b, z)x),(b, y), (b, z)B到A的笛卡兒乘積BA=(x, a),(y, a),(z, a),(x, b),(y, b), (z, b)49第四章 關(guān)系n4.1關(guān)系及其運(yùn)算、關(guān)系的表示方式n4.2關(guān)系的有關(guān)性質(zhì)n4.3關(guān)系的閉包運(yùn)算n4.4等價(jià)關(guān)系和相容關(guān)系n4.5偏序關(guān)系50關(guān)系的實(shí)質(zhì)n由于二元關(guān)系就是符合某種特定要求的有序?qū)Φ募?nA上的二元關(guān)系應(yīng)是A上的笛卡兒乘積A A的子集。n此A到B的二元關(guān)系應(yīng)是笛卡兒乘積A B的子集51

23、n元關(guān)系的定義n定義n對(duì)于二元關(guān)系R,如果 (a, b) R，也可記作aRb，并稱a 與b 有關(guān)系R。如果(a, b) R，也可記作a R b，并稱a與b沒有關(guān)系R。.,2121的一個(gè)子集是元關(guān)系所確定的由集合nnXXXnXXX52二元關(guān)系的二元關(guān)系的定義域定義域和和值域值域n定義 設(shè)S是A到B的二元關(guān)系，使(x, y) S的所有x組成的集合稱為S的定義域，記作D(S)；n使(x, y) S的所有y組成的集合稱為S的值域，記作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一個(gè)元素構(gòu)成的集合, C(S)就是S的所有有序偶的第二個(gè)元素構(gòu)成的集合.53求關(guān)系的求關(guān)系的定義域定義域和和值域值

24、域n例如:設(shè) 則R的定義域D(R) ， 值域C(R) )b,a(),b,a(),b,a(R,b,b,bB,a,a,a,aA3433113214321a,a,a431,31bb54三種特殊的關(guān)系n對(duì)于任意集合，空集和集合本身都是它的子集，常稱這兩種子集為平凡子集。n定義笛卡兒乘積A B的兩個(gè)平凡子集，空集和A B本身稱為集合A到B的空關(guān)系和全域關(guān)系。n定義 設(shè)R是A上的二元關(guān)系且滿足則稱R為A上的恒等關(guān)系，并記作。)a, a(RAa AI552 關(guān)系的表示方法n1.1.關(guān)系矩陣關(guān)系矩陣 設(shè)集合 ，R是A到B的二元關(guān)系，令則稱為R的關(guān)系矩陣.b,b,bB,a,a,aAm2121nR)b,a(0R)

25、b,a(1cjijiij nm2n1nm22221m11211ijRccccccccccM56關(guān)系的表示方法n例1:設(shè) R是A到B的二元關(guān)系，且則R的關(guān)系矩陣為 b,b,b,b,bB,a,a,a,a,a,aA54321654321)b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a(R5646255433322111110000001010000001000010000011MRA是行，是行，B是列是列57復(fù)合關(guān)系n1. 復(fù)合關(guān)系的定義n定義 R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，R和S的復(fù)合記作RS，它是A到C的二元關(guān)系，僅當(dāng) (a, b)R，且

26、(b , c)S時(shí)，(a, c)RS(a, c)RS。n例:設(shè) ，R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，且 則R和S的復(fù)合 c,c,cC,b,b,b,bB,a,a,aA3214321321)c,b(),c,b(),c,b(),c,b( S)b,a (),b,a (),b,a (),b,a(R2332211143232211)c,a(),c,a(),c,a(),a(SR33322111c58復(fù)合關(guān)系的矩陣表示n定理 R是A到B的二元關(guān)系，其關(guān)系矩陣為 ，S是B到C的二元關(guān)系，其關(guān)系矩陣為 ，復(fù)合關(guān)系RS是A到C的二元關(guān)系，其關(guān)系矩陣為 ，則 注意:按普通矩陣乘法求 ,只不過是將乘法改為布爾

27、乘,加法改為布爾加.RMSMSRMSRSRMMMSRMM運(yùn)算法則與合運(yùn)算法則與合取連接詞一致取連接詞一致運(yùn)算法則與析取運(yùn)算法則與析取連接詞一致連接詞一致59例1n設(shè)A = 1，2，3，B = a, b, c, d, C = x, y, z，R是A到B的二元關(guān)系，R = (1, a), (1, b), (2, b), (3, c)，S是B到C的二元關(guān)系，S = (a, x), (b, x), (b, y), (b, z)。求復(fù)合關(guān)系RS的關(guān)系矩陣.n解:因?yàn)?n所以000000111001M,010000100011SRM000111111000000111001010000100011MMMS

28、RSR604-2 關(guān)系的重要性質(zhì)n關(guān)系的基本類型：自反的二元關(guān)系反自反的二元關(guān)系對(duì)稱的二元關(guān)系反對(duì)稱的二元關(guān)系可傳遞的二元關(guān)系n或稱為關(guān)系的性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、可傳遞性611. 自反的二元關(guān)系n定義定義 設(shè)設(shè)R R是是A A上的二元關(guān)系，如果對(duì)于上的二元關(guān)系，如果對(duì)于A A中中每一個(gè)每一個(gè)元素元素x x ，都有都有(x, x )R(x, x )R，則稱，則稱R R是是自反的自反的，也稱，也稱R R具有具有自反性自反性。n例例1 1: A = a, b, c, A: A = a, b, c, A上的二元關(guān)系上的二元關(guān)系 R = (a, a), (b, b), (c, c),

29、 (a, c), (c, b) R = (a, a), (b, b), (c, c), (a, c), (c, b) ，則則R R是是自反的二元關(guān)系。自反的二元關(guān)系。n例例2:2:設(shè)設(shè)A=1,2,3,4,A=1,2,3,4, R=(1,1),(2,2),(3,4),(4,2), R=(1,1),(2,2),(3,4),(4,2),因?yàn)橐驗(yàn)?A,3A,但但(3,3) , (3,3) , 所以所以R R不是不是A A上的自反關(guān)系上的自反關(guān)系. .R622. 反自反的二元關(guān)系n定義 R是A上的二元關(guān)系，如果對(duì)于A中每一個(gè)元素x,都有(x, x ) ,則稱R是反自反的，也稱R具有反自反性。n例1:設(shè)A

30、 = a, b, c, R = (a, c), (b, a), (b, c), (b, b) n因?yàn)?b,b)R, 則R不是A上的反自反關(guān)系。 n例2:設(shè)A = 1，2，3，R是A上的小于關(guān)系，即(1,2),(1,3),(2,3)n由于(1, 1), (2, 2), (3, 3)都不屬于R，所以R是A上的反自反關(guān)系。R632. 反自反的二元關(guān)系n例例3:3:設(shè)設(shè)A=1,2,3,R=(1,2),(2,3),(3,2),(3,3),A=1,2,3,R=(1,2),(2,3),(3,2),(3,3), S=(1,1),(2,2),(2,3),(3,3), S=(1,1),(2,2),(2,3),(3

31、,3),則則 R R既不是既不是A A上的反自反關(guān)系上的反自反關(guān)系( (因因(3,3)R),(3,3)R), 也不是也不是A A上的自反關(guān)系上的自反關(guān)系( (因因(1,1) ) (1,1) ) S S是是A A上的自反關(guān)系上的自反關(guān)系, ,但不是反自反關(guān)系但不是反自反關(guān)系. .注意注意: :一個(gè)關(guān)系一個(gè)關(guān)系R R如果不是如果不是自反關(guān)系，自反關(guān)系，不一定是不一定是反自反反自反關(guān)系關(guān)系. .R643. 對(duì)稱的二元關(guān)系n定義定義 R R是是A A上的二元關(guān)系，上的二元關(guān)系，每當(dāng)每當(dāng)(x, y) R(x, y) R時(shí)，就一定時(shí)，就一定有有(y, x) R(y, x) R，則稱，則稱R R是是對(duì)稱的對(duì)

32、稱的，也稱，也稱R R具有具有對(duì)稱性對(duì)稱性。n例例1 1: :設(shè)設(shè)A = a, b, c, R = (a, b), (b, a), (a, A = a, b, c, R = (a, b), (b, a), (a, c), (c, a) c), (c, a) ，所以，所以R R是對(duì)稱的是對(duì)稱的。n例例2 2: :設(shè)設(shè)A=1,2,3,4A=1,2,3,4上的二元關(guān)系上的二元關(guān)系 R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),因?yàn)橐驗(yàn)?4,3)R(4,3)R但但(3,4) (3,4) 。所以所以

33、R R不是對(duì)稱的不是對(duì)稱的。 R654. 反對(duì)稱的二元關(guān)系n定義定義 R R是是A A上的二元關(guān)系，上的二元關(guān)系，當(dāng)當(dāng)x yx y時(shí)，如果時(shí)，如果 (x, y) R(x, y) R，則必有，則必有(y, x)(y, x) ，稱，稱R R是是反對(duì)稱反對(duì)稱的的，也稱，也稱R R具有具有反對(duì)稱性反對(duì)稱性。n例例1:1: A=1,2,3, A=1,2,3,上的關(guān)系上的關(guān)系R=(1,2),(2,2),(3,1),R=(1,2),(2,2),(3,1),則則R R是是反對(duì)稱反對(duì)稱的的. .但但S=(1,2),(1,3),(2,2),(3,1)S=(1,2),(1,3),(2,2),(3,1)不是反對(duì)稱的不

34、是反對(duì)稱的. .因因?yàn)闉?313但但(1,3)S,(1,3)S,且且(3,1)S(3,1)SR664. 反對(duì)稱的二元關(guān)系n例例2:2: 設(shè)設(shè)A = 2A = 2，3 3，4 4，6 6， ，R R是是A A上的整除關(guān)系上的整除關(guān)系( (即當(dāng)即當(dāng)a, bAa, bA且且a a能整除能整除b b時(shí)，（時(shí)，（a, ba, b）R)R)，問，問R R是否是是否是A A上的反對(duì)稱關(guān)系上的反對(duì)稱關(guān)系? ?n解解: :因?yàn)橐驗(yàn)镽 = R = （2 2，2 2）, ,（2 2，4 4）, ,（2 2，6 6）, ,（3 3，3 3）, ,（3 3，6 6）, ,（4 4，4 4）, ,（6 6，6 6） n由

35、定義知：由定義知：R R是反對(duì)稱的是反對(duì)稱的. .n例例3 3: : 實(shí)數(shù)集合上的實(shí)數(shù)集合上的小于關(guān)系小于關(guān)系和和小于等于關(guān)系小于等于關(guān)系都是都是反對(duì)稱反對(duì)稱的的. .674. 反對(duì)稱的二元關(guān)系n例4:設(shè)A=a, b, c, d上的關(guān)系 R=(a ,a) ,(b ,c) ,(c ,d) ,(d ,c) ,S=(a ,a) ,(b ,b) ,(d ,d),則R既不是對(duì)稱的(因?yàn)?b ,c)R但(c ,b) ),也不是反對(duì)稱的 (因?yàn)?c ,d)R且(d ,c)R) 而S既是對(duì)稱的,也是反對(duì)稱的.R684. 反對(duì)稱的二元關(guān)系 小結(jié)n注意:對(duì)稱關(guān)系和反對(duì)稱關(guān)系不是兩個(gè)相互否定的概念. 存在既是對(duì)稱的

36、也是反對(duì)稱的二元關(guān)系,也存在既不是對(duì)稱的也不是反對(duì)稱的二元關(guān)系.695. 可傳遞的二元關(guān)系n定義 設(shè)R是A上的二元關(guān)系， 每當(dāng)(x, y) R且(y, z) R時(shí)，必有 (x, z) R，則稱R是可傳遞的，也稱R具有可傳遞性。n例1:實(shí)數(shù)集上的小于關(guān)系和小于等于關(guān)系都是可傳遞關(guān)系.如：ab,bc 則ac705. 可傳遞的二元關(guān)系n例2:設(shè)A=a ,b ,c上的關(guān)系R=(a ,a) ,(a ,b) ,(b ,c) ,(a ,c), S=(a ,b) ,(c ,b) , T=(a,b) ,(b ,b) ,(b ,c),則R,S,T是否可傳遞？ R,S是可傳遞的,T不是可傳遞的 因?yàn)門中有(a ,b

37、)T ,(b ,c) T但(a ,c) ,所以T不是可傳遞關(guān)系T71關(guān)系性質(zhì)總結(jié)1n集合A上的自反關(guān)系自反關(guān)系中必包含A中由每個(gè)每個(gè)元素自身所組成的有序?qū)ψ陨硭M成的有序?qū)?。?duì)應(yīng)關(guān)系矩陣主對(duì)角線上所有元素都為1；n恒等關(guān)系是自反關(guān)系，但自反關(guān)系不一定是恒等關(guān)系。n集合A上的反自反關(guān)系反自反關(guān)系中必不包含必不包含A中任意一個(gè)元素自身所組成的任意一個(gè)元素自身所組成的有序?qū)τ行驅(qū)Α?duì)應(yīng)關(guān)系矩陣主對(duì)角線上所有元素都為0.n對(duì)應(yīng)關(guān)系矩陣主對(duì)角線上元素有1，但不全為1的關(guān)系，既不是自反關(guān)系，也不是反自反關(guān)系。72關(guān)系性質(zhì)總結(jié)2n集合A上的對(duì)稱關(guān)系要求其中每個(gè)有序?qū)蓚€(gè)客體前后位置交換后的每個(gè)有序?qū)蓚€(gè)客體

38、前后位置交換后的有序?qū)θ栽谟行驅(qū)θ栽诖岁P(guān)系中。對(duì)應(yīng)關(guān)系矩陣一定是對(duì)稱矩陣。n集合A上的反對(duì)稱關(guān)系要求其中每個(gè)有序?qū)蓚€(gè)客體前后位置交換后每個(gè)有序?qū)蓚€(gè)客體前后位置交換后的有序?qū)σ欢ú辉诘挠行驅(qū)σ欢ú辉诖岁P(guān)系中。對(duì)應(yīng)關(guān)系矩陣一定不是對(duì)稱矩陣，但是不對(duì)稱的矩陣不一定就對(duì)應(yīng)于反對(duì)稱關(guān)系。n恒等關(guān)系即為對(duì)稱關(guān)系，又為反對(duì)稱關(guān)系。n關(guān)系中存在兩個(gè)僅客體順序不同的有序?qū)?，但又不全是的關(guān)系，既不是對(duì)稱關(guān)系，又不是反對(duì)稱關(guān)系。73等價(jià)關(guān)系的定義與實(shí)例等價(jià)關(guān)系的定義與實(shí)例定義定義 設(shè)設(shè) R 為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果 R 是是自反的、對(duì)自反的、對(duì)稱的和傳遞的稱的和傳遞的, 則稱則稱 R 為

39、為 A 上的上的等價(jià)關(guān)系等價(jià)關(guān)系. 設(shè)設(shè) R 是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系, 若若(x,y)R, 稱稱 x 等價(jià)于等價(jià)于y, 記做記做 xy. 實(shí)例實(shí)例 設(shè)設(shè) A=1,2,8, 如下定義如下定義A上的關(guān)系上的關(guān)系 R： R = (x,y) | x,yAxy(mod 3) 其中其中 xy(mod 3) 叫做叫做 x 與與 y 模模3相等相等, 即即 x 除以除以3的余數(shù)的余數(shù)與與 y 除以除以3的余數(shù)相等的余數(shù)相等. 74 偏序關(guān)系偏序關(guān)系定義定義 非空集合非空集合A上的上的自反自反、反對(duì)稱反對(duì)稱和和傳遞傳遞的關(guān)系，稱的關(guān)系，稱為為A上的上的偏序關(guān)系偏序關(guān)系. 實(shí)例實(shí)例 集合集合A上的上的恒等關(guān)

40、系恒等關(guān)系 IA 是是A上的偏序關(guān)系上的偏序關(guān)系. 小于等于關(guān)系小于等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系的偏序關(guān)系. 75偏序關(guān)系的定義偏序關(guān)系的定義n常常把集合A以及A上的偏序關(guān)系R合在一起統(tǒng)稱為偏序集，記作（A，R）。n由于偏序關(guān)系是自反的、反對(duì)稱的、傳遞的二元關(guān)系，所以一般用符號(hào)“”表示偏序。當(dāng)(a, b)R，時(shí)，常記作ab，偏序集也常記作（A，）。76例：n集合A=2，3，4，6，8n關(guān)系R=(x,y)|xA, yA, x整除yn即：R=(2,2),(3,3),(4,4),(6,6),(8,8),(2,4),(2,6),(2,8),(3

41、,6),(4,8)nR為偏序關(guān)系；n(A,R)為偏序集。77線性次序線性次序n定義 設(shè)設(shè)R R是集合是集合A A上的偏序，如果對(duì)每個(gè)上的偏序，如果對(duì)每個(gè)x,yx,yA A，必有，必有x xy y或或y y x x ，則稱，則稱R R是是線性線性次序的次序的( (全序的全序的) )，或稱，或稱R R是集合是集合A A上的上的線性次線性次序關(guān)系序關(guān)系。n易知：在易知：在線性次序關(guān)系線性次序關(guān)系中，中，任意兩個(gè)元素都任意兩個(gè)元素都是有關(guān)系是有關(guān)系的。的。78線性次序線性次序n例在整數(shù)集合中，例在整數(shù)集合中，大于等于關(guān)系大于等于關(guān)系是線性是線性序關(guān)系。序關(guān)系。n例設(shè)例設(shè)1,3,6,12,24, 1,3

42、,6,12,24, 是是整除關(guān)整除關(guān)系系 , ,則則是線性次序的是線性次序的, ,并且對(duì)并且對(duì)A A中元素有中元素有 1 3 6 12 241 3 6 12 2479偏序關(guān)系的哈斯圖表示n定義 設(shè)R是集合A上的偏序關(guān)系，a和b是A中的元素，如果(a, b) R，且在A中沒有其他元素c，使得 (a, c) R，(c, b) R，則稱元素b蓋住a。n例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除關(guān)系，由“蓋住”的定義可知，元素4蓋住2；但元素8并不蓋住2，因?yàn)橛性?，使得(2, 4)R和(4, 8)R，所以8不蓋住2。利用元素間的蓋住關(guān)系，能較方便地畫出偏序關(guān)系

43、的哈斯圖(即關(guān)系圖的簡化)80畫哈斯圖的方法n用平面上的點(diǎn)代表集合中的元素，當(dāng)b蓋住a時(shí)，代表b的點(diǎn)應(yīng)畫在代表a的點(diǎn)的上方，并用直線段連接否則不畫線n上面例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除關(guān)系，的哈斯圖如下：n n 24 16 12 8 6 4 10 3 2 5 181偏序集中的特殊元素n定義 設(shè)(A，)是偏序集，如果A中存在元素a，使得A中沒有其他元素x，滿足xa，則稱a為A中的極小元。n定義 設(shè)(A，)是偏序集，如果A中存在元素a，使得A中沒有其他元素x，滿足ax，則稱a為A中的極大元。82偏序集中的特殊元素n定義 設(shè)(A，)是偏序集，如果A中存在元素a，使得對(duì)于A中任何元素x，都有ax，則稱a為A中的最小元。n定義 設(shè)(A，)是偏序集，如果A中存在元素a，使得對(duì)于A中任何元素x，都有xa，則稱a為A中的最大元。n注意:最大(小)元與極大(小)元的區(qū)別83偏序集中的特殊元素n例1:A = 2，3，4，6，8，12，16,24，是A上的整除關(guān)系。其哈斯圖見圖1。n由定義可知，(A，)的極小元為2和3，極大元為16和24。 24 16 12 8 6 4 3 2