大连理工大学软件学院离散数学习题答案

目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc387312710"第一章命题逻辑PAGEREF_Toc387312710\h2HYPERLINK\l"_Toc387312711"第二章谓词逻辑PAGEREF_Toc387312711\h9HYPERLINK\l"_Toc387312712"第三章集合论习题答案PAGEREF_Toc387312712\h13HYPERLINK\l"_Toc387312713"第四章二元关系习题答案PAGEREF_Toc387312713\h21HYPERLINK\l"_Toc387312714"第五章函数习题答案PAGEREF_Toc387312714\h42HYPERLINK\l"_Toc387312715"第六章代数系统习题答案PAGEREF_Toc387312715\h51HYPERLINK\l"_Toc387312716"第七章群与环习题答案PAGEREF_Toc387312716\h57HYPERLINK\l"_Toc387312717"第八章格与布尔代数习题答案PAGEREF_Toc387312717\h66HYPERLINK\l"_Toc387312718"第九章图的基本概念及其矩阵 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示PAGEREF_Toc387312718\h71HYPERLINK\l"_Toc387312719"第十章几种图的介绍PAGEREF_Toc387312719\h82HYPERLINK\l"_Toc387312720"第十一章树PAGEREF_Toc387312720\h90命题逻辑（1）不是命题；（2）不是命题；（3）不是命题；（4）是命题；（5）是命题；（1）并非大连的每条街都临海；（2）2不是一个偶数或者8不是一个奇数；（3）2不是偶数并且-3不是负数；逆命题：如果我去公园，那么天不下雨。否命题：如果天下雨，我将不去公园。逆否命题：如果我不去公园，那么天下雨。逆命题：如果我逗留，那么你去。否命题：如果你不去，那么我不逗留。逆否命题：如果我不逗留，那么你不去。逆命题：如果方程无整数解，那么n是大于2的正整数。否命题：如果n不是大于2的正整数，那么方程有整数解。逆否命题：如果方程有整数解，那么n不是大于2的正整数。逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。否命题：如果我获得更多的帮助，则我能完成这项任务。逆否命题：如果我能完成这项任务，则我获得更多的帮助。（1）T；（2）T；（3）T；（4）F；（1）PQR00010011010101111000101111011111（3）PQR00000010010101111001101111011110（2）（4）略P:他聪明；Q:他用功；命题：P∧Q。P:天气好；Q:我骑车上班；命题：Q→P。P:老李是球迷；Q:小李是球迷；命题：P∨Q。P:休息好；Q:身体好；命题：Q→P。证明：PQP→QQ→PPQ00111011001001011111真值表：xyz(x∧y)∧zx∧(y∧z)(x∨y)∨zx∨（y∨z）0000000001001101000110110011100001110100111111111xyz(x→y)→zx→(y→z)(xy)zx（yz）0000100001111101001110111100100111110111001111111可得：∧，∨，是可结合的。（1）（P∧Q）→R；（2）┓P；（3）（┓P∧┓Q）→┓R不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。本题可用真值表求解：（4）得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。（8）得真值表如下：PQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他小题可用同样的方法求解。（2）原式┓((P∨Q)∧R)∨P∨R┓(P∨Q)∨┓R∨P∨R┓(P∨Q)∨P∨TT（4）原式P∨（┓（┓Q∧R）∨P）P∨（Q∨┓R∨P）P∨Q∨┓R┓（┓P∧┓Q∧R）第（1）、（3）、（5）小题方法相同，解答略。（3）原式┓P∧┓Q∧（R∨P）（┓P∧┓Q∧R）∨（┓P∧┓Q∧P）（┓P∧┓Q∧R）∨F┓（P∨Q∨┓R）第（1）、（2）小题方法相同，解答略。（2）左式（P∨（┓Q∧Q））∧（┓P∨┓Q）（P∨F）∧（┓P∨┓Q）（P∧┓P）∨（P∧┓Q）F∨（P∧┓Q）P∧┓Q右式P∧┓Q故：左式右式，证明完毕。根据对偶式定义，该式的对偶式为：（P∧┓Q）∨（P∧Q）∨（┓P∧┓Q）第（1）、（3）小题方法相同，解答略。（1）原式（P∧（┓P∨Q））→Q（（P∧┓P）∨（P∧Q））→Q（F∨（P∧Q））→Q（┓P∨┓Q）∨Q┓P∨TT（3）原式（（┓P∨Q）∧（┓Q∨R））→（┓P∨R）（P∧┓Q）∨（Q∧┓R）∨（┓P∨R）（（P∧┓Q）∨Q）∧（（P∧┓Q）∨┓R）∨（┓P∨R）（P∨Q）∧（┓Q∨Q）∧（P∨┓R）∧（┓Q∨┓R）∨（┓P∨R）（P∨（Q∧┓R））∧（┓Q∨┓R）∨（┓P∨R）（（P∨（Q∧┓R））∧┓Q）∨（（P∨（Q∧┓R））∧┓R）∨（┓P∨R）（P∧┓Q）∨（Q∧┓R∧┓Q）∨（P∧┓R）∨（Q∧┓R∧┓R）∨（┓P∨R）（P∧┓Q）∨（P∧┓R）∨（Q∧┓R）∨┓（P∧┓R）（P∧┓Q）∨（Q∧┓R）∨TT第（2）、（4）小题方法相同，解答略。（1）证明：假设P∧Q为真，则P为真且Q为真，则P→Q为真。所以：P∧QP→Q。（3）证明：右侧┓P∨Q，假设┓P∨Q为假，则P为真且Q为假，则P→Q为假。所以：P→QP→P∧Q。（5）证明：假设Q→R为假，则Q为真且R为假，则左侧为假。所以：（P∨┓P→Q）→（P∨┓P→R）Q→R。第（2）、（4）、（6）小题方法相同，解答略。（1）代入可得：（（（P→Q）→（（P→Q）→R））→（P→Q））→（P→Q）（2）代入可得：（（Q→┓P）→（┓P→Q））（1）主析取范式：原式（P∧Q）∨（P∧┓Q）m2∨m3∑（2,3）主合取范式：原式（（P∧Q）∨P）∧（（P∧Q）∨┓Q）P∧（P∨Q）∧（P∨┓Q）∧TP∨（Q∧┓Q）M0∧M1∏（0,1）（3）主析取范式：原式（（（┓P∨Q）∧┓P）∨（（┓P∨Q）∧R））∧（（（P∨┓Q）∧P）∨（（P∨┓Q）∧┓R））（┓P∨（┓P∧Q）∨（┓P∧R）∨（Q∧R））∧（（P∧Q）∨（P∧┓Q）∨（P∧┓R）∨（┓Q∧┓R））（（┓P∧┓Q）∨（┓P∧Q）∨（┓P∧R）∨（Q∧R））∧（（P∧Q）∨（P∧┓Q）∨（P∧┓R）∨（┓Q∧┓R））（（┓P∧（┓Q∨R））∨（Q∧（┓P∨R）））∧（（P∧（Q∨┓R）∨（┓Q∧（P∨┓R）））F∨（Q∧（┓P∨R）∧P∧（Q∨┓R））∨（┓P∧（┓Q∨R）∧┓Q∧（P∨┓R））∨F（P∧Q∧R∧Q）∨（P∧Q∧R∧┓R）∨（┓P∧┓Q∧┓R）∨（┓P∧┓R∧R）（P∧Q∧R）∨（┓P∧┓Q∧┓R）m0∨m7∑（0,7）主合取范式：原式（┓P∨（Q∧R））∧（P∨（┓Q∧┓R））（┓P∨Q）∧（┓P∨R）∧（P∨┓Q）∧（P∨┓R）（┓P∨Q）∨（R∧┓R）∧（┓P∨R）∨（Q∧┓Q）∧（P∨┓Q）∨（R∧┓R）∧（P∨┓R）∨（Q∧┓Q）（┓P∨Q∨R）∧（┓P∨Q∨┓R）∧（┓P∨Q∨R）∧（┓P∨┓Q∨R）∧（P∨┓Q∨R）∧（P∨┓Q∨┓R）∧（P∨Q∨┓R）∧（P∨┓Q∨┓R）M1∧M2∧M3∧M4∧M5∧M6∏（1,2,3,4,5,6）第（2）、（4）小题方法相同，解答略。（1）证明：左侧（┓P∨Q）∧（┓P∨R）（┓P∨Q∨R）∧（┓P∨Q∨┓R）∧（┓P∨Q∨R）∧（┓P∨┓Q∨R）∏（4,5,6）右侧┓P∨（Q∧R）…∏（4,5,6）左侧右侧，得证。（3）证明：左侧┓（┓P∨Q）∨（P∧Q）（P∧┓Q）∨（P∧Q）∑（2,3）右侧（P∨Q）∧（P∨┓Q）（P∧P）∨（P∧┓Q）∨（P∧Q）∨（Q∧┓Q）（P∧┓Q）∨（P∧Q）∑（2,3）左侧右侧，得证。第（2）、（4）小题方法相同，解答略。对于A,B,C,D,E5个变元的所有真值指派，推出前提A↔B，B↔（C∧D），C↔（A∨E），A∨E和结论A∧E的值，得到真值表。当真值表中各前提的真值都为1时，若结论也为1，则结论有效，否则结论无效。（1）采用真值表证明：PQP→QP→（P∧Q）0011011110001111根据真值表可看出，当前提为1时，结论也为1，则结论有效。（3）采用推理方法证明：P∧Q为真，可得P为真且Q为真，又P→（Q→R）为真且P、Q为真，得R也为真。则结论有效。第（2）、（4）小题方法相同，解答略。（1）证明：假设公式全部同时成立，由┓S为真得到S为假，由┓P→S为真，得P为真，由P↔Q为真得到Q为真，由Q→R为真得到R为真，由┓R∨S为真得到S为真。这与前面“S为假”矛盾，则公式不能同时成立。（2）证明：假设公式全部同时成立，由┓S为真得到S为假，由┓R∨S为真得到R为假，由R∨M为真得到M为真，由┓M为真得到M为假，矛盾。则公式不能同时成立。首先符号化：P:大连获得冠军；Q:北京获得亚军；R:上海获得亚军；S:广州获得亚军。即求公式：P→（Q∨R），R→┓P，S→┓Q，P┓S是否成立。{1}（1）PP规则{2}（2）R→┓PP规则{1,2}（3）┓RT规则{4}（4）P→（Q∨R）P规则{1,2,4}（5）QT规则{6}（6）S→┓QP规则{1,2,4,6}（7）┓ST规则（1）证明：（1）┓RP规则（2）┓Q∨RP规则（3）┓QT规则（1）（2）（4）┓（P∧┓Q）P规则（5）┓PT规则（3）（4）（3）题目有误（5）证明：（1）PP规则（附件前提）（2）P→（P∧Q）P规则（3）P∧QT规则（1）（2）（4）QT规则（1）（3）（5）P→QCP规则第（2）、（4）小题方法相同，解答略。（1）证明：（1）┓┓PP规则（假设前提）（2）PT规则（1）（3）P→QP规则（4）QT规则（2）（3）（5）R→┓QP规则（6）┓RT规则（4）（5）（7）R∨SP规则（8）ST规则（6）（7）（9）S→┓QP规则（10）┓QT规则（8）（9）（11）Q∧┓QT规则（4）（10）（12）┓PF规则（1）（11）（2）证明：（1）┓RP规则（2）R∨SP规则（3）ST规则（1）（2）（4）S→┓QP规则（5）┓QT规则（3）（4）（6）P↔QP规则（7）┓PT规则（5）（6）（3）原式修改为：┓（P→Q）→┓（R∨S），（Q→P）∨┓R，RP↔Q证明：（1）RP规则（2）R∨ST规则（1）（3）┓（P→Q）→┓（R∨S）P规则（4）P→QT规则（2）（3）（5）（Q→P）∨┓RP规则（6）Q→PT规则（1）（5）（7）（P→Q）∧（Q→P）T规则（4）（6）P↔QT规则（7）第二章谓词逻辑（1）S(x)：x聪明；L(x)：x好学；a：表示小明，命题：S(a)∧L(a)。（2）S(x)：x是素数；G(x,y)：x大于y，命题：(∀x)(S(x)→(∃y)(S(y)∧G(y,x)))（3）U(x)：x是大学生；S(x)：x能成为科学家，命题：(∃x)(U(x)⋀¬S(x))（4）N(x)：x是自然数；A(x)：x是奇数；B(x)：x是偶数，命题：(∀x)(N(x)→(A(x)∨B(x)))（5）P(x)：x是诗人；T(x,y)：x游览y；V(x)：x是名山大川；a：表示李白命题：(∀x)(Pa∧Vx⋀Ta,x)（1）约束变元：x，辖域：P(x)→Q(x)和R(x,y)；自由变元：y。（2）约束变元：Px∨Qy中的x,y和R(x)⋀Sz中的z；自由变元：R(x)⋀Sz中的x。（3）约束变元：x,y，辖域：P(x,y)⋀Qy,z；自由变元：z。参考教材2.3部分。（1）证明：（1）(x)¬B(x)P（2）¬B(x)US（1）（3）(x)(¬A(x)→B(x))P（4）¬A(x)→B(x)US（3）（5）A(x)T（2）（4）（6）(x)A(x)EG（5）（3）证明：由于：(x)(A(x)→B(x))(x)A(x)→(x)B(x)；(x)(C(x)→¬B(x))(x)C(x)→(x)¬B(x)；(x)(C(x)→¬A(x))(x)C(x)→(x)¬A(x)即证：(x)A(x)→(x)B(x)，(x)C(x)→(x)¬B(x)(x)C(x)→(x)¬A(x)（1）(x)C(x)P（附加）（2）C(x)US（1）（3）(x)C(x)→(x)¬B(x)P（4）C(x)→¬B(x)US（3）（5）¬B(x)T（2）（4）（6）(x)A(x)→(x)B(x)P（7）A(x)→B(x)US（6）（8）¬A(x)T（5）（7）（9）(x)¬A(x)UG（8）（10）(x)C(x)→(x)¬A(x)CP（1）（9）第（2）、（4）小题方法相同，解答略。（1）证明：（1）(x)P(x)P（附加）（2）P(x)US（1）（3）(x)(P(x)→Q(x))P（4）P(x)→Q(x)US（3）（5）Q(x)T（2）（4）（6）(x)Q(x)UG（5）（7）(x)P(x)→(x)Q(x)CP（1）（6）（2）证明：由于：(x)P(x)∨(x)Q(x)(x)¬P(x)→(x)Q(x)即证：(x)(P(x)∨Q(x))(x)¬P(x)→(x)Q(x)（1）(x)¬P(x)P（附加）（2）¬P(x)ES（1）（3）(x)(P(x)∨Q(x))P（4）P(x)∨Q(x)US（3）（5）Q(x)T（2）（4）（6）(x)Q(x)EG（5）（7）(x)¬P(x)→(x)Q(x)CP（1）（6）（1）W(x)：x喜欢步行；C(x)：x喜欢乘汽车；B(x)：x喜欢骑自行车；即需证：(x)(W(x)→¬C(x)),(x)(C(x)∨B(x)),(x)¬B(x)(x)¬W(x)证明：（1）(x)¬B(x)P（2）¬B(x)ES（1）（3）(x)(C(x)∨B(x))P（4）C(x)∨B(x)US（3）（5）C(x)T（2）（4）（6）(x)(W(x)→¬C(x))P（7）W(x)→¬C(x)US（6）（8）¬W(x)T（5）（7）（9）(x)¬W(x)EG（8）（3）F(x)：x是资深人士；S(x)：x是院士；P(x)：x是参事；C(x)：x是委员；a：张伟；即需证：(x)(F(x)→(S(x)∨P(x))),(x)(F(x)→C(x)),F(a)∧¬S(a)(x)(C(x)∧P(x))证明：（1）(x)(F(x)→C(x))P（2）F(a)→C(a)US（1）（3）F(a)∧¬S(a)P（4）F(a)T（3）（5）C(a)T（2）（4）（6）(x)(F(x)→(S(x)∨P(x)))P（7）F(a)→(S(a)∨P(a))US（6）（8）¬S(a)T（3）（9）P(a)T（4）（7）（8）（10）C(a)∧P(a)T（5）（9）（11）(x)(C(x)∧P(x))EG（10）第（2）、（4）小题方法相同，解答略。（d）是错误的。错误。第二行的y是泛指，第四行的y是特指。修改如下：（1）P（2），(1)（3）P（4），（3）（5）T，（2），（4）和（6），（5）（1）证明：（1）(x)P(x)P（2）P(a)ES（1）（3）(x)Q(x)P（4）Q(b)ES（3）（5）(x)P(x)→(x)((P(x)∨Q(x))→R(x))P（6）(x)((P(x)∨Q(x))→R(x))T（1）（5）（7）(P(a)∨Q(a))→R(a)US（6）（8）P(a)∨Q(a)T（2）（9）R(a)T（7）（8）（10）(P(b)∨Q(b))→R(b)US（6）（11）P(b)∨Q(b)T（4）（12）R(b)T（10）（11）（13）R(a)∧R(b)T（9）（12）（14）(y)(R(a)∧R(y))EG（13）（15）(x)(y)(R(x)∧R(y))EG（14）（2）证明：（1）(x)P(x)→(x)Q(x)P（假设）（2）¬(x)P(x)∨(x)Q(x)T（1）（3）(x)¬P(x)∨(x)Q(x)T（2）（4）(x)(¬P(x)∨Q(x))T（3）（5）(x)(P(x)→Q(x))T（4）（1）原式(x)(¬P(x)∨(y)Q(y))(x)(y)(¬P(x)∨Q(y))（3）原式(x)(y)A(x,y)∨(x)(y)(B(x,y)∧(y)(A(x,y)→B(x,y)))(x)(y)A(x,y)∨(u)(v)(B(u,v)∧(z)(¬A(z,u)∨B(u,z)))(x)(y)(u)(v)(z)(A(x,y)∨(B(u,v)∧(¬A(z,u)∨B(u,z))))（2）解：前束析取范式：由于是基本和，因此前束合取范式与前束析取范式一样：（4）解：前束析取范式：前束合取范式：第三章集合论习题答案对应课本页数：P51-54写出下列集合的表达式。所有一元一次方程的解所组成的集合：答案：集合可表示为(2)在实数域中的因式集。答案：集合可表示为(3)直角坐标系中，单位圆内（不包括单位圆）的点集。答案：集合可表示为(4)极坐标系中单位圆外（不包括单位圆）的点集。答案：集合可表示为(5)能被5整除的整数集。答案：集合可表示为2.解：设戏剧、音乐、广告分配的时间分别为可表示为可表示为可表示为可表示为3.给出集合、和的例子，使得，而。解：4.确定下列命题是否为真。(1)该命题为真命题(2)该命题为假命题(3)该命题为真命题(4)该命题为真命题(5)该命题为真命题(6)该命题为真命题(7)该命题为真命题(8)该命题为假命题。5.，是可能的么，给予证明。解：可能。若，则且。6.(1)解：设则(2)解：设则(3)解：设则(4)解：设则(5)解：设则7.设，解：(1)，(2)，(3)，8.设某集合有101个元素，试问：(1)可构成多少个子集：2101(2)其中有多少个子集的元素为奇数：2100(3)是否会有102个元素的子集：不会9.解：把17化为二进制，是00010001，；把31化为二进制，是00011111，，编码为01000110，为，编码为10000001，为10.求A∪B，A∩B。解：11.解：12.解：(1)(2)(3)(4)13.证明对于所有集合A,B,C有，当且仅当。证明：充分性：由于所以，即充分性得证。必要性：由于所以所以必要性得证。14.证明对所有集合A,B，C，有：（1）证明：（2）证明：（3）证明：因此，15.确定下列各式的运算结果。解:16.假设A和B是E的子集，证明下列各式中每个关系式彼此等价。(1)证明：=1\*GB3①证明∼B⊆∼A。充分性：若，则若，那么必有。因此，若，则必有，即若x∈∼B，则有x∈∼A，即∼B⊆∼A；必要性：若∼B⊆∼A，则若x∈∼B，则有x∈∼A，即若，则必有。那么，若，那么必有，即；由以上两点可知：∼B⊆∼A。=2\*GB3②证明：A∪B=B充分性：若，那么有或。若，则由可知，必有，所以若，必有，即；若，那么必有，即，所以A∪B=B，充分性得证；必要性：因为A∪B=B，所以，对于任意的，必有，所以，必要性得证；由以上两点可知：A∪B=B=3\*GB3③证明：A∩B=A充分性：若，那么必有，即；若，那么由可知，必有，所以，即，所以，A∩B=A；必要性：因为A∩B=A，所以对于任意的，必有，，所以；由以上两点可知，A∩B=A。由以上三点可知，∼B⊆∼A⟺A∪B=B⟺A∩B=A。(2)=1\*GB3①证明:A⊆∼B充分性：因为，所以对于任意的，若，则必有，即x∈∼B，所以A⊆∼B；必要性：因为A⊆∼B，所以对于任意的，若，则必有x∈∼B，即，所以；由以上两点可知：A⊆∼B=2\*GB3②证明：B⊆∼A充分性：因为，所以对于任意的，若，则必有，即x∈∼A，所以B⊆∼A；必要性：因为B⊆∼A，所以对于任意的，若，则必有x∈∼A，即，所以；由以上两点可知：B⊆∼A.由上可知：A⊆∼B⟺B⊆∼A.(3)=1\*GB3①证明：A∪B=E⟺∼A⊆B充分性：因为A∪B=E，所以若，则必有，即若x∈∼A，则必有，所以∼A⊆B；必要性：因为A∪∼A=E，又∼A⊆B，必有A∪B=E；由以上两点可知：A∪B=E⟺∼A⊆B=2\*GB3②证明：A∪B=E⟺∼B⊆A充分性：因为A∪B=E，所以若，则必有，即若x∈∼B，则必有，所以∼B⊆A；必要性：因为B∪∼B=E，又∼B⊆A，必有A∪B=E；由以上两点可知：A∪B=E⟺∼B⊆A.由上可知：A∪B=E⟺∼A⊆B⟺∼B⊆A.。(4)证明：A=B⟺A⊕B=ϕ充分性：由于A=B，所以A∩∼B=ϕ,B∩∼A=ϕ所以A⊕B=A∩∼B∪B∩∼A=ϕ必要性：因为A⊕B=A∩∼B∪B∩∼A=ϕ所以A∩∼B=ϕ且B∩∼A=ϕ因为A∩∼B=ϕ，所以A⊆B又B∩∼A=ϕ，所以B⊆A所以A=B。由上可知：A=B⟺A⊕B=ϕ。17.化简下述集合公式。(1)结果：A∩B(2)结果：A-B(3)结果：A(4)结果：C∩（A∪B）18.设A,B,C是任意集合，分别求使得下述等式成立的充分必要条件。(1)B⊆A(2)B∩A=∅(3)B=A=∅(4)B=A(5)B=∅(6)B=A(7)解：由于，因此必有且。也就是并且。（8）解：由于，因此必有且。也就是并且。(9)解：因此，意味着(10)解：两种可能，第一种，即B=C；第二种，或者19.借助文氏图，考察下列命题的正确性。EB(1)CAE(2)AC20.设A,B,C为任意集合，是判断下面命题的真假。如果为真，给出证明，否则给出反例。21.设在10名青年中有5名是工人，7名是学时，其中兼具工人与学生双重身份的青年有三人，求既不是学生也不是工人的青年有多少？设A，B分别代表工人、学生，则：所以既不是学生也不是工人的青年有1人。22.求1到250之间能够被2,3,5,7中任何一个整除的整数的个数。设A=250∕2=125，B=250∕3=83，C=250∕5=50，D=250∕7=35则所求的答案表达式为A∪B∪C∪D。求解：A∪B∪C∪D=125+83+50+31–(41+25+17+16+11+7)+(8+5+3+2)-(1)=189;所以,这样的数共有189个。23.解：设A，B，C分别表示参加足球队、篮球队和棒球队的队员的集合即同时参加两个对的队员共有18个。24.解：设A，B，C分别表示读甲种、乙种、丙种杂志的学生的集合。(1)所以确定读两种杂志的学生的百分比为60%。(2)所以不读任何杂志的学生的百分比为30%。第四章二元关系习题答案对应于课本88-93页1.如果A={0,2}和B={1,2}，试求下列集合。（1）解：（2）解（3）解：2.解：表示在在笛卡尔坐标系中，且的矩形区域内的点集。3.（1）证明：任取,有由取值的任意性知，。（2）当且仅当才，才有证明：当时，，于是。当时，任取，可知，由知，于是得到。所以，。4.证明：必要性：若，；同理，若，；若，则显然有；必要性得证。充分性性：由于所以对于任意的,必有即若则必有；若，则必有，所以当时，；充分性得证。5.（1）解：任取,有选择A={1}，B={2}，C={a}，D={b}则因此该等式不成立。（2）解：任取,有选择A={1，2}，B={1}，C={a，b}，D={a}因此，该等式不成立。（3）解：设A={1，2}，B={2}，C={3，4}，D={4}则因此，该等式不成立。（4）解：取,有因此，该等式成立。（5）解：任取取,有因此，该等式成立。（6）存在集合A使得A⊆A×A；取A=∅，则该命题成立。（7）PA×PA=PA×A假设结合A有n个元素，则PA有2n个元素，则PA×PA共有22n个元素；则A×A有n2个元素，PA×A则有2n2个元素，显然两者元素数不一样，故命题不成立。6.设A=1,2,3,4，列出以下关系R。（1）R=x,yx,y∈A∧x+y≠2解：R=1,2，1,3，1,4，2,1，2,2，2,3，2,4，3,1，3,2，3,3，3,4，4,1，4,2，4,3，4,4（2）R=x,yx,y∈A∧x-y=1解：R=1,1，1,3，1,4，2,2，2,4，3,1，3,3，4,1，4,2，4,4（3）R=x,yx,y∈A∧x∕y∈A解：R=1,1，2,1，2,2，3,1，3,3，4,1，4,2，4,4（4）R=x,yx,y∈A∧y为素数解：R=1,2，1,3，2,2，2,3，3,2，3,3，4,2，4,37.列出集合A=2,3,4上的恒等关系IA和全域关系EA。解：IA=2,2，3,3，4,4；。EA=2,2，2,3，2,4，3,2，3,3，3,4，4,2，4,3，4,48.给出下列关系R的所有序偶。（1）解：（2）解：9.设和都是从到的二元关系，并且求、、、、、、、。解：fldR1-R2=fld1,2,3,3=1,2∪2,3=1,2,3R1∘R2=1,4,2,2R2∘R1=1,3,4,4R12=1,4,3,3R23=4,4,2,210.设集合A=1,2,3，问A上有多少种不同的二元关系。解：232=512种关系。11.设关系R=0，1，0，2，0，3，1，2，1，3，2，3，求R∘R，R-1，R1,2，R1,2解：R∘R=0,2，0,3，1,3R-1=1，0，2，0，3，0，2，1，3，1，3，2R1,2=1，2，1，3，2，3R1,2=2,312.设关系R=∅，∅，∅，∅，∅，求R-1，R2，R3，R∅，R∅,R|∅,R∅，R∅。解：R-1=∅，∅，∅，∅，∅R2=∅，∅，∅R3=∅R∅=∅，∅，∅R|∅=∅R|∅=∅，∅R∅=∅13.说明以下关系R具有那些性质并说明理由。（1）：反自反的、反对称的、可传递的；（2）：反自反的、对称的、不可传递的；（3）：自反、对称、可传递；（4）：自反、对称、可传递；14.设A是所有人的集合，定义A上的二元关系R1和R2，说明R1和R2具有哪些性质。解：R1具有的性质：反自反的、反对称的、可传递的；R2具有的性质：自反、对称、可传递；15.设和是集合X中的二元关系。试证或反证下列命题：（1）如果和是自反的，则也是自反的。（2）如果和是反自反的，则也是反自反的。（3）如果和是对称的，则也是对称的。（4）如果和是反对称的，则也是反对称的。（5）如果和是可传递的，则也是可传递的。解：（1）证明：任取，由于和是自反的，因此，，可得，由x取值的任意性可知，是自反的。（2）设，则，不是反自反的。（3）设，则，不是对称的。（4）设，则，不是反对称的。（5）设，则，不可传递。16.证明：若R是集合A上的自反和可传递关系，则R∘R=R。证明：任意取x,y∈A,x,y∈R,由于R是集合A上的自反，则可知y,y，x,x∈R，则R={x,y,x,y,y,y,x,x}R∘R={x,y,x,y,y,y,x,x}=R;17.如果关系R和S都是自反的。证明：，也是自反的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。因为R和S都是自反的，所以对于都有，对于都有。（1）设，那么或。若，有，那么必有。若，有，那么必有。因此，当时，必有，所以也是自反的。（2）设，那么因此且，即。所以也是自反的。18.证明：如果关系R和S都是自反的、对称的、可传递的，证明：也是自反的、对称的和可传递的。证明：设R是集合A上的二元关系，S是集合B上的二元关系。=1\*GB3①自反性的证明如题4。=2\*GB3②对于任意的，若，那么且因为R和S都是对称的，所以且，所以。即对于任意的，若，则必有，所以是对称的。=3\*GB3③对于任意，若且，那么有。因为R和S都是可传递的，所以有且，即。即对于任意，若且，都有。所以是可传递的。19.设集合A是有限集，且A=n，求：（1）A上有多少不同的对称关系。解：也就是说集合A有n平方个有序对，由对称定义可知，对于。另外知道在n平方个有序对中有n个有序对，相应的就有个有序对（X,Y)且X，定义可知后面的个有序对只能成对出现，所以有对。前面的那n对可以出现任意多对。图片如下。（1,1)(2,2).......(n,n)(1,2)(1,3).........(n-1,n)n个有序对(2,1)(3,1).........(n,n-1)()/2个有序对对共有n+()/2个元素即()/2个所以得到对称关系数为：（2）A上有多少不同的反对称关系。由定义：如果如下图。（1,1)(2,2)......................(n,n)(1,2)(1,3)...................................(n-1,n)n个有序对(2,1)(3,1)...................................(n,n-1)这n个有序对可以出现任意多次()/2个有序对对(由6可知）所以得结果：即（3）A上有多少不同的既非自反又非反自反的关系。解：20.试着画出R的关系图并写出对应的关系矩阵。解：关系图如下：21.设，和是A中的关系，试求出关系矩阵：；；；；；。解：由此可得：所以：22.给定集合。图4-6给出了A中的关系R的12个关系图。对于每个关系图，写出相应的关系矩阵，并证明被表达的关系是否是自反的或反自反的；是否是对称的或反对称的；是否是可传递的。（1）自反的、不对称的、不可传递的；其对应的关系矩阵为：（2）不自反的、反对称的、不可传递的；其对应的关系矩阵为：（3）自反的、对称的、可传递的；其对应的关系矩阵为：（4）自反的、不对称的、不可传递的；其对应的关系矩阵为:（5）不自反的、不对称的、不可传递的；其对应的关系矩阵为：（6）不自反的、对称的、不可传递的；其对应的关系矩阵为：（7）自反的、反对称的、可传递的；其对应的关系矩阵为：（8）自反的、不对称的、不可传递的；其对应的关系矩阵为：（9）不自反的、对称的、可传递的；此题图有错误其对应的关系矩阵为：（10）自反的、反对称的、不可传递的；其对应的关系矩阵为：（11）自反的、反对称的、可传递的；其对应的关系矩阵为：（12）不自反的、反对称的、可传递的。其对应的关系矩阵为：23.设X是一个集合，和是X中的二元关系，并设，试证明：（1）（2）（3）证明：a）因为，故R1∪IA⊇⊇R2∪IA，即b）因为s（R1）对称，且s（R1）⊇R1，但R1⊇R2，故s（R1）⊇R2，由s（R2）的定义，s（R2）是包含R2的最小对称关系，故s（R1）⊇s（R2）c）因为t（R1）传递，且t（R1）⊇R1，但R1⊇R2，故t（R1）⊇R2因t（R2）是包含R2的最小传递关系，所以t（R1）⊇t（R2）24.在图4.23中给出三个关系图。试求每一个的自反的、对称的和可传递的闭包，并画出闭包的关系图。（1）解：由关系图可知，则：（2）解：由关系图可知，则：（3）解：由关系图可知，则：25．和是集合A中的关系。试证明：（1）（2）（3）证明：(1)r（R1∪R2）=R1∪R2∪IA=R1∪IA∪R2∪IA=r（R1）r∪（R2）2）s（R1∪R2）=（R1∪R2）∪（R1∪R2）C=R1∪R2∪R1C∪R2C=（R1∪R1C）∪（R2∪R2C）=s（R1）∪s（R2）3）因为R1∪R2⊇R1，由习题3-98，则t（R1∪R2）=t（R1）同理t（R1∪R2）=t（R2）所以t（R1∪R2）=t（R1）∪t（R2）26.设集合，是中的二元关系，图4-12给出了的关系图。试画出可传递闭包的关系图，并求出。解：由关系图可知，则：27.设是集合中的任意关系。试证明：（1）（2）（3）证明：a）（R+）+=t（t（R）），因为t（R）是传递的，根据定理3-8.1，t（t（R））=t（R），即（R+）+=R+。b）R○R*=R○（tr（R））=R○（rt（R））=R○（t（R）∪IA）∞=R○t（R）R○∪IA=R○R∪∞∞i=1=R∪iR=R∪∪i=t（R）=R+i=2i=1同理可证R+=R*○Rc）因为r（R）是自反的，有习题3-97a），tr（R）是自反的，根据定理3-8.1，rtr（R）=tr（R），即tr（R*）=R*。所以，（R*）*=R*。29设是集合A的划分。试证明：是集合的划分。证明：因为是集合的划分，所以（1）因为所以（2）（3）（1），（2），（3）构成满足划分的条件，因此是集合的划分。30.把个元素的集合划分成两个类，共有多少种不同的分法？解：31.在图4.25中给出了集合中的两个关系图，判断这两个关系是否是等价关系。解：左侧的关系不是等价关系，因为不满足可传递性；右侧的关系是等价关系。32.在等价关系图中，应如何识别等价类？解：如果两个元素之间有两条连线，那么说明这两个元素是等价类。33.设R是集合X中的关系。对于所有的，如果，就有，则称关系R是循环关系。试证明：当且仅当R是一个等价关系，R才是自反的和循环的。证明：（1）当R是个等价关系时，由等价关系的定义知，等价关系满足自反性，即R是自反的。任取，，由R的可传递性，知，再由R的对称性，知。根据x，y，z取值的任意性，知R是循环的。（2）当R是自反的，可知对任意，。任取，使得，因为R是循环的，故当，时，。由x，y取值的任意性知，R是对称的；任取，，由R的循环性知，，因为R是对称的，因此，由x，y，z取值的任意性，知R是可传递的。因为R是自反的、对称的和可传递的，因此R是一个等价关系。34.设和是集合X中的等价关系。试证明：当且仅当中的每一个等价类都包含于的某一个等价类之中，才有。证明：设等价关系造成的集合X的划分为，等价关系造成的集合X的划分为当中的每一个等价类都包含于的某一个等价类之中时，任取中的一个等价类，则必包含在的一个等价类里，设包含在中，。任取中两元素x，y，由等价类的性质知，。由，可知若，则，即。由i,j,x,y取值的任意性知，。如果，那么对任意的→永真，等价于x,y落入的某个等价类中，等价于x,y落入的某个等价类中，即若，则，由x,y的任意性可知，,由i的任意性可知，中的每一个等价类都包含在的某一个等价类之中。综上所述，当且仅当中的每一个等价类都包含于的某一个等价类之中，才有。37.设和是集合X中的等价关系，并分别有秩和。试证明：也是集合X中的等价关系，它的秩至多为。还要证明不一定是集合X的一个等价关系。证明：(1)=1\*GB3①因为是自反的，所以对于任意的，都有对于任意的，故，所以是自反的；=2\*GB3②对于任意的，若，则且。又是对称的，所以有，，故，即是对称的；=3\*GB3③对于任意的，若，，则，且，。又是可传递的，所以有，，故，即是可传递的；综上，是等价关系。(2)=1\*GB3①因为是自反的，所以对于任意的，都有对于任意的，故，所以是自反的；=2\*GB3②对于任意的，若，则可能有三种情况：若且，那么因为是对称的，所以有，，故，即是对称的；若但，那么有且，此时，即是对称的；所以是对称的；若但，那么有且，此时，即是对称的；=3\*GB3③对于任意的，若，，当，时，不能确定，故不是可传递的。由上可知，不是等价关系。（1）（2），（3），，，，，合并后，有，（4），，（5），，，，，，合并，得，，，综上，最大相容类有四个，分别是，，，。38.给定集合的覆盖，如何才能确定此覆盖的相容关系。解：相容关系是具有反对称性的关系，集合的任何一个覆盖均能确定一个相容关系，反之亦然。设是集合的一个覆盖，则由此覆盖确定的上的相容关系是：，其中指的子集的笛卡尔积。如是的一个覆盖，则此覆盖确定的上的相容关系是：39.设集合，R是X中的关系。图4-23给出了R的关系图。试画出的关系图。解：40.假定是集合X中的恒等关系，R是X中的任何关系。试证明：是相容关系。证明：设（1）由于，因此，。知是自反的；（2）任取，，则或者或者。若，则，，；若，则，；若，则，。可知无论任何情况，若，则。故是对称的。综上所述，既是自反的又是对称的，因此，是相容关系。41.给定等价关系R和S，它们的关系矩阵是试证明：不是等价关系。证明：可知不是对称的，因此，不是等价关系。42.设集合。求出X中的等价关系和，使得也是个等价关系。解：设则和是集合X中的等价关系。此时，也是个等价关系。43.对于下列集合中的整除关系画出哈斯图。（1）（2）解：（1）（2）44.如果R是集合X中的偏序关系，且。试证明：是A中的偏序关系。证明：因为R是集合X中的偏序关系，所以R是自反的，反对称的，可传递的。（1）因为R是自反的，所以；又，所以；所以R是自反的。（2）对于任意，若,那么且；又R是反对称的，所以，即，所以是反对称的。（3）对于任意，若，那么且。又R是可传递的，所以，，即：，所以是可传递的。由此可知，满足自反性、反对称性、可传递性，即是A中的偏序关系。45.试给出集合X的实例，它能使是全序集合。解：，则此时，对于任意的，都有所以是全序集合。46.给出一个关系，它是集合中的偏序关系又是等价关系。解：集合上的恒等关系，既是偏序关系又是等价关系。47.证明下列命题：（1）如果是拟序关系，则也是拟序关系。（2）如果是偏序关系，则也是偏序关系。（3）如果是全序关系，则也是全序关系。（4）存在一个集合和中的关系R，使得是良序的，但不是良序的。证明：设是上的二元关系，（a）若是自反的，则，由于的转置仍是，因此，，故是自反的；（b）若是反自反的，则。把和都取转置，由于的转置仍是，因此，，故是反自反的；（c）若是对称的，任取，则，由的对称性可知，，于是。由x，y取值的任意性知，是对称的；（d）若是反对称的，任取，则，由的反对称性可知，，于是。由x，y取值的任意性知，是反对称的；（e）若是可传递得，任取，则，，由的可传递性，可知，于是。故是可传递的。从上述5条可以证明（1）——（3）（1）若是拟序关系，即是反自反的和可传递得，由（b）（e）可知，也是反自反的和可传递得，因此，是拟序关系。（2）若是偏序关系，即是自反的、反对称的，可传递的，由（a）（d）（e）可知，也是自反的、反对称的，可传递的，因此，是偏序关系。（3）若是全序关系，则是偏序关系，由（2）知也是偏序关系；另知，，或成立，当时，，当时，。因此不论任何情况，，或总成立。综上，也是全序关系。（4）举例子，设，N是自然数集合，则是良序，但是不是良序。因为取全集N，在中没有最小成员。48.设R是集合A上的二元关系，证明，当且仅当和，才是拟序的。当且仅当和，才是偏序的。证明：设是集合上的关系（1）充分性：，故是可传递的；，所以对于任意的，都有，即是反自反的。所以，当和时，是拟序的。必要性：因为是拟序的，所以是反自反的、可传递的、反对称的。是可传递的，故；是反对称的，所以对于任意，若，则；又是反自反的，所以。所以，当是拟序时，且。（2）充分性：，故，即是自反的；又，所以对于任意，若，则，即是反对称的；又，所以是可传递的；所以，当和时，R是偏序关系。必要性：因为R是偏序关系，所以R是自反的，反对称的，可传递的。是自反的，故IX⊆R且IX⊆；是反对称的，故对于任意的，若，则，所以。又是自反的，可传递的，所以它的自反可传递闭包是其本身，即；所以，当是偏序关系时，且。49.图4-28给出了偏序集合的哈斯图，这里。(1)下列关系中哪一个是真的：(2)求出中的最大成员和最小成员，如果他们存在的话。(3)求出中的极大成员和极小成员。(4)求出子集的上届及下届。并指出这些子集的LUB和GLB，如果它们存在的话。解：(1)，是真的，(2)最大成员：；最小成员：无。(3)极大成员：；极小成员：(4)子集上届：；下届：；LUB：；GLB：。子集上届：，；下届：无；LUB：；GLB：无。子集上届：；下届：；LUB：；GLB：。第五章函数习题答案P[109-111]下列关系中哪些能够构成函数？对于不是函数的关系，说明不能构成函数的原因。(1)(2)(3)解：(1)不能构成函数。对于某些，不止存在一个使得成立。(2)能构成函数。(3)不能构成函数。对于某些对于某些，存在两个使得成立。2.下列集合中，哪些能够用来定义函数？试求出所定义的函数的域和值域。(1)(2)(3)(4)解：(1)能够用来定义函数。域：值域：(2)能够用来定义函数。域：值域：(3)不能够用来定义函数。(4)能够用来定义函数。域：值域：3．设是证书集合，是正整数集合，并且把函数，定义为。试求出函数的值域。解：为正奇数的集合。4．设是全集，是的幂集，是由的子集所构成的所有序偶的集合，对任意的,把定义为。试证明：的陪域与值域相等。证明：f的陪域为，设值域为，假定f的陪域与值域不相等，即。那么一定存在的一个元素A，使得。因为，因此，不存在任何一个，使得。设，则对于任何，，由知，由取值的任意性可知，。这与A的取值在中相矛盾，因此f的陪域与值域不相等不成立。即的陪域与值域相等。5.设，并定义函数如下：写出的全部序偶。求出。写出。有多少个和具有相同的定义域和值域的函数。解：（1）（2）（3）（4）f定义域元素的个数是9，值域元素的个数是5。求的个数，等同于求从9个元素的集合到5个元素集合满射函数的个数。6．设是实数集合，并且对于，函数，和，试求出合成函数。解：7.设集合。试求出中如下的所有函数：(1)(2)(3)解：10种情况4种情况3种情况设是自然数集合，是实数集合。下列函数中哪些是满射的，哪些是单射的，哪些是双射的？(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)解：是单射，不是满射，不是双射。不是单射，不是满射，不是双射。不是单射，不是满射，不是双射。不是单射，是满射，不是双射。是单射，不是满射，不是双射。不是单射，不是满射，不是双射。是单射，是满射，是双射。是单射，不是满射，不是双射。是单射，不是满射，不是双射。是单射，不是满射，不是双射。不是单射，是满射，不是双射。设和都是有限集合，和的基数分别为和。有多少个从到的单射函数？有多少个从到的满射函数？有多少个不同的双射函数？解：(1)当存在从X到Y的单射函数时，，单射函数有(2)当存在从X到Y的满射函数时，，满射函数的个数有当存在从X到Y的双射函数时，，双射函数的个数有个。设。有多少个从到的满射函数具有性质？解：有两个。分别为和。设，有多少满足以下条件的从到的函数：(1)(2)(3)解：有个函数满足。有个函数满足。有多少个函数满足12.设集合，且函数是有多少与具有同样的域和值域的不同函数？解：同P110页第5题（4）。解：设故解：设单射函数，但是。证明：设则，满足所以，存在一对一的映射。因为是一对一的映射，不同的对应的不相等，所以至少需要个与之想对应，所以该映射是满射。16.证明：特征函数所具有的性质(1)-(7)和(10)-(11)。证明：由特征函数的定义可知。充分性：因ψA=0，故对于任意的，都有所以。必要性：因，所以对于任意的，都有，即对于所有的，都有ψA(x)=0，即ψA=0。充分性：因ψA=1，故对于任意的，都有所以。必要性：因，所以对于任意的，都有，即对于所有的，都有ψA(x)=1，即ψA=1。充分性：因ψA≤ψB，则有三种情况ψA=0，ψB=0；ψA=0，ψB=1；ψA=1，ψB=1。当ψA=0，ψB=0时，，所以；当ψA=0，ψB=1时，，所以；当ψA=1，ψB=1时，，所以；所以，当ψA≤ψB时，有，充分性得证。必要性：当时，ψA=1；由于，所以必定有，所以ψB=1；所以有ψA≤ψB；当时，ψA=0；由于，所以有或两种情况。若，则ψB=1，此时ψA≤ψB；若，则ψB=0，此时ψA≤ψB；所以，当时，有ψA≤ψB，必要性得证。充分性：当ψA=ψB=0时，对于所有的，都有且，故。当ψA=ψB=1时，对于所有的，都有且，故。所以当ψA=ψB时，必有，充分性得证。必要性：当时，ψA=1；由于，所以必定有，所以ψB=1；所以有ψA=ψB；当时，ψA=0；由于，所以必定有，故ψB=0；所以有ψA=ψB；所以，当时，有ψA=ψB，必要性得证。若，则必有x∉∼A。此时ψA=1，ψ∼A=0，即ψ∼A=1-ψA。当时，ψA∩B=1,由于，所以有ψA=1，ψB=1所以有ψA∩B=ψA*ψB；当时，ψA∩B=0,由于，于是有以下几种情况：若，此时ψA=0，ψB=1，ψA∩B=ψA*ψB=0；若，此时ψA=1，ψB=0，ψA∩B=ψA*ψB=0；若，此时ψA=0，ψB=0，ψA∩B=ψA*ψB=0；得证。见书上P108。当时，ψA-B=1,由于，此时ψA=1，ψB=0ψA-B=ψA-ψA*ψB=1-1*0=1当时，，ψA-B=0，由于，于是可能有以下几种情况：若且，则ψA=0，ψB=0，ψA-B=ψA-ψA*ψB=0；若且，则ψA=1，ψB=1，ψA-B=ψA-ψA*ψB=0；若且，则ψA=0，ψB=1，ψA-B=ψA-ψA*ψB=0；得证。充分性：若，则ψA=1，由于ψA=ψA*ψB，所以ψB=1，即若，则必有，即；若，则ψA=0，即。所以必有；当ψA=ψA*ψB时，必有，充分性得证。必要性：若，则ψA=1，由于，于是，ψB=1，此时ψA=ψA*ψB=1；若，则ψA=0，由于，于是有以下两种情况；若，则ψB=0，此时ψA=ψA*ψB=0；若，则ψB=1，此时ψA=ψA*ψB=0；当时，必有ψA=ψA*ψB，必要性得证。若，则ψA=1，此时ψA=ψA*ψA=1；若，则ψA=0，此时ψA=ψA*ψA=0.所以ψA=ψA*ψA。应用特征函数求下列各式成立的充分必要条件。A-B∪(A-C)=AA⊕B=∅A⊕B=AA∩B=A∪B解：ψA-B∪(A-C)=ψA-B+ψA-C-ψA-B*ψA-C.=(ψA-ψA*ψB)+ψA-ψA*ψC)-(ψA-ψA*ψB*(ψA-ψA*ψC)=ψA-ψA*ψB*ψCψA-ψA*ψB*ψC=ψA⟺ψA*ψB*ψC=0即A∩B∩C=ϕ所以A-B∪(A-C)=A的充要条件为A∩B∩C=ϕ。ψA⊕B=ψA-B∪(B-A)=ψA-B+ψ(B-A)-ψA-B*ψ(B-A).=(ψA-ψA*ψB)+ψB-ψB*ψA)-(ψA-ψA*ψB*(ψB-ψB*ψA)=ψA+ψB-2ψA*ψBψA+ψB-2ψA*ψB=ψϕ⟺ψA-ψB=0即ψA=ψB，A=B所以A⊕B=∅的充要条件为A=BψA⊕B=ψA-B∪(B-A)=ψA-B+ψ(B-A)-ψA-B*ψ(B-A).=(ψA-ψA*ψB)+ψB-ψB*ψA)-(ψA-ψA*ψB*(ψB-ψB*ψA)=ψA+ψB-2ψA*ψBψA+ψB-2ψA*ψB=ψA⟺ψB(1-2ψA)=0即ψB=0或ψA=1/2(不符合)即B=ϕ所以A⊕B=A的充