自反性和反自反性課件

3-6關(guān)系的性質(zhì)

本節(jié)討論集合X上的二元關(guān)系R的一些特殊性質(zhì)。3-6關(guān)系的性質(zhì)本節(jié)討論集合X上的二元關(guān)系1一、自反性和反自反性1、自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是自反的。R在X上自反(x)(xX<x，x>R)2、反自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是反自反的。R在X上反自反(x)(xX<x，x>R)一、自反性和反自反性2例如，在實(shí)數(shù)集合中，””是自反的，因?yàn)閷τ谌我鈱?shí)數(shù)xx成立。

平面上三角形的全等關(guān)系是自反的。例：X={a，b，c}，R1={<a，a>，<b，b>，<c，c>，<a，b>，<c，a>}是自反的，R2={<a，b>，<b，c>，<c，a>}是反自反的，R3={<a，a>，<b，c>}不是自反的也不是反自反的。注意：R不是自反的，未必一定是反自反的。一個(gè)關(guān)系可能既不是自反的，也不是反自反的。例如，在實(shí)數(shù)集合中，””是自反的，因?yàn)閷τ谌我鈱?shí)數(shù)xx成33、關(guān)系矩陣的特點(diǎn)自反關(guān)系的關(guān)系矩陣的對角元素均為1，反自反關(guān)系的關(guān)系矩陣的對角元素均為0。4、關(guān)系圖的特點(diǎn)自反關(guān)系的關(guān)系圖，每個(gè)結(jié)點(diǎn)均有自回路，而反自反關(guān)系的關(guān)系圖，每個(gè)結(jié)點(diǎn)均沒有自回路。3、關(guān)系矩陣的特點(diǎn)45、結(jié)論：R是X上的二元關(guān)系，則：(1)R是自反關(guān)系的充要條件是IXR。(2)R是反自反關(guān)系的充要條件是RIX=。如果|X|=n，其中n個(gè)序偶為<x，x>，則X上的自反關(guān)系共有2n*n-n個(gè)。例|X|=3，X上關(guān)系共有29個(gè)，而自反關(guān)系共有26個(gè)。5、結(jié)論：5二、對稱性和反對稱性1、對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R，就有<y，x>R，則稱R是對稱的。R在X上對稱(x)(y)(xXyX<x,y>R<y,x>R)2、反對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R和<y，x>R必有x=y，則稱R是反對稱的。R在X上反對稱(x)(y)(xXyX<x,y>R<y,x>Rx=y)二、對稱性和反對稱性6例如，平面上三角形的相似關(guān)系是對稱的。例：R1={<1，1>，<2，3>，<3，2>}是對稱的，R2={<1，1>，<3，3>}是對稱的也是反對稱的，R3={<2，2>，<2，3>，<3，2>，<3，1>}不是對稱的也不是反對稱的，R4={<2，2>，<2，3>，<3，1>}是反對稱的。注意：存在關(guān)系既不是對稱的，也不是反對稱的。也存在關(guān)系既是對稱的，也是反對稱的。例如，平面上三角形的相似關(guān)系是對稱的。73、關(guān)系矩陣和關(guān)系圖的特點(diǎn)對稱關(guān)系的關(guān)系矩陣是對稱矩陣，即對所有i，j，rij＝rji，對稱關(guān)系的關(guān)系圖，任何兩個(gè)不同的結(jié)點(diǎn)之間，或者有雙向兩條弧，或者沒有弧。反對稱關(guān)系的關(guān)系矩陣，如果在非對角元上rij＝1，則在其對稱位置上rji＝0，反對稱關(guān)系的關(guān)系圖，任何兩個(gè)不同的結(jié)點(diǎn)之間至多有一條弧。3、關(guān)系矩陣和關(guān)系圖的特點(diǎn)8三、傳遞性1、定義：設(shè)R是集合X上的二元關(guān)系，如果對于任意x，y，zX，每當(dāng)<x，y>R，<y，z>R時(shí)就有<x，z>R，則稱R是傳遞的。R在X上傳遞(x)(y)(z)(xXyXzX<x,y>R<y,z>R<x,z>R)例：R1={<x,y>,<z,x>,<z,y>}是傳遞的，R2={<x,b>,<c,d>}也是傳遞的，它沒有違背定義。R3={<x,b>,<b,x>}不是傳遞的。三、傳遞性92、定理：設(shè)R、S是A上的傳遞關(guān)系，則RS也是A上的傳遞關(guān)系。注意：R、S均是傳遞的，但RS未必是傳遞的。例：R={<a，b>}，S={<b，c>}，則R、S均是傳遞的，但RS={<a，b>，<b，c>}不是傳遞的。證明：設(shè)<x,y>RS，<y,z>RS，則<x,y>R，<y,z>R且<x,y>S，<y,z>S。因?yàn)镽、S是A上的傳遞關(guān)系，所以<x,z>R，<x,z>S，從而<x,z>RS，即RS是A上的傳遞關(guān)系。2、定理：設(shè)R、S是A上的傳遞關(guān)系，則RS也是A上的傳遞關(guān)10有人說：集合A上的關(guān)系R，如果是對稱且傳遞的，則它也是自反的。其理由是，從aRb，由對稱性得bRa，再由傳遞性得aRa，你說對嗎？為什么？不對！再看自反性、對稱性、傳遞性的定義。有人說：集合A上的關(guān)系R，如果是對稱且傳遞的，則11自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是自反的。對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R，就有<y，x>R，則稱R是對稱的。傳遞性：設(shè)R是集合X上的二元關(guān)系，如果對于任意x,y,zX，每當(dāng)<x，y>R，<y，z>R時(shí)就有<x，z>R，則稱R是傳遞的。自反性：對稱性：傳遞性：12自反性是說對于每一個(gè)xX，有<x，x>R。對稱性是說每當(dāng)<x，y>R，就有<y，x>R，沒有要求對于每一個(gè)xX，傳遞性是說每當(dāng)<x，y>R，<y，z>R時(shí)就有<x，z>R，也沒有要求對于每一個(gè)xX。因此不能從一個(gè)關(guān)系是對稱且傳遞的推出它是是自反的。例如A={a，b，c}，R={<a,a>，<b,b>，<a,b>，<b,a>}是A上的一個(gè)二元關(guān)系，R是對稱且傳遞的，但R不是自反的，因?yàn)閷τ赾A，沒有<c,c>R。自反性是說對于每一個(gè)xX，有<x，x>R。對13非空集合上的空關(guān)系是反自反的，對稱的，反對稱的和傳遞的，但不是自反的?？占仙系目贞P(guān)系則是自反的，反自反的，對稱的，反對稱的和傳遞的。非空集合上的全域關(guān)系是自反的，對稱的和傳遞的，但不是反自反的和反對稱的。非空集合上的空關(guān)系是反自反的，對稱的，反對稱的和14112頁例題4設(shè)某人有三個(gè)兒子，組成集合A={T,G,H}，在A上的兄弟關(guān)系具有哪些性質(zhì)。例題5集合I={1,2,3,4}，I上的關(guān)系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}討論R的性質(zhì)。練習(xí)113頁(1),(2),(3),(5)112頁練習(xí)15作業(yè)113頁(4)114頁(6)作業(yè)163-6關(guān)系的性質(zhì)

本節(jié)討論集合X上的二元關(guān)系R的一些特殊性質(zhì)。3-6關(guān)系的性質(zhì)本節(jié)討論集合X上的二元關(guān)系17一、自反性和反自反性1、自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是自反的。R在X上自反(x)(xX<x，x>R)2、反自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是反自反的。R在X上反自反(x)(xX<x，x>R)一、自反性和反自反性18例如，在實(shí)數(shù)集合中，””是自反的，因?yàn)閷τ谌我鈱?shí)數(shù)xx成立。

平面上三角形的全等關(guān)系是自反的。例：X={a，b，c}，R1={<a，a>，<b，b>，<c，c>，<a，b>，<c，a>}是自反的，R2={<a，b>，<b，c>，<c，a>}是反自反的，R3={<a，a>，<b，c>}不是自反的也不是反自反的。注意：R不是自反的，未必一定是反自反的。一個(gè)關(guān)系可能既不是自反的，也不是反自反的。例如，在實(shí)數(shù)集合中，””是自反的，因?yàn)閷τ谌我鈱?shí)數(shù)xx成193、關(guān)系矩陣的特點(diǎn)自反關(guān)系的關(guān)系矩陣的對角元素均為1，反自反關(guān)系的關(guān)系矩陣的對角元素均為0。4、關(guān)系圖的特點(diǎn)自反關(guān)系的關(guān)系圖，每個(gè)結(jié)點(diǎn)均有自回路，而反自反關(guān)系的關(guān)系圖，每個(gè)結(jié)點(diǎn)均沒有自回路。3、關(guān)系矩陣的特點(diǎn)205、結(jié)論：R是X上的二元關(guān)系，則：(1)R是自反關(guān)系的充要條件是IXR。(2)R是反自反關(guān)系的充要條件是RIX=。如果|X|=n，其中n個(gè)序偶為<x，x>，則X上的自反關(guān)系共有2n*n-n個(gè)。例|X|=3，X上關(guān)系共有29個(gè)，而自反關(guān)系共有26個(gè)。5、結(jié)論：21二、對稱性和反對稱性1、對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R，就有<y，x>R，則稱R是對稱的。R在X上對稱(x)(y)(xXyX<x,y>R<y,x>R)2、反對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R和<y，x>R必有x=y，則稱R是反對稱的。R在X上反對稱(x)(y)(xXyX<x,y>R<y,x>Rx=y)二、對稱性和反對稱性22例如，平面上三角形的相似關(guān)系是對稱的。例：R1={<1，1>，<2，3>，<3，2>}是對稱的，R2={<1，1>，<3，3>}是對稱的也是反對稱的，R3={<2，2>，<2，3>，<3，2>，<3，1>}不是對稱的也不是反對稱的，R4={<2，2>，<2，3>，<3，1>}是反對稱的。注意：存在關(guān)系既不是對稱的，也不是反對稱的。也存在關(guān)系既是對稱的，也是反對稱的。例如，平面上三角形的相似關(guān)系是對稱的。233、關(guān)系矩陣和關(guān)系圖的特點(diǎn)對稱關(guān)系的關(guān)系矩陣是對稱矩陣，即對所有i，j，rij＝rji，對稱關(guān)系的關(guān)系圖，任何兩個(gè)不同的結(jié)點(diǎn)之間，或者有雙向兩條弧，或者沒有弧。反對稱關(guān)系的關(guān)系矩陣，如果在非對角元上rij＝1，則在其對稱位置上rji＝0，反對稱關(guān)系的關(guān)系圖，任何兩個(gè)不同的結(jié)點(diǎn)之間至多有一條弧。3、關(guān)系矩陣和關(guān)系圖的特點(diǎn)24三、傳遞性1、定義：設(shè)R是集合X上的二元關(guān)系，如果對于任意x，y，zX，每當(dāng)<x，y>R，<y，z>R時(shí)就有<x，z>R，則稱R是傳遞的。R在X上傳遞(x)(y)(z)(xXyXzX<x,y>R<y,z>R<x,z>R)例：R1={<x,y>,<z,x>,<z,y>}是傳遞的，R2={<x,b>,<c,d>}也是傳遞的，它沒有違背定義。R3={<x,b>,<b,x>}不是傳遞的。三、傳遞性252、定理：設(shè)R、S是A上的傳遞關(guān)系，則RS也是A上的傳遞關(guān)系。注意：R、S均是傳遞的，但RS未必是傳遞的。例：R={<a，b>}，S={<b，c>}，則R、S均是傳遞的，但RS={<a，b>，<b，c>}不是傳遞的。證明：設(shè)<x,y>RS，<y,z>RS，則<x,y>R，<y,z>R且<x,y>S，<y,z>S。因?yàn)镽、S是A上的傳遞關(guān)系，所以<x,z>R，<x,z>S，從而<x,z>RS，即RS是A上的傳遞關(guān)系。2、定理：設(shè)R、S是A上的傳遞關(guān)系，則RS也是A上的傳遞關(guān)26有人說：集合A上的關(guān)系R，如果是對稱且傳遞的，則它也是自反的。其理由是，從aRb，由對稱性得bRa，再由傳遞性得aRa，你說對嗎？為什么？不對！再看自反性、對稱性、傳遞性的定義。有人說：集合A上的關(guān)系R，如果是對稱且傳遞的，則27自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)xX，有<x，x>R，則稱R是自反的。對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個(gè)x，yX，每當(dāng)<x，y>R，就有<y，x>R，則稱R是對稱的。傳遞性：設(shè)R是集合X上的二元關(guān)系，如果對于任意x,y,zX，每當(dāng)<x，y>R，<y，z>R時(shí)就有<x，z>R，則稱R是傳遞的。自反性：對稱性：傳遞性：28自反性是說對于每一個(gè)xX，有<x，x