左孝凌離散數(shù)學(xué)課件3.6關(guān)系的性質(zhì).ppt

2019/7/8,1,離散數(shù)學(xué)(Discrete Mathematics),2019/7/8,1,3.6 關(guān)系的性質(zhì),一、自反性與反自反性 二、對(duì)稱性與反對(duì)稱性 三、傳遞性,1.自反性 設(shè)R為定義在A上的二元關(guān)系，即RAA, 如果對(duì)于每一個(gè)xA，有xRx (R)，則稱二元關(guān)系R是自反的。 R在A上是自反的 (x)( xA xRx) R在A上是非自反的 (x)( xA R) 例如，在實(shí)數(shù)集合中，“”是自反的，因?yàn)閷?duì)于任意實(shí)數(shù)xx成立。 平面上三角形的全等關(guān)系是自反的,一、自反性與反自反性,1.自反性 例：設(shè)集合A=a,b,c上有下列關(guān)系： R1=, R2=, R3=, R4=A上的空關(guān)系= 分析它們的自反性，并畫出關(guān)系圖和關(guān)系矩陣,一、自反性與反自反性,1 1 0 0 1 0 1 0 1,0 1 0 0 0 1 1 0 0,1 0 0 0 0 1 0 0 0,0 0 0 0 0 0 0 0 0,自反,1.自反性,一、自反性與反自反性,特點(diǎn)： 具有自反性的關(guān)系矩陣主對(duì)角線元素全是1； 關(guān)系圖上每個(gè)節(jié)點(diǎn)都有自回路 思考： 具有自反性的關(guān)系與恒等關(guān)系有何區(qū)別和聯(lián)系,2.反自反性：設(shè)RAA, 如果對(duì)于每一個(gè)xA，有R，則稱二元關(guān)系R是反自反的。 R在A上是反自反的 (x)(xA R ) R在A上是非反自反的 (x)( xA xRx),一、自反性與反自反性,2.反自反性 例：設(shè)集合A=a,b,c上有下列關(guān)系： R1=, R2=, R3=, R4=A上的空關(guān)系= 分析它們的反自反性，并畫出關(guān)系圖和關(guān)系矩陣,一、自反性與反自反性,1 1 0 0 1 0 1 0 1,0 1 0 0 0 1 1 0 0,1 0 0 0 0 1 0 0 0,0 0 0 0 0 0 0 0 0,反自反,既非自反也非反自反,反自反,2.反自反性,一、自反性與反自反性,特點(diǎn)： 對(duì)于關(guān)系矩陣，其主對(duì)角線元素全是0； 對(duì)于關(guān)系圖，其每個(gè)節(jié)點(diǎn)都沒(méi)有自回路,2.反自反性,一、自反性與反自反性,注意： 如果R不是自反關(guān)系，則R未必一定是反自反關(guān)系，有可能既非自反關(guān)系，也非反自反關(guān)系，如R3； 一個(gè)非空集合上的關(guān)系不能既是自反關(guān)系，又是反自反關(guān)系。 結(jié)論： R是A上的關(guān)系，則： 1）R是自反關(guān)系的充要條件是IA R; 2）R是反自反關(guān)系的充要條件是RIA =;,1.對(duì)稱性： 設(shè)RAA, 如果對(duì)于每個(gè)x,yA,每當(dāng) xRy，則必有 yRx，則稱集合A上的關(guān)系R是對(duì)稱的。 R在A上對(duì)稱(x)(y)(xAyA xRyyRx) R非對(duì)稱 (x)(y)(xAyA xRyyRx) 例如，實(shí)數(shù)集R上的“=”，三角形的相似關(guān)系，朋友關(guān)系都是對(duì)稱的。,二、對(duì)稱性與反對(duì)稱性,1.對(duì)稱性： 設(shè)RAA, 如果對(duì)于任意x,yA,每當(dāng) xRy，則必有 yRx，則稱集合A上的關(guān)系R是對(duì)稱的。 R在A上對(duì)稱(x)(y)(xAyA xRyyRx) R非對(duì)稱 (x)(y)(xAyA xRyyRx) 例：設(shè)集合A=a,b,c上有下列關(guān)系： R1=, R2=, R3=, R4=, R5=, R6=,二、對(duì)稱性與反對(duì)稱性,1.對(duì)稱性 例：設(shè)集合A=a,b,c上有下列關(guān)系： R1=, R2=, R3=, R4=, R5=, R6=,二、對(duì)稱性與反對(duì)稱性,0 1 0 1 0 0 0 0 0,0 1 0 0 0 1 0 1 0,1 0 0 0 1 0 0 0 0,1 0 0 0 1 0 0 0 1,0 1 0 0 0 0 0 1 0,對(duì)稱,對(duì)稱,對(duì)稱,對(duì)稱,1.對(duì)稱性 特點(diǎn)： 具有對(duì)稱性的關(guān)系矩陣關(guān)于主對(duì)角線對(duì)稱 關(guān)系圖的特點(diǎn)是任何兩個(gè)不同的節(jié)點(diǎn)之間，或者是一來(lái)一回兩條弧，或者是沒(méi)有弧。是否有自回路，對(duì)對(duì)稱沒(méi)有影響。 即：R是對(duì)稱的 MR是對(duì)稱的 GR的任何兩個(gè)頂點(diǎn)之間若有邊, 則必有兩條方向相反的有向邊,二、對(duì)稱性與反對(duì)稱性,2.反對(duì)稱性： 設(shè)RAA,如果對(duì)于每個(gè)x,yA,每當(dāng) xRy和yRx，必有x=y，則稱集合A上的關(guān)系R是反對(duì)稱的。 R是反對(duì)稱的 (x)(y)(xAyA xRy yRx x=y ) (x)(y)(xAyA xy xRy yRx ) R非反對(duì)稱 (x)(y)(xA yA xRy yRx xy) 例如，實(shí)數(shù)集合R上的“”、“”集合上的“”關(guān)系，都是反對(duì)稱的。,二、對(duì)稱性與反對(duì)稱性,2.反對(duì)稱性： 例：設(shè)集合A=a,b,c上有下列關(guān)系，考察其反對(duì)稱性 R1=, R2=, R3=, R4=, R5=, R6=,二、對(duì)稱性與反對(duì)稱性,2.反對(duì)稱性 例：設(shè)集合A=a,b,c上有下列關(guān)系： R1=, R2=, R3=, R4=, R5=, R6=,二、對(duì)稱性與反對(duì)稱性,0 1 0 1 0 0 0 0 0,0 1 0 0 0 1 0 1 0,1 0 0 0 1 0 0 0 0,1 0 0 0 1 0 0 0 1,0 1 0 0 0 0 0 1 0,既非對(duì)稱也非反對(duì)稱,反對(duì)稱,反對(duì)稱,反對(duì)稱,反對(duì)稱,R1=， R2=， R3=， R4=，,對(duì)稱的,是對(duì)稱的也是反對(duì)稱的,不是對(duì)稱的也不是反對(duì)稱的，,反對(duì)稱的,2.反對(duì)稱性 特點(diǎn)： 具有反對(duì)稱性的關(guān)系矩陣如果在非對(duì)角元上rij=1，則在其對(duì)稱位置上，rji=0 ，即rji和rij（ ij ）這兩個(gè)數(shù)至多有一個(gè)是1，但允許兩個(gè)均為0 關(guān)系圖上任何兩個(gè)不同的節(jié)點(diǎn)之間，至多有一條弧，但允許沒(méi)有弧 即：R是反對(duì)稱的 在MR中, xi xj( ij rij=1rji=0) 在GR中, xi xj (ij), 若有有向邊, 則必沒(méi)有。,二、對(duì)稱性與反對(duì)稱性,說(shuō)明：反對(duì)稱性的等價(jià)說(shuō)法 x,y A,如x y且 R,則必有 R 即兩個(gè)不同點(diǎn)結(jié)點(diǎn)間不允許有兩條??； 總結(jié)： 有些關(guān)系既不是對(duì)稱的，也不是反對(duì)稱的； 有些關(guān)系既是對(duì)稱的，也是反對(duì)稱的； 空關(guān)系、恒等關(guān)系既是對(duì)稱的，也是反對(duì)稱的； 全關(guān)系EA不是反對(duì)稱的。,二、對(duì)稱性與反對(duì)稱性,三、傳遞性,定義：設(shè)RAA, 如果對(duì)于任意的x,y,zA, 每當(dāng)xRy， yRz 時(shí)就有xRz ，稱關(guān)系R在A上是傳遞的。 R在A上是傳遞的 (x)(y)(z)(xAyAzAxRy yRz xRz) R非傳遞 (x)(y)(z)(xAyAzAxRy yRzxRz)。 例如，實(shí)數(shù)集R上的“”“”“”“”以及集合上的“”,三、傳遞性,定義：設(shè)RAA, 如果對(duì)于任意的x,y,zA, 每當(dāng)xRy， yRz 時(shí)就有xRz ，稱關(guān)系R在A上是傳遞的。 R在A上是傳遞的 (x)(y)(z)(xAyAzAxRy yRz xRz) R非傳遞 (x)(y)(z)(xAyAzAxRy yRzxRz)。,例：設(shè)A=a,b,c考擦下列關(guān)系的傳遞性 R1=, R2= R3=,三、傳遞性,特點(diǎn)： 如果R是傳遞關(guān)系，如果結(jié)點(diǎn)x能通過(guò)有向弧組成的有向路通向結(jié)點(diǎn)z，（該有向路包含兩條或兩條以上的?。﹦tx必須有有向弧直接指向z，否則R就不是傳遞的； 傳遞關(guān)系的關(guān)系矩陣的特點(diǎn)不是很容易看出，后面會(huì)講到,三、傳遞性,定理1： 如果R是傳遞關(guān)系，如果結(jié)點(diǎn)x能通過(guò)有向弧組成的有向路通向結(jié)點(diǎn)z，（該有向路包含兩條或兩條以上的?。﹦tx必須有有向弧直接指向z，否則R就不是傳遞的； 傳遞關(guān)系的關(guān)系矩陣的特點(diǎn)不是很容易看出，后面會(huì)講到,有人說(shuō)：集合A上的關(guān)系R，如果是對(duì)稱且傳遞的，則它也是自反的。其理由是，從aRb，由對(duì)稱性得bRa，再由傳遞性得aRa，你說(shuō)對(duì)嗎？為什么？,不對(duì)！再看自反性、對(duì)稱性、傳遞性的定義。,自反性： 設(shè)R是集合X上的二元關(guān)系，如果對(duì)于每一個(gè)xX，有R，則稱R是自反的。,對(duì)稱性： 設(shè)R是集合X上的二元關(guān)系，如果對(duì)于每一個(gè)x，yX，每當(dāng)R，就有R，則稱R是對(duì)稱的。,傳遞性： 設(shè)R是集合X上的二元關(guān)系，如果對(duì)于任意x,y,zX，每當(dāng)R，R時(shí)就有R，則稱R是傳遞的。,自反性是說(shuō)對(duì)于每一個(gè)xX，有R。對(duì)稱性是說(shuō)每當(dāng)R，就有R，沒(méi)有要求對(duì)于每一個(gè)xX，傳遞性是說(shuō)每當(dāng)R，R時(shí)就有R ，也沒(méi)有要求對(duì)于每一個(gè)xX。因此不能從一個(gè)關(guān)系是對(duì)稱且傳遞的推出它是是自反的。,例如A=a，b，c， R=，是A上的一個(gè)二元關(guān)系，R是對(duì)稱且傳遞的，但R不是自反的，因?yàn)閷?duì)于cA，沒(méi)有 R。,非空集合上的空關(guān)系是反自反的，對(duì)稱的，反對(duì)稱的和傳遞的，但不是自反的?？占仙系目贞P(guān)系則是自反的，