离散数学习题课带答案.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,命题逻辑习题课参考答案,一,.,命题符号化,P:,天下雪。,Q:,我将去镇上。,R:,我有时间。,(1),如果天不下雪且我有时间，那么我将去镇上。,(,PR)Q,(2),我将去镇上，仅当我有时间。,QR,(3),天下雪，那么我不去镇上。,P,Q,(4),或者你没有给我写信，或者它在途中丢失了。,显然这里的“或者”是“不可兼取的或”。,令,P:,你给我写信。,Q:,信在途中丢失了。,P Q,或,(,P,Q)(,P,Q),(5),我们不能既划船又跑步。,令,P:,我们划船。,Q:,我们跑步。,(,PQ,),(6),如果你来了，那么他唱不唱歌将看你是否为他伴奏而定。,令,P:,你来了。,Q:,你为他伴奏。,R:,他唱歌。,P(QR)(,Q,R),或：,P(Q,R),(7),假如上午不下雨，我去看电影，否则就在家里读书或看报。,令,P:,上午下雨。,Q:,我去看电影。,R:,我在家里读书。,S:,我在家里看报。,(,PQ)(P(R,S,),(8),我今天进城，除非下雨。,令,P:,我今天进城。,Q:,今天下雨。,表达式为,:,QP,(9),仅当你走我将留下。,令,P:,你走。,Q:,我留下。,表达式为,:,QP,或者,P,Q,二,.,重言式的证明方法,方法,1,：列真值表。,方法,2,：公式的等价变换，化简成“,T”,。,方法,3,：用公式的主析取范式。,(1),证明,(PQ)(P(P,Q,),是,重言式。,方法,1,:,P Q,PQ P(P,Q,)(PQ)(P(P,Q,),F F T T T,F T T T T,T F F F T,T T T T T,方法,2,:,(,PQ)(P(P,Q,),(P,Q)(,P,(PQ),(P,Q)(,P,P)(,P,Q),(P,Q)(T(,P,Q),(P,Q)(,P,Q),(P,(,P,Q),),(,Q(,P,Q),(P,P),Q),),(,Q(Q,P,),(T,Q),),(,QQ),P,),T,(T,P,),T,T,T,方法,3,(,PQ)(P(P,Q,),(P,Q)(,P,(PQ),(P,Q),P,(PQ),(P,Q)(,P,(Q,Q)(PQ),(P,Q)(,P,Q)(,P,Q)(PQ),(PQ),(P,Q)(,P,Q)(,P,Q),可见，该公式的主析取范式含有全部,(,四个,),小项，这表明,(,PQ)(P(P,Q,),是永真式,四,.,等价公式的证明方法,方法,1,：用列真值表。（不再举例）,方法,2,：用公式的等价变换,.(,用置换定律,),(1),证明,(AB)C)(B(DC),(B(DA)C,左式,(,AB)C)(,B,(DC),(,A,B)C)(,B,(DC),(,B,A)C)(,B,D)C),(,B,A)(,B,D)C,(,B,(,AD)C,(,B(A,D)C,(,B(DA)C,(2),化简,(A,BC)(,A,B,C,）,上式,(A,A)(,B,C,）,T,(,B,C,）,B,C,五,.,范式的写法及应用,(1),写出,(P,(,Q,R),),(,P,(Q,R,),的主析取范式和主合取范式,方法,1,，用,真值表,令,A(P,Q,R),(P,(,Q,R),),(,P,(Q,R,),A(P,Q,R),m,0,m,7,(,P,Q,R,),(,P,Q,R,)(0,7),A(P,Q,R),M,1,M,2,M,3,M,4,M,5,M,6,(P,Q,R),(,P,Q,R,)(,P,Q,R,),(,P,Q,R,)(,P,Q,R,)(,P,Q,R,),(1,2,3,4,5,6),P Q R P,(,Q,R),P,(Q,R,)A(P,Q,R),0 F F F T T T,1 F F T T F F,2 F T F T F F,3 F T T T F F,4 T F F F T F,5 T F T F T F,6 T T F F T F,7 T T T T T T,方法,2,.,等价变换,(P,(,Q,R),),(,P,(Q,R,),(,P,(,Q,R),),(P,(Q,R,),(,P,P),(,P,Q,R),),(,P,Q,R,),(,Q,R)(,Q,R,),F,(,P,Q,R),),(,P,Q,R,),F,(,P,Q,R),),(,P,Q,R,),(P,(,Q,R),),(,P,(Q,R,),(,P,(,Q,R),),(P,(Q,R,),(,PQ),(,P,R),),(P,Q),(P,R,),(,PQ(R,R,),(,P(Q,Q,),R),(P,Q,(R,R,),(P,(Q,Q,),R,),(,PQR),(,PQ,R,),(,PQ,R),(,P,Q,R)(P,Q,R),(P,Q,R,),(P,Q,R,),(P,Q,R,),(,PQR),(,PQ,R,),(,P,Q,R)(P,Q,R),(P,Q,R,),(P,Q,R,),(2)A,B,C,D,四个人中要派两个人出差，按下述三个条件有几种派法？,若,A,去则,C,和,D,中要去一个人。,B,和,C,不能都去。,C,去则,D,要留下。,解.设,A,B,C,D,分别表示,A,去，,B,去，,C,去，,D,去。,A,(C,D),(,C,D),A,(C,D),(,C,D),(B,C)B,C,C,D,C,D,总的条件为：,(,A(C,D)(,C,D),(B,C),(C,D),令此式为真。,将,(,A(C,D)(,C,D),(B,C),(C,D),化成析取范式。,上式,(,A(C,D)(,C,D),),(,C,(,B,D),),(,A,C),(C,D,C),(,C,D,C),(,A,B,D),(C,D,B,D),(,C,D,B,D),(,A,C),F(,C,D,),(,A,B,D),(C,D,B),F,可以取,A,C,为,T,，得,B,和,D,去。,取,C,D,为,T,，得,A,和,D,去，或者,B,和,D,去。,取,C,D,B,为,T,，得,A,和,C,去。,最后得三种派法：,A,和,C,去、,A,和,D,去、,B,和,D,去。,(3),有工具箱,A,、,B,、,C,、,D,，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。,解：设,A,、,B,、,C,、,D,分别表示带,A,、,B,、,C,、,D,箱。,则总的条件为：,(,A,C,),(A,B,D),(B,C),(B,D),为真。,改锥,扳手 钳子 锤子,工具,箱,改 锥 扳 手 钳 子 锤 子,A,有 有,B,有 有 有,C,有 有,D,有 有,将,(,A,C,),(A,B,D),(B,C),(B,D),写成析取范式，,上式,(,(,A,C,),(B,C),(,(A,(,B,D),(B,D),),(,(,A,B,),C),(,B,D),(,A,B,B,),(,C,B),(,A,B,D),(,C,D),(,A,B,),(,C,B),(,A,B,D),(,C,D),分别可以取,(,A,B,),、,(,C,B),、,(,C,D),为真。,于是可以得到三种携带方法：,带,A,和,B,箱，带,B,和,C,箱，带,C,和,D,箱。,六,.,逻辑推理,熟练掌握三种推理方法。,(1)(AB),(C,D),(DE),P,A,P,1.,直接推理,(AB),(C,D)P,(AB)(C,D)T E,(,A,B)(C,D)T E,(,AC),(,BC),(,AD),(,BD)T E,AD T I,A,D T E,(DE),P P,(DE)P T E,(,D,E)P T E,(,D P),(,EP)T E,DP T I,D,P T E,A,P T I,2.,附加前提,A P(,附加前提,),AB T I,(AB),(C,D)P,C,D T I,D T I,DE T I,(DE),P P,P T I,A,P CP,3.,反证法,(A,P)P(,假设前提,),(,AP)T E,A,P T E,A T I,AB T I,(AB),(C,D)T,C,D T I,D T I,DE T I,(DE),P P,P T I,P T I,P,P T I,(2),请根据下面事实，找出凶手：,1.,清洁工或者秘书谋害了经理。,2.,如果清洁工谋害了经理，则谋害不会发生在午夜前。,3.,如果秘书的证词是正确的，则谋害发生在午夜前。,4.,如果秘书的证词不正确，则午夜时屋里灯光未灭。,5.,如果清洁工富裕，则他不会谋害经理。,6.,经理有钱且清洁工不富裕。,7.,午夜时屋里灯灭了。,令,A:,清洁工谋害了经理。,B:,秘书谋害了经理。,C:,谋害发生在午夜前。,D:,秘书的证词是正确的,.,E:,午夜时屋里灯光灭了。,H:,清洁工富裕,.,G:,经理有钱,.,命题符号为：,AB,A,C,DC,DE,HA,G,H,E,?,AB,A,C,BC,DC DE,HA,G,H,E,?,E P,DE P,D T I,D T E,DC P,C T I,A,C P,A T I,AB P,B T I,结果是秘书谋害了经理。,谓词逻辑习题课,1.,将下列命题符号化,（,1,）在湖南高校学习的学生，未必都是湖南籍的学生,H,(,x,),：,x,是在湖南高校学习的学生,;,S,(,x,),：,x,是湖南籍的学生,x,(,H,(,x,),S,(,x,),（,2,）对于每一个实数,x,，存在一个更大的实数,y,R,(,x,),：,x,是实数；,G,(,x,y,):,x,比,y,大,x,(,R,(,x,),y,(,R,(,y,),G,(,y,x,),（,3,）存在实数,x,，,y,和,z,，使得,x,与,y,之和大于,x,与,z,之积,f,(,x,y,)=,x,+,y,;,g,(,x,y,)=,x,y,x,y,z,(,R,(,x,),R,(,y,),R,(,z,),G,(,f,(,x,y,),g,(,x,z,),（,4,）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快,C,(,x,),：,x,是汽车；,H,(,x,),：,x,是火车；,S,(,x,y,):,x,比,y,慢,x,(,C,(,x,),y,(,H,(,y,),S,(,x,y,),z,(,H,(,z,),y,(,C,(,y,),S,(,y,z,),（,5,）对任何整数,x,和,y,，,x,y,且,y,x,是,x,=,y,的充要条件,I,(,x,),：,x,是整数；,E,(,x,y,),：,x,=,y,；,G,(,x,y,),：,x,y,x,y,(,I,(,x,),I,(,y,),(,G,(,x,y,),G,(,y,x,),E,(,x,y,),（,6,）若,m,是奇数，则,2,m,不是奇数,O,(,x,),：,x,是奇数；,f,(,x,y,)=,x,y O,(,m,),O,(,f,(2,m,),（,7,）那位戴眼镜的用功的大学生在看这本大而厚的巨著,A,(,x,):,x,是戴眼镜的,B,(,x,):,x,是用功的,C,(,x,):,x,是大学生,D,(,x,):,x,是大的,E,(,x,):,x,是厚的，,F,(,x,):,x,是巨著,G,(,x,y,):,x,在看,y,a,:,那位，,b,:,这本,A,(,a,),B,(,a,),C,(,a,),D,(,b,),E,(,b,),F,(,b,),G,(,a,b,),（,8,）每个自然数都有唯一的后继数,N,(,x,),：,x,是自然数；,L,(,x,y,),：,x,是,y,的后继数,x,(,N,(,x,),(,y,(,N,(,y,),L,(,y,x,),z,(,N,(,z,),L,(,z,x,),E,(,y,z,),（,9,）没有一个自然数使数,1,是它的后继数,x,(,N,(,x,),L,(1,x,),（,10,）每个不等于,1,的自然数都有唯一的一个数是它的直接先行者,S,(,x,y,),：,x,是,y,的先行者,x,(,N,(,x,),E,(,x,1),!,y,(,N,(,y,),S,(,y,x,),z,(,N,(,z,),S,(,y,z,),S,(,z,x,),2.,变元的约束,（,1,）对下列谓词公式中的约束变元换名,x,(,P,(,x,)(,R,(,x,),Q,(,x,),xR,(,x,),zS,(,x,z,),y,(,P,(,y,)(,R,(,y,),Q,(,y,),t,R,(,t,),u,S,(,x,u,),（,2,）对下列谓词公式中的,自由变元代入,(,yA,(,x,y,),x,B,(,x,z,),x,z,C,(,x,y,z,),(,yA,(,u,y,),x,B,(,x,v,),x,z,C,(,x,w,z,),3.,讨论在给定解释下谓词公式的真值,（,1,）,x,(,P,Q,(,x,),R,(,a,),D,=-2,3,6,P,:21,Q,(,x,):,x,3,R,(,x,):,x,5,a,:5,x,(,P,Q,(,x,),R,(,a,),(,P,x,Q,(,x,),R,(,a,),(,P,(,Q,(-2),Q,(3),Q,(6),R,(5),(,T,(,T,T,F,),F,(,T,F,),F,F,F,F,（,2,）,x,y,(,P,(,x,),Q,(,x,y,),D,=,1,2，,P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2),F T T T F F,真值为,F,4.,判断下列公式是不是永真式，并加以说明,（,1,）,(,xP,(,x,),xQ,(,x,),x,(,P,(,x,),Q,(,x,),),解：不是永真式，取解释如下,D,=,1,2,P,(1),P,(2),Q,(1),Q,(2),F,T,F,T,在该解释下,xP,(,x,),为,T,，,xQ,(,x,),为,F,，所以,xP,(,x,),xQ,(,x,),为,F,；而,(,P,(1),Q,(1),为,T,，,(,P,(2),Q,(2),为,T,，所以,x,(,P,(,x,),Q,(,x,),),为,T,；综上该公式不是永真式,（,2,）,x,y(,P,(,x,),Q,(,y,),(,xP,(,x,),y,Q,(,y,),),解：是永真式。,证明：法,1,，形式证明,法,2,，量词作用域的收缩与扩张公式,5.,用形式推理证明：,（,1,）,x,P,(,x,),x,Q,(,x,),x,(,P,(,x,),Q,(,x,),(1),x,(,P,(,x,),Q,(,x,)P(,假设,),(2),x,(,P,(,x,),Q,(,x,)T(1)E,(3),(,P,(,c,),Q,(,c,)ES(2),(4),P,(,c,),Q,(,c,)T(3)E,(5),P,(,c,),T(4)I,(6),x,P,(,x,)EG(5),(7),x P,(,x,),T(6)E,(8),x,P,(,x,),x,Q,(,x,)P,(9),x,Q,(,x,)T(7)(8)I,(10),Q,(,c,)US(9),(11),Q,(,c,)T(4)I,(12),Q,(,c,),Q,(,c,)T(10)(11)I,（,2,）,xF,(,x,),y,(,G,(,y,),H,(,y,),xM,(,x,),yG,(,y,),x,(,F,(,x,),M,(,x,),yH,(,y,),(1),x,(,F,(,x,),M,(,x,)P(,附加,),(2),xF,(,x,),y,(,G,(,y,),H,(,y,)P,(3),xM,(,x,),yG,(,y,)P,(4),xF,(,x,),xM,(,x,)T(1)I,(5),xF,(,x,)T(4)I,(6),y,(,G,(,y,),H,(,y,)T(2)(5)I,(7),xM,(,x,)T(4)I,(8),yG,(,y,)T(3)(7)I,(9),G,(,c,)ES(8),(10),G,(,c,),H,(,c,)US(6),(11),H,(,c,)T(9)(10)I,(12),yH,(,y,)EG(11),(13),x,(,F,(,x,),M,(,x,),yH,(,y,)CP,（,3,）,任何人如果他喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因此有的人不爱步行,设,A(x):x,是人,B(x):x,是,喜欢步行,C(x):x,喜欢乘汽车，,D(x):x,喜欢骑自行车,x(,A(x)(B(x),C(x),),x(,A(x)(C(x),D(x),),x(A(x),D(x),x(A(x),B(x),x(A(x),D(x),P,A(a),D(a),ES,A(a),T,I,D(a),T,I,x(,A(x)(B(x),C(x),)P,A(a)(B(a),C(a),)US,B(a),C(a),)T,I,x(,A(x)(C(x),D(x),)P,A(a)(C(a),D(a),)US,C(a),D(a)T I,C(a)T I,B(a)T I,A(a),B(a)T I,x(A(x),B(x)EG,（,4,）,每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生,设,A(x):x,是大学生,B(x):x,是,文科生,C(x):x,是理工科生,，,D(x):x,是优等生,a:,小张,x(,A(x)(,B(x)C(x),),x(A(x),D(x),C(a),D(a),A(a)B(a),x(,A(x)(,B(x)C(x),),x(A(x),D(x),C(a),D(a),A(a)B(A),A(a)P(,附加前提),x(,A(x)(,B(x)C(x),)P,A(a)(,B(a)C(a),)US,B(a)C(a),)T I,C(a),D(a)P,C(a)T,I,B(a)T,I,B(a)T,E,A(a)B(a)CP,集合论习题课,1.,判断下面命题的真值,(,真的话证明，假的话举反例,),a,),如果,A,B,，,B,C,，则,A,C,T,b,),如果,A,B,，,B,C,，则,A,C,F,举反例,A,=1,B,=1,C,=1,2,c,),如果,A,B,，,B,C,，则,A,C,F,举反例,A,=1,B,=1,2,C,=1,2,d,),如果,A,B,，,B,C,，则,A,C,F,举反例,A,=1,B,=1,2,C,=1,2,2.,集合,计算,a,),=,b,),=,c,),=,d,),-,=,e,),-,=,3.,在什么条件下，下面命题为真？,a,)(,A,-,B,),(,A,-,C,)=,A,(,A,-,B,),(,A,-,C,)=(,A,B,),(,A,C,)=,A,(,B,C,),=,A,(,B,C,)=,A,-(,B,C,)=,A,所以满足此式的,充要条件,是：,A,B,C,=,b,)(,A,-,B,),(,A,-,C,)=,(,A,-,B,),(,A,-,C,)=,A,-(,B,C,)=,所以满足此式的,充要条件,是：,A,B,C,c,)(,A,-,B,),(,A,-,C,)=,(,A,-,B,),(,A,-,C,)=(,A,B,),(,A,C,)=,A,(,B,C,),=,A,(,B,C,)=,A,-(,B,C,)=,所以满足此式的,充要条件,是:,A,B,C,d,)(,A,-,B,)(,A,-,C,)=,因为 当且仅当,A,=,B,，,才有,A,B,=,所以满足此式的,充要条件,是:,A,-,B,=,A,-,C,4.,集合的基数,A,B,是有限集合,已知,|,A,|=3,|,(,B,)|=64,|,(,A,B,)|=256,则,|,B,|=(),|,A,B,|=(),|,A,-,B,|=(),|,A,B,|=(),解：,由,|,(,B,)|=64=2,6,，得,|,B,|=6,由,|,(,A,B,)|=256,2,8,，得,|,A,B,|=8,由容斥原理得,|,A,B,|=|,A,|+|,B|-,|,A,B,|,|,A,B,|=|,A,|+|,B|-,|,A,B,|=3+6-8=1,，,所以,|,A,B,|,1,|,A,-,B,|=,|,A,|,|,A,B,|=3-1=2,|,A,B,|=,|,A,B,|,|,A,B,|=8-1=7,5.,集合的证明,a,),证明,(,A,B,),C,=,A,(,B,C,),iff,C,A,证明；充分性 已知,C,A,(,A,B,),C,=(,A,C,)(,B,C,),=,A,(,B,C,)(,C,A,A,C,=,A,),必要性 已知,(,A,B,),C,=,A,(,B,C,),x,C,，,x,C,x,(,A,B,),C,x,A,(,B,C,),x,A,所以,C,A,b,),证明,(,A,-,B,)-,C,=(,A,-,C,)-,B,x,：,x,(,A,-,B,)-,C,x,(,A,-,B,),x,C,(,x,A,x,B,),x,C,(,x,A,x,C,),x,B,x,(,A,-,C,),x,B,x,(,A,-,C,)-,B,所以,(,A,-,B,)-,C,=(,A,-,C,)-,B,c,),证明以下各式彼此等价：,A,B,=,U,A,B,B,A,A,B,=,U,x,(,x,A,B,x,U,),x,(,x,A,B,),(,x,U,为,T,),x,(,x,A,x,B,),x,(,x,A,x,B,),x,(,x,A,x,B,),A,B,同理,A,B,=,U,.,x(x,A,x,B,),x,(,x,B,x,A,),x,(,x,B,x,A,),B,A,所以,A,B,=,U,A,B,B,A,.,6.,幂集,设,A,B,是集合，证明以下命题成立,a,),(,A,B,)=,(,A,),(,B,),S,：,S,(,A,B,),S,A,B,S,A,S,B,S,(,A,),S,(,B,),S,(,A,),(,B,),b,),(,A,),(,B,),(,A,B,),S,：,S,(,A,),(,B,),S,(,A,),S,(,B,),S,A,S,B,S,A,B,S,(,A,B,),c,),A,B,iff,(,A,),(,B,),证明：,必要性：若,A,B,证明,(,A,),(,B,),S,：,S,(,A,),即,S,A,A,B,S,B,即,S,(,B,),(,A,),(,B,),充分性：若,(,A,),(,B,),证明,A,B,x,：,x,A,必,S,，,S,A,，使得,x,S,(,A,),(,B,),由,S,A,即,S,(,A,),可得到,S,(,B,),也就是说,S,B,x,B,A,B,综上所述：,A,B,iff,(,A,),(,B,),7.,笛卡尔积,A,=0,1,B,=1,2,求,A,2,B,A,2,B=,B,=,1,2,1,2,1,2,1,2,注意,：,A,2,B=,(,A,A,),B A,A,B,二元关系习题课,一,.,判断题,(F),设,A,、,B,、,C,和,D,是四个非空集合,且,AC,BD,，则,A,B,且,C,D,。,(F),设,A,、,B,、,C,和,D,是四个集合，则,AC=BD,，,iff A=B,且,C=D,。,(F)3.,传递关系的对称闭包仍是传递的。,(F)4.,非空集合上的关系不是对称的，则必是反对称的。,(T)5.,非空集合上的自反关系必不是反自反的。,(F)6.,若,R,和,S,是二个有完全相同的二元组的集合，则称它们是相等的二元关系。,(F)7.,设,A,是一个非空集合，则,A,上的等价关系都不是偏序关系。,(T)8.,有限集上的全序关系必是良序关系。,(F)9.,有限集上的偏序关系必是全序关系。,(F)10.,是偏序集，则的任何非空子集必有极小元。,(F)11.,是偏序集，则的非空子集的上确界必是的最大元。,(F)12.,是全序集，则的任何非空子集必有唯一极小元。,(F)13.,是全序集，则的非空子集的下确界必是的最小元。,二、多项选择题,(1,2 ),下列说法中正确的有：,任何集合都不是它自身的元素 任何集合的幂集都不是空集,若,，则,任意两集合的迪卡尔积都不是空集,(4,5 )1,2,3,4,5,上的关系,R=,是,自反的 反自反的 对称的 反对称的 传递的,(1,2,3),设,R=,是,1,2,3,上的关系，则,rst(R),是等价关系 ,10,r(R),是偏序 ,tr(R),是良序,(5 ),设,R,和,S,分别是,A,到,B,和,B,到,C,的关系，且,RS=,，那么,R,是空关系 ,S,是空关系 ,R,和,S,都是空关系,R,和,S,中至少有一个是空关系 以上答案都不对,(2),若,R,和,S,是集合,A,上的等价关系，则下列关系中一定是等价关系的有,RS RS R,S R,S,(1,2,4),若,R,是集合,A,上的等价关系，则,R,2,R t(R),R ,A,R R,-1,R,(1,2,3,4,5),空集上的空关系是,关系。,线序 等价 偏序 拟序 良序,(2,4)8.1,2,3,4,5,上的全序关系一定是,关系。,等价 偏序 拟序 良序,(1,4,5)9.1,2,3,4,5,上的良序关系一定是,自反的 反自反的 对称的 反对称的 传递的,(1,2,3,4)10.,设和都是到的关系，下列关系式中正确的有：,(,),-1,-1,-1,(,),-1,-1,-1,(,),-1,-1,-1,(,),-1,-1,-1,三、计算与作图,1.,若集合,=1,2,3,4,5,上的等价关系,=,，求商集,/,解：,/,=1,2,3,4,5,2.,为集合,=1,2,3,4,5,上的等价关系，已知商集,/,=1,2,3,4,5,，求,R,解：,=,A,3.,设,=3,6,9,15,54,90,135,180,，为自然数的整除关系。画出,的,asse,图，并求,6,15,90,的上、下确界。,3,6,9,15,54,90,135,180,6,15,90,的上确界：,90,下确界：,3,四、证明题,设,R,是集合,A,上的关系。证明：,R,是偏序关系，,iff R,-1,R=I,A,且,=rt(,),。,设,R,是集合,A,上的关系。证明：,R,是拟序关系，,iff R,-1,R=,且,=t(,),。,函数习题课,一、多项选择,(1,2,3)1.,函数,f,：,，,f()=,是,入射 满射 双射 以上答案都不对,(2 )2.,函数,f,：,，,f()=(x+y)/2,是,入射 满射 双射 以上答案都不对,(1 )3.,设,=a,b,为字母表，则,f,：,*,，,f(x)=axb,是,入射 满射 双射 以上答案都不对,(1 )4.,函数,f,：,0,1 0,1,，,f(x)=x/2+1/4,是,入射 满射 双射 以上答案都不对,(1 )5.,从,0,1,2,到,a,b,c,d,的二元关系,R,：,a,b,c,b,是,函数 入射 满射 双射 以上答案都不对,(4,5)6.,若,f,、,g,是上的函数且,gf,是双射，则,f,和,g,都是双射 ,f,为满射 ,g,为入射 ,f,有左逆 ,g,有右逆,二、填空,1.,若,A=a,b,，,B=1,2,，则,B,A,=,。,2.,用,表示字母表,=a,b,上的空串，定义,f,：,*,如下：,x*f(x)=axb,则,f(,a,b)=,ab,aab,abb,。,3.,用,表示字母表,=a,b,上的空串，定义,f,：,*,如下：,x*f(x)=axb,则,f(,a,b,)=aab,abb,ab,。,设,1,2,4,是全集,U,1,2,3,4,5,的子集，则的特征函数,A,。,三、计算,1.,设,a,b,1,2,3,4,，,f,是到的函数，试找出,f,的所有左逆和右逆,(,如果存在的话,),。,解：,f,是单射，有,4,个左逆，无右逆,g,1,=,g,2,=,g,3,=,g,4,=,2.,设,1,2,3,4,5,a,b,，,f,是到的函数，试找出,f,的所有左逆和右逆,(,如果存在的话,),。,解：,f,是满射，有,6,个右逆，无左逆,h,1,=,h,2,=,h,3,=,h,4,=,h,5,=,h,6,=,四、证明,若,f,是,A,到,B,的函数，其中,A,和,B,都是非空有限集，且,|,A,|=|,B,|,，那么：,f,是一个入射,iff f,是一个满射,证明：必要性,若,f,是一个入射，则,|,A,|=|,f,(,A,)|=|,B,|,又,f,(,A,),B,且,B,是有限集，所以,f,(,A,)=,B,即,f,是满射,充分性,若,f,是一个满射，则,f,(,A,)=,B,于是,|,A,|=|,B,|=|,f,(,A,)|,因为,A,是有限集，所以,f,是入射,