离散数学：4-3 二元关系与函数

请交作业三P54-55:14(1),15(2)，17第二章补充题：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第十章补充题：P77:例4.2(3)(4)作业讲评二P33:10,15,19(1)(4)(5)P54:3,7P33.10用给定联结词集合表示公式①{,}②{,}③{,}

④{}⑤{}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用给定联结词集合表示公式pqFGHR00011011

0010

0101

10101110H=q

①~③

=

qq=qq

④⑤R=(pq)

②

=pq④=

pq

③

=pq

①=

(pq)

=

(pq)

=

((pp)(qq))=

((pp)(qq))((pp)(qq))⑤①{,}②{,}③{,}④{}⑤{}P34.15某勘探队有3名队员，有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁。经实验室鉴定后发现，其中一个人两个判断都正确，一个人判对一半，另一个人全错了。根据以上情况判断矿样种类。解：设P：矿样为铁，Q：矿样为铜，R：矿样为锡。则：甲：

P

Q

乙：P

R

丙：P

RP34.15设P:矿样是铁,Q:矿样是铜,R:矿样是锡“√”：全对，“&”：对一半，“×”：全错以甲为例，“√”：全对

P

Q“&”：对一半

(P

Q)(

P

Q)“×”：全错

P

Q例:甲全对，乙对一半，丙全错

(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构造下述推理的证明前提:

(p

q),qr,

r

结论:p

证明：

①qr

前提引入

②r前提引入

③q

①②析取三段论

④(p

q)前提引入⑤pq④置换

⑥p

③⑤析取三段论⑤p结论否定引入⑥

pq

③⑤合取⑦(pq)(pq)

④⑥合取P35:19构造下述推理的证明(4)前提:

qp,qs,st,tr

结论:pqsr

证明:

①

tr

前提引入

②

t

①化简律

③

st前提引入

④(st)(ts)

③置换

⑤

ts

④化简律⑥

s②⑤假言推理

⑦qs前提引入⑧

(qs)(sq)⑦置换⑨

sq⑧化简律⑩q

⑥⑨假言推理⑾qp

前提引入⑿

p

⑩⑾假言推理⒀

r

①化简律⒁

pqsr⑥⑩⑿⒀合取

P35:19构造下述推理的证明(5)前提:

(pq)r,rs,

s,p

结论:q

证明:①rs

前提引入

②s前提引入

③

r

①②析取三段论

④(pq)r

前提引入⑤(pq)

③④拒取式

⑥pq

⑤置换

⑦p前提引入⑧

q⑥⑦析取三段论P53.3(个体域为“全总个体域”)(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：

设

R(x):x是大红书柜

Q(y):y是古书

F(x,y):x摆满了y

a:这只

b:那些

F(R(a)

,Q(b))解法2：

设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(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带蓝笔另一解释：D=自然数域谓词:G(x):x是奇数，

F(x):x是偶数。P54.7公式的解释给定解释I如下：D={1,2};谓词:G(x):G(1)=1，G(2)=0F(x):F(1)=0，F(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带蓝笔另一解释：D=自然数域谓词:G(x):x是奇数，

F(x):x是偶数。第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数关系基本运算的性质

定理4.2

设F、G、H是任意关系,则有

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))Þ

(x)P(x)(x)Q(x)(x)(P(x)Q(x))=(x)P(x)(x)Q(x)合成运算对“”可分配合成运算对“”不可分配A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

(1)R0={<x,x>|xA}=IA（恒等关系）

(2)Rn+1=Rn∘R

（n≥1）注意：对于A上的任何关系R1和R2都有

R10=R20=IA

对于A上的任何关系R都有

R1=R0∘

R=R定理

设R是A上的关系,m,nN,则

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

幂的求法[P84例4.8]设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5。解：R0=IA，其关系矩阵和关系图分别为幂的求法设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求R0,R1,R2,R3,R4,R5。解：R1=R，其关系矩阵和关系图为幂的求法设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}解：R2=R∘R

，关系矩阵为关系图幂的求法设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}解：R3=R2∘R

，其关系矩阵为关系图同理，R4=R3∘R=R2，

R5=R4∘

R=R3还可以得到——

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

幂的求法（续）说明：对于有限集A上的关系R，R不同的幂只有有限个!R0,R1,R2,R3,…的关系图如下图所示:幂的求法（续）4.3关系的性质自反性反自反性对称性反对称性传递性关系的自反性

定义:

设RAA，(x)(xA

x,xR)，则称R在A上是自反的。自反关系的特点其关系矩阵MR的主对角线全为1；其关系图中每一个结点上都有自回路。实例：设A={1,2,3}，A上的二元关系RR={1,1,2,2,3,3,1,2}自反关系——全域关系EA恒等关系IA

小于等于关系LA

整除关系DA关系的反自反性定义：设RAA，(x)(xAx,xR)，则称R在X上是反自反的反自反关系的特点其关系矩阵MR的主对角线全为0；其关系图中每一个结点上都没有自回路。实例：设A={1,2,3}，X上的二元关系

R={1,2,2,3,3,1}，反自反关系——空关系实数集的小于关系实例关系性质自反性反自反性R1×R2×R3××

例1A={1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>,<3,3>,<1,2>}R2＝{<1,3>}R3＝{<1,1>,<2,2>}关系的对称性定义：

设RAA，(x)(y)(xAyAx,yRy,xR)

则称R在A上是对称的。对称关系的特点其关系矩阵MR是对称阵。其关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。实例：设A={1,2,3}，A上的二元关系R={1,2,2,1,3,3}

对称关系——全域关系EA,恒等关系IA空关系关系的反对称性定义：

设RAA，(x)(y)(xAyAx,yRy,xR(x=y))则称R在A上是反对称的。反对称关系的特点其关系矩阵MR中以主对角线为轴的对称位置上不能同时为1(主对角线除外)。其关系图中，每两个不同结点间至多有一条边。实例：设A={1,2,3}，A上的二元关系R={1,2,2,3,3,3>}

反对称关系——恒等关系IA小于等于关系LA实例关系性质对称性反对称性R1R2×R3×R4××

例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,

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

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

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

关系的传递性

定义：设RAAxyz(xAyAzA<x,y>R<y,z>R

<x,z>R)则称R是A上的传递关系.传递关系在关系图上的特点若xi到xk有边,xk到xj有边,则从xi到xj有边。实例：A上的全域关系EA,恒等关系IA和空关系