交大数理逻辑课件-关系

P85:3(4)指出下列推演中的错误，并改正之(

x)P(x)=F(

x)P(x)

(

x)P(x)改为：(

x)P(x)=F(

x)P(x)

(

x)P(x)或(

x)P(x)=F(

x)P(x)

(

x)P(x)必有(

x)P(x)=F不一定有(

x)P(x)=F必有(

x)P(x)=F

P85:3(4)指出下列推演中的错误，并改正之必有(x)P195:1(4)列出下列各集合所有的元素：A={z|z={x,y}∧x∈Z∧y∈Z∧0≤x≤2∧-2≤y≤1}A={{0,-2},{0,-1},{0,0},{0,1}

{1,-2},{1,-1},{1,1}

{2,-2},{2,-1},{2,0},{2,1}}P195:1(4)列出下列各集合所有的元素：第10章关系10.1二元关系10.2关系矩阵和关系图10.3关系的逆、合成、限制和象10.4关系的性质10.5关系的闭包10.6等价关系和划分10.7相容关系和覆盖10.8偏序关系第10章关系关系的合成运算

F∘G={<x,y>|

z(<x,z>

G

<z,y>

F)}

x1x2z3z2z1y1y2F∘GFG关系的合成运算F∘G={<x,y>|z(<x关系基本运算的性质

定理10.3.1设X,Y,Z是集合,R

X×Y,S

Y×Zdom(R

1)=ran(R)

ran(R

1)=dom(R)(R

1)

1=R(S∘R)

1=R

1∘S

1证

(4)对任取<x,z>

x,z

(S∘R)-1

z,x

(R∘S)

(

y)(

z,y

S∧

y,x

R)

(

y)(

y,zS-1∧x,yR-1)

x,z

S-1∘R-1R

1

={<y,x>|<x,y>R}

F∘G={<x,y>|

z(<x,z>

G

<z,y>

F)}

关系基本运算的性质定理10.3.1设X,Y,Z是集合,关系基本运算的性质定理10.3.2

设X，Y，Z，W是集合，Q

X×Y，S

Y×Z，R

Z×W，则

(R∘S)∘Q=R∘(S∘Q)证明：对任取<x,w>

(R∘S)∘Q

(

y)(x,y

Q

∧

y,w

R∘S)

(

y)(

x,y

Q)∧(

z)(y,z

S∧z,w

R))

(

y)(

z)(

x,y

Q)∧z,w

R∧y,z

S)

(

z)(

y)(z,w

R∧

x,y

Q∧y,z

S)

(

z)(z,w

R)∧(

y)(

x,y

Q∧y,z

S)

(

z)(z,w

R∧

x,z

S∘Q)

x,w

R∘(S∘Q)所以(R∘S)∘Q=R∘(S∘Q)

F∘G={<x,y>|

z(<x,z>

G

<z,y>

F)}

关系基本运算的性质定理10.3.2设X，Y，Z，W是集合关系基本运算的性质定理10.3.3

设X,Y,Z是集合,S、T

X×Y,R

Y×Z,则

R∘(S∪T)=R∘S∪R∘T(R∪S)∘T=R∘T∪S∘T

R∘(S∩T)

R∘S∩R∘T(R∩S)∘T

R∘T∩S∘T证明：仅证明⑶，类似地可证明⑴、⑵和⑷。

x,z

R∘(S∩T)

(

y)(

y,z

R∧

x,y

S∩T)

(

y)(

y,z

R∧(

x,y

S∧

x,y

T))

(

y)((

y,z

R∧

x,y

S)∧(y,z

R∧

x,y

T))

(

y)(

y,z

R∧

x,y

S)∧(

y)(

y,z

R∧

x,y

T)

x,y

R∘S∧

x,y

R∘T

x,y

R∘S∩R∘T故R∘(S∩T)

R∘S∩R∘T关系基本运算的性质定理10.3.3设X,Y,Z是10.4关系的性质关系的自反性定义:设RA×A，(

x)(xA→

x,x

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

1,1

,

2,2

,

3,3

,

1,2}自反关系——全域关系EA恒等关系IA

小于等于关系LA

整除关系DA10.4关系的性质关系的自反性定义:设RA×A，自反关关系的反自反性定义：设R

A×A，(

x)(x

A→

x,x

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

R={

1,2

,

2,3

,

3,1}，反自反关系——实数集上的小于关系幂集上的真包含关关系的反自反性定义：设RA×A，反自反关系——实例例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>}R1自反,R2反自反,R3既不是自反也不是反自反的实例例1A={1,2,3},R1,R2,R3是关系的对称性定义：

设RA×A，(

x)(

y)(xA∧yA∧

x,y

R→

y,x

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

1,2

,

2,1

,

3,3}

对称关系——全域关系EA,恒等关系IA空关系

关系的对称性定义：设RA×A，对称关系——关系的反对称性定义：

设RA×A，(

x)(

y)(xA∧yA∧

x,y

R∧

y,x

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

1,2

,

2,3

,

3,3>}

反对称关系——恒等关系IA空关系关系的反对称性定义：设RA×A，(实例例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>}

R1

对称、反对称.R2

对称，不反对称.R3

反对称，不对称.R4

不对称、也不反对称.实例例2设A＝{1,2,3},R1,R2,R3和关系的传递性

定义：设R

A×A

x

y

z(<x,y>∈R∧<y,z>∈R→<x,z>∈R)

则称R是A上的传递关系.传递关系的特点其关系矩阵M(R)中1所在位置,M(R)中相应位置都是1如果顶点xi连通到xk,则从xi到xk有边实例：A上的全域关系EA,恒等关系IA和空关系

小于等于关系,小于关系，整除关系，包含关系，真包含关系

关系的传递性定义：设RA×A实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中

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

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

R3＝{<1,3>}R1和R3是A上的传递关系R2不是A上的传递关系实例例3设A＝{1,2,3},R1,R2,R3是A判断下图中关系的性质图1图2图3自反性××√反自反性×√×对称性√××反对称性×√√传递性×√×判断下图中关系的性质图1图2图3自反性××√反自反性×√×10.4.2运算与性质的关系设R,S是自反的,则

IA

R，IA

S所以IA

R∪S，IA

R∩S，即R∪S和R∩S也是自反的自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××原有性质运算

设R={<1,2>},S={<2,1>}则

R和S都是传递的、反对称的但R∪S={<1,2>,<2,1>}

不是传递的，不是反对称的10.4.2运算与性质的关系设R,S是自反的,自反性10.5关系的闭包设R为A上的关系,n为自然数,则R的n次幂定义为：

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

(2)Rn+1=Rn∘R

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

R10=R20=IA

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

R1=R0∘

R

=R10.5关系的闭包设R为A上的关系,n为自然数,则R10.5.1多个关系合成的运算[P174例3]设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R0,R1,R2,R3,R4,R5。解：R0=IA，其关系矩阵和关系图分别为10.5.1多个关系合成的运算[P174例3]设A={多个关系合成的运算设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多个关系合成的运算设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多个关系合成的运算设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}解：R3=R2∘R

，其关系矩阵为关系图多个关系合成的运算设A={a,b,c,d},R={<a,b同理，R4=R3∘R=R2，

R5=R4∘

R=R3还可以得到——

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

多个关系合成的运算说明：对于有限集A和A上的关系R，R的不同的幂只存在有限个同理，R4=R3∘R=R2，R5=R4∘R0,R1,R2,R3,…的关系图如下图所示多个关系合成的运算R0,R1,R2,R3,…的关系图如下图所示多个关系合定理

设A是的限集,R是A上的关系,m,n∈N,则

(1)Rm∘Rn=Rm+n

(2)(Rm)n=Rmn

证(1)

用归纳法

对

m∈N,施归纳于n.