离散数学课后习题答案_(邱学绍).doc

第一章习题1.1 1解 ：A=； ：B=a, e, i,m, n, o, r, t, u； ：C=-3,2。 2解 A=x|1 x 79, x N； B=x| x=2k+1, kN； C=x| x=5n, nI。 3解 ：1，2，3，4，6，9，12，18，36； ：a，b； ：1，。习题1.2 1解 互不相同。是不包含任何元素的空集，是以空集f为元素的单元素集合，是以0为元素的单元素集合，但和的集合中的元素不同。 2证明 若，则； 反之，若，则 ， 因此，。 3解 设，则； 设，则； 设，则； 设，则。 4解 MT；NP；PT=f 。 5解 由题意可得：；。 A(B(CD) = ABCD =0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64； A(B(CD)=f；因为，AC=0,1,2,3,6,7,8,9,12,15,18,21,24,27,30,所以，B- AC=4,5； ，=；6解 、的文氏图如图1-1所示，图中阴影部分表示所求集合。7解 所求集合的集合成员表如表1-1所示。表1-1AB00000010001000111101 所求集合的集合成员表如表1-2所示。表1-2ABC000000001000010100011111100100101110110100111110 8证明 = =A- (BC)= 9证明 。 因为，则，所以，因此，。 。 ，。因为，所以，B=f B=因此。习题1.3 1解 f=0； f=1； 1,2,3,2,13； 1,2,1=2。2解 8，8，8，10，3，6，5，12。因为，=-，所以=-=60-25-26-26+9+11+8-8=3=52-11-9-8+32=30NTFU图1-3（原教材图1-4）3解 设A=xx N,1x100, x能被5整除，B=xx N,1x100, x能被4整除，C=xx N,1x100, x能被6整除，则，因此，=20-1=19。习题1.4 1解 20=27+6； 58=227+4； 3=08+3； 57=319+0。2解 因为,。所以，14和35的最大公因数为7，即GCD(14,35)=7，且由以上两式可推得7=135-214。 因为58=134+24,34=124+10,24=210+4,10=24+2,4=22。所以34和58的最大公因数为2，即GCD(34,58)=2，且由以上各式可推得2=1234-758。 因为，。所以，180和252的最大公因数为36，即GCD(180,252)=36，且由以上各式可推得36=3180-2252。 因为，。所以128和77互素，即GCD(128,77)=1，且由以上各式可推得1=577-3128。3解 因为，所以GCD(108,72)=36，因此LCM(108,72)=10872/36=216。 因为，所以GCD(245,175)=35，因此LCM(245,175)=245175/35=1225。 因为，所以GCD(252,180)=36，因此LCM(252,180)=252180/36=1260。 因为，所以GCD(64,81)=1，因此LCM(64,81)=6481=5184。 4证明 设，则存在整数、，使得 ，因为是、的最大公因数，所以，、。因此， 另一方面，因为是、的最大公因数，所以、，因此，与互素，否则与有大于1的公因数，则d2c，d2d1，又，由整除的传递性，所以，。因此，与有大于1的因数，这与GCD(a,c)=1矛盾。由于与互素，且，由定理6，则，又，因此 由于、都是正整数，由可得。因为b,c都和a互素，则GCD(a,b)=1，GCD(a,c)=1，由则有GCD(a, bc)=1，即bc也和a互素。 5证明 设GCD(a,b)=d，则da，db。因为c0，所以，cdac，cdbc。另一方面，因为GCD(a,b)=d，所以存在s,tI,使得sa+tb=d，此式两边同乘c得sac+tbc=cd因此，对于任何的正整数e, 若eac，ebc，则ecd。又因为cd0，故cd是ac和bc的最大公因数，即GCD(ac,bc)= cd= cGCD(a,b)。 6.证明 因为am，所以存在整数，使得又bm，即，而、互素，由定理6，则有。 因此，存在整数q1，使得，代入既可得 即abm。7.证明 设（）,由，则。同理，由，则。即为、的公倍数，又是、的最小公倍数，因此，即，所以mk。复习题1 1. 解 S5=3，5,所以，X中不含元素3,5。故。因为, 所以,因此或。因为，XS2=S1，所以，S1-S2X，因此，X=S3或S1。S2=2，4，6，8,，所以X中不含元素2,4,6,8,所以X=S3或,但XS4，故X=S5。因为XS1，所以，X=S2, S3, S4, S5，而XS3=f，即X中无奇数，所以，X=S2。 2.解 是可以作到的。 如，则. 3.解 ，则； ，则； ，则； =1，2，则。 4.证明 对于任意的XP(B)，则，又,，所以XP(A)，由的任意性可知, . 5.解 可构成个子集。 其中有个子集中元素个数为奇数。 6.证明 左边=右边,故原题得证. 证明 = 7.解 =； =； =； =； =。 8. 证明 若，对于任意的xB， 若xA，则xAB，所以，xAB，则xAC，由可得xAC，而，则xAC，所以xC；因此，BC。若xA，则xAB，又xB，所以，xAB，由且，可得，xAB，因此，xAC，但且，所以，xC，因此，BC。采用同样的方法可证。故。 9.方法证明 对于任意的x(A-B)(B-A)，则或，即有,或者；当时,且，当时,亦有且，故有。因此，同理可证综上知, 方法作集合成员表如表1-4所示可见与对应填入值相同故.表1-4ABA-BB-A00000000010111011010110111000110方法(3) 证明 = 10.解 设A、B、C分别表示选修法、德、俄语的学生的集合 则， ，=150。=150+260+208+160-76-48-62+30=622 =76-30=46；同理=62-30=32；=260-76-48+30=166；同理。 11.解 |P(B)|=64；又；，则|AB|=6+3-8=1，所以|A-B|=|A|-|AB|=3-1=2；=8-2=6。 12.证明 因为GCD(a，b)=d，则存在整数、，使得又因为a，b不全为0，所以GCD(a，b)=d，因此，、所以，、都是整数，由此可得所以，对于任意的正整数c，若，则c1，因此GCD。 反之，因为d是a，b的正因数，所以、都是整数，又GCD，则存在整数、，使得两边乘以得因此，对于任何的正整数c，若ca，cb，则cd，故GCD（a，b）=d第二章 命题逻辑习题2.1.解 不是陈述句，所以不是命题。 x取值不确定，所以不是命题。 问句，不是陈述句，所以不是命题。 惊叹句，不是陈述句，所以不是命题。 是命题，真值由具体情况确定。 是命题，真值由具体情况确定。 是真命题。 是悖论，所以不是命题。 是假命题。 2解 是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为。 是疑问句，所以不是命题。 是悖论，所以不是命题。 是原子命题。 是复合命题。设p：王海在学习；q：李春在学习。命题符号化为pq。 是复合命题。设p：你努力学习；q：你一定能取得优异成绩。pq。 不是命题。 不是命题 。是复合命题。设p：王海是女孩子。命题符号化为：p。 3解 如果李春迟到了，那么他错过考试。 要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 李春错过考试当且仅当他迟到了。 如果李春迟到了并且错过了考试，那么他没有通过考试。4解 p(qr)。pq。qp。q p。习题2.2 1解 是1层公式。 不是公式。 一层： pq，p 二层：pq所以，是3层公式。 不是公式。 (pq)(q( qr)是5层公式，这是因为 一层：pq，q，r 二层：qr 三层：q( qr) 四层：(q( qr) 2解 A=(pq)q是2层公式。真值表如表2-1所示：表2-1pq0000011110101111 是3层公式。真值表如表2-2所示：表2-2pq00101011101000111111 是3层公式。真值表如表2-3所示：表2-3pqr00000010010001010001101100111000011101001111010111111111是4层公式。真值表如表2-4所示： 3解 真值表如表2-5所示：表2-5pq001111011000100101110001所以其成真赋值为：00，10，11；其成假赋值为01。 真值表如表2-6所示：表2-6pqr0000100100010010110010001101001101111111所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。真值表如表2-7所示，所以其成真赋值为：00，11；成假赋值为：01，10，。 4解 设，其真值表如表2-8所示：表2-8pq00011010111001111101故为重言式。 设A=(pq)(pq)，其真值表如表2-9所示：表2-9pqpqpq(pq)A000010010100100100111100故A=(pq)(pq)为矛盾式。 设A=(pq)(pq)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(pq)(pq)为可满足式。 设，其真值表如表2-11所示：表2-11pqr0001111100111111010100110111111110001001101010111101000111111111故为重言式。习题2.3 1解 真值表如表2-12所示：表2-12pq0011101011001010010101100010由真值表可以看出和所在的列相应填入值相同，故等值。 真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相应填入值相同，故等值。 真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出p和(pq)(pq)所在的列相应填入值相同，故等值。真值表如表2-15所示：pqrqr p(qr) pq (pq)r 00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p(qr)和(pq)r所在的列相应填入值相同，故等值。2证明 (pq) (pq) (pq)( pq) p (qq) p。(pq)(qp)(pq) (qp)(pq)(p p)( qq)(q p)( pq)(pq)。由可得，(pq)( pq)(pq)( pq)(pq)(qp)(pq)pq。p(qr) p(q r) q(p r) q( p r)。 3解 (pq)(pq)pq (pq)( pq)pq (pq)(pq)(qp)(pq)(qp)(pq) (pq) pq。同理可证(pq) pq。 4解 与习题2.2第4（4）相同。 真值表如表2-16所示：表2-16p q p q pq q p A 0011111011011110010011100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100 真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111 真值表如表2-19所示，所以公式仅为可满足式。表2-19001011011101100100110100 真值表如表2-20所示，所以公式是重言式。表2-20pqr pqrqpr(pq)(rq)(pr)qA000110111001100011010110111011110111100010011101001001110110111111111111 5解 设p：他努力学习；q：他会通过考试。则命题符号化pq。其否定(pq) pq。 所以语句的否定：他学习很努力但没有通过考试。 设p：水温暖；q：他游泳。则命题符号化pq。其否定(pq) pq。 所以语句的否定：当且仅当水不温暖时他游泳。 设p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化p(qr) 其否定( p(qr) (p(qr) p( qr) p(q r) 所以语句的否定：天冷并且他不穿外套或者穿衬衫。 设p：他学习；q：他将上清华大学；r：他将上北京大学。则命题符号化其否定所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学。 6解 设p：张三说真话；q：李四说真话；r：王五说真话。则：pq, qr(qr), r(pq)为真,因此p(pq)(ppq)(p(pq)pq为真。因此，p为假，q为真，所以r为假。故张三说谎，李四说真话，王五说谎。 7解 设p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：p(qr)，qp，sr，p结论：s证明 p(qr)为真，其前件p为真，所以qr为真，又qp为真，其后件p为假，所以要求q为假，所以r为真。又sr为真，其后件r为假，所以要求s为假，故s为真。习题2.4 1解 设p：明天下雨；q：后天下雨。命题符号化。 设p：明天我将去北京；q：明天我将去上海。命题符号化。 2解 3证明 因为，是功能完备联结词集，所以，含有外的其他联结词的公式均可以转换为仅含中的联结词的公式。又因为即含有的公式均可以转换为仅含中的联结词的公式。因此，含外其他联结词的公式均可以转换为仅含中的联结词的公式。 故是功能完备联结词集。 4证明 是极小功能完备集，因而只需证明中的每个联结词都可以用 表示，就说明是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，p(pp)pp，pq(pq)(pq)(pq)(pq)。对于证明是极小功能完备集，可类似证明。习题2.5 1解 ； 2解 即为其析取范式。即为其合取范式。即为其合取范式。p(qr)p(qr)(qr)(pqr)(pqr) 即为其析取范式。即为其合取范式。为其析取范式。即为其析取范式和合取范式。 3解 即为其主合取范式。其主析取范式为3pq。 。故其主析取范式为(0,1,2,3)=(pq)(pq)(pq)(pq)。 即为其主合取范式。其主析取范式为(2,4,5,6,7) (pqr)(pqr)(pqr)(pqr)(pqr)。 即为其主合取范式。其主析取范式为。 4解 真值表如表2-21所示, 所以其极小项是pq，极大项为pq，pq，pq。表2-21pq0010011010011110其主析取范式是：pq，主合取范式为：(pq)( pq)(pq)。 真值表如表2-222所示, 所以其极小项是pq, pq, pq, 极大项为pq。表2-22pq000100011101101011111101其主析取范式是：(pq)(pq)(pq)，主合取范式为：pq。 真值表如表2-23所示，所以其极小项是pqr,pqr, pqr, pqr,pqr,表2-23pqr000100001100010100011111100001101001110001111001极大项为pqr，pqr，pqr。其主析取范式是：(pqr)(pqr)(pqr)(pqr)(pqr)，主合取范式为：(pqr)(pqr)(pqr) 。 真值表如表2-24所示,所以其极小项为pqr,pqr,pqr,pqr,pqr,而极大项分为pqr，pqr，pqr.主合取范式为(pqr)(pqr)(pqr),主析取范式为(pqr)(pqr)(pqr,)(pqr)(pqr)。表2-24pqr00010001110101001111100011010111010111115解 (pq)(pq)(pq)(pq) q (pq)(pq)， 故为可满足式。 故为重言式。(p(qr)(pq)(pr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)p(qr)(pqr)(qr)0。 故为矛盾式。 故仅为可满足式。6证明 右边已经是主合取范式。而左边主合取范式已是pq，因此，(p q)pq，证毕。右边(p q)(pq)已经是主合取范式。pp(qq) (p q)(pq)。因此，。左边p(qr)p(qr)pqr，而右边(pq)rpqr，因此，。习题2.61解 设p：这里有演出；q：这里通行是困难的；r：他们按照指定时间到达。前提：pq, rq,r结论：p证明 r Prq Pq T假言推理pq P p T拒取式2证明 s Psp P p T假言推理pq Pq T假言推理证明 r P附加前提引入rq Pq T假言推理pq Pp T拒取式ps Ps T假言推理rs TCP证明 p P否定结论引入pq Pq T假言推理qr Pr T假言推理rs Pr T化简rr T合取证明 p P附加前提引入pq Pq 析取三段论rq Pr 拒取式pr CP证明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入r T假言推理(rs)t Prst T蕴涵等价式st T析取三段论h(st) Pst h T假言易位 h T假言推理 qh TCP13. p(qh) TCP 3解 推理不正确。在到化简时，只能对整个公式进行而不是子公式。 4解 正确。P，P附加前提引入；T析取三段论；P；T假言推理；P；T假言推理；TCP。 5解 设p：张三努力工作，q：李四高兴，r：王五高兴，s：刘六高兴 前提：p(qr)，qp，sr 结论：ps 证明：p P附加前提引入p(qr) Pqr T假言推理qp Pq T拒取式r T析取三段论sr Ps T拒取式ps TCP 6解 设：p：天下雪；q：马路结冰；r：汽车开得快；s：马路塞车。前提：pq，qr，rs，s结论：p证明pq Pqr Ppr 推理三段论rs Pps 推理三段论s P p 拒取式复习题2 1解 设p：3是偶数，q：中国人的母语是汉语。命题符号化。 设p：你抽烟，q：你很容易得病。命题符号化。 设p：今天是星期一，q：明天才是星期二。命题符号化。 设p：李春这个学期离散数学考了100分。q：李春这个学期数据结构考了100分。命题符号化。 设p：下雪路滑，q：他迟到了。命题符号化。 设p：经一事，q：长一智。命题符号化。 设p：一朝被蛇咬，q：十年怕井绳。命题符号化。 设p：以物喜，q：以己悲。命题符号化。 2. 解 命题中的“或”是不可兼或，因此，可以直接用“”符号化；根据联结词的性质及其之间的转换关系，可知命题“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于1980年）或生于1980年（但不能生于1979年）”，因此，也可以转化为“”对其进行符号化。3解 设p：李刚会拳击，q：李春会唱歌。命题符号化(pq)(pq)。而(pq)(pq)(pq)(pq)(pq)pqpq因此，李刚会拳击并且李春不会唱歌。 4解 A的极小项对应于其真值表中的成真赋值0001，0110，1000，1001，1010，1100，1101，1111。成真赋值对应二进制数转化为十进制数就是A的极小项的下标。由此可得，A的极小项为： ；。 相应的，A的极大项对应于其真值表中的成假赋值，成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得，A的极大项为： ；。 由问题得到了A的极小项和极大项，于是与A等值的主析取范式和主合取范式可以直接得到，分别为：；。 从A的主析取范式出发，进行等值演算化简，可得析取范式的最简形式：(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(qrs)(pqr)(pqrs)(pqr)(pr)(pqrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqs) 5 证明 6解 公式的真值表如表2