离散数学习题答案.doc

习题1：1. 解 （1）{2，3，5，7，11，13，17，19} （2）{x|x=20*k,k是自然数} （3）{2，-1}2. 解 （1）{2，4} （2）{1，2，3，4，5} （3）{1，3} （4）{1，3，5}3. 解 （1）{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} （2）f （3）全体自然数 （4）{0，2，4，6，8，10，12，14，16，18，20} （5）1，3，5，7，9，11，13，15，17，19}4. 解 （1）正确 （2）正确 （3）错误 （4）正确5. 解 （1）A={1}，B={{1}}，C={{1}} （2）A={1}，B={{1}}，C={{{1}}}6. 解 （1）正确由子集的定义 （2） 不一定如：A={1}，B={{1}}，C={{1}} （3）不一定如：A={1}，B={1，2}，C={{1，2}} （4）不一定。

如：A={1}，B={1，2}，C={{1，2}}7. 解 A={1，2}，B={1}，C={2}，有，但是成立 A={1，2}，B={1}，C={1}，有，但是成立8. 解 （1）f （2）{f} （3）{{f}} （4）{f，{f}}9. 解 （1）{1,2,3,4,5,6,7,8,9} （2）{0,1,2,3,4,5,6,7,8,9,10} （3）{0,3,6,7,8,9}10. 解 33311. 解 2512. 解（1）454 （2）124 （3）22013. 解 （1）{f} （2）{f，{a}} （3）{f，{f}，{a}，{f,a}} （4）{f，{f}，{{f}}，{{f},f}} （5）{f，{{f}}，{f}，{a}，{{f},f}，{{f},a}，{f,a}，{{f},f,a}}14. 证明：假设B¹C，则至少存在一元素xÎB且xÏC (1) 若xÏA，因为xÎB，所以xÎAÅB；因为xÏC，所以xÏ AÅC，则AÅB¹ AÅC，与已知条件AÅB= AÅC矛盾。

(2) 若xÎ A，因为xÎB，所以xÏAÅB；因为xÏC，所以xÎAÅC，则AÅB¹ AÅC，与已知条件AÅB= AÅC矛盾由(1)，(2)可知，假设不成立，因此B=C成立15. 证明： （1）左边=（AIB’）IC’=AIB’ IC’=AI(B’ IC’)=AI(BUC)’=A- BUC=右边. （2）左边=(AUB) IC’=( AU C’) I(B UC’)=(A-C) I(B-C) (3) 左边=A I( BUC)’=AIB’ IC’=( AIB’) I(AIC’)=(A-B) I(A-C)16. 证明：(1)反证法，假设B¹C, 则至少存在一元素xÎB且xÏC 若xÏA，因为xÎB，所以xÎA U B；因为xÏC，所以xÏ AUC，则AUB¹ AUC，与已知条件AUB= AUC矛盾 若xÎ A，因为xÎB，所以xÎ A’ U B；因为xÏC，所以xÏ A’UC，则A’ U B ¹ A’UC，与已知条件A’ U B = A’UC矛盾 所以，假设不成立，因此B=C成立 （2）因为A U B = AUC，A I B = AIC，所以A U B - A I B = AUC- AIC，即A Å B = AÅC，由第14题可得，B=C。

习题二：1. 原题改为：设，，计算P(A),P(B),A´B,P(A)´P(B)解P(A)={ f,{1},{2},{1,2}}; P(B)={ f,{a},{b},{a,b}}; A´B={(1,a),(1,b),(2,a),(2,b)};P(A)´P(B)={(f,f),(f,{a}),(f,{b}),(f,{a,b}),({1},f),({1},{a}),({1},{b}),({1},{a,b}), ({2},f),({2},{a}),({2},{b}),({2},{a,b}),({1,2},f),({1,2},{a}),({1,2},{b}),({1,2},{a,b})}2. 略3. 解 （1）成立 （2）不一定成立反例：A={1，2}，B={2}，C={a，b}，D={b}（3）不一定成立反例：A={1，2}，B={2}，C={a，b}，D={b}（4）不一定成立反例：A={1}，B={2}，C={a }，D={b}4. 解 f，{(1,3)}, {(2,3)}, {(1,3),(2,3)}5．解IA={(1,1),(2,2),(3,3)} UA={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}6. 解（1） （2）略 （3）domR={1,2,3}; ranR={a,b,c}7. 解RÈS={(1,a),(1,b),(1,c),(2,a),(2,c),(3,a),(3,b)}R∩S={(1,a),(2,c),(3,a)}R-S={(1,b)}R-1={(a,1),(b,1),(c,2),(a,3)}8. 解 R.S={(a,a),(b,b),(b,d)} S.R={(a,a),(a,b),(b,a),(b,b),(c,c)} R-1.S-1={(a,a),(a,b),(b,a),(b,b),(c,c)} S-1.R-1={(a,a),(b,b),(d,b)}9. 解 R={(a,a),(b,b),(c,c)}10. 解 (1) R={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c)} (2) R={(a,b),(b,a)} (3) R={(a,b)}11. 解 设集合A={1,2,3,4,5}（1）正确。

（2）不成立反例：R={(1,2)},S={(2,1)} （3）不成立反例：R={(1,2),(2,1)},S={(2,3),(3,2)} （4）不成立反例：R={(1,2),(3,4)},S={(2,3),(4,5)}12. 解 r(R)={(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)} s(R)={(a,b),(b,a),(b,c),(c,b),(c,d),(d,c)} t(R)={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}13. 证明：直接利用闭包的构造式即可得证14.解 等价关系是{(a,a),(b,b),(c,c),(d,d),(a,c),(c,a),(b,d),(d,b)}15.证明:必要性： R是一个等价关系，则当(a,b)ÎR，(a,c)ÎR必有(b,c)ÎR 因为R对称，所以当(a,b)ÎR时，有(b,a)ÎR， 因为R传递，所以当(b,a)ÎR，(a,c)ÎR时有(b,c)ÎR充分性：R是A上的一个自反关系，当(a,b)ÎR，(a,c)ÎR必有(b,c)ÎR，证明R是等价关系。

自反:条件已知；对称:若(a,b)ÎR,因为R自反,故(a,a)ÎR, 现在(a,b)ÎR,(a,a)ÎR,则根据条件(b,a)ÎR；传递: 若(a,b)ÎR,(b,c)ÎR 因为(a,b)ÎR,(b,c)ÎR, 而R对称,所以(b,a)ÎR, 现在(b,a)ÎR,(b,c)ÎR, 所以根据条件有(a,c)ÎR16. 解 1517. 解 A/R={{a,b},{c},{d}}18. 解 R={(a,a),(b,b),(c,c),(d,d),(b,c),(c,b)}65432119. 解 最大元是e，最小元是a，极大元是e，极小元是a20. 解 21. 是全序、良序习题六：1. 解 （1）不是命题 （2）是命题，（看具体日期确定） （3）是命题，（看具体情况） （4）若进行的布尔运算，则是真命题；若十进制运算则是假命题 （5）不是命题 （6）是真命题 （7）是真命题 （8）不是命题 （9）是命题目前不能知道真值 （10）是命题变元根据x，y的取值确定真值 （11）不是命题2. 解 （1）P：付出劳动；Q：有收获。

则命题符号化为：ØP®ØQ （2）P：今天下雨；Q：我去看电影 则命题符号化为：ØP®Q （3）P：a是奇数；Q：b是奇数；R：a与b的和是偶数 则命题符号化为：PÙQ®R （4）P：小明学习好；Q：小明乐于助人 则命题符号化为：PÙQ （5）P：小明骑自行车；Q：小明听音乐 则命题符号化为：PÙQ （6）P：今天是周二；Q：我准备下周开会的材料 则命题符号化为：PÙQ3. 解(1) Øp®Øq(2) Øp®r(3) Øp®rÅq4. 解 （1）可满足式 （2）可满足式 （3）可满足式 （4）可满足式 （5）重言式5. 证明 （1）左边ÛØPÚØQÚPÛ PÚ(ØPÚØQ) ÛØP®(P®ØQ) Û右边 （2）左边ÛØ(ØPÚQ) Û PÙØQ Û右边 (3) 左边Û PÚ(ØPÚØQ) ÛØPÚ(ØQÚ P) Û P®( Q ® P) Û右边 (4) 右边Û(ØPÚR) Ú(ØQÚR) ÛØPÚØQÚRÛØ(PÙQ) ÚRÛ(PÙQ) ®R Û左边6. 解 此题答案不唯一。

（1）合取范式与析取范式都可以是PÚQ （2）原式是重言式合取范式与析取范式都可以是1 （3）合取范式可以是（ØPÚQ）Ù (PÚØQ) 析取范式可以是（ØPÙØQ）Ú (PÙQ) （4）原式是重言式合取范式与析取范式都可以是17. 解 （1）主析取范式：(ØPÙQ) Ú( PÙQ) 主合取范式：（PÚQ）Ù（ØPÚQ） (2) 主析取范式：(ØPÙØQÙØR) Ú (ØPÙØQÙR) Ú (ØPÙØQÙØR) Ú (ØPÙQÙR) Ú (PÙØQÙØR) Ú (PÙØQÙR) Ú (PÙQÙØR) Ú (PÙQÙR) 主合取范式：空 （3）主析取范式：（PÙØQ）Ú（PÙQ） 主合取范式：（PÚQ）Ù（PÚØQ） （4）主析取范式：(ØPÙØQÙØR) Ú (ØPÙØQÙR) Ú (ØPÙØQÙØR) Ú (ØPÙQÙ。