离散数学课后习题答案 VIP专享VIP免费

离散数学课后习题答案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-...