司法考试习题课件

《司法考试习题课件》由会员分享，可在线阅读，更多相关《司法考试习题课件（70页珍藏版）》请在装配图网上搜索。

1、,,,,,,,,,,,,,,,,,,,,,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,,,,,,,,,,,,,,,,,,,,,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,精选PPT课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,,精选PPT课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,,精选PPT课件,*,习题,1,精选PPT课件,习题1精选PPT课件,主析取范式和主合取范式,试化下列公式为主析取范式和主合取范式，

2、并判断各公式类型,(,,,P,∨,,Q),,(P,,,Q), ,(,,,P,∨,,Q),∨,(P,,,Q),,∧,(,,Q,,P),,,(P,∧,Q),∨,(,,P,∨,,Q),∧,(Q,∨,P),,(P,∧,Q),∨,((,Q,∨,P,),∧,,P),∨,(,(Q,∨,P),,∧,,Q),,(P,∧,Q),∨,(,,P,∧,Q),∨,(,,P,∧,P),∨,(,,Q,∧,Q),∨,(,,Q,∧,P),,(,,P,∧,Q),∨,(P,∧,,Q),∨,(P,∧,Q),,m,01,∨,m,10,∨,m,11,,,M,00,是偶然式,主析取范式和

3、主合取范式试化下列公式为主析取范式和主合取范式，,主析取范式和主合取范式,试化下列公式为主析取范式和主合取范式，并判断各公式类型,P,∨,(,,P,,(Q,∨,(,,Q,,R))),,P,∨,(P,∨,(Q,∨,(Q,∨,R))),,P,∨,Q,∨,R,,M,000,,m,001,∨,m,010,∨,m,011,∨,m,100,∨,m,101,∨,m,110,∨,m,111,是偶然式,主析取范式和主合取范式试化下列公式为主析取范式和主合取范式，,主析取范式和主合取范式,试化下列公式为主析取范式和主合取范式，并判断各公式类型,(,P,,(Q,∧,R)),∧ (,,,P,

4、,(,,Q,,R)),,(,,,P,∨,(Q,∧,R)),∧ (,P,∨,(Q,∨,R)),,(,,,P,∨,Q),∧,(,,,P,∨,R),∧,(P,∨,Q,∨,R),,(P,∨,Q,∨,R),∧,(,,P,∨,Q,∨,R),∧,(,,P,∨,Q,∨,,R),∧,(,,P,∨,,Q,∨,R),,M,000,∧,,M,100,∧,,M,101,∧,,M,110,,m,001,∨,m,010,∨,m,011,∨,m,111,是偶然式,用同一律和互补律,(,A,,A,∨ (,B,∧,,B ),)，补充简单析取式中未出现的命题变元，并用分配律展开,主析取范式和主合取

5、范式试化下列公式为主析取范式和主合取范式，,主析取范式和主合取范式,试化下列公式为主析取范式和主合取范式，并判断各公式类型,((,P,∨,Q,),,,R),,P, ,(,,(,P,∨,Q,),,∨,R),∨,P,,( (,P,∨,Q,),,∧,,R),∨,P,,(P,∨,Q,∨,P),∧,(,,R,∨,P),,(P,∨,Q),∧,(P,∨,,R),,,(P,∨,Q,∨,R),∧,(P,∨,Q,∨,,R),∧,(P,∨,,Q,∨,,R),,M,000,∧,M,001,∧,M,011,,m,010,∨,m,100,∨,m,101,∨,m,110,∨,m,111,

6、是偶然式,主析取范式和主合取范式试化下列公式为主析取范式和主合取范式，,主析取范式,真值表法：,例1.37：求 (,P,,Q),∧,Q,的主析取范式,P Q,m,00,m,01,m,10,m,11,,,P,∧,,Q,,P,∧,Q,P,∧,,Q,P,∧,Q,0 0,1,0,0,0,,0 1,0,1,0,0,,1 0,0,0,1,0,,1 1,0,0,0,1,,P Q,m,00,m,01,m,10,m,11,(,P,,Q),∧,Q,,P,∧,,Q,,P,∧,Q,P,∧,,Q,P,∧,Q,0 0,1,0,0,0,0,0 1,0,1,0,0,1,1 0,0,0,1

7、,0,0,1 1,0,0,0,1,1,∴ (,P,,Q),∧,Q,,(,,P,∧,Q),∨ (,P,∧,Q),,m,01,∨,m,11,主析取范式真值表法：P Qm00m01m10m11 P∧,主合取范式,真值表法：,例1.40：求 (,P,,Q),∧,Q,的主合取范式,P Q,M,00,M,01,M,10,M,11,(,P,,Q),∧,Q,P,∨,Q,,P,∨,,Q,,,P,∨,Q,,,P,∨,,Q,0 0,0,1,1,1,0,0 1,1,0,1,1,1,1 0,1,1,0,1,0,1 1,1,1,1,0,1,∴ (,P,,Q),∧,Q,,(,P,∨,

8、Q),∧ (,,,P,∨,Q),,M,00,∧,M,10,主合取范式真值表法：P QM00M01M10M11(P ,分别用真值表法和公式法求,(,P,,(,Q,∨,R,))∧(,,P,∨(,Q,,R,)),的主析取范式与主合取范式（,10,分）,主析取范式和主合取范式,分别用真值表法和公式法求(P(Q∨R))∧(P∨(QR,命题逻辑,已知命题公式,A(P, Q, R),，并且知道只有当赋值为,001,、,110,和,111,时公式真值为假。求命题公式,A(P, Q, R),的主析取范式为,__________________,。,命题逻辑已知命题公式 A(P, Q, R)，

9、并且知道只有当赋,命题逻辑的推理理论,符号化下述论断，并证明其有效性。,如果今天是周一，则进行离散数学或,C,语言其中一门考试,如果,C,语言老师有会，则不考,C,语言,今天是周一,C,语言老师有会,所以：进行离散数学考试,设：,P：,今天是周一，,Q：,考,C,语言，,R：,考离散数学，,S：C,语言老师有会，,P,,Q,,R,S,,,Q,P,S,R,命题逻辑的推理理论符号化下述论断，并证明其有效性。设： P：,命题逻辑的推理理论,前提：,P,,Q,,R,，,S,,,Q,，,P,，,S,结论：,R,证明：,(1),,P,,P,,(2),,P,,Q,,R,P,,(3),,Q

10、,,R,T (1) (2) I,8,,(4),,,(,Q,,R ),T (3),,(5),,,Q,,R,T (4) E,12,(6),,,Q,,R,T (5) I,18,(7),,S,P,(8),,S,,,Q,P,(9),,,Q,T (7) (8) I,8,(10),,R,,T (6) (9) I,8,命题逻辑的推理理论前提： P  Q  R ， S  ,命题逻辑的推理理论,符号化下面命题，并推证之,。,如果厂方拒绝增加工资，则罢工不会停止除非罢工超过一年，并且工厂厂长辞职,因此：若厂方拒绝增加工资，而罢工又刚刚开始， 罢工是不会停止的,设：,P：,厂方拒绝增

11、加工资，,Q：,罢工会停止，,R：,罢工超过一年，,S：,工厂厂长辞职，,(P,,,,Q),,,,( R,∧,S ),P,∧,,,R,,,,Q,命题逻辑的推理理论符号化下面命题，并推证之。设： P：厂方拒,习题23,前提：,(P,,,,Q),,,,( R,∧,S ),结论：,P,∧,,,R,,,,Q,证明：,(1),,Q,P（,假设前提）,,(2),,(P,,,,Q),,,,( R,∧,S ),,,P,,(3),,,( R,∧,S ),,(P,,,,Q),,,T (2) I,18,,(4),(,R,∧,S),∨,,(,,,P,∨,,,Q),T (

12、3) E,11,,(5),,,,Q,∨,(,,,P,∨,(,R,∧,S) ),T (4) E,2,E,3,(6),,Q,,(,,,P,∨,R),∧,(,,,P,∨,S),T (5) E,11,E,3,(7),(,,,P,∨,R),∧,(,,,P,∨,S),T (1)(6) I,8,(8),,,,P,∨,R,T (7) I,1,,(9),,,(,P,∧,,R ),T (8) E,5,,,(10),,Q,,,(,P,∧,,R ),CP (1) (9),(11),,P,∧,,,R,,,,Q,,T (10) E,11,习题23前提： (P   Q)   ( R∧

13、S ),习题23,前提：,(P,,,,Q),,,,( R,∧,S ),结论：,P,∧,,,R,,,,Q,证明：,(1),,P,∧,,,R,P（,假设前提）,,(2),(,P,∧,,R),∨,(,P,∧,,S),T (1) I,3,,(3),,P,∧,(,,R,∨,,S ),T (2) E,4,,(4),,P,∧,,(,,R,∧,,S ),T (3) E,5,,(5),,,(,,R,∧,,S ),T (4) I,1,(6),,(P,,,,Q),,,,( R,∧,S ),,,P,,(7),,,( R,∧,S ),,(P,,,,Q),,,T (6) I,1

14、8,,(8),,P,,,,Q,,,T (5)(7) I,18,,(9),,P,T (4) I,1,,(10),,,Q,T (8) (9) I,8,(11),,P,∧,,,R,,,,Q,,CP (1) (10),习题23前提： (P   Q)   ( R∧S ),只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。,命题逻辑的推理理论,只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有,谓词逻辑的推理理论,构造证明下列各式,(,,x,)P(x),,(,,x)Q(x),,(,,

15、x)(P(x),,Q(x)),(,,x) (P(x),,Q(x)),,(,,x) (R(x),,,Q(x)),,(,,x) (R(x),,,P(x)),,(,,x)(P(x),,Q(x)),,(,,x)P(x),,(,,x)Q(x),谓词逻辑的推理理论构造证明下列各式,习题20,证明：,(1),,(,,x)P(x),,(,,x)Q(x),,P,,(2),,,(,,x)P(x),∨,(,,x)Q(x),T (1) E,11,,,(3),,(,,x),,P(x),∨,(,,x)Q(x),T (2) Q,,(4),,(,,x)(,,P(x),∨,

16、Q(x)),T (3) Q,,(5),,(,,x)(P(x),,Q(x)),,T (4) E,11,1),(,,x,)P(x),,(,,x)Q(x),,(,,x)(P(x),,Q(x)),习题20证明：(1) (x)P(x)  (x)Q(x),习题20,证明：,(1),,,(,,x) (R(x),,,P(x)),,P(,附加前提),,(2),,,(,,x) (,,R(x),∨,,P(x)),T (1) E,11,,,(3),(,,x) (R(x),∧,P(x)),T (2) Q E,1,E,5,,(4),,R(y),∧,P(y),EI (3),,(5),

17、,R(y),T (4) I,1,,,(6),,(,,x) (R(x),,,Q(x)),,P,,(7),,R(y),,,,Q(y),UI (6),,(8),,,,Q(y),T (5) (7) I,8,,,(9),,(,,x) (P(x),,Q(x)),,P,,(10),,P(y),,Q(y),UI (9),,(11),,P(y),T (4) I,2,,,(12),,Q(y),T (10)(11) I,8,,,(13),,Q(y),∧,,Q(y),,,T (8)(12),2) (,,x) (P(x),,Q(x)),,(,,x) (R(x),,,Q(x)),,(,

18、,x) (R(x),,,P(x)),,习题20证明： (1)  (x) (R(x)  P(,习题20,证明：,(1),,(,,x)P(x),,P(,附加前提),,(2),,P(y),,,UI (1),,(3),,(,,x)(P(x),,Q(x)),,,P,,(4),,P(y),,Q(y),UI (3),,(5),,Q(y),T (2)(4) I,8,,(6),,(,,x) Q(x),,UG (5),(,7),,(,,x)P(x),,(,,x)Q(x),,,CP(1)(6),3) (,,x)(P(x),,Q(x)),,(,,x)P(x),,(,,x)Q(

19、x),习题20证明： (1) (x)P(x) P(附加前提),谓词逻辑,设论域元素为,a,1,，,a,2,，,a,3,，,a,4,，则,,；,,,。,,,谓词逻辑设论域元素为a1，a2，a3，a4，则,前束范式,在下列公式中，对约束变元进行改名，对自由变元进行代入,(,,x)(P(x),,(Q(x),∨,R(x))),∧(,,x)(R(x),,(,,y)S(x, y)),,(,,x) (P(x),,Q(x)),,,(,,x) (R(x),∧,S(x)),改名：把第一个约束变元,x,改为,u，,把第二个约束变元,x,改为,v,把第三个约束变元,y,改为,w,改名：把第一个

20、约束变元,x,改为,u，,把第二个约束变元,x,改为,v,(,,u,)(P(,u,),,(Q(,u,),∨,R(,u,))),∧(,,v,)(R(,v,),,(,,w,)S(,v,,,w,)),(,,u,) (P(,u,),,Q(,u,)),,,(,,v,) (R(,v,),∧,S(,v,)),前束范式在下列公式中，对约束变元进行改名，对自由变元进行代入,前束范式,在下列公式中，对约束变元进行改名，对自由变元进行代入,(,,x)P(x, y),∧(,,x)(Q(x, z),,(,,z),(,,x)R(x, y, z)),改名：把第一个约束变元,x,改为,u，,把第四

21、个约束变元,x,改为,v,改名：把第二个约束变元,x,改为,s，,把第三个约束变元,z,改为,t,(,,u,)P(,u,, y),∧(,,x)(Q(x, z),,(,,z),(,,v,)R(,v,, y, z)),(,,u,)P(,u,, y),∧(,,s,)(Q(,s,, z),,(,,t,),(,,v,)R(,v,, y,,t,)),代入：将第一个自由变元,y,代入,r，,将第二个自由变元,z,代入,w,(,,u,)P(,u,,,r,),∧(,,s,)(Q(,s,,,w,),,(,,t,),(,,v,)R(,v,,,r,,,t,)),前束范式在下列公式中，对约

22、束变元进行改名，对自由变元进行代入,前束范式,在下列公式中，对约束变元进行改名，对自由变元进行代入,(,,x)(P(x, y),,(,,z)Q(x, z)),∧ (,,y)R(x, y),改名：把第一个约束变元,x,改为,u，,把第二个约束变元,z,改为,v,把第三个约束变元,y,改为,w,代入：将第一个自由变元,y,代入,s，,将第二个自由变元,x,代入,t,(,,u,)(P(,u,, y),,(,,v,)Q(,u,,,v,)),∧ (,,w,)R(x,,w,),(,,u)(P(u,,s,),,(,,v)Q(u, v)),∧ (,,w)R(,t,, w),前束范式在下

23、列公式中，对约束变元进行改名，对自由变元进行代入,等价式,量词辖域的扩大与缩小（小结,）,(,,x)(A (x),∧,B),,(,,x)A (x),∧,B,(,,x)(A (x),∨,B),,(,,x)A (x),∨,B,(,,x)(A (x),∧,B),,(,,x)A (x),∧,B,(,,x)(A (x),∨,B),,(,,x)A (x),∨,B,(,,x)(A (x),,,B),,(,,x)A (x),,,B,(,,x)(A (x),,,B),,(,,x)A (x),,,B,(,,x)(B,,A (x)),,B,,(,,x)A (x)

24、,(,,x)(B,,A (x)),,B,,(,,x)A (x),,等价式量词辖域的扩大与缩小（小结） (x)(A (x),前束范式,例2.11：将公式,((,,x)P(x),,∨,(,,y)Q(y)),,(,,x)R(x),化为前束范式,解： 公式,,(,(,,x)P(x),,∨,(,,y)Q(y),),,,(,,z,)R(,z,),,,(,,x),,(,P(x),,∨,(,,y)Q(y),),,,(,,z)R(z),,,(,,x),(,,y),(,P(x),,∨,,Q(y),),,,(,,z)R(z),,(,,x),(,,y),,

25、(,(P(x),∨,Q(y)),,,(,,z)R(z),),,,(,,x),(,,y),(,,z),(,(,P(x),,∨,,Q(y),),,,R(z),),解：,（公式,,(,,x),(,,y),(,,z),(,(,P(x),,∨,,Q(y),),,,R(z),),）,公式,,(,(,,x)P(x),∨ (,,y)Q(y),),,,(,,z,)R(,z,),,,(,,y),,(,(,,x)P(x),,∨,,Q(y),),,,(,,z)R (z),,,(,,y),(,,x),(,,P(x),,∨,,Q(y),),,,(,,z)R (z),,

26、,(,,y),(,,x),(,,z),(,(,P(x),,∨,,Q(y),),,,R (z),),若公式中有约束变元重复出现，或者与公式中的自由变元重名，则将公式中的约束变元改名,前束范式不是唯一的,前束范式例2.11：将公式((x)P(x) ∨ (y),求下列公式的前束范式,,,(,,x),(,(∃y)A(x,y) →(∃x)(,,y),(,B(x,y) ∧(,,y),(,A(y,x) →B(x,y),),),),,,,,(∃x)((∃y)A(x,y),∧,(,,u)(∃v)(,,,B(u,v),∨,(∃w),,(A(w,u)→B(u,w)))),(∃x)(∃y

27、)(,,u)(∃v)(∃w)(A(x,y),∧,(,,,B(u,v),∨,,(A(w,u)→B(u,w)))),前束范式,求下列公式的前束范式(∃x)((∃y)A(x,y)∧(u),(,,x)(P(x)→((∃y)Q(y)→(∃y)R(x,y))),,,,前束范式,( x)(P(x)→((∃y)Q(y)→(∃y)R(x,y,谓词逻辑的推理理论,符号化下列各命题，并给出构造推理证明。,每一个自然数不是奇数就是偶数,自然数是偶数当且仅当它能被2整除,并不是所有自然数都能被2整除,所以：有的自然数是奇数,设：,N(x)：x,是自然数，,O(x)：x,是奇数，,E(x)：x,是偶数，,T(

28、x)：x,能被2整除,(,,x)(N(x),,O(x),,E(x) ),(,,x)(N(x),,(E(x),,,T(x))),,(,,x)(N(x),,T(x) ),(,,x)(N(x),∧,O(x)),谓词逻辑的推理理论符号化下列各命题，并给出构造推理证明。设：,谓词逻辑的推理理论,前提：,(,,x)(N(x),,O(x),,E(x)),,,(,,x)(N(x),,(E(x),,,T(x))),,,,(,,x)(N(x),,T(x)),结论：,(,,x)(N(x),∧,O(x)),证明：,(1),,,(,,x)(N(x),,T(x) ),,P,,

29、(2),,,(,,x)(,,N(x),∨,T(x)),T (1) E,11,,,(3),(,,x)(N(x),∧,,T(x)),T (2) Q, E,1,, E,5,,(4),,N(y),∧,,T(y),EI (3),,(5),,N(y),T (4) I,1,(6),,(,,x)(N(x),,(E(x),,,T(x))),,P,(7),,N(y),,(E(y),,,T(y)),UI (6),(8),,E(y),,,T(y),T (5)(7) I,8,(9),,E(y),,,T(y),T (8) I,18,谓词逻辑的推理理论前提： (x)(N(x) O(x)E,习

30、题22(1),,(10),,,T(y),T (4) I,1,,(11),,,E(y),T (9)(10) I,9,,,(12),,(,,x)(N(x),,O(x),,E(x)),,P,,(13),,N(y),,O(y),,E(y),UI (12),,(14),,O(y),,E(y),T (5)(13) I,8,(15),,,( O(y),,,E(y) ),T (14),(16),,O(y),,,E(y),T (15) E,12,(17),,O(y),T (11)(16) I,8,(18),,N(y),∧,,O(y),T (5)(17),,(19),,(,,x)(N(x

31、),∧,O(x)),,EG (18),(4),,N(y),∧,,T(y),EI (3),(5),,N(y),T (4) E,1,(9),,E(y),,,T(y),T (8) E,18,习题22(1) (10)  T(y) T (4),谓词逻辑的推理理论,符号化下列各命题，并给出构造推理证明。,如果一个人怕困难，那么他就不会获得成功,每个人或者获得成功，或者失败过,有些人未曾失败过,所以：有些人不怕困难,设：,P(x)：x,是人，,D(x)：x,怕困难，,S(x)：x,成功，,F(x)：x,失败,(,,x)(P(x),∧,,D(x),,,,S(x)),(,,x)(P(x)

32、,,(S(x),∨,,F(x))),(,,x)(P(x),∧,,,F(x),),(,,x)(P(x),∧,,D(x)),谓词逻辑的推理理论符号化下列各命题，并给出构造推理证明。设：,谓词逻辑的推理理论,前提：,(,,x)(P(x),∧,D(x),,,,S(x)),,,(,,x)(P(x),,(S(x),∨,F(x))),,,(,,x)(P(x),∧,,,F(x),),结论：,(,,x)(P(x),∧,,D(x)),证明：,(1),,(,,x)(P(x),∧,,,F(x)),,P,,(2),,P(y),∧,,,F(y),EI (1),,(3),,P(y),T (

33、2) I,1,,(4),,,,F(y),T (2) I,1,,(5),,(,,x)(P(x),,(S(x),∨,F(x))),,P,(6),,P(y),,(S(y),∨,F(y)),UI (5),(7),,S(y),∨,F(y),T (3)(6) I,8,(8),,S(y),T (4)(7) I,10,谓词逻辑的推理理论前提： (x)(P(x)∧D(x),习题22(2),,(9),,(,,x)(P(x),∧,D(x),,,,S(x)),,P,,(10),,P(y),∧,D(y),,,,S(y),UI (1),,(11),,,(P(y),∧,D(y)),T (8)(10

34、) I,9,,(12),,,,P(y),∨,,,D(y),T (11) E,5,,(13),,,,D(y),T (3) (12) I,10,(14),,P(y),∧,,,D(y),T (3) (13),(15),,(,,x)(P(x),∧,,D(x)),,EG (14),(3),,P(y),T (2) I,1,(8),,S(y),T (4)(7) I,10,习题22(2) (9) (x)(P(x)∧D(x),谓词逻辑的推理理论,符号化下列各命题，并给出构造推理证明。,每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的科学工作者都将获得事业的成功,,华有为是一名科学工作者，

35、并且他是聪明的,所以：华有为将获得事业上的成功,S(x)：x,是科学工作者，,H(x)：x,刻苦钻研，,C(x)：x,是聪明的,P(x)：x,在获得事业上的成功，,a：,华有为,(,,x)(S(x),,H(x)),(,,x)(S(x),∧,H(x),∧,C(x),,P(x)),S(a),∧,C(a),P(a),谓词逻辑的推理理论符号化下列各命题，并给出构造推理证明。S(,谓词逻辑的推理理论,前提：,(,,x)(S(x),,H(x)),,,(,,x)(S(x),∧,H(x),∧,C(x),,P(x)),,,S(a),∧,C(a),,结论：,P(a),证明：,(1),,(,,x)

36、(S(x),,H(x)),,P,,(2),,S(a),,H(a),UI (1),,(3),,S(a),∧,C(a),,P,,(4),,S(a),T (3) I,1,,(5),,H(a),T (2)(4) I,8,(6),,(,,x)(S(x),∧,H(x),∧,C(x),,P(x)),,P,(7),,S(a),∧,H(a),∧,C(a),,P(a),UI (6),(8),,P(a),,T (3)(5)(7) I,8,谓词逻辑的推理理论前提： (x)(S(x)  H(x)),谓词逻辑的推理理论,符号化下列各命题，并给出构造推理证明。,每个资深名士，或是政协委员，或是国务院参事,资深

37、名士,张大为不是政协委员，但他是中科院院士,所以：有的中科院院士是国务院参事,K(x)：x,是资深名士，,Z(x)：x,是政协委员，,G(x)：x,是国务院参事，,S(x)：x,是中科院院士，,a：,张大为,(,,x)(K(x),,(Z(x),∨,,G(x)),),K(a),∧,,,Z(a),∧,S(a),(,,x)(S(x),∧,G(x)),谓词逻辑的推理理论符号化下列各命题，并给出构造推理证明。K(,习题22(4),证明：,(1),,(,,x)(K(x),,(Z(x),∨,,G(x))),,P,,(2),,K(a),,(Z(a),∨,,G(a)),UI (1),,(3),,K

38、(a),∧,,,Z(a),∧,S(a),,,P,,(4),,K(a),T (3) I,1,,(5),,Z(a),∨,,G(a),T (2)(4) I,8,(6),,,,Z(a),,T (3) I,1,,(7),,G(a),T (5)(6) I,10,(8),,S(a),T (3) I,1,(9),,G(a),∧,,S(a),T (7) (8),,(10),,(,,x)(S(x),∧,G(x)),,EG (9),前提：,(,,x)(K(x),,(Z(x),∨,,G(x)),),,,K(a),∧,,,Z(a),∧,S(a),,结论：,(,,x)(S(x),∧,G(x)),习题22(4

39、)证明： (1) (x)(K(x)  (Z(,每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。,谓词逻辑的推理理论,每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小,集合,设,A、B、C、D,是集合，求证：,(,A,,B)×,(,C,,D),,(,A,×,C),,,(,B,×,D),,证明：对于 (,A,,B) ×,(,C,,D),中的任意元素<,x, y>,，有：,<,x, y>,,(,A,,B)×,(,C,,D),,,x,,(,A,,B),∧,,y,,(,C,,D)

40、, (,x,,A,∧,x,,B),∧,(,y,,C,∧,y,,D), (,x,,A,∧,y,,C),∧,(,x,,B,∧,y,,D),,<,x, y>,,(,A,×,C,),∧,,<,x, y>,,(,B,×,D,),,,<,x, y>,,(,A,×,C),,,(,B,×,D),,集合设A、B、C、D是集合，求证：  (A  B)×(C,集合,20. 4) (A,-,B)×C =,(,A,×,C),-,,(,B,×,C),证明：,对于,(,A,-,B)×C,中的任意元素<,x, y>,，有,<,x, y>,,(,A,-,B)×C,,,x,,(,A,-

41、,B),∧,y,,C, (,x,,A,∧,x,,,B),∧,y,,C, (,x,,A,∧,y,,C,∧,x,,,B ),∨,(,x,,A,∧,y,,C,∧,y,,C,), (,x,,A,∧,y,,C),∧,(,x,,,B,∨,y,,,C,), (,x,,A,∧,y,,C),∧,,,(,x,,B,∧,y,,C,),,<,x, y>,,(,A,×,C),,∧,,<,x, y>,,,(,B,×,C),,,<,x, y>,,(,A,×,C),-,,(,B,×,C),集合20. 4) (A - B)×C = (A×C) -,集合,求证：若,A×A

42、 = B×B，,则：,A=B,证明：,假设,A,≠,B，,则必,存在,x，,有,x,,A,∧,x,,B,，或存在,y，,有,y,,A,∧,y,,B,若存在,x，,有,x,,A,∧,x,,B,，,则<,x,x>,,A×A，,且,<,x,x>,,B×B ，,则,A×A,≠,B×B,若存在,y， y,,A,∧,y,,B,，,则<,y,y>,,B×B，,且,<,y,y>,,A×A ，,则,A×A,≠,B×B,综上所述，可知：若,A×A = B×B，,则必有,A=B,集合求证：若A×A = B×B，则：A=B证明：假设 A ≠,集合,求证：若,A×B = A×C，,且,A,≠ 

43、，,则：,B=C,证明：,假设,B,≠,C，,则必,存在,y，,有,y,,B,∧,y,,C,，或存在,z，,有,z,,B,∧,z,,C，,又因为,A,≠ ，则必存在,x,,A,。,若存在,y，,有,y,,B,∧,y,,C,，,有,,,,A×B，,且,<,x,y>,,A×C ，,则,A×B,≠,A×C,若存在,z，,有,z,,B,∧,z,,C,，,有,则<,x,z>,,A×B，,且,<,x,z>,,A×C ，,则,A×B,≠,A×C,综上所述，可知：若,A×B = A×C，,且,A,≠ ，,则必有,B=C,集合求证：若A×B = A×C，且A ≠ ，则：B=C证明

44、,设,A,、,B,、,C,、,D,为四个非空集合，则,A×B,,C×D,的充要条件是,A,,C,，,B,,D,,已知,A,、,B,、,C,是三个集合，证明,(,A,∪,B,),－,C,＝,(,A,－,C,)∪(,B,－,C,),集合,设A、B、C、D为四个非空集合，则A×B  C×D的充要条,闭包运算,构造,r(R),、,s(R),、,t(R),的方法就是给,R,补充必要的有序对,。,设,G,是集合,A,上二元关系,R,的关系图，给,G,中所有结点都补充上有向环，就得到了,R,的自反闭包,r(R),的关系图。,定理：,若,R,,A×A，,则,r(R),=,R,,I,A,证明： 因为

45、是,I,A,自反的，因此,R,,I,A,是自反的,且,R,,R,,I,A,设,R,1,是,A,上任意的自反关系，且,R,,R,1,，,由于,R,1,是自反的，因此,I,A,,,R,1,，,又因为,R,,R,1,，因此,R,,I,A,,R,1,，,故,r(R),=,R,,I,A,参照定义,闭包运算构造r(R)、s(R)、t(R)的方法就是给R补充必,闭包运算,设,G,是集合,A,上二元关系,R,的关系图，将,G,中所有的弧都画成“有来有往”（即如果有从,a,到,b,的弧，就有从,b,到,a,的弧）就得到了,R,的对称闭包,s(R),的关系图。,定理：,若,R,,A×A，,则,

46、s(R),=,R,,R,-1,证明：,1)设,R,1,=R,,R,-1,，,显然,R,,R,1,,。,2)因为,R,1,-1,= (,R,,R,-1,),-1,=,R,-1,,,(R,-1,),-1,=,R,-1,,,R = R,1,,所以,R,1,是对称的,。,定理：,若,R,,A×A，,则,R,是对称的,,,R=R,-1,闭包运算设G是集合A上二元关系R的关系图，将G中所有的弧都画,闭包运算,3) 设,R,2,是,A,上任意的对称关系，且,R,,R,2,。,对于任意<,x,y>,,R,1,，,或者<,x,y>,,R，,或者<,x,y>,,R,-1,,若<,x,y>,

47、,R，,则<,x,y>,,R,2,；,若<,x,y>,,R,-1,，,则<,y,x>,,R，,则<,y,x>,,R,2,，,又因为,R,2,是对称的，所以<,x,y>,,R,2,；,所以,R,1,,,R,2,,综上所述，证得,s(R),=,R,,R,-1,闭包运算3) 设R2是A上任意的对称关系，且R  R2。,闭包运算,设,G,是集合,A,上二元关系,R,的关系图，如果有从,a,到,b,的弧，并且有从,b,到,c,的弧，就补充上从,a,到,c,的弧，就得到了,R,的传递闭包,t(R),的关系图。,定理：若,R,,A×A，,则,t(R),=,,R,i,=R,,R,2,,

48、,R,3,,,……,证明略（教材,P73）,定理：若,R,,A×A，|A|= n,则,t(R),=,,R,i,=R,,R,2,,,R,3,,,……,,R,n,,i=1,n,证明略（教材,P74）,i=1,,闭包运算设G是集合A上二元关系R的关系图，如果有从a到b的弧,闭包运算,定理：,若,R,是,A,上的二元关系，则：,rs(R),=,sr(R),证明：,sr(R),,=,s(R,,I,A,),,=,(R,,I,A,),,(R,,I,A,),-1,= (R,,I,A,), (,R,-1,,,I,A,-1,),,= (,R,,R,-1,),,I,A,,=,r,

49、,(,R,,R,-1,),,= rs (R),定理：,若,R,,A×A，,则,r(R),=,R,,I,A,定理：,若,R,,A×A，,则,s(R),=,R,,R,-1,闭包运算定理：若R是A上的二元关系，则：rs(R) = sr,闭包运算,定理：,若,R,是,A,上的二元关系，则：,rt(R),=,tr(R),证明： 由于,R°I,A,= I,A,°R=R，,且,I,A,° I,A,= I,A,,；,,(R,,I,A,),2,= (,,R,,I,A,),,° (,,R,,I,A,),,=,,R° (R,,I,A,),,I,A,° (R,,I,A,) = I,A,,,R,

50、,R,2,,因此，,tr(R) = t (,R,,I,A,) =,,,(,R,,I,A,),i,,i=1,,,i=1,n,用归纳法可证：,(,R,,I,A,),n,= I,A,,(,,R,i,),i=1,,=,,(,I,A,,(,,R,j,) ),=,I,A,,(,,R,j,) = I,A,,t(R),= rt(R),j=1,i,,j=1,,R ° (S,,T),=,R ° S,,R ° T,R,2,R,p73,闭包运算定理：若R是A上的二元关系，则：rt(R) = tr,关系的闭包运算,设集合,A={a,b,c,d},上的关系,R={,,,},，用矩阵运

51、算求出,R,的传递闭包,关系矩阵：,关系的闭包运算设集合A={a,b,c,d}上的关系R={

52、3},{4,5}}的等价关系，并画出关系图：,解：,R =,({1,2},×,{1,2}),,({3},×,{3}),,({4,5},×,{4,5}),= {, , , , <3,3,>,,, ,,,},,,,1,2,,,3,,,4,5,,等价关系与划分设集合A={1,2,3,4,5}，求A上的一个,等价关系与划分的对应关系,已知,Π={{a}{b,c}},是,A={a,b,c},的一个划分，由,Π,决定的,A,上的一个等价关系是,,。,等价关系与划分的对应关系已知Π={{a}{b,c}}是A={,等价关系的证明,设,R,和,S,是非空集合,A,上的等价关系，试确定下面各式是否为等价关系。

53、若是则证明之，若不是则举例说明：,R,2,证明：1) 对于,,,x,,A，,有,xRx。,因此有,xR,2,x，,故,R,2,是自反的,2),对于,,,x, y,,A，,若有,xR,2,y，,则必存在,z,,A，,有,xRz, zRy，,因为,R,是对称的，所以必定有：,yRz, zRx，,即有,yR,2,x,。,也就是说：若有,xR,2,y，,则必有,yR,2,x，,故,R,2,是对称的,3),对于,,x,y,z,,A，,若有,xR,2,y, yR,2,z，,则,,,a,b,,A，,有：,xRa,和,aRy,以及,yRb,和,bRz，,因为,R,是传递的，所以必定有：,xR

54、y, yRz。,,则若有,xR,2,y, yR,2,z，,必有,xR,2,z，,故,R,2,是传递的,。,∴,R,2,是等价关系,是,。,等价关系的证明设R和S是非空集合A上的等价关系，试确定下面各,等价关系的证明,设,R,是,A,上的二元关系，对于,,a, b, c,,A，,若,aRb, bRc，,则,cRa，,称,R,是,循环的,。求证：,R,是自反的和循环的，当且仅当,R,是等价关系,证明：1),若,R,是等价关系,，则,R,是自反的,、对称的和传递的。,对于,,a, b, c,,A，,若,aRb, bRc，,因为,R,是传递的，所以有,aRc,又因为,R,是对称的，所以有,c

55、Ra。,所以,R,是循环的,2),若,R,是,自反的,和循环的,，,则对于,,a, b, c,,A，,若,aRb, bRc，,则,cRa,因为,R,是自反的，所以有,aRa，,所以有,aRc，,所以,R,是传递的,若有,aRb，,因为有,bRb，,则有,bRa，,所以,R,是对称的,，故,R,是等价关系,cRa,aRa,则,aRc,等价关系的证明设R是A上的二元关系，对于a, b, c ,偏序关系的证明,设,R,是集合,A,上的偏序关系，且,B,,A，,求证：,R,,(B×B),是,B,上的偏序关系,证明：1),对于,,x,,B,，,一定有：<,x,x>,,B×B,因为,B,

56、,A，,所以,x,,A，,所以一定有：<,x,x>,,R,,所以，,一定有<,x,x>,,R,,(B×B),，,所以：,R,,(B×B),是,自反的,偏序关系的证明设R是集合A上的偏序关系，且B  A，求证,偏序关系的证明,设,R,是集合,A,上的偏序关系，且,B,,A，,求证：,R,,(B×B),是,B,上的偏序关系,2) 对于,,x, y,,B，,一定有<,x,y>,,B×B,且<,y,x>,,B×B,因为,R,是反对称的，所以若有<,x,y>,,R,且<,y,x>,,R，,则有,x=y,所以：,若有<,x,y>,,R,,(B×B),且<,y,x>,,

57、R,,(B×B),，,则有： <,x,y>,,R,且<,y,x>,,R，,则有：,x=y,所以：,R,,(B×B),是,反对称的,偏序关系的证明设R是集合A上的偏序关系，且B  A，求证,偏序关系的证明,设,R,是集合,A,上的偏序关系，且,B,,A，,求证：,R,,(B×B),是,B,上的偏序关系,3) 对于,,x, y, z,,B，,一定有<,x,y>,,<,y,z>, ,,B×B,因为,R,是传递的, 所以若有<,x,y>,,R,且<,y,z>,,R,,则有<,x,z>,,R,所以：,若有<,x,y>,,R,,(B×B),且<,y,z>,,R,,(B×

58、B),，,则有：,<,x,z>,,R,,(B×B),,所以：,R,,(B×B),是,传递的,。故,R,,(B×B),是,B,上偏序关系,偏序关系的证明设R是集合A上的偏序关系，且B  A，求证,,设,R,1,是,A,上的等价关系，,R,2,是,B,上的等价关系，,A,≠,,且,B,≠,,。,关系,R,满足,<<,x,1,,,y,1,>,<,x,2,,,y,2,>>∈,R,,<,x,1,,,x,2,>∈,R,1,且,<,y,1,,,y,2,>∈,R,2,，证明,R,是,A,×,B,上的等价关系,设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠,哈斯图与偏序集中特殊位

59、置的元素,图中给出了偏序集<,A,,≤,>,的哈斯图，其中,A=,,{a,b,c,d,e},,判断下面各式的真假,a,≤,b,d,≤,a,c,≤,e,b,≤,e,F,a,≤,a,b,≤,c,d,≤,e,T,F,F,T,F,F,,,,,c,b,a,d,,e,哈斯图与偏序集中特殊位置的元素图中给出了偏序集的,哈斯图与偏序集中特殊位置的元素,图中给出了偏序集<,A,,≤,>,的哈斯图，其中,A=,,{a,b,c,d,e},,求,A,中最大元和最小元求,A,中的极大元和极小元,最大元：,a,,,,,c,b,a,d,,e,最小元：无,极大元：,a,极小元：,d,和,e,哈斯图与偏序集中特殊位置的元素

60、图中给出了偏序集的,图中给出了偏序集<,A,,≤,>,的哈斯图，其中,A=,,{a,b,c,d,e},,求下面各子集的上界和下界并指出它们的上确界和下确界,{a, b, c},{b, c, d},{c, d, e},上界： 下界： 上确界： 下确界：,哈斯图与偏序集中特殊位置的元素,a,,,,,c,b,a,d,,e,d,a,d,上界： 下界： 上确界： 下确界：,a,d,a,d,上界： 下界： 上确界： 下确界：,a,c,无,c,无,图中给出了偏序集的哈斯图，其中A= {a,b,c,哈斯图,设,A={2,5,6,10,15,30},，,R,是,A,上的整除关系，,B=

61、{2,5,6,10},，则,B,的极小元是,,，极大元是,,，最小元是,,，最大元是,,，上界是,,，下界是,,，上确界是,,，下确界是,,。,哈斯图设A={2,5,6,10,15,30}，R是A上的整除,函数,求证：从,N×N,到,N,的函数,f(x, y)=x+y，,和,g(x, y)=x·y,是满射函数，但不是单射函数,证明：,1),对于,,x,,N,，f(x,0)=x+0=x，,g(x, 1)=x·1=x,因此，总存在<,x,0>,,N×N,，,使得,f(x, 0) = x，,所以,f,是满射的,且总存在<,x,1>,,N，,使得,g(x, 1) = x，,所以,g,是满射的,

62、2),因为有：,<,1,3>,,,<,1,4>,,N×N,，,且,f(1, 3) = f(2, 2) = 4，,且,g(1, 4) = f(2, 2) = 4,,所以,f,和,g,都不是单射的,函数求证：从N×N到N的函数f(x, y)=x+y，和g(x,函数,设,f: A,,B,是满射函数，且函数,g: B,,P(A)，,定义为：,g(b) = {x|x,,A,∧,f(x)=b},求证：,g,是单射的。其逆是否成立？,证明： 对于,,b,1,, b,2,,,B，,且,b,1,≠,b,2,由于,f,是满射的，则必存在,a,1,,a,2,,A，,使得,f(,a,1,)=b,1,，

63、f(,a,2,)=b,2,g(b,1,)={x|x,,A,∧,f(x)=b,1,}, g(b,2,)={x|x,,A,∧,f(x)=b,2,},则,对于,,x,,g(b,1,),，,有,f(x)=b,1,，,且有,f(x),≠,b,2,，,即,x,,g(b,2,),即,对于,,b,1,, b,2,,,B，,且,b,1,≠,b,2,，,都有,g(b,1,),,≠,g(b,2,),所以，,g,是单射的,函数设 f: A  B 是满射函数，且函数 g: B ,函数,设,f: A,,B,是满射函数，且函数,g: B,,P(A),，定义为：,g(b) = {x|x,,A ∧ f(x)=b},求证：,g,是单射的。,设,g,,f,是复合函数，如果,g,,f,是双射，那么,f,是入射而,g,是满,射,函数设 f: A  B 是满射函数，且函数 g: B ,此课件下载可自行编辑修改，此课件供参考！,部分内容来源于网络，如有侵权请与我联系删除！感谢你的观看！,此课件下载可自行编辑修改，此课件供参考！,此课件下载可自行编辑修改，此课件供参考！,部分内容来源于网络，如有侵权请与我联系删除！感谢你的观看！,此课件下载可自行编辑修改，此课件供参考！,