离散数学课后习题答案

1.3.1习题1.1解答1设S={2，a，{3}，4}，R={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错的？{a}S,{a}R,{a,4,{3}}S,{{a},1,3,4}R,R=S,{a}S,{a}R,R,{{a}}RE,{}S,R,{{3},4}。解：{a}S，{a}R，{a，4，{3}}S，{{a}，1，3，4}R，R=S，{a}S，{a}R，R，{{a}}RE，{}S，R，{{3}，4}2写出下面集合的幂集合{a，{b}}，{1，}，{X，Y，Z}解：设A={a，{b}}，则(A)={，{a}，{{b}}，{a，{b}}}；设B={1，}，则(B)={，{1}，{}，{1，}}；设C={X，Y，Z}，则(C)={，{X}，{Y}，{Z}，{X，Y}，{X，Z}，{Y，Z}，{X，Y，Z}}；3对任意集合A，B，证明：(1)AB当且仅当(A)(B)；(2)(A)(B)(AB)；(3)(A)(B)=(AB)；(4)(A-B)((A)-(B)){}。举例说明：(A)∪(B)≠(A∪B)证明：(1)证明：必要性，任取x(A)，则xA。由于AB，故xB，从而x(B)，于是(A)(B)。充分性，任取xA，知{x}A，于是有{x}(A)。由于(A)(B)，故{x}(B)，由此知xB，也就是AB。（2）证明：任取X(A)∪(B)，则X(A)或X(B)∴XA或XB∴X(A∪B)∴X(A∪B)所以(A)∪(B)(A∪B)（3）证明：先证(A)∩(B)(A∩B)任取X(A)∩(B)，则X(A)且X(B)∴XA且XB∴XA∩B∴X(A∩B)所以(A)∩(B)(A∩B)再证(A∩B)(A)∩(B)任取Y(A∩B)，则YA∩B∴YA且YB∴Y(A)且Y(B)∴Y(A)∩(B)所以(A∩B)(A)∩(B)故(A)∩(B)=(A∩B)得证。举例：A={1}，B={a}则(A)={，{1}}，(B)={，{a}}(A)∪(B)={，{1}，{a}}A∪B={1，a}(A∪B)={，{1}，{a}，{1，a}}可见{1，a}(A∪B)，{1，a}(A)∪(B)所以(A)∪(B)≠(A∪B)(4)对任意的集合x，若x=，则x(A-B)且x((A)-(B))∪{}。若x，则x(A-B)当且仅当x(A-B)当且仅当xAx⊈B当且仅当x(A)x(B)当且仅当x((A)-(B))。综上所述，可知(A-B)((A)-(B)){}。4.设A,B,C为任意三个集合，下列各式对否？并证明你的结论。（1）若AB且BC，则AC；（2）若AB且BC，则AC；（3）若AB且BC，则AC；（4）若AB且BC，则AC。解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不正确，举一个反例即可。1.3.1习题1.2解答3.R，S是集合A上的两个关系。试证明下列等式：（1）(R•S)-1=S-1•R-1（2）(R-1)-1=R（3）(R∪S)-1=R-1∪S-1（4）(R∩S)-1=R-1∩S-1证明：（1）先证(R•S)-1S-1•R-1，对任意(x，y)(R•S)-1，则(y，x)(R•S)，则存在aA，满足(y，a)R且(a，x)S，那么(x，a)S-1且(a，y)R-1，所以(x，y)S-1•R-1，因此(R•S)-1S-1•R-1；再证S-1•R-1(R•S)-1，对任意(x，y)S-1•R-1，则存在aA，满足(x，a)S-1且(a，y)R-1，所以(y，a)R且(a，x)S，所以(y，x)(R•S)，所以(x，y)(R•S)-1，因此S-1•R-1(R•S)-1。（2）先证(R-1)-1R，对任意(x，y)(R-1)-1，则(y，x)R-1，则(x，y)R，所以(R-1)-1R；再证R(R-1)-1，对任意(x，y)R，则(y，x)R-1，则(x，y)(R-1)-1，所以R(R-1)-1。故(R-1)-1=R得证。（3）先证(R∪S)-1R-1∪S-1，对任意(x，y)(R∪S)-1，则(y，x)R∪S，则(y，x)R或(y，x)S，则(x，y)R-1或者(x，y)S-1，所以(x，y)R-1∪S-1，所以(R∪S)-1R-1∪S-1；再证R-1∪S-1(R∪S)-1，对任意(x，y)R-1∪S-1，则(x，y)R-1或者(x，y)S-1，则(y，x)R或(y，x)S，所以(y，x)R∪S，所以(x，y)(R∪S)-1，所以R-1∪S-1(R∪S)-1。故(R∪S)-1=R-1∪S-1得证。（4）先证(R∩S)-1R-1∩S-1，对任意(x，y)(R∩S)-1，则(y，x)R∩S，则(y，x)R且(y，x)S，则(x，y)R-1且(x，y)S-1，所以(x，y)R-1∩S-1，所以(R∩S)-1R-1∩S-1；再证R-1∩S-1(R∩S)-1，对任意(x，y)R-1∩S-1，则(x，y)R-1且(x，y)S-1，则(y，x)R且(y，x)S，所以(y，x)R∩S，所以(x，y)(R∩S)-1，所以R-1∩S-1(R∩S)-1。故(R∩S)-1=R-1∩S-1得证。1.3.3习题1.3解答2.将集合M中元素映射到自身的变换称为同一变换，记为I。设，是集合M上的两个变换，如果•=•=I，则，是1–1变换，并且=-1。证明：（1）先证、分别是单映射。对任意x1，x2M，如果(x1)=(x2)，则有x1=I(x1)=(•)(x1)=((x1))=((x2))=(•)(x2)=I(x2)=x2所以是单映射。同理可证是单映射。（2）再证、分别是满射。因为和都是M到M的单映射，所以有(M)M，(M)M，于是M=I(M)=(•)(M)=((M))(M)，同理A=I(M)=(•)(M)=((M))(M)，所以(M)=M，(M)=M，即、是满射。（3）往证=-1。由是1–1映射，故存在-1，对任意xM，-1(x)=I(-1(x))=(•)(-1(x))=((-1(x))=(x)故=-1。习题2.1解答2.说出下述每一命题的逆命题和逆否命题：（1）如果天下雨，我将不去。（2）仅当你去我将逗留。（3）如果n是大于2的正整数，则方程xn+yn=zn无正整数解。（4）如果我不获得更多帮助，我不能完成这个任务。解：（1）逆命题为：如果我不去，那么天下雨；逆否命题为：如果我去，那么天不下雨。（2）逆命题为：仅当我将逗留你去；逆否命题为：你不去我将不逗留。（3）逆命题为：如果方程xn+yn=zn无正整数解，则n是大于2的正整数；逆否命题为：如果方程xn+yn=zn有正整数解，则n是不大于2的正整数。(4)逆命题为：我不能完成这个任务，因为我没有获得更多帮助。逆否命题：如果我完成了任务，则我获得了更多帮助。3.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)解：a)令G=(P(QR))((PQ)(RS))则：TI(G)=(1(10))((11)(00))=00=1b)令G=((PQ)R)(((PQ)R)S)则：TI(G)=((11)0)(((11)0)0)=10=1c)令G=((PQ)R)((QP)(RS))=((PQ)R)(((QP)(PQ))(RS))=(PQR)((QP)(PQ)(RS))则：TI(G)=(110)((11)(11)(00))=11=1d)令G=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=((P(Q(RP)))(QS))((QS)(P(Q(RP))))=(P(Q(RP)))(QS))((QS)(P(Q(RP))))TI(G)=(1(1(01)))(10))((10)(1(1(01))))=11=1习题2.2解答3.对P和Q的所有值，证明PQ与PQ有同样的真值。证明（PQ）（PQ）是恒真的。解：对PQ的任意解释I，若I使PQ为真，则I使P为假或P和Q同时为真，若I使P为假，则使P，此时PQ为真，若I使P和Q同时为真，则Q为真，此时PQ为真，也就是说PQ为真时PQ为真。若I使PQ为假，则I使P为真Q为假，此时PQ为假，也就是说PQ为假时PQ为假。综上知PQ与PQ同真同假，由定义知（PQ）（PQ）是恒真的。习题2.3解答2设S={G1，…，Gn}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。提示：考虑G1…Gn的主合取范式。解：任设一公式G’为从S出发演绎出来的公式。则可知G’为G=G1…Gn的一个逻辑结果。而G有唯一一个与其等价的主合取范式，设为G’’。可设G’’共有m个极大项，则可以知道令G’’取1的解释使这m个极大项也取1。则从S出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组成，共有2m个，其中包括恒真公式这里用1表示。设H为由若干极大项构成的合取公式。现在证明：1)S=H，即G=H。从定义出发，设有一解释I使G=G1…Gn取1值，必使G的主合取范式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组成的公式H也取1值，则有S=H。2)任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的极大项都在G的主合取范式G”中。反证法：若不然，假设H中有一个极大项mk不在G的主合取范式中。则取使mk为0的解释I，可有解释I使H取0值。而I使所有不等于mk的极大项都为1，则可有G的主合取范式G’’在I下取1值，即G在I下取1值，这与G=H矛盾。5.设G1，…，Gn是公式。证明：从{G1，…，Gn}出发可演绎出公式G的充要条件是从{G1，…，Gn，G}出发可演绎出公式(RR)。其中R为任意公式。证明：充分性，即{G1，…，Gn，G}=(RR)，可有G1…GnG=(RR)，因(RR)恒假，则G1…GnG恒假。那么有（G1…Gn）G恒真，即（G1…Gn）G恒真，则有(G1…Gn)=G，因此有{G1，…，Gn}蕴涵G。必要性，即已知：{G1，…，Gn}=G，有（G1…Gn）G恒真，即（G1…Gn）G恒真，那么对上式取非有G1…GnG恒假，也就是(G1…GnG)(RR)恒真，其中R为任意一个公式，则有(G1…GnG)=(RR)，即从{G1，…，Gn，G}出发可演绎出公式(RR)。命题得证。习题2.4解答3.证明：命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其