離散數(shù)學(xué)：4-1-1 二元關(guān)系與函數(shù)

第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)4.1集合的笛卡兒積和二元關(guān)系有序?qū)?序偶)由兩個(gè)元素x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?lt;x,y>實(shí)例：點(diǎn)的直角坐標(biāo)(3,4)有序?qū)π再|(zhì)當(dāng)xy時(shí)，<x,y><y,x>

<x,y>與<u,v>相等的充分必要條件是

<x,y>=<u,v>x=uy=v注意：區(qū)別<a,b>和{a,b}當(dāng)ab時(shí)，有{a,b}={b,a}。有序n元組定義

一個(gè)有序n(n3)元組<x1,x2,…,xn>是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序n-1元組，即

<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

當(dāng)n=1時(shí),<x>形式上可以看成有序1元組.實(shí)例：有序3元組<a,b,c>=<<a,b>,c><a,<b,c>>

兩個(gè)n元組相等的條件x1,x2,…,xn=y1,y2,…,yn

(x1=y1)(x2=y2)…(xn=yn)笛卡兒積(

)（直積）定義

設(shè)A,B為集合，A與B的笛卡兒積記作AB，

AB={<x,y>|xAyB}例2A={1,2},B={a,b,c}

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>}

A={},P(A)={,{}}

P(A)A={<,>,<{},>}A

B

B

An階笛卡兒積設(shè)A1，A2，…An為集合(n

2),它們的n階笛卡兒積記作A1

A2

，…

An,其中A1

A2…An={(a1,a2,…,an)|aiAi,i=1,2,…,n}例：設(shè)R是實(shí)數(shù)集，即R={x|-<x<+}，則RRR={(x,y,z)|-<x<+,-<y<+,-<z<+}當(dāng)A1=A2=…=An=A時(shí)，它們的n階笛卡爾積記為An

。R3=n階笛卡兒積的運(yùn)算設(shè)A={1,2}，B={a,b}，C={x,y}，求：

(AB)C，A(BC)解：

(AB)C={1,a,1,b,2,a,2,b}×{x,y}={1,a,

x,1,b,

x,2,a,x,2,b,x,1,a,

y,1,b,

y,2,a,y,2,b,y

}={1,a,x,1,b,x,2,a,x,2,b,x,

1,a,y,1,b,y,2,a,y,2,b,y

}

A(BC)={1,2}×{a,x,a,y,b,x,b,y}

={1,a,x,1,a,y,1,b,x,1,b,y2,a,x,2,a,y,2,b,x,2,b,y}

即

(AB)C≠A(BC)<a,b,c>=<<a,b>,c>

<<a,b>,c><a,<b,c>>

笛卡兒積()的性質(zhì)約定：若A=或

B=，則

A

B=一般地，不滿足交換律：

A

B≠BA一般地，不滿足結(jié)合律：

(AB)C≠A(BC)

若|A|=n，|B|=m，則：|A

B|=nm=|A||B|對(duì)于并或交運(yùn)算滿足分配律

A(BC)=(AB)(AC)

(BC)A=(BA)(CA)

A(BC)=(AB)(AC)(BC)A=(BA)(CA)

AB={<x,y>|xA

yB}<<a,b>,c>

<a,<b,c>>

直積運(yùn)算性質(zhì)的證明證明:

A(BC)=(AB)(AC)證:

任取<x,y><x,y>A(BC)

xA

y(BC)

xA

(yByC)(xA

yB)(xA

yC)

<x,y>A

B

<