離散數(shù)學(xué)集合論免費(fèi)

1第1頁(yè)，共21頁(yè)，2023年，2月20日，星期一自反性與反自反性定義設(shè)R為A上的關(guān)系,

(1)若x(x∈A→<x,x>R),則稱R在A上是自反的.

(2)若x(x∈A→<x,x>R),則稱R在A上是反自反的.

實(shí)例：自反關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA

小于等于關(guān)系LA,整除關(guān)系DA反自反關(guān)系：實(shí)數(shù)集上的小于關(guān)系冪集上的真包含關(guān)系

第2頁(yè)，共21頁(yè)，2023年，2月20日，星期一實(shí)例例1A={1,2,3},R1,R2,R3是A上的關(guān)系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,1>,<2,2>,<3,3>,<1,2>}

R3＝{<1,3>}R2自反,R3反自反,R1既不是自反也不是反自反的第3頁(yè)，共21頁(yè)，2023年，2月20日，星期一對(duì)稱性與反對(duì)稱性定義

設(shè)R為A上的關(guān)系,

(1)若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對(duì)稱的關(guān)系.

(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對(duì)稱關(guān)系.

實(shí)例：對(duì)稱關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系IA，空關(guān)系是A上的反對(duì)稱關(guān)系.

第4頁(yè)，共21頁(yè)，2023年，2月20日，星期一實(shí)例例2設(shè)A＝{1,2,3},R1,R2,R3和R4都是A上的關(guān)系,

其中

R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}

R1

對(duì)稱、反對(duì)稱.R2

對(duì)稱，不反對(duì)稱.R3

反對(duì)稱，不對(duì)稱.R4

不對(duì)稱、也不反對(duì)稱.第5頁(yè)，共21頁(yè)，2023年，2月20日，星期一傳遞性定義

設(shè)R為A上的關(guān)系,若xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

則稱R是A上的傳遞關(guān)系.

實(shí)例：

A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系

第6頁(yè)，共21頁(yè)，2023年，2月20日，星期一實(shí)例例3設(shè)A＝{1,2,3},R1,R2,R3是A上的關(guān)系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1和R3是A上的傳遞關(guān)系R2不是A上的傳遞關(guān)系第7頁(yè)，共21頁(yè)，2023年，2月20日，星期一關(guān)系性質(zhì)的充要條件設(shè)R為A上的關(guān)系,則

(1)R在A上自反當(dāng)且僅當(dāng)IAR

(2)R在A上反自反當(dāng)且僅當(dāng)R∩IA=

(3)R在A上對(duì)稱當(dāng)且僅當(dāng)R=R1

(4)R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R1IA

(5)R在A上傳遞當(dāng)且僅當(dāng)RRR

第8頁(yè)，共21頁(yè)，2023年，2月20日，星期一關(guān)系性質(zhì)判別自反反自反對(duì)稱反對(duì)稱傳遞表達(dá)式IARR∩IA=R=R1

R∩R1

IA

RRR關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1,且i≠j,則rji＝0對(duì)M2中1所在位置,M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒(méi)有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,是一對(duì)方向相反的邊(無(wú)單邊)如果兩點(diǎn)之間有邊,是一條有向邊(無(wú)雙向邊)如果頂點(diǎn)xi連通到xk,則從xi到xk有邊

第9頁(yè)，共21頁(yè)，2023年，2月20日，星期一實(shí)例例8判斷下圖中關(guān)系的性質(zhì),并說(shuō)明理由.(2)反自反，不是自反的；反對(duì)稱，不是對(duì)稱的；是傳遞的.(1)不自反也不反自反；對(duì)稱,不反對(duì)稱；不傳遞.(3)自反，不反自反；反對(duì)稱，不是對(duì)稱；不傳遞.第10頁(yè)，共21頁(yè)，2023年，2月20日，星期一自反性證明證明模式證明R在A上自反任取x,xA

……………..….…….<x,x>R

前提推理過(guò)程結(jié)論例4證明若IAR，則

R在A上自反.證任取x,

xA<x,x>IA<x,x>R

因此R在A上是自反的.第11頁(yè)，共21頁(yè)，2023年，2月20日，星期一對(duì)稱性證明證明模式證明R在A上對(duì)稱任取<x,y><x,y>R

……………..….…….<y,x>R

前提推理過(guò)程結(jié)論例5證明若R=R1,則R在A上對(duì)稱.證任取<x,y>

<x,y>R<y,x>R

1

<x,y>R

因此R在A上是對(duì)稱的.

第12頁(yè)，共21頁(yè)，2023年，2月20日，星期一反對(duì)稱性證明證明模式證明R在A上反對(duì)稱任取<x,y><x,y>R<y,x>R

………..……….

x=y

前提推理過(guò)程結(jié)論例6證明若R∩R1IA,

則R在A上反對(duì)稱.證任取<x,y>

<x,y>R<y,x>R

<x,y>R<x,y>R

1

<x,y>R∩R

1

<x,y>IA

x=y

因此R在A上是反對(duì)稱的.第13頁(yè)，共21頁(yè)，2023年，2月20日，星期一傳遞性證明證明模式證明R在A上傳遞任取<x,y>，<y,z><x,y>R<y,z>R

…..……….<x,z>R

前提推理過(guò)程結(jié)論例7證明若RRR

,

則R在A上傳遞.證任取<x,y>，<y,z><x,y>R<y,z>R

<x,z>RR

<x,z>R

因此R在A上是傳遞的.第14頁(yè)，共21頁(yè)，2023年，2月20日，星期一運(yùn)算與性質(zhì)的關(guān)系自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1°R2

√××××第15頁(yè)，共21頁(yè)，2023年，2月20日，星期一4.4關(guān)系的閉包閉包定義閉包的構(gòu)造方法集合表示矩陣表示圖表示閉包的性質(zhì)第16頁(yè)，共21頁(yè)，2023年，2月20日，星期一閉包定義定義設(shè)R是非空集合A上的關(guān)系,R的自反（對(duì)稱或傳遞）閉包是A上的關(guān)系R,使得R滿足以下條件：

（1）R是自反的（對(duì)稱的或傳遞的）

（2）RR

（3）對(duì)A上任何包含R的自反（對(duì)稱或傳遞）關(guān)系R

有RR.

一般將R的自反閉包記作r(R),對(duì)稱閉包記作s(R),傳遞閉包記作t(R).第17頁(yè)，共21頁(yè)，2023年，2月20日，星期一閉包的構(gòu)造方法定理1設(shè)R為A上的關(guān)系,則有

(1)r(R)=R∪R0

(2)s(R)=R∪R1

(3)t(R)=R∪R2∪R3∪…

說(shuō)明：對(duì)于有窮集合A(|A|=n)上的關(guān)系,(3)中的并最多不超過(guò)Rn.

若R是自反的，則r(R)=R;若R是對(duì)稱的，則

s(R)=R;若R是傳遞的，則t(R)=R.第18頁(yè)，共21頁(yè)，2023年，2月20日，星期一閉包的構(gòu)造方法（續(xù)）設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms和Mt,則

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同階的單位矩陣,M’是M的轉(zhuǎn)置矩陣.注意在上述等式中矩陣的元素相加時(shí)使用邏輯加.第19頁(yè)，共21頁(yè)，2023年，2月20日，星期一閉包的構(gòu)造方法（續(xù)）設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt的頂點(diǎn)集與G的頂點(diǎn)集相等.除了G的邊以外,以下述方法添加新邊：

考察G的每個(gè)頂點(diǎn),如果沒(méi)有環(huán)就加上一個(gè)環(huán)，最終得到Gr.考察G的每條邊,如果有一條xi到xj的單向邊,i≠j,則在G中加一條xj到xi的反方向邊，最終得到Gs.考察G的每個(gè)頂點(diǎn)xi,找從xi出發(fā)的每一條路徑，如果從x