发布时间 : 星期四 文章离散数学课后习题答案（左孝凌版）更新完毕开始阅读
前束合取范式
习题2-7 (1) 证明：
(2) a) ①(?x)(┐A(x)→B(x)) P ②┐A(u)→B(u) US① ③( ?x)┐B(x) P ④┐B(u) US③ ⑤A(u)∨B(u) T②E ⑥A(u) T④⑤I ⑦ ( ?x)A(x) EG⑥
b) ①┐( ?x)(A(x)→B(x)) P（附加前提）②( ?x)┐(A(x)→B(x)) T①E ③┐(A(c)→B(c)) ES② ④A(c) T③I ⑤┐B(c) T③I ⑥( ?x)A(x) EG④ ⑦ (?x)A(x)→(?x)B(x) P ⑧(?x)B(x) T⑥⑦I ⑨B(c) US⑧ ⑩B(c)∧ ┐B(c) T⑤⑨矛盾 c）①(?x)(A(x)→B(x)) P ②A(u)→B(u) US① ③( ?x)(C(x)→┐B(x)) P ④C(u)→┐B(u) US③ ⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥ d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P ②B(u)→┐C(u) US① ③( ?x)C(x) P ④C(u) US③
⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US ⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明：
a)①( ?x)P(x) P（附加前提） ②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)
故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P（附加前提） ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)
解：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。
本题符号化为：
(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P ④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I
⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧
b)设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车 本题符号化为：
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③ ⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。
设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。 S（x）：x是优秀生。c：小张。 本题符号化为：
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c) ①G(c) P（附加前提） ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P ⑥ L(c) T④⑤I ⑦G(c) →L(c) CP
注意：本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S（x）：x是优秀
生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证仍是有效的。
3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解：Z1={} Z2={} Z3={} Z4={,} Z5={,} Z6={,} Z7={,,} 3-5.2 在一个有n个元素的集合上，可以有多少种不同的关系。 解 因为在X中的任何二元关系都是X×X的子集，而X×X=X2中共有n2个元素，取0个到n2个元素，共可组成2n2个子集，即|?(X?X)|?2n2。 3-5.3 设A＝{6：00，6：30,7：30，?, 9：30,10：30}表示在晚上每隔半小时的九个时刻的集合，设B={3,12,15,17}表示本地四个电视频道的集合,设R1和R2是从A到B的两个二元关系，对于二无关系R1，R2，R1∪R2，R1∩R2，R1?R2和R1-R2可分别得出怎样的解释。 解：A×B表示在晚上九个时刻和四个电视频道所组成的电视节目表。 R1和R2分别是A×B的两个子集，例如R1表示音乐节目播出的时间表，R2是戏曲节日的播出时间表，则R1∪R2表示音乐或戏曲节目的播出时间表，R1∩R2表示音乐和戏曲一起播出的时间表，R1?R2表示音乐节目表以及戏曲节目表，但不是音乐和戏曲一起的节日表，R1-R2表示不是戏曲时间的音乐节目时间麦。 3-5.4 设L表示关系“小于或等于”，D表示‘整除”关系,L和D刀均定义于{1,2,3,6}，分别写出L和D的所有元素并求出L∩D. 解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>} D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L∩D= {<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} 3-5.5对下列每一式，给出A上的二元关系，试给出关系图： a){|0?x∧y?3}，这里A={1,2,3,4}； b){|2?x,y?7且x除尽y,这里A＝{n|n?N∧n?10} c) {|0?x-y<3}，这里A={0,1,2,3,4}； d){|x,y是互质的}，这里A={2,3,4,5,6} 解： a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图 b) R={<2,0>,<2,2>,<2,4>,<2,6>, <3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>, <6,0>,<6,6>, <7,0>,<7,7>} 3-6.1 分析集合A={1，2，3}上的下述五个关系： （1）R={＜1，1＞，＜1，2＞，＜1，3＞，＜3，3＞}； （2）S={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞}； （3）T={＜1，1＞，＜1，2＞，＜2，2＞，＜2，3＞}； （4）?=空关系； （5）A×A=全域关系。 判断A中的上述关系是否为a）自反的，b）对称的，c）可传递的，d）反对称的。 解（1）R是可传递和反对称的。 （2）S是自反，对称和可传递的。 （3）T是反对称的。 （4）空关系是对称，可传递和反对称的。 （5）全域关系是自反，对称和可传递的。 3-6.2给定A={1，2，3,4}，考虑a上的关系R,若R={＜1，3＞，＜1，4＞，＜2，3＞，＜2，4＞，＜3，4＞} a) 在A?A的坐标图上标出R，并绘出它的关系图； b) R是ⅰ)自反的ⅱ）对称的ⅲ)可传递的，iv) 反对称的吗？ 解 a） 1 2 4 3 R是可传递的的和反对称的；但不是自反的和对称的。 3-6.3 举出A={1，2，3}上关系R的例子，使其具有下述性质： a）既是对称的，又是反对称的； b）R既不是对称的，又不是反对称的； c）R是可传递的。 解 a）R={＜1，1＞，＜2，2＞，＜3，3＞} b）R={＜1，2＞，＜2，1＞，＜2，3＞} c) R={＜1，2＞，＜2，1＞，＜1，1＞，＜2，2＞，＜3，3＞} 3-6.4 如果关系R和S是自反的，对称的和可传递的，证明R∩S也是自反，对称和可传递的。 证明 设R和S是X上的自反的，对称的和可传递的关系。 1）对任意x?X，有＜x，x＞?R和＜x，x＞?S，所以＜x，x＞?R∩S，即R∩S在X上是自反的。 2）对任意的＜x，y＞?R∩S，有＜x，y＞?R∧＜x，y＞?S，因为R和S是对称的，故必有＜y，x＞?R∧＜y，x＞?S。即＜y，x＞?R∩S，所以R∩S在X上是对称的。 3）对任意的＜x，y＞?R∩S∧＜y，z＞?R∩S，则有 ＜x，y＞?R∧＜x，y＞?S∧＜y，z＞?R∧＜y，z＞?S 因为R和S是传递的，故得＜x，z＞?R∧＜x，z＞?S，即＜x，z＞?R∩S，所以R∩S在X上是传递的。 3-6.5给定S={1，2，3，4}和S上关系：R={＜1，2＞，＜4，3＞，＜2，2＞，＜2，1＞，＜3，1＞} 说明R是不可传递的，找出关系R1?R，使得R1是可传递的，还能找出另一个3-7.1设R1和R2是A上的任意关系，说明以下命题的真假并予以证明。 a）若R1和R2是自反的，则R1○R2也是自反的； b）若R1和R2是反自反的，则R1○R2也是反自反的； c）若R1和R2是对称的，则R1○R2也是对称的； d）若R1和R2是传递的，则R1○R2也是传递的。 证明 a）对任意a∈A，设R1和R2是自反的，则＜a，a＞∈R1，＜a，a＞∈R2 所以，＜a，a＞∈R1○R2，即R1○R2也是自反的。 b）假。例如：设A={a，b}，有R1={＜a，b＞}与R2={＜b，a＞} R1和R2是反自反的。但R1○R2={＜a，a＞}，所以R1○R2在A上不是反自反的。 c)假。例如：设A={a，b，c}，有 R1={＜a，b＞，＜b，a＞，＜c，c＞}，R2={＜b，c＞，＜c，b＞} R1和R2是对称的，但R 1○R2={＜a，c＞，＜c，b＞} 所以，R1○R2不是对称的。 d）假。例如：设A={a，b，c}，有 R1={＜a，b＞，＜b，c＞，＜a，c＞}，R2={＜b，c＞，＜c，a＞，＜b，a＞} 则R1，R2都是传递的。但R 1○R2={＜a，c＞，＜a，a＞，＜b，a＞} 所以，R1○R2不是传递的。 3-7.2 证明 若S为集合X上的二元关系： a）S是传递的，当且仅当（S○S）?S； b）S是自反的，当且仅当IX?S； c）证明定理3-7.3（b）（即S是反对称的，当且仅当S∩Sc?IX）。 证明 a）设S为传递的，若＜x，z＞∈S○S，则存在某个y∈X，使得＜x，y＞∈S，且＜y，z＞∈S。 若S是传递的，＜x，z＞∈S，所以（S○S）?S。 反之，设（S○S）?S ，假定＜x，y＞∈S且＜y，z＞∈S，则＜x，z＞∈S○S。因为（S○S）?S，故＜x，z＞∈S，得到S是传递的。 b）设S是自反的，令＜x，y＞∈IX，则x=y。但＜x，x＞∈S，因此＜x，y＞=＜x，x＞∈S，得IX?S。 反之，令IX?S，设任意x∈X，＜x，x＞∈IX，故＜x，x＞∈S，因此S是自反的。 c）设S是反对称的。假定＜x，y＞∈S∩Sc，则 ＜x，y＞∈S∧＜x，y＞∈Sc?＜x，y＞∈S∧＜y，x＞∈S 因为S是反对称的，故x＝y， 所以＜x，y＞＝＜x，x＞∈IX，即S∩Sc?IX。 反之，若S∩Sc?IX，设＜x，y＞∈S且＜y，x＞∈S，则 ＜x，y＞∈S∧＜x，y＞∈Sc ?＜x，y＞∈S∩Sc ?＜x，y＞∈IX 故x＝y，即S是反对称的。 3-7.3 设S为X上的关系，证明若S是自反和传递的，则S○S=S，其逆为真吗 ？ 证明 若S是X上传递关系，由习题3-7.2a）可知（S○S）?S， 令＜x，y＞∈S，根据自反性，必有＜x，x＞∈S，因此有＜x，y＞∈S○S，即S?S○S。得到 S=S○S. 这个定理的逆不真。例如X={1，2，3}，S={＜1，2＞，＜2，2＞，＜1，1＞}，3-8.1 根据图3-8.1中的有向图，写出邻接矩阵和关系R，并求出R的自反闭包和对称闭包。 解 a M1 1 0 R= 0 0 1 b c 0 1 0 图3-8.1 R={＜a，a＞，＜a，b＞，＜b，c＞，＜c，b＞＝ r（R）= R∪IX ={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝ s（R）= R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞} 3-8.2 设集合A={a，b，c，d}A上的关系 R={＜a，b＞，＜b，a＞，＜b，c＞，＜c，d＞} a） 用矩阵运算和作图方法求出R的自反、对称、传递闭包； b） 用Warshall算法，求出R的传递闭包。 解 a） 0 1 0 0 MR= 1 0 1 0 0 0 0 1 0 0 0 0 R的关系图如图所示。 a b d c M0 1 0 0 1 0 0 0 1 1 0 0 R+MIA= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 r（R）= R∪IA ={＜a，a＞，＜a，b＞，＜b，a＞，＜b，b＞，＜b，c＞，＜c，c＞，＜c，d＞，＜d，d＞}（图（a）） a b d c 图（a） 0 1 0 0 0 1 0 0 0 1 0 0 MR+MRc= 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 + 0 1 0 0 = 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 3-9.1 4个元素的集合共有多少不同的划分。 解 整数4可划分为：4，1+3，1+1+2，2+2，1+1+1+1。 1+C12+14+C4 C224+1=15（种） 3-9.2 设{A1，A2，?，Ak}是集合A的一个划分，我们定义A上的一个二元关系R，使＜a,b＞∈R当且仅当a和b在这个划分的同一块中。证明R是自反的，对称的，和传递的。 证明 设对任意a∈A，则必存在Ai，使a∈Ai，因a与a必可看作在同一块中，故有＜a,a＞∈R。即R是自反的。 设a,b∈A，若有＜a,b＞∈R，则a与b必在同一块，故b与a亦在同一块，＜b, a＞∈R，即R是对称的。 对任意a,b,c∈A， ＜a,b＞∈R∧＜b,c＞∈R ?（?i）（a∈Ai∧b∈Ai）∧（?j）（b∈Aj∧c∈Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧b∈Ai∩Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧Ai∩Aj≠?） ?（?i）（?j）（a∈Ai∧c∈Aj∧i=j）（∵i≠j?Ai∩Aj= ?） ?a,c在同一块 ?＜a,c＞∈R ∴R传递