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

請(qǐng)交作業(yè)三P54-55:14(1),15(2)，17第二章補(bǔ)充題：1，2P74:9,11(1)(2),12(2)(4),13(1),14(2)P75:15,16(2)(4)(6),17(1),18,19,21P113:1,P114:2,3P115:11第十章補(bǔ)充題：P77:例4.2(3)(4)作業(yè)講評(píng)二P33:10,15,19(1)(4)(5)P54:3,7P33.10用給定聯(lián)結(jié)詞集合表示公式①{,}②{,}③{,}

④{}⑤{}pqFGHR00011011

0010

0101

10101110F=pq

②

=

(pq)

③=(pq)①=

(p)q=

(pp)q⑤

=(p

q)

=(p(q))=

(p(qq))=(p(qq))(p(qq))④G=q①~⑤P33.10用給定聯(lián)結(jié)詞集合表示公式pqFGHR00011011

0010

0101

10101110H=q

①~③

=

qq=qq

④⑤R=(pq)

②

=pq④=

pq

③

=pq

①=

(pq)

=

(pq)

=

((pp)(qq))=

((pp)(qq))((pp)(qq))⑤①{,}②{,}③{,}④{}⑤{}P34.15某勘探隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，3人的判斷如下：甲說：這不是鐵，也不是銅；乙說：這不是鐵，是錫；丙說：這不是錫，是鐵。經(jīng)實(shí)驗(yàn)室鑒定后發(fā)現(xiàn)，其中一個(gè)人兩個(gè)判斷都正確，一個(gè)人判對(duì)一半，另一個(gè)人全錯(cuò)了。根據(jù)以上情況判斷礦樣種類。解：設(shè)P：礦樣為鐵，Q：礦樣為銅，R：礦樣為錫。則：甲：

P

Q

乙：P

R

丙：P

RP34.15設(shè)P:礦樣是鐵,Q:礦樣是銅,R:礦樣是錫“√”：全對(duì)，“&”：對(duì)一半，“×”：全錯(cuò)以甲為例，“√”：全對(duì)

P

Q“&”：對(duì)一半

(P

Q)(

P

Q)“×”：全錯(cuò)

P

Q例:甲全對(duì)，乙對(duì)一半，丙全錯(cuò)

(PQ)((PR)(P

R))(PR)=((PQ)(P

R)(PR))

((PQ)(PR)(PR))甲乙丙真值1√&×02√×&03×√&04×&√05&√×P

Q

R6&×√P

Q

R甲：

P

Q乙：

P

R丙：

P

RP35:19構(gòu)造下述推理的證明前提:

(p

q),qr,

r

結(jié)論:p

證明：

①qr

前提引入

②r前提引入

③q

①②析取三段論

④(p

q)前提引入⑤pq④置換

⑥p

③⑤析取三段論⑤p結(jié)論否定引入⑥

pq

③⑤合?、?pq)(pq)

④⑥合取P35:19構(gòu)造下述推理的證明(4)前提:

qp,qs,st,tr

結(jié)論:pqsr

證明:

①

tr

前提引入

②

t

①化簡(jiǎn)律

③

st前提引入

④(st)(ts)

③置換

⑤

ts

④化簡(jiǎn)律⑥

s②⑤假言推理

⑦qs前提引入⑧

(qs)(sq)⑦置換⑨

sq⑧化簡(jiǎn)律⑩q

⑥⑨假言推理⑾qp

前提引入⑿

p

⑩⑾假言推理⒀

r

①化簡(jiǎn)律⒁

pqsr⑥⑩⑿⒀合取

P35:19構(gòu)造下述推理的證明(5)前提:

(pq)r,rs,

s,p

結(jié)論:q

證明:①rs

前提引入

②s前提引入

③

r

①②析取三段論

④(pq)r

前提引入⑤(pq)

③④拒取式

⑥pq

⑤置換

⑦p前提引入⑧

q⑥⑦析取三段論P(yáng)53.3(個(gè)體域?yàn)椤叭倐€(gè)體域”)(2)“有些人喜歡所有的花”F(x):x是人，G(y):y是花,

H(x,y):x喜歡yx(F(x)

y(G(y)H(x,y)))(5)任何金屬都可以溶解在某種液體中F(x):x是金屬，G(y):y是液體,

H(x,y):x溶解于y中x

(F(x)

y(G(y)

H(x,y)))x((M(x)F(x))x((M(x)F(x))這只大紅書柜擺滿了那些古書。解法1：

設(shè)

R(x):x是大紅書柜

Q(y):y是古書

F(x,y):x擺滿了y

a:這只

b:那些

F(R(a)

,Q(b))解法2：

設(shè)A(x):x

是書柜

B(x):x是大的

C(x):x是紅的

D(y):y是古老的

E(y):y是圖書

F(x,y):x擺滿了y

a:這只

b:那些F(A(a)

B(a)

C(a)

,D(b)E(b))P54.7公式的解釋給定解釋I如下：D={1,2};謂詞:G(x):G(1)=1，G(2)=0F(x):F(1)=0，F(xiàn)(2)=1(1)(x)(F(x)G(x))((x)F(x)(x)G(x))

((F(1)G(1))(F(2)G(2)))((F(1)F(2))(G(1)G(2)))((10)(01))((10)(01))

(11)(00)100

xA(x)=A(a1)A(a2)…A(an)G(x):x帶紅筆F(x):

x帶藍(lán)筆另一解釋：D=自然數(shù)域謂詞:G(x):x是奇數(shù)，

F(x):x是偶數(shù)。P54.7公式的解釋給定解釋I如下：D={1,2};謂詞:G(x):G(1)=1，G(2)=0F(x):F(1)=0，F(xiàn)(2)=1(2)((x)F(x)(x)G(x))(x)(F(x)G(x))((F(1)F(2))(G(1)G(2)))((F(1)G(1))(F(2)G(2)))((10)(01))((10)(01))

(11)(00)100

xA(x)=A(a1)A(a2)…

A(an)

G(x):x帶紅筆F(x):

x帶藍(lán)筆另一解釋：D=自然數(shù)域謂詞:G(x):x是奇數(shù)，

F(x):x是偶數(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ù)關(guān)系基本運(yùn)算的性質(zhì)

定理4.2

設(shè)F、G、H是任意關(guān)系,則有

F°(GH)=F°G

F°H(GH)°F=G°F

H°F

F°(GH)F°G

F°H(GH)°FG°F

H°F證明：僅證明⑶，類似地可證明⑴、⑵和⑷。

x,z

F°(GH)(y)(x,y

GH

y,zF)(y)((x,yG

x,yH)

y,zF)(y)((x,yG

y,zF)

(x,yHy,zF))

(y)(x,yG

y,zF)

(y)(x,yH<y,zF)x,yF°G

x,yF°Hx,yF°G

F°H(x)(P(x)Q(x))T

(x)P(x)(x)Q(x)(x)(P(x)Q(x))=(x)P(x)(x)Q(x)合成運(yùn)算對(duì)“”可分配合成運(yùn)算對(duì)“”不可分配A上關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|xA}=IA（恒等關(guān)系）

(2)Rn+1=Rn°R

（n≥1）注意：對(duì)于A上的任何關(guān)系R1和R2都有

R10=R20=IA

對(duì)于A上的任何關(guān)系R都有

R1=R0°

R=R定理

設(shè)R是A上的關(guān)系,m,nN,則

(1)Rm°Rn=Rm+n(2)(Rm)n=Rmn

冪的求法[P84例4.8]設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5。解：R0=IA，其關(guān)系矩陣和關(guān)系圖分別為冪的求法設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求R0,R1,R2,R3,R4,R5。解：R1=R，其關(guān)系矩陣和關(guān)系圖為冪的求法設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}解：R2=R°R

，關(guān)系矩陣為關(guān)系圖冪的求法設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}解：R3=R2°R

，其關(guān)系矩陣為關(guān)系圖同理，R4=R3°R=R2，

R5=R4°

R=R3還可以得到——

R2=R4=R6=…,R3=R5=R7=…

冪的求法（續(xù)）說明：對(duì)于有限集A上的關(guān)系R，R不同的冪只有有限個(gè)!R0,R1,R2,R3,…的關(guān)系圖如下圖所示:冪的求法（續(xù)）4.3關(guān)系的性質(zhì)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性關(guān)系的自反性

定義:

設(shè)RAA，(x)(xA

x,xR)，則稱R在A上是自反的。自反關(guān)系的特點(diǎn)其關(guān)系矩陣MR的主對(duì)角線全為1；其關(guān)系圖中每一個(gè)結(jié)點(diǎn)上都有自回路。實(shí)例：設(shè)A={1,2,3}，A上的二元關(guān)系RR={1,1,2,2,3,3,1,2}自反關(guān)系——全域關(guān)系EA恒等關(guān)系IA

小于等于關(guān)系LA

整除關(guān)系DA關(guān)系的反自反性定義：設(shè)RAA，(x)(xAx,xR)，則稱R在X上是反自反的反自反關(guān)系的特點(diǎn)其關(guān)系矩陣MR的主對(duì)角線全為0；其關(guān)系圖中每一個(gè)結(jié)點(diǎn)上都沒有自回路。實(shí)例：設(shè)A={1,2,3}，X上的二元關(guān)系

R={1,2,2,3,3,1}，反自反關(guān)系——空關(guān)系實(shí)數(shù)集的小于關(guān)系實(shí)例關(guān)系性質(zhì)自反性反自反性R1×R2×R3××

例1A={1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>,<3,3>,<1,2>}R2＝{<1,3>}R3＝{<1,1>,<2,2>}關(guān)系的對(duì)稱性定義：

設(shè)RAA，(x)(y)(xAyAx,yRy,xR)

則稱R在A上是對(duì)稱的。對(duì)稱關(guān)系的特點(diǎn)其關(guān)系矩陣MR是對(duì)稱陣。其關(guān)系圖中，如果兩個(gè)不同的結(jié)點(diǎn)間有邊，一定有方向相反的兩條邊。實(shí)例：設(shè)A={1,2,3}，A上的二元關(guān)系R={1,2,2,1,3,3}

對(duì)稱關(guān)系——全域關(guān)系EA,恒等關(guān)系IA空關(guān)系關(guān)系的反對(duì)稱性定義：

設(shè)RAA，(x)(y)(xAyAx,yRy,xR(x=y))則稱R在A上是反對(duì)稱的。反對(duì)稱關(guān)系的特點(diǎn)其關(guān)系矩陣MR中以主對(duì)角線為軸的對(duì)稱位置上不能同時(shí)為1(主對(duì)角線除外)。其關(guān)系圖中，每?jī)蓚€(gè)不同結(jié)點(diǎn)間至多有一條邊。實(shí)例：設(shè)A={1,2,3}，A上的二元關(guān)系R={1,2,2,3,3,3>}

反對(duì)稱關(guān)系——恒等關(guān)系IA小于等于關(guān)系LA實(shí)例關(guān)系性質(zhì)對(duì)稱性反對(duì)稱性R1R2×R3×R4××

例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>}

關(guān)系的傳遞性

定義：設(shè)RAAxyz(xAyAzA<x,y>R<y,z>R

<x,z>R)則稱R是A上的傳遞關(guān)系.傳遞關(guān)系在關(guān)系圖上的特點(diǎn)若xi到xk有邊,xk到xj有邊,則從xi到xj有邊。實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系