数理逻辑与集合论：10-1 关系

1、作业讲评4P85: 3(1)n指出下列推演中的错误，并改正之 ( x)(P(x)Q(x) =T xD, 有有P(x) =T，Q(x)=T改为：改为： ( x)(P(x)Q(x) =T xD, P(x)Q(x) =T或或( x)(P(x)Q(x) =T xD, P(x) =F 或或 Q(x) =T P Q P Q F FF TT FT TTTFT P85: 3(4)n指出下列推演中的错误，并改正之 ( x)P(x) = F ( x)P(x) ( x)P(x)改为：改为：n( x)P(x) = F ( x)P(x) ( x)P(x)或n( x)P(x) = F ( x)P(x) ( x)P(x)必

2、有必有( x)P(x)=F不一定有不一定有( x)P(x)=F必有必有( x)P(x) = F 推理规则 (1)(1)前提引入规则前提引入规则 (2)(2)结论引入规则结论引入规则(3)(3)置换规则置换规则 (4)(4)假言推理规则假言推理规则 (AB) A B (5)(5)附加规则附加规则 A (A B)(6)(6)化简规则化简规则 (A B) A (7)(7)拒取式规则拒取式规则 (AB)B A(8)(8)假言三段论规则假言三段论规则 (AB) (BC) (AC) (9)(9)析取三段论规则析取三段论规则 (A B)B A(10)(10)构造性二难推理规则构造性二难推理规则 (AB) (

3、CD) (A C) (B D)(11)(11)合取引入规则合取引入规则 A, B A A B B有关量词的推理规则(12) 全称量词消去规则全称量词消去规则（UI规则）规则）(13) 全称量词引入规则全称量词引入规则（UG规则）规则）)()(cAxxA(14) 存在量词引入规则存在量词引入规则（EG规则规则）(15) 存在量词消去规则存在量词消去规则 （EI规则规则）)()(xxAyA)()(xxAcA )()(cAxxA P86: 5(1) 推理规则法证明前提：前提：( x)(P(x) Q(x)，( x)(Q(x)R(x)结论：结论：( x)(R(x)P(x)证明：证明： ( x)(P(x)

4、 Q(x) 前提前提 ( x)(Q(x)R(x) 前提前提 P(y) Q(y) UI Q(y)R(y) UI R(y)Q(y) 置换置换 Q(y)P (y) 置换置换 R(y)P(y) 假言三段论假言三段论 ( x)(R(x)P(x) EGP86: 5(1) 归结法证明( x)(P(x) Q(x) ( x)(Q(x)R(x) ( x)(R(x)P(x)A1= P(x) Q(x)， A2=Q(x) R(x)B= R(x)P(x), B= (R(x) P(x)= R(x) P(x)证明：证明： P(x) Q(x) 子句子句 Q(x) R(x) 子句子句 R(x) 子句子句 P(x) 子句子句 Q(

5、x) 归结归结 Q(x) 归结归结 归结归结P86: 5(2) 推理规则法证明前提：前提：( x)(P(x) Q(x)，( x)Q(x)结论：结论：P(a)证明：证明： ( x)(P(x) Q(x) 前提前提 ( x)Q(x) 前提前提 P(y) Q(y) UI Q(y) UI P(y) 拒取式拒取式 ( x) P(x) UG P(a) UIP86: 5(2) 归结法证明 ( x)(P(x) Q(x) ( x)Q(x) P(a) A1= P(x) Q(x)， A2=Q(x) B= P(a), B= P(a)证明：证明： P(x) Q(x) 子句子句 Q(x) 子句子句 P(a) 子句子句 Q(

6、a) 归结归结 归结归结 P86: 5(4) 推理规则法证明P86: 5(4)归结法证明(M(a) P(a)=M(a) P(a)第10章 关 系10.1 二元关系10.2 关系矩阵和关系图10.3 关系的逆、合成、限制和象10.4 关系的性质10.5 关系的闭包10.6 等价关系和划分10.7 相容关系和覆盖10.8 偏序关系10.1 二元关系n二元关系的定义nA，B是任意两个集合，是任意两个集合，A B的任一个子集的任一个子集称为称为集合集合A到到B的一个的一个二元关系二元关系。一般。一般记作记作R。n如果如果R, 可记作可记作 xRy；n如果如果 R, 则记作则记作x R y。n若若A=B

7、，则，则A A的任一个子集称为的任一个子集称为A上的二元上的二元关系关系。n 例：已知例：已知 A=0,1, B=a, b, c, n R1=, R2=AB, R3=, R4=. n则则 R1, R2, R3是从是从 A 到到 B 的二元关系的二元关系, R3 , R4是是 A上的上的二元关系二元关系. 集合A上重要的二元关系nA上重要关系n空关系空关系n全域关系全域关系EA=|xAyA=AAn恒等关系恒等关系IA =|xAn小于等于关系小于等于关系LA LA=| x,yAxy, A R，R为实数集合为实数集合 n整除关系整除关系DADA= | x,yAx整除整除y, A Z*, Z*为非为非

8、0整数集整数集 n关系的计数n若若|A|=n，则，则A上有上有 2n2 个不同的二元关系个不同的二元关系. n 设A=1，2EA=, ,=AAIA =,LA =, DA=, 定义域、值域 和 域n对A到B的一个关系R，可以定义：nR的定义域：的定义域：domR = x | y ( R) nR的值域：的值域： ranR = y | x ( R) nR的域：的域： fldR = domR ranR n例例1 R=, , , , 则则 domR = 1, 2, 4 ranR = 2, 3, 4 fldR = 1, 2, 3, 410.2 关系矩阵和关系图n关系的表示方法 n列举法列举法n例例:设设A

9、=a,b，B=1,2 A到到B的全域关系的全域关系E为为 E=AB= a,1 , a,2 , b,1 , b,2 n集合表示式法集合表示式法n 例例: 设设R是实数集，是实数集，LR= x,y | x Ry Rxy，LR是实数集是实数集R上的二元关系上的二元关系小于等于关系小于等于关系n关系矩阵法关系矩阵法n关系图法关系图法关系的矩阵表示法n设A=a1,a2,am, B=b1,b2,bn R是是A到到B的二元关系，的二元关系，R的关系矩阵定义的关系矩阵定义为：为： M(R)称为二元关系R的关系矩阵。nmijrRM)()(),.,2 , 1,.2 , 1(,01njmiRRbbaarjjiiij

10、4321321011001110101)(aaaaRMbbb用矩阵表示从A到B的二元关系n 设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1, a1,b3, a2,b2, a2,b3, a3,b1, a4,b1,a4,b2n 则R的关系矩阵为RRbbaarjjiiij,01用矩阵表示A上的二元关系A=1,2,3,4, R=,R的的关系矩阵关系矩阵M(R)如下：如下：432100100000110000114321)(RM关系的表示n 用关系图表示二元关系n以集合中的元素为顶点，若以集合中的元素为顶点，若 R，则用，则用一条带箭头的弧线把一条带箭头

11、的弧线把xi和和xj连起来，箭头的方连起来，箭头的方向由向由xi指向指向xj，得到的图就是表示，得到的图就是表示R的关系图。的关系图。用关系图表示从A到B的二元关系n 设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1, a1,b3, a2,b2, a2,b3, a3,b1, a4,b1,a4,b2n 则R的关系图为：4321321011001110101)(aaaaRMbbb用关系图表示A上的二元关系A=1,2,3,4, R=,R的的关系图关系图GR如下：如下：432100100000110000114321)(RM10.3 关系的逆、合成、限制

12、和像n关系F的逆F 1 = | Fn如 R=, , , n则 R 1 =, , , n关系F和G的合成F G F G = | z ( G F) x1 1x2 2z3 3z2 2z1 1y1 1y2 2FG关系的合成运算nF G = | z ( G F) n如：如： R =, , , S = , , , , 则则R S = , , , S R = , , x1 1x2 2z3 3z2 2z1 1y1 1y2 2FG关系的限制与像n R 在在A上的上的限制限制 R A = | xRy x An A 在在R下的下的像像RA = ran(R A) n 实例：实例：R=, , , R 1=, （R在在1上的限制）上的限制） R1=2,4 （1在在R下的像）下的像） R = R1,2=2,3,4n 注意：注意：F A F, FA ranF S R的关系矩阵n 设设A=1,2,3,4, R=,S =,n 则则S R的关系矩阵为nnijnnijsSMrRM)()(,)()()()()(SMRMRSM000000101000100000100001100001000000100000100010)()()(SMRMRSM）（jkijnjiksrw1关系基本运算的性质 R 1 = | R F G = | z ( G F) 设X, Y, Z,