《司法考试习题》PPT课件.ppt

习题 主析取范式和主合取范式 v试化下列公式为主析取范式和主合取范式，并判断各公式类型 v( P Q) (P Q) ( P Q) (P Q) ( Q P) (PQ)( P Q)(QP) (PQ)(QP) P) (QP) Q) (PQ)( PQ)( PP)( QQ)( QP) ( PQ)(P Q)(PQ) m01m10m11 M00 是偶然式 主析取范式和主合取范式 v试化下列公式为主析取范式和主合取范式， 并判断各公式类型 vP( P (Q ( Q R) P(P (Q (QR) PQR M000 m001m010m011m100m101m110m111 是偶然式 主析取范式和主合取范式 v试化下列公式为主析取范式和主合取范式， 并判断各公式类型 v(P (QR) ( P ( Q R) ( P(QR) (P (Q R) ( PQ)( PR)(PQR) (PQR)(PQR)(PQR)(PQR) M000 M100 M101 M110 m001m010m011m111 是偶然式 用同一律和互补律 (A A (B B )，补 充简单析取式中未出现的命 题变元，并用分配律展开 主析取范式和主合取范式 v试化下列公式为主析取范式和主合取范式， 并判断各公式类型 v(P Q) R) P ( (P Q) R) P ( (P Q) R) P (PQP)(RP) (PQ)(PR) (PQR)(PQR)(PQR) M000M001M011 m010m100m101m110m111 是偶然式 主析取范式 v真值表法： 例1.37：求 (P Q) Q 的主析取范式 P Qm00m01m10m11 P Q PQ P QPQ 0 01000 0 10100 1 00010 1 10001 P Qm00m01m10m11(P Q) Q P Q PQ P QPQ 0 010000 0 101001 1 000100 1 100011 (P Q) Q ( PQ) (PQ) m01 m11 主合取范式 v真值表法： 例1.40：求 (P Q) Q 的主合取范式 P QM00M01M10M11(P Q) Q PQ P Q PQ P Q 0 001110 0 110111 1 011010 1 111101 (P Q) Q (PQ) ( PQ) M00 M10 v分别用真值表法和公式法求 (P(QR)(P(QR)的主析取范式与主 合取范式（10分） 主析取范式和主合取范式 命题逻辑 v已知命题公式 A(P, Q, R)，并且知道只有当赋值 为001、110和111时公式真值为假。求命题公式 A(P, Q, R)的主析取范式为 _。 命题逻辑的推理理论 v符号化下述论断，并证明其有效性。 如果今天是周一，则进行离散数学或C语言其中一门考试 如果C语言老师有会，则不考C语言 今天是周一 C语言老师有会 所以：进行离散数学考试 设：P：今天是周一， Q：考C语言， R：考离散数学， S：C语言老师有会， P Q R S Q P S R 命题逻辑的推理理论 前提： P Q R ， S Q ， P ， S 结论： R 证明：(1)P P (2)P Q R P (3)Q R T (1) (2) I8 (4) ( Q R ) T (3) (5) Q R T (4) E12 (6) Q R T (5) I18 (7)S P (8)S Q P (9) Q T (7) (8) I8 (10)R T (6) (9) I8 命题逻辑的推理理论 v符号化下面命题，并推证之。 如果厂方拒绝增加工资，则罢工不会停止 除非罢工超过一年，并且工厂厂长辞职 因此：若厂方拒绝增加工资，而罢工又刚刚开始， 罢工是不会停止的 设：P：厂方拒绝增加工资， Q：罢工会停止， R：罢工超过一年， S：工厂厂长辞职， (P Q) ( RS ) P R Q 习题23 前提： (P Q) ( RS ) 结论： P R Q 证明：(1)Q P（假设前提） (2)(P Q) ( R S ) P (3) ( RS ) (P Q) T (2) I18 (4) (RS) ( P Q)T (3) E11 (5) Q ( P(RS) )T (4) E2 E3 (6)Q ( PR)( PS) T (5) E11 E3 (7)( PR)( PS)T (1)(6) I8 (8) PR T (7) I1 (9) ( P R ) T (8) E5 (10) Q ( P R )CP (1) (9) (11)P R Q T (10) E11 习题23 前提： (P Q) ( RS ) 结论： P R Q 证明：(1)P R P（假设前提） (2)(P R) (P S)T (1) I3 (3)P ( R S )T (2) E4 (4) P ( R S )T (3) E5 (5) ( R S ) T (4) I1 (6)(P Q) ( R S ) P (7) ( RS ) (P Q) T (6) I18 (8)P Q T (5)(7) I18 (9)P T (4) I1 (10) Q T (8) (9) I8 (11)P R Q CP (1) (10) v只要今天天气不好，就一定有考生不能提前进入考 场，当且仅当所有考生提前进入考场，考试才能准 时进行。所以，如果考试准时进行，那么天气就好 。 命题逻辑的推理理论 谓词逻辑的推理理论 v构造证明下列各式 vv( (x)P(x) )P(x) ( ( x)Q(x) x)Q(x) ( ( x)(P(x) x)(P(x) Q(x)Q(x) vv( ( x) (P(x) x) (P(x) Q(x), Q(x), ( ( x) (R(x) x) (R(x) Q(x) Q(x) ( ( x) (R(x) x) (R(x) P(x)P(x) vv( ( x)(P(x) x)(P(x) Q(x) Q(x) ( ( x)P(x) x)P(x) ( ( x)Q(x) x)Q(x) 习题20 证明：(1)( ( x)P(x) x)P(x) ( ( x)Q(x)x)Q(x)P (2) (x)P(x)(x)Q(x) T (1) E11 (3)(x) P(x)(x)Q(x)T (2) Q (4)(x)( P(x)Q(x)T (3) Q (5)( ( x)(P(x) x)(P(x) Q(x)Q(x) T (4) E11 1)1) ( (x)P(x) )P(x) ( ( x)Q(x) x)Q(x) ( ( x)(P(x) x)(P(x) Q(x)Q(x) 习题20 证明：(1) ( ( x) (R(x) x) (R(x) P(x)P(x)P(附加前提) (2) (x) ( R(x) P(x) T (1) E11 (3)(x) (R(x)P(x) T (2) Q E1 E5 (4)R(y)P(y) EI (3) (5)R(y) T (4) I1 (6)( ( x) (R(x) x) (R(x) Q(x)Q(x)P (7)R(y) Q(y) UI (6) (8) Q(y) T (5) (7) I8 (9)( ( x) (P(x) x) (P(x) Q(x)Q(x)P (10)P(y) Q(y) UI (9) (11)P(y) T (4) I2 (12)Q(y) T (10)(11) I8 (13)Q(y)Q(y) Q(y)Q(y)T (8)(12) 2)2) ( ( x) (P(x) x) (P(x) Q(x), Q(x), ( ( x) (R(x) x) (R(x) Q(x) Q(x) ( ( x) (R(x) x) (R(x) P(x)P(x) 习题20 证明：(1)( ( x)P(x)x)P(x)P(附加前提) (2)P(y) UI (1) (3)( ( x)(P(x) x)(P(x) Q(x)Q(x) P (4)P(y) Q(y) UI (3) (5)Q(y) T (2)(4) I8 (6)( ( x) Q(x)x) Q(x) UG (5) (7)( ( x)P(xx)P(x) ) ( ( x)Q(xx)Q(x) ) CP(1)(6) 3)3) ( ( x)(P(x) x)(P(x) Q(x) Q(x) ( ( x)P(x) x)P(x) ( ( x)Q(x) x)Q(x) 谓词逻辑 v设论域元素为a1，a2，a3，a4，则 ； v 。 前束范式 v在下列公式中，对约束变元进行改名，对自由变元进行代入 vv( ( x)(P(x)x)(P(x)(Q(x)(Q(x)R(x)R(x)( ( x)(R(x)x)(R(x)( ( y)S(x, y) y)S(x, y) vv( ( x) (P(x) x) (P(x) Q(x) Q(x) ( ( x) (R(x)x) (R(x)S(x)S(x) 改名：把第一个约束变元x改为u，把第二个约束变元x改为v 把第三个约束变元y改为w 改名：把第一个约束变元x改为u，把第二个约束变元x改为v (u u)(P(u u)(Q(u u)R(u u)(v v)(R(v v)(ww)S(v v, ww) (u u) (P(u u) Q(u u) (v v) (R(v v)S(v v) 前束范式 v在下列公式中，对约束变元进行改名，对自由变元进行代入 vv( ( x)P(x, y)x)P(x, y)( ( x)(Q(x, z)x)(Q(x, z)( ( z)z)( ( x)R(x, y, z)x)R(x, y, z) 改名：把第一个约束变元x改为u，把第四个约束变元x改为v 改名：把第二个约束变元x改为s，把第三个约束变元z改为t (u u)P(u u, y)(x)(Q(x, z)(z)(v v)R(v v, y, z) (u u)P(u u, y)(s s)(Q(s s, z)(t t)(v v)R(v v, y, t t) 代入：将第一个自由变元y代入r，将第二个自由变元z代入w (u u)P(u u, r r)(s s)(Q(s s, ww)(t t)(v v)R(v v, r r, t t) 前束范式 v在下列公式中，对约束变元进行改名，对自由变元进行代入 vv( ( x)(P(xx)(P(x, y) , y) ( ( z)Q(xz)Q(x, z) , z) ( ( y)R(xy)R(x, y), y) 改名：把第一个约束变元x改为u，把第二个约束变元z改为v 把第三个约束变元y改为w 代入：将第一个自由变元y代入s，将第二个自由变元x代入t (u u)(P(u u, y) (v v)Q(u u, v v) (ww)R(x, ww) (u)(P(u, s s) (v)Q(u, v) (w)R(t t, w) 等价式 量词辖域的扩大与缩小（小结） ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(A (x) x)(A (x) B) B) ( ( x)A (x) x)A (x) B B ( ( x)(B x)(B A (x) A (x) B B ( ( x)A (x)x)A (x) ( ( x)(B x)(B A (x) A (x) B B ( ( x)A (x)x)A (x) 前束范式 例2.11： 将公式( x)P(xx)P(x) ) ( ( y)Q(y y)Q(y) ) ( ( x)R(xx)R(x) )化为前束范式 解： 公式 (x)P(x) (y)Q(y) (z z)R(z z) ( ( x)x) ( (P(xP(x) ) ( ( y)Q(y y)Q(y) ) ) (z)R(z) ( ( x)x)( ( y) y) ( ( P(xP(x) ) Q(yQ(y) ) ) (z)R(z) ( ( x)x)( ( y)y) ( ( (P(xP(x) ) Q(yQ(y) ) (z)R(z) ( ( x)x)( ( y)y)( ( z) z) ( ( (P(xP(x) ) Q(yQ(y) ) ) R(zR(z) ) ) 解： （公式( ( x)x)( ( y)y)( ( z) z) ( ( (P(xP(x) ) Q(yQ(y) ) ) R(zR(z) ) ) ） 公式 (x)P(x) (y)Q(y) (z z)R(z z) ( ( y)y) ( ( ( x)P(xx)P(x) ) Q(yQ(y) ) ) (z)R (z) ( ( y)y)( ( x) x) ( ( P(xP(x) ) Q(yQ(y) ) ) (z)R (z) ( ( y)y)( ( x)x)( ( z) z) ( ( (P(xP(x) ) Q(yQ(y) ) ) R (z)R (z) ) 若公式中有约束变元重复出现，或者与公式中的自若公式中有约束变元重复出现，或者与公式中的自 由变元重名，则将公式中的约束变元改名由变元重名，则将公式中的约束变元改名 前束范式不是唯一的前束范式不是唯一的 v求下列公式的前束范式 ( ( x)x)( ( (y)A(x,yy)A(x,y) ) ( (x)(x)( y)y)( (B(x,yB(x,y) ) ( ( y)y)( (A(y,xA(y,x) ) B(x,yB(x,y) ) ) ) ) ( (x)(x)(y)A(x,y)y)A(x,y)( (u)(u)(v v)()( B(u,v)B(u,v)( (w)w) (A(w,u)(A(w,u)B(u,wB(u,w) ) ( (x)(x)(y)(y)(u)(u)(v)(v)(w)(A(x,yw)(A(x,y) )( ( B(u,v)B(u,v) (A(w,u)(A(w,u)B(u,wB(u,w) ) 前束范式 ( ( x)(P(x)x)(P(x)(y)Q(y)y)Q(y)( (y)R(x,yy)R(x,y) 前束范式 谓词逻辑的推理理论 v符号化下列各命题，并给出构造推理证明。 每一个自然数不是奇数就是偶数 自然数是偶数当且仅当它能被2整除 并不是所有自然数都能被2整除 所以：有的自然数是奇数 设：N(x)：x是自然数， O(x)：x是奇数， E(x)：x是偶数， T(x)：x能被2整除 (x)(N(x) O(x) E(x) ) ( ( x)(N(x)x)(N(x)(E(x) (E(x) T(x)T(x) ( ( x)(N(x) x)(N(x) T(x) )T(x) ) ( ( x)(N(x)x)(N(x)O(x)O(x) 谓词逻辑的推理理论 前提： (x)(N(x) O(x)E(x) , ( ( x)(N(x)x)(N(x)(E(x) (E(x) T(x)T(x) , ( ( x)(N(x) x)(N(x) T(x)T(x)结论： ( ( x)(N(x)x)(N(x)O(x)O(x) 证明：(1) ( ( x)(N(x) x)(N(x) T(x) )T(x) ) P (2) (x)( N(x)T(x) T (1) E11 (3)(x)(N(x) T(x)T (2) Q, E1, E5 (4)N(y) T(y) EI (3) (5)N(y) T (4) I1 (6)( ( x)(N(x)x)(N(x)(E(x) (E(x) T(x)T(x) P (7)N(y)(E(y) T(y) UI (6) (8)E(y) T(y) T (5)(7) I8 (9)E(y) T(y) T (8) I18 习题22(1) (10) T(y) T (4) I1 (11) E(y) T (9)(10) I9 (12)( ( x)(N(x) x)(N(x) O(x)O(x)E(x)E(x) P (13)N(y) O(y)E(y) UI (12) (14)O(y)E(y) T (5)(13) I8 (15) ( O(y) E(y) )T (14) (16)O(y) E(y) T (15) E12 (17)O(y) T (11)(16) I8 (18)N(y) O(y) T (5)(17) (19)( ( x)(N(x)x)(N(x)O(x)O(x) EG (18) (4)N(y) T(y) EI (3) (5)N(y) T (4) E1 (9)E(y) T(y) T (8) E18 谓词逻辑的推理理论 v符号化下列各命题，并给出构造推理证明。 如果一个人怕困难，那么他就不会获得成功 每个人或者获得成功，或者失败过 有些人未曾失败过 所以：有些人不怕困难 设：P(x)：x是人， D(x)：x怕困难， S(x)：x成功， F(x)：x失败 (x)(P(x) D(x) S(x) ( ( x)(P(x) x)(P(x) (S(x) (S(x) F(x)F(x) ( ( x)(P(x) x)(P(x) F(x) ) ( ( x)(P(x)x)(P(x) D(x)D(x) 谓词逻辑的推理理论 前提： (x)(P(x)D(x) S(x), ( ( x)(P(x) x)(P(x) (S(x)(S(x)F(x)F(x), ( ( x)(P(x) x)(P(x) F(x) )结论： ( ( x)(P(x)x)(P(x) D(x)D(x) 证明：(1)( ( x)(P(x) x)(P(x) F(x)F(x) P (2)P(y) F(y) EI (1) (3)P(y) T (2) I1 (4) F(y) T (2) I1 (5)( ( x)(P(x) x)(P(x) (S(x)(S(x)F(x)F(x) P (6)P(y) (S(y)F(y) UI (5) (7)S(y)F(y) T (3)(6) I8 (8)S(y) T (4)(7) I10 习题22(2) (9)( ( x)(P(x)x)(P(x)D(x)D(x) S(x)S(x) P (10)P(y)D(y) S(y) UI (1) (11) (P(y)D(y)T (8)(10) I9 (12) P(y) D(y)T (11) E5 (13) D(y) T (3) (12) I10 (14)P(y) D(y) T (3) (13) (15) ( ( x)(P(x)x)(P(x) D(x)D(x) EG (14) (3)P(y) T (2) I1 (8)S(y) T (4)(7) I10 谓词逻辑的推理理论 v符号化下列各命题，并给出构造推理证明。 每个科学工作者都是刻苦钻研的 每个刻苦钻研而又聪明的科学工作者都将获得事业的成功 华有为是一名科学工作者，并且他是聪明的 所以：华有为将获得事业上的成功 S(x)：x是科学工作者，H(x)：x刻苦钻研， C(x)：x是聪明的 P(x)：x在获得事业上的成功，a：华有为 (x)(S(x) H(x) ( ( x)(S(x)x)(S(x)H(x)H(x)C(x) C(x) P(x)P(x) S(a) S(a) C(a) P(a)P(a) 谓词逻辑的推理理论 前提： (x)(S(x) H(x), ( ( x)(S(x)x)(S(x)H(x)H(x)C(x) C(x) P(x)P(x), S(a) S(a) C(a)结论： P(a)P(a) 证明：(1)( ( x)(S(x) x)(S(x) H(x)H(x) P (2)S(a) H(a) UI (1) (3)S(a) S(a) C(a) P (4)S(a) T (3) I1 (5)H(a) T (2)(4) I8 (6)( ( x)(S(x)x)(S(x)H(x)H(x)C(x) C(x) P(x)P(x) P (7)S(a)H(a)C(a) P(a) UI (6) (8)P(a)P(a) T (3)(5)(7) I8 谓词逻辑的推理理论 v符号化下列各命题，并给出构造推理证明。 每个资深名士，或是政协委员，或是国务院参事 资深名士资深名士张大为不是政协委员，但他是中科院院士 所以：有的中科院院士是国务院参事 K(x)：x是资深名士，Z(x)：x是政协委员， G(x)：x是国务院参事，S(x)：x是中科院院士，a：张大为 (x)(K(x) (Z(x) (Z(x) G(x)G(x) K(a) K(a) Z(a) S(a) ( ( x)(S(x)x)(S(x)G(x)G(x) 习题22(4) 证明：(1)( ( x)(K(x) x)(K(x) (Z(x) (Z(x) G(x)G(x) P (2)K(a) (Z(a) G(a) UI (1) (3)K(a)K(a) Z(a)S(a) P (4)K(a) T (3) I1 (5)Z(a) G(a)T (2)(4) I8 (6) Z(a) T (3) I1 (7)G(a) T (5)(6) I10 (8)S(a) T (3) I1 (9)G(a) S(a) T (7) (8) (10) ( ( x)(S(x)x)(S(x)G(x)G(x) EG (9) 前提： (x)(K(x) (Z(x) (Z(x) G(x)G(x), K(a)K(a) Z(a)S(a) 结论： ( ( x)(S(x)x)(S(x)G(x)G(x) v每个大学生不是文科学生就是理工科学生，有的大 学生是优等生，小张不是理工科学生，但他是优等 生，因而如果小张是大学生，他就是文科学生。 谓词逻辑的推理理论 集合 v设A、B、C、D是集合，求证： ( (A A B) B)( (C C D) D) ( (A AC) C) ( (B BD)D) 证明：对于 (A B) (C D) 中的任意元素，有： x, y ( (A A B) B)( (C C D) D) x (A B) y (C D) (x A x B) (y C y D) (x A y C) (x B y D) x, y ( (AC) ) x, y ( (BD) ) (AC) (BD) 集合 20. 4) (A 20. 4) (A - B)C = B)C = ( (A AC) C) - ( (B BC)C) 证明：证明：对于 ( (A A - B)C B)C中的任意元素，有 x, y ( (A A - - B)C B)C x x ( (A A - - B) B) y y C C ( (x x A A x x B) B) y y C C ( (x x A A y y C C x x B )B )( (x x A Ay y C C y y C C ) ) ( (x x A A y y C) C) (x x B B y y C C ) ( (x x A A y y C) C) (x x B B y y C C ) x, y ( (A AC)C) x, y ( (B BC)C) x, y ( (A AC) C) - - ( (B BC)C) 集合 v求证：若AA = BB，则：A=B 证明：证明：假设 A B，则必存在存在x x，有有 x x A A x x B B，或存在，或存在y y， 有有 y y A A y y B B 若存在若存在x x，有有x x A Ax x B B， 则则 x,x AA，且 x,x BB ，则 AA BB 若存在若存在y y， y y A A y y B B ， 则则 y,y BB，且 y,y AA ，则 AA BB 综上所述，可知：若AA = BB，则必有A=B 集合 v求证：若AB = AC，且A ，则：B=C 证明：证明：假设 B C，则必存在存在y y，有有 y y B B y y C C，或存在，或存在z z， 有有 z z B B z z C C，又因为又因为A ，则必存在x x A A。 若存在若存在y y，有有 y y B B y y C C ，有有 AB，且 x,y AC ，则 AB AC 若存在若存在z z，有有 z z B B z z C C ，有有 则则 x,z AB，且 x,z AC ，则 AB AC 综上所述，可知：若AB = AC，且A ，则必有B=C v设A、B、C、D为四个非空集合，则AB CD 的充要条件是A C，B D v已知A、B、C是三个集合，证明(AB)C(A C)(BC) 集合 闭包运算 vv构造构造r(R)r(R)、s(R)s(R)、t(R)t(R)的方法就是给的方法就是给R R补充必要的有序对补充必要的有序对 。 设G是集合A上二元关系R的关系图，给G中所有结点都 补充上有向环，就得到了R的自反闭包r(R) 的关系图。 定理：若若R R AA AA，则则r(R)r(R)=R R I I A A 证明：因为是IA自反的，因此R R I I A A 是自反的是自反的 且 R R R R I I A A 设R1是A上任意的自反关系，且R R1 ， 由于R1是自反的，因此IA R1， 又因为R R1 ，因此R R I IA A R R 1 1 ，故故r(R)=R IA 参照定义 闭包运算 设G是集合A上二元关系R的关系图，将G中所有的弧都画 成“有来有往”（即如果有从a到b的弧，就有从b到a的弧 ）就得到了R的对称闭包s(R) 的关系图。 定理：若若R R AA AA，则则s(R)s(R)=R R R R-1 -1 证明： 1)设R1=R R-1，显然R R R R 1 1 。 2)因为R1-1= (R R-1)-1= R-1 (R-1)-1= R-1 R = R1 所以R R 1 1 是对称的是对称的。 定理：若若R R AA AA，则则R R是对称的 是对称的 R=RR=R-1 -1 闭包运算 3) 设R2是A上任意的对称关系，且R R2。 对于任意 R1 ，或者 R，或者 R- 1 若 R，则 R2； 若 R-1 ，则 R，则 R2 ， 又因为R2是对称的，所以 R2 ； 所以R R 1 1 R R 2 2 综上所述，证得 s(R)s(R)=R R R R-1 -1 闭包运算 设G是集合A上二元关系R的关系图，如果有从a到b的弧 ，并且有从b到c的弧，就补充上从a到c的弧，就得到了R 的传递闭包t(R) 的关系图。 定理：若R AA，则t(R)= Ri=R R2 R3 证明略（教材P73） 定理：若R AA，|A|= n 则t(R)= Ri=R R2 R3 Rn i=1 n 证明略（教材P74） i=1i=1 闭包运算 v定理：若若R R是是A A上的二元关系，则：上的二元关系，则：rs(Rrs(R) ) = = sr(Rsr(R) ) 证明： sr(Rsr(R) ) = s(R IA) = (R IA) (R IA)-1 = (R IA) (R -1 IA-1) = (R R -1) IA =r (R R -1) = = rsrs (R) (R) 定理：若若R R AA AA，则则r(R r(R) )=R R I I A A 定理：若若R R AA AA，则则s(R s(R) )=R R R R-1 -1 闭包运算 v定理：若若R R是是A A上的二元关系，则：上的二元关系，则：rt(Rrt(R) ) = = tr(Rtr(R) ) 证明： 由于RIA= IAR=R，且IA IA = IA ； (R IA)2 = ( R IA ) ( R IA ) = R (R IA) IA (R IA) = IA R R2 因此， tr(R) = t (R IA) = (R IA) i i=1 i=1i=1 n n 用归纳法可证： ( (R R I I A A ) ) n n = I = IA A ( ( R R i i ) ) i=1 = (IA ( Rj) ) = IA ( Rj) = IA t(R) = rt(R) j=1 i j=1 R (S T) = R S R T R2R p73 关系的闭包运算 v设集合A=a,b,c,d上的关系 R=,，用矩阵运 算求出R的传递闭包 关系矩阵： 自反闭包：r(R) = R IA 关系的闭包运算 所以，r(R) = , , , , v对称闭包： vS(R) = MR MR-1 关系的闭包运算 v传递闭包： 关系的闭包运算 t(R) = , , , , , , , , 等价关系与划分 v设集合A=1,2,3,4,5，求A上的一个划分 1,2,3,4,5的等价关系，并画出关系图： 解：R = (1,2(1,21,2) 1,2) (3(33) 3) (4,5(4,54,5)4,5) = , , , , , , , , , , , , , 12345 等价关系与划分的对应关系 v已知=ab,c是A=a,b,c的一个划分， 由决定的A上的一个等价关系是 。 等价关系的证明 v设R和S是非空集合A上的等价关系，试确定下面各式是否为 等价关系。若是则证明之，若不是则举例说明： R R2 2 证明：1) 对于 x A，有xRx。因此有xR2x，故故R R 2 2 是自反的是自反的 2) 对于 x, y A， 若有xR2y， 则必存在z A，有xRz, zRy， 因为R是对称的，所以必定有：yRz, zRx，即有yR2x 。 也就是说：若有xR2y，则必有yR2x，故故R R 2 2 是对称的是对称的 3) 对于x,y,z A，若有xR2y, yR2z，则 a,b A，有：xRa和aRy 以及 yRb和bRz，因为R是传递的，所以必定有：xRy, yRz。 则若有xR2y, yR2z，必有xR2z，故故R R 2 2 是传递的是传递的。R R 2 2 是等价关系是等价关系 是是。 等价关系的证明 v设R是A上的二元关系，对于a, b, c A， 若aRb, bRc，则cRa，称R是循环的循环的。 求证：R是自反的和循环的，当且仅当R是等价关系 证明：1) 若若R R是等价关系是等价关系，则R R是自反的 是自反的、对称的和传递的。 对于a, b, c A，若aRb, bRc，因为R是传递的，所以有aRc 又因为R是对称的，所以有cRa。所以R R是循环的是循环的 2) 若若R R是是自反的自反的和循环的 和循环的， 则对于a, b, c A，若aRb, bRc，则cRa 因为R是自反的，所以有aRa，所以有aRc，所以R R是传递的是传递的 若有aRb，因为有bRb，则有bRa，所以R R是对称的是对称的，故R是等价关系 cRa,aRa 则aRc 偏序关系的证明 v设R是集合A上的偏序关系，且B A， 求证：R (BB)是B上的偏序关系 证明：1) 对于对于 x x B B，一定有： BB 因为B A，所以x A，所以一定有： R 所以，一定有一定有 x,x R R (BB)(BB)， 所以：R (BB)是自反的自反的 偏序关系的证明 v设R是集合A上的偏序关系，且B A， 求证：R (BB)是B上的偏序关系 2) 对于x, y B，一定有 BB 且 BB 因为R是反对称的，所以若有 R且 R，则有x=y 所以：若有若有 x,y R R (BB)(BB)且 且 y,x R R (BB)(BB) ， 则有： R 且 R，则有：则有：x=yx=y 所以：R (BB)是反对称的反对称的 偏序关系的证明 v设R是集合A上的偏序关系，且B A， 求证：R (BB)是B上的偏序关系 3) 对于x, y, z B，一定有, , BB 因为R是传递的, 所以若有R且R, 则有R 所以：若有若有 x,y R R (BB)(BB)且 且 y,z R R (BB)(BB) ， 则有： x,z R R (BB) (BB) 所以：R (BB)是传递的传递的。故R (BB)是B上偏序关系 v设R1是A上的等价关系，R2是B上的等价关系， A且B。 v关系R满足 ,RR1且 R2，证明R是AB上的等价关系 哈斯图与偏序集中特殊位置的元素 v图中给出了偏序集的哈斯图，其中A=