離散數(shù)學復(fù)習2

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

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

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

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

5、是大學生是大學生”可表示為可表示為F(a)62.1.2 量詞)(xxF 全稱量詞記作 “ x ”，其含意是：“所有的x ”、“每一個x ”、“凡是x ”、“任意的x ”等等。表示表示對個體域中的所有個體其對個體域中的所有個體其謂詞謂詞F(x)F(x)均為真均為真。72.1.2 量詞)(xxF 存在量詞記作 “ ”，其含意是：“存在著x ”、“有些x ” 等等。表示表示個體域中存在個體域中存在某些個體某些個體其其謂詞謂詞F(x)F(x)均為真均為真。x8函數(shù) 在謂詞邏輯中，在謂詞邏輯中，個體與個體間有一定的關(guān)系個體與個體間有一定的關(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)：李平的媽媽；句子符號化為：D(f(a)9用謂詞和量詞表示句子的步驟：n參考題目給出的個體域，如果沒有指明，假設(shè)為全總個體域；n確定句子中的謂詞和個體變元；在全總個體域下，句子中的名詞（人、數(shù)、動物等）都需要使用特性謂詞表示；多元謂詞使用多個不同的個體變元。n根據(jù)句子中特性謂詞前的修飾詞選擇量詞； ：“所有的”、“凡是”、“一切”、“任意”、“每一個”等詞，或省略的情況 ：“存在”、“有些”、“某些”、“幾個”等詞n根據(jù)量詞確定謂詞之間的關(guān)系； 所限定的個體變元所在的特性

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

8、所組成的符號串符號串。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練習：n下列哪些是謂詞公式：)()(.(7)()(. 6)(. 5)(),(. 4)()(. 3),(),),(. 2),(. 1xPxxyPxPxZPyxzxPxyxPxyyQxPxyxQzyyxpAyxyxP162.1.4 自由變元和約束變元由于全稱量詞的作用，

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

10、1解：在這個謂詞公式中，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對于謂詞公式中的自由變元，也可以更改，這種更改稱為代入，代入時應(yīng)對謂詞公式中出現(xiàn)該自由變元的每一處都進行。這稱為自由元代入規(guī)則n例如， 可更改為y)R(x,P(x)x)(y)R(z,P(x)x)(20例1（續(xù)）n對下列謂詞公式中自由元進行代入，使得一個變量在謂詞公式中只呈一種形式（約束元或自由

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

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

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

14、前面。n3.利用換名、代入規(guī)則，使所有的約束變元均不同名，且自由變元與約束變元也不同名。n4.利用E27、E28 、E29 、E30 、E31 、E32擴大量詞的作用域至整個公式。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練習n課后題 1.32（2）32第三章 集合n3.1集合的基本概念n3.2集合的運算及基本公式n3.3冪集n3.4包含排斥原理n3.5集合的直積333.1.1 集合的表示n一般用大寫的英文字母A, B, C, 來代表集合，|A|表示集合中元素的個數(shù)；n用小寫的英文字母a , b , c, 來代表集合中的元素。n一些特殊集合的表示：n代表自然數(shù)集合，n代表整數(shù)集合，n代表有理數(shù)集合，n代表實數(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練習：列出下列集合的元素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研究對象的全體稱為全集，記作E。nE=x|P(x) P(x)n注意：全集是個相對性的概念，由于研究的問題不同，所取的全集也不同，即使是同一個問題也可以有不同的全集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 集合的運算及其基本公式n1.并運算n2.交運算交運算n3.差集差集n4.補集補集n5.布爾和布爾和393.2 集合的運算及其基本公式3.差集：設(shè)A，B是集合，由所有屬于屬于A但不屬于不屬于B的元素構(gòu)成的集合稱為A對B的差集差集，記作：A-B 例如: A = 1，2，3，4，B = 3，4，5 差集 A B = 1 , 2 , B AAB=5403.2 集合的運算及其基本公式n4.補集n集合A的補集補集 A

18、可定義為 A=E A =x| (xA)A413.2 集合的運算及其基本公式n5.布爾和（對稱差）n集合A,B的布爾和（對稱差）A+B 定義為： A+B=(A - B) (B - A)AB A+B=(A B) -(A B)42練習：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、符號化表示冪集的符號化表示 = x| )(AAx 例：設(shè)集合例：設(shè)集合 A = 1, 2A = 1, 2，則其冪集，則其冪集2,1,2,1,)(A例：設(shè)集合例：設(shè)集合 A = aA = a，b b，c c ，則其冪集，則其冪集 ,)(AcbcabacbaA44練習練習:1,1)3(,)2(,) 1 (,)() 1 (1 ,1,1 ,1,)1 ,1()3( 分別求下列集合的冪集分別求下列集合的冪集解：它們的冪集分別為解：它們的冪集分別為 ,)()2(45冪集n2定理定理： 設(shè)集合設(shè)集合A A是由是由n n個元素個元素所組成的有所組成的有限集，則限集，則A A的冪集的冪集是有限集是有限集，且由，且

20、由個元素組成。也即個元素組成。也即|(A)|=n2將集合中元素的個數(shù)稱為將集合中元素的個數(shù)稱為基數(shù)基數(shù)。463.5 笛卡爾乘積n1.有序?qū)?有序偶)和有序n元組定義定義：由兩個客體由兩個客體a和和b(允許允許a=b）按一定的順序排）按一定的順序排列成的列成的二元組二元組稱為一個稱為一個有序?qū)τ行驅(qū)Γ涀?，記作（a , b）,其中其中a稱為有序?qū)Φ姆Q為有序?qū)Φ牡谝豢腕w第一客體，b稱為有序?qū)Φ姆Q為有序?qū)Φ牡诙腕w第二客體如：平面直角坐標系中點的坐標如：平面直角坐標系中點的坐標(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)系及其運算、關(guān)系的表示方式n4.2關(guān)系的有關(guān)性質(zhì)n4.3關(guān)系的閉包運算n4.4等價關(guān)系和相容關(guān)系n4.5偏序關(guān)系50關(guān)系的實質(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對于二元關(guān)系R,如果 (a, b) R，也可記作aRb，并稱a 與b 有關(guān)系R。如果(a, b) R，也可記作a R b，并稱a與b沒有關(guān)系R。.,2121的一個子集是元關(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òu)成的集合, C(S)就是S的所有有序偶的第二個元素構(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對于任意集合，空集和集合本身都是它的子集，常稱這兩種子集為平凡子集。n定義笛卡兒乘積A B的兩個平凡子集，空集和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)系，僅當 (a, b)R，且

26、(b , c)S時，(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運算法則與合運算法則與合取連接詞一致取連接詞一致運算法則與析取運算法則與析取連接詞一致連接詞一致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解:因為 n所以000000111001M,010000100011SRM000111111000000111001010000100011MMMS

28、RSR604-2 關(guān)系的重要性質(zhì)n關(guān)系的基本類型：自反的二元關(guān)系反自反的二元關(guān)系對稱的二元關(guān)系反對稱的二元關(guān)系可傳遞的二元關(guān)系n或稱為關(guān)系的性質(zhì)：自反性、反自反性、對稱性、反對稱性、可傳遞性611. 自反的二元關(guān)系n定義定義 設(shè)設(shè)R R是是A A上的二元關(guān)系，如果對于上的二元關(guān)系，如果對于A A中中每一個每一個元素元素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),因為因為3A,3A,但但(3,3) , (3,3) , 所以所以R R不是不是A A上的自反關(guān)系上的自反關(guān)系. .R622. 反自反的二元關(guān)系n定義 R是A上的二元關(guān)系，如果對于A中每一個元素x,都有(x, x ) ,則稱R是反自反的，也稱R具有反自反性。n例1:設(shè)A

30、 = a, b, c, R = (a, c), (b, a), (b, c), (b, b) 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)系. .注意注意: :一個關(guān)系一個關(guān)系R R如果不是如果不是自反關(guān)系，自反關(guān)系，不一定是不一定是反自反反自反關(guān)系關(guān)系. .R643. 對稱的二元關(guān)系n定義定義 R R是是A A上的二元關(guān)系，上的二元關(guān)系，每當每當(x, y) R(x, y) R時，就一定時，就一定有有(y, x) R(y, x) R，則稱，則稱R R是是對稱的對

32、稱的，也稱，也稱R R具有具有對稱性對稱性。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是對稱的是對稱的。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),因為因為(4,3)R(4,3)R但但(3,4) (3,4) 。所以所以

33、R R不是對稱的不是對稱的。 R654. 反對稱的二元關(guān)系n定義定義 R R是是A A上的二元關(guān)系，上的二元關(guān)系，當當x yx y時，如果時，如果 (x, y) R(x, y) R，則必有，則必有(y, x)(y, x) ，稱，稱R R是是反對稱反對稱的的，也稱，也稱R R具有具有反對稱性反對稱性。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是是反對稱反對稱的的. .但但S=(1,2),(1,3),(2,2),(3,1)S=(1,2),(1,3),(2,2),(3,1)不是反對稱的不

34、是反對稱的. .因因為為1313但但(1,3)S,(1,3)S,且且(3,1)S(3,1)SR664. 反對稱的二元關(guān)系n例例2:2: 設(shè)設(shè)A = 2A = 2，3 3，4 4，6 6， ，R R是是A A上的整除關(guān)系上的整除關(guān)系( (即當即當a, bAa, bA且且a a能整除能整除b b時，（時，（a, ba, b）R)R)，問，問R R是否是是否是A A上的反對稱關(guān)系上的反對稱關(guān)系? ?n解解: :因為因為R = 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是反對稱的是反對稱的. .n例例3 3: : 實數(shù)集合上的實數(shù)集合上的小于關(guān)系小于關(guān)系和和小于等于關(guān)系小于等于關(guān)系都是都是反對稱反對稱的的. .674. 反對稱的二元關(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既不是對稱的(因為(b ,c)R但(c ,b) ),也不是反對稱的 (因為(c ,d)R且(d ,c)R) 而S既是對稱的,也是反對稱的.R684. 反對稱的二元關(guān)系 小結(jié)n注意:對稱關(guān)系和反對稱關(guān)系不是兩個相互否定的概念. 存在既是對稱的

36、也是反對稱的二元關(guān)系,也存在既不是對稱的也不是反對稱的二元關(guān)系.695. 可傳遞的二元關(guān)系n定義 設(shè)R是A上的二元關(guān)系， 每當(x, y) R且(y, z) R時，必有 (x, z) R，則稱R是可傳遞的，也稱R具有可傳遞性。n例1:實數(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不是可傳遞的 因為T中有(a ,b

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

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

39、為 A 上的上的等價關(guān)系等價關(guān)系. 設(shè)設(shè) R 是一個等價關(guān)系是一個等價關(guān)系, 若若(x,y)R, 稱稱 x 等價于等價于y, 記做記做 xy. 實例實例 設(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上的上的自反自反、反對稱反對稱和和傳遞傳遞的關(guān)系，稱的關(guān)系，稱為為A上的上的偏序關(guān)系偏序關(guān)系. 實例實例 集合集合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)系是自反的、反對稱的、傳遞的二元關(guān)系，所以一般用符號“”表示偏序。當(a, b)R，時，常記作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上的偏序，如果對每個上的偏序，如果對每個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)系中，中，任意兩個元素都任意兩個元素都是有關(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)系系 , ,則則是線性次序的是線性次序的, ,并且對并且對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，因為有元素4，使得(2, 4)R和(4, 8)R，所以8不蓋住2。利用元素間的蓋住關(guān)系，能較方便地畫出偏序關(guān)系

43、的哈斯圖(即關(guān)系圖的簡化)80畫哈斯圖的方法n用平面上的點代表集合中的元素，當b蓋住a時，代表b的點應(yīng)畫在代表a的點的上方，并用直線段連接否則不畫線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，使得對于A中任何元素x，都有ax，則稱a為A中的最小元。n定義 設(shè)(A，)是偏序集，如果A中存在元素a，使得對于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