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

'第一章命题逻辑习题1.11．解⑴不是陈述句，所以不是命题。⑵x取值不确定，所以不是命题。⑶问句，不是陈述句，所以不是命题。⑷惊叹句，不是陈述句，所以不是命题。⑸是命题，真值由具体情况确定。⑹是命题，真值由具体情况确定。⑺是真命题。⑻是悖论，所以不是命题。⑼是假命题。2．解⑴是复合命题。设p：他们明天去百货公司；q：他们后天去百货公司。命题符号化为p∨q。⑵是疑问句，所以不是命题。⑶是悖论，所以不是命题。⑷是原子命题。⑸是复合命题。设p：王海在学习；q：李春在学习。命题符号化为p∧q。→⑹是复合命题。设p：你努力学习；q：你一定能取得优异成绩。pq。⑺不是命题。⑻不是命题⑼。是复合命题。设p：王海是女孩子。命题符号化为：¬p。3．解⑴如果李春迟到了，那么他错过考试。⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。⑶李春错过考试当且仅当他迟到了。⑷如果李春迟到了并且错过了考试，那么他没有通过考试。4．解⑴¬p→(q∨r)。⑵p→q。⑶q→p。⑷q→p。习题1.21．解⑴是1层公式。⑵不是公式。⑶一层：p∨q，¬p二层：¬p↔q所以，(p∨q)→(¬p↔q)是3层公式。⑷不是公式。⑸(p→q)∧¬(¬q↔(q→¬r))是5层公式，这是因为一层：p→q，¬q，¬r二层：q→¬r三层：¬q↔(q→¬r)¬¬↔→¬四层：(q(qr))∨∧2．解⑴A=(pq)q是2层公式。真值表如表2-1所示：表2-1pqp∨qA0000011110101111⑵A=q∧(p→q)→p是3层公式。真值表如表2-2所示：1 表2-2pqp→qq∧(p→q)A00101011101000111111⑶A=(p∧q∧r)→(p∨q)是3层公式。真值表如表2-3所示：表2-3pqrp∧qp∧q∧rp∨qA00000010010001010001101100111000011101001111010111111111⑷A=(p∨q)∧(¬p∨r)∧(q∨r)是4层公式。真值表如表2-4所示：3．解⑴A=(¬p∧¬q)∨p真值表如表2-5所示：表2-5pq¬p¬q¬p∧¬qA001111011000100101110001所以其成真赋值为：00，10，11；其成假赋值为01。⑵A=r→(p∧q)真值表如表2-6所示：表2-6pqrp∧qA00001001000100101100100011010011011111112 所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。⑶A=(p→q)↔(p∨¬q)真值表如表2-7所示，所以其成真赋值为：00，11；成假赋值为：01，10，。4．解⑴设A=p∨¬(p∧q)，其真值表如表2-8所示：表2-8pqp∧q¬(p∧q)A00011010111001111101故A=p∨¬(p∧q)为重言式。∧∧¬∨⑵设A=(pq)(pq)，其真值表如表2-9所示：表2-9pqp∧qp∨q¬(p∨q)A000010010100100100111100故A=(p∧q)∧¬(p∨q)为矛盾式。⑶设A=(p→q)↔(¬p↔q)，其真值表如表2-10所示：表2-10pq¬p¬p↔qp→qA001010011111100100110010→↔¬↔故A=(pq)(pq)为可满足式。⑷设A=((p→q)∧(q→r))→(p→r)，其真值表如表2-11所示：表2-11pqrp→qq→r(p→q)∧(q→r)p→rA000111110011111101010011011111111000100110101011110100013 11111111故A=((p→q)∧(q→r))→(p→r)为重言式。习题1.31．解⑴真值表如表2-12所示：表2-12pq¬p¬q¬p∧¬qp∨q¬(p∨q)0011101011001010010101100010由真值表可以看出¬(p∨q)和¬p∧¬q所在的列相应填入值相同，故等值。⑵真值表如表2-13所示：表2-13pq¬qp∧qp∧¬q(p∧q)∨(p∧¬q)001000010000101011110101由真值表可以看出p和(p∧q)∨(p∧¬q)所在的列相应填入值相同，故等值。⑶真值表如表2-14所示：表2-14pq¬p¬qp→qp→¬q(p→q)∧(p→¬q)0011111011011110010101100100¬→∧→¬由真值表可以看出p和(pq)(pq)所在的列相应填入值相同，故等值。⑷真值表如表2-15所示：pqrq→rp→(q→r)p∧q(p∧q)→r00011010011101010010101111011001101101110111000104 1111111表2-15由真值表可以看出p→(q→r)和(p∧q)→r所在的列相应填入值相同，故等值。2．证明⑴(p∧q)∨¬(¬p∨q)⇔(p∧q)∨(p∧¬q)⇔p∧(q∨¬q)⇔p。→∧→⇔¬∨∧¬∨⑵(pq)(qp)(pq)(qp)⇔¬∧¬∨¬∧∨∧¬∨∧(pq)(pp)(qq)(qp)⇔(p∧q)∨(¬p∧¬q)。⑶由⑵可得，¬(p↔q)⇔¬((p∧q)∨(¬p∧¬q))⇔(¬p∨¬q)∧(p∨q)⇔(q→¬p)∧(¬p→q)⇔¬p↔q。→→⇔¬∨¬∨⑷p(qr)p(qr)⇔¬∨¬∨⇔→→q(pr)q(pr)。⑸p→(q∨r)⇔¬p∨(q∨r)⇔(¬p∨q)∨r⇔¬(p∧¬q)∨r⇔(p∧¬q)→r⑹(p→q)∧(r→q)⇔(¬p∨q)∧(¬r∨q)⇔(¬p∧¬r)∨q⇔(p∨r)→q3．解⑴¬(p→¬q)⇔¬(¬p∨¬q)⇔p∧q⑵¬(¬p→¬q)⇔¬(p∨¬q)⇔¬p∧q⑶¬(p↔¬q)⇔¬((p→¬q)∧(¬q→p))⇔¬(p→¬q)∨¬(¬q→p)⇔(p∧q)∨(¬p∧¬q)⇔p↔q。⑷同理可证¬(¬p↔q)⇔p↔q。4．解⑴与习题2.2第4（4）相同。⑵真值表如表2-16所示：表2-16pq¬p¬qp→q¬q→¬pA0011111011011110010011100111所以公式是重言式。⑶真值表如表2-17所示，所以公式是矛盾式。表2-17pq¬p¬q¬p∨qp∧¬qA0011100011010010010105 1100100⑷真值表如表2-18所示，所以公式是重言式。表2-18pqrp∧qp∧q∧rA000001001001010001011001100001101001110101111111⑸真值表如表2-19所示，所以公式仅为可满足式。表2-19pq¬p¬p→q¬(¬p→q)A001011011101100100110100⑹真值表如表2-20所示，所以公式是重言式。表2-20pqrp→qr→qp∧r(p→q)∧(r→q)(p∧r)→qA0001101110011000110101101110111101111000100111010010011101101111111111115．解⑴设p：他努力学习；q：他会通过考试。则命题符号化p→q。其否定¬(p→q)⇔p∧¬q。所以语句的否定：他学习很努力但没有通过考试。↔q⑵设p：水温暖；q：他游泳。则命题符号化p。其否定¬(p↔q)⇔p↔¬q。所以语句的否定：当且仅当水不温暖时他游泳。⑶设p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化p→(q∧¬r)¬→∧¬⇔¬¬∨∧¬其否定(p(qr))(p(qr))⇔p∧¬(q∧¬r)⇔p∧(¬q∨r)所以语句的否定：天冷并且他不穿外套或者穿衬衫。⑷设p：他学习；q：他将上清华大学；r：他将上北京大学。则命题符号化p→(q∨r)6 其否定¬(p→(q∨r))⇔¬(¬p∨(q∨r))⇔p∧¬q∧¬r所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学。6．解设p：张三说真话；q：李四说真话；r：王五说真话。则：p↔¬q,q↔¬r(⇔¬q↔r),r↔(¬p∧¬q)为真,因此p↔(¬p∧¬q)⇔(p∧¬p∧¬q)∨(¬p∧(p∨q))⇔¬p∧q为真。因此，p为假，q为真，所以r为假。故张三说谎，李四说真话，王五说谎。7．解设p：甲得冠军；q：乙得亚军；r：丙得亚军；s：丁得亚军。前提：p→(q∨r)，q→¬p，s→¬r，p结论：¬s证明p→(q∨r)为真，其前件p为真，所以q∨r为真，又q→¬p为真，其后件¬p为假，所以要求q为假，所以r为真。又s→¬r为真，其后件¬r为假，所以要求s为假，故¬s为真。习题1.41．解⑴设p：明天下雨；q：后天下雨。命题符号化p∨q。⑵设p：明天我将去北京；q：明天我将去上海。命题符号化p∨q。2．解⑴(p→q)∨p⇔((p→q)∧¬p)∨(¬(p→q)∧p)⇔((¬p∨q)∧¬p)∨(¬(¬p∨q)∧p)⇔¬p∨(p∧¬q∧p)⇔¬p∨¬q⑵p↓(q∨p)⇔¬(p∨(q∨p))⇔¬(p∨(q∧¬p)∨(¬q∧p))⇔¬(p∨(q∧¬p))⇔¬(p∨q)⇔¬p∧¬q⑶(p↑q)↓r⇔¬((p↑q)∨r)⇔¬(¬(p∧q)∨r)⇔p∧q∧¬r3．证明因为，{¬,∨,∧,→,↔}是功能完备联结词集，所以，含有{¬,∨,∧,→,↔}外的其他联结词的公式均可以转换为仅含{¬,∨,∧,→,↔}中的联结词的公式。p→q⇔¬p∨q又因为p↔q⇔(p→q)∧(q→p)⇔(¬p∨q)∧(¬q∨p)7 即含有→,↔的公式均可以转换为仅含{¬,∨,∧}中的联结词的公式。因此，含{¬,∨,∧}外其他联结词的公式均可以转换为仅含{¬,∨,∧}中的联结词的公式。故{¬,∨,∧}是功能完备联结词集。↑4．证明{¬,∧}是极小功能完备集，因而只需证明{¬,∧}中的每个联结词都可以用表示，就说明{↑}是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，¬p⇔¬(p∧p)⇔p↑p，p∧q⇔¬¬(p∧q)⇔¬(p↑q)⇔(p↑q)↑(p↑q)。对于证明{↓}是极小功能完备集，可类似证明。习题1.51．解⑴¬(p∧¬q)∨(¬p∧q)；⑵(p∧(¬(q∨r)∨(p∧¬r))∨¬p2．解⑴(p→q)→(r→s)⇔¬(¬p∨q)∨(¬r∨s)⇔(p∧¬q)∨¬r∨s即为其析取范式。(p→q)→(r→s)⇔(p∧¬q)∨¬r∨s⇔(p∨¬r∨s)∧(¬q∨¬r∨s)即为其合取范式。¬p∧(q↔r)⇔¬p∧(¬q∨r)∧(¬r∨q)⑵即为其合取范式。¬p∧(q↔r)⇔¬p∧((q∧r)∨(¬q∧¬r))⇔(¬p∧q∧r)∨(¬p∧¬q∧¬r)即为其析取范式。⑶(p∨q)∧¬r即为其合取范式。(p∨q)∧¬r⇔(p∧¬r)∨(q∧¬r)为其析取范式。p→(q→r)⇔¬p∨¬q∨r⑷即为其析取范式和合取范式。3．解⑴p∧(¬p∨q)⇔(p∨(¬q∧q))∧(¬p∨q)⇔(p∨¬q)∧(p∨q)∧(¬p∨q)⇔∏(0,1,2)即为其主合取范式。其主析取范式为∑3⇔p∧q。⑵(¬p→q)∨(¬p∧¬q)⇔(p∨q)∨¬(p∨q)⇔1。∑¬∧¬∨¬∧∨∧¬∨∧故其主析取范式为(0,1,2,3)=(pq)(pq)(pq)(pq)。⑶((p∨q)→r)→p⇔¬(¬(p∨q)∨r)∨p8 ⇔((p∨q)∧¬r)∨p⇔(p∨q)∧(p∨¬r)⇔((p∨q)∨(r∧¬r))∧((p∨¬r)∨(q∧¬q))⇔(p∨q∨r)∧(p∨q∨¬r)∧(p∨q∨¬r)∧(p∨¬q∨¬r)⇔∏(0,1,3)即为其主合取范式。其主析取范式为∑(2,4,5,6,7)⇔(¬p∧q∧¬r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)。⑷(p→q)→(r→s)⇔¬(¬p∨q)∨(¬r∨s)⇔(p∧¬q)∨(¬r∨s)⇔(p∨¬r∨s)∧(¬q∨¬r∨s)⇔(p∨q∨¬r∨s)∧(p∨¬q∨¬r∨s)∧(p∨¬q∨¬r∨s)∧(¬p∨¬q∨¬r∨s)⇔∏(2,6,14)即为其主合取范式。其主析取范式为∑(0,1,3,4,5,7,8,9,10,11,12,13,15)。4．解⑴真值表如表2-21所示,所以其极小项是p∧¬q，极大项为p∨q，p∨¬q，¬p∨¬q。表2-21pqp→q¬(p→q)0010011010011110其主析取范式是：p∧¬q，主合取范式为：(p∨q)∧(p∨¬q)∧(¬p∨¬q)。⑵真值表如表2-222所示,所以其极小项是¬p∧q,p∧¬q,p∧q,极大项为p∨q。表2-22pqp∨qp→q¬(p→q)¬(p→q)∨(p∨q)000100011101101011111101¬∧∨∧¬∨∧∨其主析取范式是：(pq)(pq)(pq)，主合取范式为：pq。⑶真值表如表2-23所示，所以其极小项是¬p∧q∧r,p∧¬q∧¬r,p∧¬q∧r,p∧q∧¬r,p∧q∧r,表2-23pqr¬p¬p∧q∧rp∨(¬p∧q∧r)0001000011000101000111119 100001101001110001111001极大项为p∨q∨r，p∨q∨¬r，p∨¬q∨r。其主析取范式是：(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)，主合取范式为：(p∨q∨r)∧(p∨q∨¬r)∧(p∨¬q∨r)。⑷真值表如表2-24所示,所以其极小项为¬p∧¬q∧r,¬p∧q∧r,p∧¬q∧¬r,p∧¬q∧r,p∧q∧r,而极大项分为p∨q∨r，p∨¬q∨r，¬p∨¬q∨r.主合取范式为(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r),主析取范式为(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧¬r,)∨(p∧¬q∧r)∨(p∧q∧r)。表2-24pqrp→q(p→q)→r0001000111010100111110001101011101011111¬∨∧¬¬∧¬⇔¬∨∧∨5．解⑴(pq)((pq))(pq)(pq)⇔⇔¬∧∨∧q(pq)(pq)，故⑴为可满足式。⑵((p→q)∧(q→r))→(p→r)⇔¬¬∨((pq)∧¬∨(qr))∨¬∨(pr)⇔(p∧¬∨q)(q∧¬∨¬∨r)(pr)⇔(p∧¬∧qr)∨(p∧¬∧¬qr)∨(p∧q∧¬r)∨¬∧(pq∧¬r)∨¬∧(pq∧r)∨¬∧(pq∧¬r)∨¬∧¬∧(pqr)∨¬∧¬∧¬(pqr)∨(p∧∧qr)(∨p∧¬∧qr)(∨¬∧∧pqr)(∨¬∧¬∧pqr)⇔∑(0,1,2,3,4,5,6,7)故⑵为重言式。⑶¬(p∨(q∧r))↔((p∨q)∧(p∨r))⇔¬(p∨(q∧r))↔(p∨(q∧r))⇔∨∧∨∨∧∧¬∨∧∨¬∨∧(p(qr))(p(qr))(p(qr))(p(qr))⇔(p∨(q∧r))∧¬(p∨(q∧r))⇔(p∨(q∧r))∧¬p∧¬(q∧r)⇔¬∧∧∧¬∨¬⇔(pqr)(qr)0。故⑶为矛盾式。10 ⑷((p→q)∨(r→s))→((p∨r)→(q∨s))⇔¬¬∨((pq)∧¬¬∨(rs))(∨¬∧¬∨∨pr)qs⇔((p∧¬q)∧(r∧¬s))∨¬∧¬(pr)∨q∨s⇔(p∧¬∧∧¬∨¬∧∧¬∧qrs)(pqrs)(∨¬∧∧¬∧¬pqrs)∨¬∧¬∧¬∧(pqrs)∨¬∧¬∧¬∧¬(pqrs)∨(p∧q∧∧rs)∨(p∧q∧∧¬rs)∨(p∧q∧¬∧rs)∨(p∧q∧¬∧¬rs)∨¬∧∧∧(pqrs)(∨¬∧∧∧¬∨¬∧∧¬∧pqrs)(pqrs)∨¬∧(pq∧¬∧¬rs)∨(p∧q∧∧rs)∨(p∧q∧¬∨rs)∨(p∧¬∧∧qrs)(∨p∧¬∧¬∧qrs)(∨¬∧∧∧pqrs)∨¬∧(pq∧¬∧rs)∨¬∧¬∧∧(pqrs)∨¬∧¬∧¬∧(pqrs)⇔∑(0,1,3,4,5,6,7,9,10,11,12,13,14,15)故仅为可满足式。6．证明⑴右边已经是主合取范式。而左边主合取范式已是¬p∧¬q，因此，¬(p∨q)⇔¬p∧¬q，证毕。∨∧∨¬⇔∨∧¬⇔∨∧∨¬⑵右边(pq)(pq)已经是主合取范式。pp(qq)(pq)(pq)。因此，p⇔(p∧q)∨(p∧¬q)。→→⇔¬∨¬∨⇔¬∨¬∨⇔¬∧∨⑶左边p(qr)p(qr)pqr，而右边(p∧q)→r(pq)r⇔¬p∨¬q∨r，因此，p→(q→r)⇔(p∧q)→r。习题1.61．解设p：这里有演出；q：这里通行是困难的；r：他们按照指定时间到达。前提：p→q,r→¬q,r结论：¬p证明①rP②r→¬qP③¬qT①②假言推理④p→qP⑤¬pT③④拒取式2．⑴证明①sP②s→pP11 ③pT①②假言推理④p→qP⑤qT③④假言推理⑵证明①rP附加前提引入②r→qP③qT①②假言推理④p→¬qP⑤¬pT③④拒取式⑥¬p→sP⑦sT⑤⑥假言推理⑧r→sT①⑦CP⑶证明①pP否定结论引入②p→qP③qT①②假言推理④q→rP⑤rT③④假言推理⑥¬r∧sP⑦¬rT⑥化简⑧r∧¬rT⑤⑦合取⑷证明①pP附加前提引入②¬p∨qP③q①②析取三段论④r→¬qP⑤¬r③④拒取式⑥p→¬r①⑥CP⑸证明①pP附加前提引入②p→(q→r)P③q→rT①②假言推理④qP附加前提引入⑤rT③④假言推理⑥(r∧s)→tP⑦¬r∨¬s∨tT⑥蕴涵等价式⑧¬s∨tT⑤⑦析取三段论⑨¬h→(s∧¬t)P⑩¬s∨t→hT⑨假言易位⒒hT⑧⑩假言推理⒓q→hT④⒒CP13.p→(q→h)T①⒓CP3．解推理不正确。在①到②化简时，只能对整个公式进行而不是子公式。4．解正确。12 ⑴P，⑵P附加前提引入；⑶T①②析取三段论；⑷P；⑸T③④假言推理；⑹P；⑺T⑤⑥假言推理；⑻T②⑦CP。5．解设p：张三努力工作，q：李四高兴，r：王五高兴，s：刘六高兴前提：p→(q∨r)，q→¬p，s→¬r结论：p→¬s证明：①pP附加前提引入②p→(q∨r)P③q∨rT①②假言推理④q→¬pP⑤¬qT①④拒取式⑥rT③⑤析取三段论⑦s→¬rP⑧¬sT⑥⑦拒取式⑨p→¬sT①⑧CP6．解设：p：天下雪；q：马路结冰；r：汽车开得快；s：马路塞车。前提：p→q，q→¬r，¬r→s，¬s结论：¬p证明①p→qP②q→¬rP③p→¬r①②推理三段论④¬r→sP⑤p→s③④推理三段论⑥¬sP⑦¬p⑤⑥拒取式复习题11．解⑴设p：3是偶数，q：中国人的母语是汉语。命题符号化p→q。⑵设p：你抽烟，q：你很容易得病。命题符号化p→q。⑶设p：今天是星期一，q：明天才是星期二。命题符号化q→p。⑷设p：李春这个学期《离散数学》考了100分。q：李春这个学期《数据结构》考了100分。命题符号化p∧q。⑸设p：下雪路滑，q：他迟到了。命题符号化q→p。⑹设p：经一事，q：长一智。命题符号化p→q。⑺设p：一朝被蛇咬，q：十年怕井绳。命题符号化p→q。⑻设p：以物喜，q：以己悲。命题符号化¬p∧¬q。2.解命题中的“或”是不可兼或，因此，可以直接用“p∨q”符号化；根据联结词的性质及其之间的转换关系，可知命题“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于1980年）或生于1980年（但不能生于1979年）”，因此，也可以转化为“(p∧¬q)∨(¬p∧q)”对其进行符号13 化。¬∨¬∧¬→3．解设p：李刚会拳击，q：李春会唱歌。命题符号化(pq)(pq)。而(¬p∨¬q)∧¬(p→q)⇔(¬p∨¬q)∧¬(¬p∨q)⇔(¬p∨¬q)∧p∧¬q⇔p∧¬q因此，李刚会拳击并且李春不会唱歌。4．解⑴A的极小项对应于其真值表中的成真赋值0001，0110，1000，1001，1010，1100，1101，1111。成真赋值对应二进制数转化为十进制数就是A的极小项的下标。由此可得，A的极小项为：m=¬∧¬∧¬∧pqrs；m=¬∧∧∧pqrs；m=p∧¬∧¬∧¬qrs；168m=p∧¬∧¬∧qrs；m=p∧¬∧∧¬qrs；m=p∧q∧¬∧¬rs；91012m=p∧q∧¬∧rs；m=p∧q∧∧rs。1315相应的，A的极大项对应于其真值表中的成假赋值，成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得，A的极大项为：M=p∨q∨∨rs；M=p∨q∨¬∨rs；M=p∨∨¬∨¬qrs；023M=p∨¬∨∨qrs；M=p∨¬∨∨¬qrs；M=p∨¬∨¬∨¬qrs；457M=¬∨pq∨¬∨¬rs；M=¬∨¬∨¬∨pqrs。1114⑵由问题⑴得到了A的极小项和极大项，于是与A等值的主析取范式和主合取范式可以直接得到，分别为：∑(1,6,8,9,10,12,13,15)；∏(0,2,3,4,5,7,11,14)。⑶从A的主析取范式出发，进行等值演算化简，可得析取范式的最简形式：(¬p∧¬q∧¬r∧s)∨(¬p∧q∧r∧s)∨(p∧¬q∧¬r∧¬s)∨(p∧¬q∧¬r∧s)∨(p∧¬q∧r∧¬s)∨(p∧q∧¬r∧¬s)∨(p∧q∧¬r∧s)∨(p∧q∧r∧s)⇔(¬p∧¬q∧¬r∧s)∨(q∧r∧s)∨(p∧¬q∧¬r)∨(p∧¬q∧r∧¬s)∨(p∧q∧¬r)⇔(p∧¬r)∨(¬p∧¬q∧¬r∧s)∨(q∧r∧s)∨(p∧¬q∧r∧¬s)⇔(p∧¬r)∨(¬q∧¬r∧s)∨(q∧r∧s)∨(p∧¬q∧r∧¬s)⇔(p∧¬r)∨(¬q∧¬r∧s)∨(q∧r∧s)∨(p∧¬q∧¬s)5．证明⑴(p→q)∧(r→q)⇔¬∨(pq)(∧¬∨rq)⇔¬∧¬∨(pr)q⇔¬(p∨r)∨q⇔(p∨r)→q⑵p→(q→r)⇔¬∨¬∨p(qr)⇔¬∨¬∨q(pr)⇔q→(p→r)⑶(p∨q)∧¬(p∧q)⇔¬¬((p∨q)∨(p∧q))⇔¬¬∧¬∨((pq)(p∧q))⇔¬(p↔q)14 ⑷(p∧q∧→rs)∧(r→p∨q∨s)⇔¬((p∧∧qr)∨s)(∧¬∨r(p∨∨qs))⇔((¬∨¬∨¬pqr)∧¬∨(rp∨q))∨s⇔¬∨¬∨¬(r((pq)(∧p∨q)))∨s⇔¬(r∧¬¬∨¬((pq)∧(p∨q)))∨s⇔¬(r∧((p∧q)∨¬∧¬(pq)))∨s⇔(r∧(p↔q))→s6．解⑴公式的真值表如表2-27所示：表2-27pq¬p¬qp→¬q¬q→¬p(p→¬q)∧(¬q→¬p)0011111011011110011001100010从真值表可见，公式所在列的填入值有1也有0，故仅为可满足式。(p→¬q)∧(¬q→¬p)⇔(¬p∨¬q)∧(q∨¬p)⇔∏(2,3)为其主合取范式，可见公式仅为可满足式。⑵公式真值表如表2-28所示：表2-28pqrp∨q∨rp→(p∨q∨r)0000100111010110111110011101111101111111→∨∨⇔¬∨∨∨⇔⇔∑p(pqr)ppqr1(0,1,2,3,4,5,6,7)从真值表可见，公式所在的列的填入值均为1，等值演算，以及求出的主析取范式均说明公式是重言式。⑶A=((p→q)∧(q→r))→(p→r)真值表见习题2.2第4(4)题。((p→q)∧(q→r))→(p→r)⇔¬((¬p∨q)∧(¬q∨r))∨(¬p∨r)⇔(p∧¬q)∨(q∧¬r))∨¬p∨r⇔1.15 从真值表可见，公式所在的列的填入值均为1，由等值演算，以及求出的主析取范式均说明公式是重言式。7．⑴证明①pP附加前提引入②p→(q→r)P③q→rT①②假言推理④qP附加前提引入⑤q→(r→s)P⑥r→sT④⑤假言推理⑦q→sT③⑥假言三段论⑧p→(q→s)T①⑦CP⑵证明①¬wP②u→wP③¬uT①②拒取式④¬s∨uP⑤¬sT③④析取三段论⑥¬r∨sP⑦¬rT⑤⑥析取三段论⑧(p∨q)→rP⑨¬(p∨q)T⑦⑧拒取式⑩¬p∧¬q)T⑨德⋅摩根律⑶证明①pP附加前提引入②p→q∨rP③q∨rT①②假言推理④q→¬pP⑤¬qT①④拒取式⑥rT③⑤析取三段论⑦s→¬rP⑧¬sT⑥⑦拒取式⑨p→¬sT①⑧CP8．解①p∧rP②pT①化简③p→qP④qT②③假言推理⑤¬(q∨s)P⑥¬q∧¬sT⑤德⋅摩根律⑦¬qT⑥化简⑧¬q∧qT④⑦合取由⑧得到矛盾，可见p→q，¬(q∨s)，p∧r不能同时成立。9．解设p：小王曾经到过受害人的房间，q：小王11点以前离开，r：小王犯了谋杀罪，s：看门人看到小王。符号化：(((p∧¬q)→r)∧p∧(q→s)∧¬s)⇒r。16 ⑴形式构造推理证明前提：(p∧¬q)→r，p，q→s，¬s结论：r证明①¬sP②q→sP③¬qT①②拒取式④pP⑤p∧¬qT③④合取⑥(p∧¬q)→rP⑦rT⑤⑥假言推理⑵真值表技术：真值表如表2-30所示，设A=(((p∧¬q)→r)∧p∧(q→s)∧¬s)。表2-29由pqrs¬q¬sp∧¬q(p∧¬q)→rq→sA真值表0000110110可以看0001100110出：0010110111∧¬(((p0011100111→q)r)0100010100∧p∧(q0101000110→s)∧¬⇔0110010101s)r，0111000111所以，∧¬1000111010(((p1001101010q)→r)∧p∧(q10101111111011101111→s)∧¬⇒1100010100s)r成立。1101000110⑶1110010101等值演1111000111算方法(((p∧¬q)→r)∧p∧(q→s)∧¬s)→r⇔¬((¬(p∧¬q)∨r)∧p∧(¬q∨s)∧¬s)∨r⇔¬((¬(p∧¬q)∨r)∧p∧(¬q∧¬s))∨r⇔(¬(¬(p∧¬q)∨r)∨¬p∨¬(¬q∧¬s))∨r⇔((p∧¬q∧¬r)∨¬(p∧¬q∧¬s))∨r⇔1。由此可以说明(((p∧¬q)→r)∧p∧(q→s)∧¬s)→r为重言式，即(((p∧¬q)→r)∧p∧(q→s)∧¬s)⇒r成立。10．解逻辑学家手指A门问旁边的一名强盗（A）说：“这扇门是生门，他（指强盗B）将回答‘是’，他的回答对吗？”设p：强盗A回答“对”；q：强盗B回答“对”；r：这扇门（A）是生门。因为，两个强盗一个总说真话，而另一个强盗一个总说假话，因此该问题符号化为：(¬p↔q)∧r。(¬p↔q)∧r⇔((¬p∧q)∨(p∧¬q))∧r⇔(¬p∧q∧r)∨(p∧¬q∧r)17 逻辑学家的提问可知，r和q都为真，由公式可以看出这时¬p为真，即p为假。所以，当被问强盗A回答“否”，则逻辑学家开启所指的门从容离去。当被问强盗A回答“对”，则逻辑学家开启另一扇门从容离去。第二章谓词逻辑习题2.11．解⑴个体：离散数学；谓词：…是一门计算机基础课程。⑵个体：田亮；谓词：…是一名优秀的跳水运动员。⑶个体：大学生；谓词：…要好好学习计算机课程；量词：所有。⑷个体：推理；谓词：…是能够由计算机来完成的；量词：一切。2．解⑴设F(x)：x是舞蹈演员；a：小芳。命题符号化：F(a)。⑵设F(x)：x是一位有名的哲学家；a：苏格拉底。命题符号化：F(a)。⑶设F(x)：x作完了他的作业家；a：张三。命题符号化：F(a)。⑷设F(x)：x身体很好；a：我。命题符号化：F(a)。3．解⑴选取个体域为整数集合。设F(x)：x的平方是奇数；G(x)：x是奇数。命题符号化：F(x)→G(x)。⑵选取个体域为所有国家的集合。设F(x)：x在南半球；G(x)：x在北半球。命题符号化：∃xF(x)∧∃xG(x)。⑶选取个体域为所有人的集合。设F(x)：x在中国居住；G(x)：x是中国人。命题符号化：¬∀x(¬F(x)→¬G(x))⑷选取个体域为所有人的集合。设M(x)：x是艺术家；F(x)：x是导演；G(x)：x是演员。命∃∧∧题符号化：x(M(x)F(x)G(x))。⑸选取个体域为所有猫的集合。设M(x)：x是好猫；F(x)：x捉耗子。命题符号化：∃x¬M(x)∧∀x(F(x)→M(x))。4．解⑴①设F(x)：x喜欢开汽车；G(x)：x喜欢骑自行车。命题符号化：∃xF(x)∧∃xG(x)。②设F(x)：x喜欢开汽车；G(x)：x喜欢骑自行车；M(x)：x是人。命题符号化：∃x(M(x)∧F(x))∧∃x(M(x)∧G(x))。⑵①设F(x)：x必须学好数学。命题符号化：∀xF(x)。②设F(x)：x必须学好数学；M(x)：x是学生。命题符号化：∀x(M(x)→F(x))。18 ⑶①设F(x)：x的平方是质数；M(x)：x是质数。命题符号化：∀x(M(x)→¬F(x))。②同①。③设F(x)：x的平方是质数。命题符号化：∀x(¬F(x))。习题2.2∀→1．解⑴x的辖域为P(x)Q(x)，个体变元x是约束变元。⑵∀x的辖域为P(x)→∃yQ(x,y)，∃y的辖域为Q(x,y)，个体变元x是约束变元，个体变元y是约束变元。⑶∀x的辖域为F(x,y)，其中个体变元x是约束变元，个体变元y是自由变元；∃的辖域为Q(x,y)，其中个体变元x是自由变元，个体变元y是约束变元。2．解⑴∀∃stPsz((,)→Qt())↔Sxy(,)。⑵Mxy(,)→∀sPsy((,)∨∀zQsz(,))。3．解⑴(∀xP(x)∧∃yQ(x))→F(s,z)；∃→∀∧∧∀∃⑵y(P(s,y)(zQ(s,z)R(s,y,v)))xrS(x,t,r)。4．解⑴S(x),∃xS(x),S(x)∧∃xS(x)的真值分别为：0，1，0。⑵S(x),∃xS(x),S(x)∧∃xS(x)的真值分别为：0，1，0。⑶S(x),∃xS(x),S(x)∧∃xS(x)的真值分别为：1，1，1。⑷S(x),∃xS(x),S(x)∧∃xS(x)的真值分别为：0，0，0。5．解⑴0。⑵1。⑶0。∃¬∃¬∃→∀6．解⑴设I为任意解释，其个体域为D，若xP(x)为真，即xP(x)为假，则xP(x)xP(x)为真；若∃xP(x)为假，即¬∃xP(x)为真，则就是说在个体域中不存在使得P(x)为真的个体，故∀xP(x)为假，即¬∃xP(x)→∀xP(x)为假。因此¬∃xP(x)→∀xP(x)仅为可满足式。⑵设I为任意解释，其个体域为D，若¬∀xA(x)为假,则∀xA(x)为真，就是说对于个体域中任意一个个¬∃¬¬∀∀体A(x)均为真，那么A(x)必为假，所以x(A(x))必为假；若xA(x)为真，即xA(x)为假，则就是说对于¬∃¬个体域中至少存在一个体使A(x)均为假，那么对于个体域中至少存在一个个体使A(x)为真，所以x(A(x))必为真，总之¬∀xA(x)↔∃x(¬A(x))对于个体域中任意一个个体必为真，即其为逻辑有效式。⑶设I为任意解释，其个体域为D，若∃x(P(x)∧Q(x))为真，即是说在个体域中至少存在一个个体使得P(x)和Q(x)同时为真，此时∃x(P(x)→¬Q(x))可真可假，所以，∃x(P(x)∧Q(x))→∃x(P(x)→¬Q(x))可真可假。因此，(∃x(P(x)∧Q(x)))→(∃xP(x)→¬Q(x))仅为可满足式。习题2.31．解⑴¬(∃xA(x)→∀xB(x))⇔¬(¬∃xA(x)∨∀xB(x))⇔∃xA(x)∧¬∀xB(x))⇔∃xA(x)∧∃x¬B(x))⑵¬(∀xA(x)∧B(x)∨∃xC(x))⇔¬∀xA(x)∨¬B(x)∧¬∃xC(x)⇔∃¬∨¬∧∀¬xA(x)B(x)xC(x)⑶¬((∃xA(x)↔∀xB(x))∧∀xC(x))⇔¬((¬∃xA(x)∨∀xB(x))∧(∃xA(x)∨¬∀xB(x)))∨¬∀xC(x)⇔(∃xA(x)∧∃x¬B(x))∨(∀x¬A(x)∧∀xB(x))∨∃x¬C(x)。2．证明⑴∀x(P(x)→Q(x))→(∃xP(x)→∃xQ(x))⇔¬∀¬∨∨¬∃∨∃⇔∃∧¬∨∀¬∨∃x(P(x)Q(x))(xP(x)xQ(x))x(P(x)Q(x))xP(x)xQ(x)19 ⇔∧¬∨∧¬∨∧¬∨¬∧¬∧¬((P(1)Q(1))((P(2)Q(2))((P(3)Q(3)))(P(1)P(2)P(3))∨Q(1)∨Q(2)∨Q(3)⇔((P(1)∨Q(1))∨((P(2)∨Q(2))∨((P(3)∨Q(3)))∨(¬P(1)∧¬P(2)∧¬P(3))⇔(P(1)∨P(2)∨P(3))∨(Q(1)∨Q(2)∨Q(3))∨¬(P(1)∨P(2)∨P(3))⇔1。∀→→∃→∃故x(P(x)Q(x))(xP(x)xQ(x))为逻辑有效式。∃→∀→∀→⇔¬¬∃∨∀∨∀¬∨⑵(xP(x)xQ(x))x(P(x)Q(x))(xP(x)xQ(x))x(P(x)Q(x))⇔∃∧∃¬∨∀¬∨(xP(x)xQ(x))x(P(x)Q(x))⇔((P(1)∨P(2)∨P(3))∧(¬Q(1)∨¬Q(2)∨¬Q(3))∨((¬P(1)∨Q(1))∧¬P(2)∨Q(2))∧¬P(2)∨Q(2)))⇔∧¬∨∧¬∨∧¬∨∧¬…[(P(1)Q(1))(P(2)Q(2))(P(3)Q(3))(P(1)Q(2))]∨¬∧∧¬∧¬∧¬∧¬((P(1)Q(1))(P(2)Q(2))(P(1)Q(1)))⇔(¬(P(1)∧Q(1))∨(P(1)∧¬Q(1))∨(P(2)∧¬Q(2))∨(P(3)∧¬Q(3))∨(P(1)∧¬Q(2))…)∧(¬(P(2)∧¬Q(2))∨(P(1)∧¬Q(1))∨(P(2)∧¬Q(2))∨(P(3)∧¬Q(3))∨(P(1)∧¬Q(2))…)∧(¬(P(1)∧¬Q(1))∨(P(1)∧¬Q(1))∨(P(2)∧¬Q(2))∨(P(3)∧¬Q(3))∨(P(1)∧¬Q(2))…)⇔∧∧111。⑶∀xAx(()∧Bx())↔∀(xAx()∧∀xBx())⇔(((1)A∧B(1))∧((2)A∧B(2))∧((3)A∧B(3)))↔(((1)A∧A(2)∧A(3))∧((1)B∧B(2)∧B(3)))⇔1习题2.41．解⑴④错。在一个逻辑推理过程中，若同时用到ES和US，并且选用代替的个体变元相同时应先用ES，再用US。⑵②错，在用UG规则时，引入的个体变元在原来的公式中不能自由出现过。③错。⑶④错，在用两次ES规则时，引入的个体常元不能是一样的。2．⑴证明①∀x¬Q(x)P②¬Q(y)T①US③∀x(¬P(x)→Q(x))P④¬P(y)→Q(y)T③US⑤P(y)T②④拒取式⑥∃xP(x)T⑤EG⑵证明∀①xP(x)P附加前提引入②P(c)T①US③∀x(P(x)→Q(x))P④P(c)→Q(c)T③US⑤Q(c)T②④假言推理⑥∀xQ(x)T⑤UG⑦∀xP(x)→∀xQ(x)T①⑥CP⑶证明20 ¬∀∨①x(P(x)Q(x))P②∃x(¬P(x)∧¬Q(x))T①量词否定，德⋅摩根律③¬P(c)∧¬Q(c)T②ES④∀xQ(x)P否定结论引入⑤Q(c)T④US⑥¬Q(c)T③化简⑦Q(c)∧¬Q(c)T⑤⑥合取由⑦得到矛盾，由间接证明原理，原命题得证明。3．解⑴设M(x)：x是鸟；N(x)：x是猴子，F(x)：x会飞。前提：∀x(M(x)→F(x))，∀x(N(x)→¬F(x))∀→¬结论：x(N(x)M(x))证明①∀x(N(x)→¬F(x))P②N(y)→¬F(y)T①US③∀x(M(x)→F(x))P④M(y)→F(y)T③US⑤¬F(y)→¬M(y)T④假言易位⑥N(y)→¬M(y)T②⑤假言三段论⑦∀x(N(x)→¬M(x))T⑥UG⑵设M(x)：x是学生；N(x)：x是教师；F(x)：x是骗子；R(x,y)：x相信y。∃∧∀→∀→∀→¬前提：x(M(x)y(N(y)R(x,y)))，x(M(x)y(F(y)R(x,y)))∀→¬结论：x(N(x)F(x))证明①∃x(M(x)∧∀y(N(y)→R(x,y)))P②M(c)∧∀y(N(y)→R(c,y))T①ES③M(c)T②化简④∀x(M(x)→∀y(F(y)→¬R(x,y)))P⑤M(c)→∀y(F(y)→¬R(c,y))T④US⑥∀y(F(y)→¬R(c,y))T③⑤假言推理⑦F(d)→¬R(c,d)T⑥US⑧∀y(N(y)→R(c,y))T②化简⑨N(d)→R(c,d)T⑧US⑩R(c,d)→¬F(d)T⑦假言易位⑾N(d)→¬F(d)T⑨⑩假言三段论⑿∀x(N(x)→¬F(x))T⑾UG⑶设M(x)：x是学术会成员；N(x)：x是工人；R(x)：x是专家；Q(x)：x是青年人。∀→∧∃∧前提：x(M(x)(N(x)R(x)))，x(M(x)Q(x))结论：∃x(M(x)∧Q(x)∧R(x))证明①∃x(M(x)∧Q(x))P②M(c)∧Q(c)T①ES③∀x(M(x)→(N(x)∧R(x)))P④M(c)→(N(c)∧R(c))T③US⑤M(c)T②化简21 ⑥N(c)∧R(c)T④⑤假言推理⑦R(c)T⑥化简⑧M(c)∧Q(c)∧R(c)T②⑦合取⑨∃x(M(x)∧Q(x)∧R(x))T⑧EG复习题21．解⑴设个体域是整数集合I，F(x)：x是最大的整数，命题符号化为¬∃xF(x)。⑵设M(x)：x是学生，F(x)：x要好好学习。命题符号化∀x(M(x)→F(x))。⑶设M(x)：x是液体，F(x)：x能溶于水。命题符号化¬∀x(M(x)→F(x))。⑷设M(x)：x是人，F(x,y)：x与y一样高。命题符号化¬∀x((M(x)∧M(y))→F(x,y))。⑸设M(x)：x是数，F(x)：x是实数，G(x)：x是复数。命题符号化∀x(M(x)→(F(x)∨G(x)))。⑹设M(x)：x是数，F(x)：x是奇数，G(x)：x是偶数，H(x)：x是2。命题符号化∀x(M(x)→((F(x)∧G(x))↔H(x)))。⑺设M(x)：x不是地球，F(x)：x上有人，c：金星。命题符号化∃x(M(x)∧F(x))→F(c)。2．解⑴∃x(A(x)∧B(x))⇔(A(1)∧B(1))∨(A(2)∧B(2))∨(A(3)∧B(3))⇔0∨0∨0⇔0。⑵∀x(A(x)→¬(x≤2))⇔(A(1)→¬(1≤2))∧(A(2)→¬(2≤2))∧(A(3)→¬(3≤2))⇔1∧0∧1⇔0。3．解⑴∀x的辖域P(x)∧Q(y)，其中x是约束变元，y是自由变元；∃y的辖域M(x,y)，其中x是自由变元，y是约束变元。⑵∃x的辖域P(x)，∀x的辖域M(x)，其中x在两个量词的不同辖域中都是约束变元，y是自由变元。⑶∀x的辖域P(x,y)，其中x是约束变元，y是自由变元；∃y的辖域Q(y)，其中y是约束变元。⑷∀x的辖域∃yP(x,y)，∃y的辖域P(x,y)，整个公式中x是约束变元，y约束变元1次，自由变元1次。4．解∃!xP(x)⇔∃x(P(x)∧∀y(P(y)→(y=x)))。5．解⑴∀xP(x)∧∀xQ(x)⇔P(a)∧P(b)∧P(c)∧Q(a)∧Q(b)∧Q(c)⑵∃x(P(x)→∀xQ(x))⇔(P(a)→(Q(a)∧Q(b)∧Q(c)))∨(P(b)→(Q(a)∧Q(b)∧Q(c)))∨(P(c)→(Q(a)∧Q(b)∧Q(c)))⑶∀x∃yR(x,y)⇔∃yR(a,y)∧∃yR(b,y)∧∃yR(c,y)⇔(R(a,a)∨R(a,b)∨R(a,c))∧(R(b,a)∨R(b,b)∨R(b,c))∧(R(c,a)∨R(c,b)∨R(c,c))6．解⑴设个体域为D={a，b}，令P(a)=1；P(b)=0；Q(a)=0；Q(b)=1。则∀xP(x)为假，∀xQ(x)为假，从而∀xP(x)→∀xQ(x)为真。由于P(a)→Q(a)为假，所以∀x(P(x)→Q(x))也为假，此时公式为假。因此，公式不是逻辑有效式。⑵设D={a}，若R(a)=1，P(a)=0，Q(a)=1，则∃x(P(x)↔Q(x))为假，而∀x((P(x)∨R(x))↔(Q(x)∨R(x)))为真，因此原公式为假。因此，公式不是逻辑有效式。⑶设个体域D={a，b}，Q(a)=Q(b)=0，取P(a)=1，P(b)=0。则∃x(P(x)→Q(y))为真，而(∃xP(x)→Q(y))为假。因此，原公式不是逻辑有效式。⑷∃x∃y(P(x)→Q(y))⇔∃x∃y(¬P(x)∨Q(y))⇔∃x(¬P(x)∨∃yQ(y))⇔∃x¬P(x)∨∃yQ(y)⇔¬∀xP(x)∨∃yQ(y)⇔∀xP(x)→∃yQ(y)因此，原公式为逻辑有效式。7．⑴证明∃z(A(x)→B(x))⇔∃x(¬A(x)∨B(x))22 ⇔∃x¬A(x)∨∃xB(x))⇔¬∀xA(x)∨∃xB(x))⇔∀xA(x)→∃xB(x))⑵证明∃xP(x)→∀yQ(y)⇔¬∃xP(x)∨∀yQ(y)⇔∀x¬P(x)∨∀yQ(y)⇔∀x∀y(¬P(x)∨Q(y))⇔∀x∀y(P(x)→Q(y))9．⑴证明①∃xF(x)P②F(c)T①ES③∀xF(x)→∀y((F(y)∨G(y))→R(y))P④F(c)→∀y((F(y)∨G(y))→R(y))T③US⑤∀y((F(y)∨G(y))→R(y))T②④假言推理⑥(F(c)∨G(c))→R(c)T⑤US⑦F(c)∨G(c)T⑥附加⑧R(c)T⑤⑦假言推理⑨F(c)∧R(c)T⑥⑧合取⑩∃x(F(x)∧R(x))T⑨EG⑵证明①∀x(C(x)→¬B(x))P②C(y)→¬B(y)T②US③∀x(A(x)→B(x))P④A(y)→B(y)T③US⑤¬B(y)→¬A(y)T④假言易位⑥C(y)→¬A(y)T②⑤假言三段论⑦∀x(C(x)→¬A(x))T⑧UG∀x(H(x))→A(x))⇒∀x∀y((H(y)∧N(x,y))→∃y(A(y)∧N(x,y))⑶证明①∀x∀y((H(y)∧N(x,y))P附加前提引入②∀y((H(y)∧N(x,y))T①US③H(v)∧N(x,v)T②US④∀x(H(x))→A(x))P⑤H(v)→A(v)T④US⑥H(v)T③化简⑥A(v)T⑤⑥假言推理⑦N(x,v)T③化简⑧A(v)∧N(x,v)T⑥⑦合取⑨∃y(A(y)∧N(x,y))T⑧EG⑩∀x∀y((H(y)∧N(x,y))→∃y(A(y)∧N(x,y))T①⑨CP10．解⑴设M(x)：x是航海家，F(x)：x教育自己的孩子成为航海家，G(x)：x教育他的孩子去做飞行家。前提：∀x(M(x)→F(x))，∀x(G(x)→¬F(x))，∃xG(x)结论：∃x¬M(x)23 证明∃①xG(x)P②G(c)T①ES③∀x(G(x)→¬F(x))P④G(c)→¬F(c)T③US⑤¬F(c)T②④假言推理⑥∀x(M(x)→F(x))P⑦M(c)→F(c)T⑥US⑧¬M(c)T⑤⑦拒取式⑨∃x¬M(x)T⑨UG⑵设M(x)：x是哺乳动物，N(x)：x是脊椎动物，F(x)：x是胎生动物。∀→∃∧¬前提：x(M(x)N(x))，x(M(x)F(x)).结论：∃x(N(x)∧¬F(x))证明①∃x(M(x)∧¬F(x))P②M(c)∧¬F(c)T①ES③∀x(M(x)→N(x))P④M(c)→N(c)T③US⑤M(c)T②化简⑥N(c)T④⑤假言推理⑦¬F(c)T②化简⑧N(c)∧¬F(c)T⑥⑦合取⑨∃x(N(x)∧¬F(x))T⑧EG⑶设F(x)：x是有理数，G(x)：x是无理数，M(x)：x是实数，N(x)：x是虚数。前提：∀x(F(x)→M(x))，∀x(G(x)→M(x))，∀x(N(x)→¬M(x))∀→¬¬结论：x(N(x)(F(x)G(x)))证明①∀x(N(x)→¬M(x))P②N(y)→¬M(y)T①US③∀x(F(x)→M(x))P④F(y)→M(y)T③US⑤¬M(y)→¬F(y)T②④假言易位⑥N(y)→¬F(y)T②⑤假言三段论⑦∀x(G(x)→M(x))P⑧G(y)→M(y)T⑦US⑨¬M(y)→¬G(y)T⑦假言易位⑩N(y)→¬G(y)T②⑨假言三段论⑾(N(y)→¬F(y))∧(N(y)→¬G(y))T⑥⑩合取⑿N(y)→（¬F(y)∧¬G(y)）T⑾蕴涵等价式，分配律⒀∀x(N(x)→(¬F(x)¬G(x)))T⑿UG第三章基础知识习题3.11．解⑴：A={2,3,5,7,11,13,17,19}；⑵：B={a,e,i,m,n,o,r,t,u}；24 ⑶：C={-3,2}。|≤≤∈2．解⑴A={x1x79,xN}；⑵B={x|x=2k+1,k∈N}；⑶C={x|x=5n,n∈I}。3．解⑴：1，2，3，4，6，9，12，18，36；⑵：a，b；⑶：1，{3}，{{a}}。习题3.21．解互不相同。⑴是不包含任何元素的空集，⑵是以空集φ为元素的单元素集合，⑶是以0为元素的单元素集合，但和⑵的集合中的元素不同。2．证明若a=c,b=d，则{{a},{a,b}}={{c},{c,d}}；反之，若{{a},{a,b}}={{c},{c,d}}，则{a}={c}，{a,b}={c,d}，因此，a=c,b=d。3．解⑴设A={}φ，则PA()={,{}}φφ；⑵设B={,{}}φφ，则PB()={,{},{{}},{,{}}}φφφφφ；⑶设C={{,},{}}φaa，则PC()={,{{,}},{{}},{{,},{}}}φφaaφaa；⑷设D={{,},{,,},{,,}}{{,}}abaabbab=ab，则PD()={,{{,}}}φab。4．解⑴M⊆T；⑵N⊆P；⑶P∩T=φ。5．解由题意可得：A={1,2,7,8}；B={0,1,2,3,4,5,6,7}；C={0,3,6,9,12,15,18,21,24,27,30}；D={1,2,4,8,16,32,64}。∪∪∪∪∪∪⑴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))=；⑶因为，A∩C={0,1,2,3,6,7,8,9,12,15,18,21,24,27,30},所以，B-A∩C={4,5}；⑷A∩B=B−A={0,3,4,5,6}，(A∩B)∪D={0,2,3,4,5,6,8,16,32,64}；6．解⑴、⑵的文氏图如图1-1所示，图中阴影部分表示所求集合。7．解⑴所求集合的集合成员表如表1-1所示。表1-1⑵所求集ABAIB(AIB)−A((AIB)−A)UA合的集合成员00000表如表1-201000所示。10001表1-211101ABCAUB(AUB)IC(AUB)IC−A00000000100001010001111110010010111011010011111025 ①U②8．证明⑴(AUB)I(AUB)=AU(BIB)=AUφ=A④③NT⑵(AIB)U(AIB)=AI(BUB)=AIU=A⑤⑥⑦⑶A-(B∩C)=A∩(B∪C)=A∩B∩C⑧F=(A∩B)∩(A∩C)=(A−B)∩(A−C)图1-3（原教材图1-4）9．证明⑴⇒⑵。因为，A⊆B，则B⊆A，所以，AUB⊇BUB=U，因此，AUB=U。⑵⇒⑶。AUB=U，AIB=AUB=U=φ。⑶⇒⑴。因为，A∩B=φ，所以，B=φ∪B=(A∩B)∪B=(A∪B)∩(B∪B)=(A∪B)∩U=A∪B因此A⊆B。习题3.31．解⑴⎟φ⎜=0；⑵⎟{φ}⎜=1；⑶⎟{1,2,{3,{2,1}}}⎜3；⑷⎟{1,2,1}⎜=2。2．解⑴①8，②8，③8，④10，⑤3，⑥6，⑦5，⑧12。⑵因为，N∪T∪F=U−N−T−F+N∩T+N∩F+T∩F-N∩T∩F，所以N∩T∩F=U−N−T−F+N∩T+N∩F+T∩F-N∪T∪F=60-25-26-26+9+11+8-8=3⑶(N∩T∩F)∪(N∩T∩F)∪(N∩T∩F)=|NUTUF|−|NIT|−|NIF|−|TIF|+2×|NITIF|=52-11-9-8+3×2=303．解设A={x⎜x∈N,1≤x≤100,x能被5整除}，B={x⎜x∈N,1≤x≤100,x能被4整除}，C={x⎜x∈N,1≤x≤100,⎢100⎥⎢100⎥⎢100⎥x能被6整除}，则A∩B∩C=⎢⎥=⎢⎥=1，A=⎢⎥=20，因此，⎣(5,4,6)⎦⎣60⎦⎣5⎦A∩B∩C=A−A∩B∩C=20-1=19。习题3.4×1．解⑴20=27+6；⑵58=2×27+4；⑶3=0×8+3；26 ×⑷57=319+0。2．解⑴因为35=2×14+7,14=2×7。所以，14和35的最大公因数为7，即GCD(14,35)=7，且由以上两式可推得7=1×35-2×14。⑵因为58=1×34+24,34=1×24+10,24=2×10+4,10=2×4+2,4=2×2。所以34和58的最大公因数为2，即GCD(34,58)=2，且由以上各式可推得2=12×34-7×58。⑶因为252=1×180+72，180=2×72+36，72=2×36。所以，180和252的最大公因××数为36，即GCD(180,252)=36，且由以上各式可推得36=3180-2252。⑷因为128=1×77+51，77=1×51+26，51=1×26+25，26=1×25+1。所以128和77互素，即GCD(128,77)=1，且由以上各式可推得1=5×77-3×128。3．解⑴因为108=1×72+36，72=2×36，所以GCD(108,72)=36，因此×LCM(108,72)=10872/36=216。⑵因为245=1×175+70，175=2×70+35，70=2×35，所以GCD(245,175)=35，因此LCM(245,175)=245×175/35=1225。⑶因为252=1×180+72，180=2×72+36，72=2×36，所以GCD(252,180)=36，因此LCM(252,180)=252×180/36=1260。⑷因为81=1×64+15，64=4×15+4，15=3×4+3，3=1×3+1，1=1×1，所以×GCD(64,81)=1，因此LCM(64,81)=6481=5184。4．证明⑴设GCDabc(,)=d1，则存在整数s1、t1，使得sa1+tbc1=d1，因为d是a、b的最大公因数，所以，da|、db|。因此，dd|①1另一方面，因为d1是a、bc的最大公因数，所以d1|a、d1|bc，因此，d1与c互素，否则d1与c有大于1的公因数d2，则d2⎢c，d2⎢d1，又d1|a，由整除的传递性，所以，d2|a。因此，a与c有大于1的因数d，这与GCD(a,c)=1矛盾。2由于d与c互素，且d|bc，由定理6，则d|b，又d|a，因此1111d|d②1由于d、d1都是正整数，由①②可得d1=d。⑵因为b,c都和a互素，则GCD(a,b)=1，GCD(a,c)=1，由⑴则有GCD(a,bc)=1，即bc也和a互素。5．证明设GCD(a,b)=d，则d⎢a，d⎢b。因为c>0，所以，cd⎢ac，cd⎢bc。∈另一方面，因为GCD(a,b)=d，所以存在s,tI,使得sa+tb=d，此式两边同乘c得sac+tbc=cd因此，对于任何的正整数e,若e⎢ac，e⎢bc，则e⎢cd。又因为cd>0，故cd是ac和bc的最大公因数，即GCD(ac,bc)=cd=c⋅GCD(a,b)。6.证明因为a⎢m，所以存在整数q，使得m=aq又b⎢m，即baq|，而a、b互素，由定理6，则有bq|。因此，存在整数q1，使得，q=bq1代入既可得m=abq1即ab|m。7.证明设k=mq+r（0≤r,<φ,y>,<{x},x>,<{x},y>,<{y},x>,<{y},y>,<{x,y},x>,<{x,y},y>}。3.解⑴不正确。例如令A=φ，B={1，2}，C={x}，则A×B=A×C=φ⑵正确。因为，∀∈(A-B)×C⇒x∈(A-B)∧y∈C⇒x∈A∧x∉B∧y∈C⇒x∈A∧y∈C∧x∉B∧y∈C⇒∈A×C∧∉B×C⇒∈(A×C-B×C)。所以，(A-B)×C⊆(A×C-B×C)。又因为，∀∈(A×C-B×C)⇒∈A×C∧∉B×C30 ⇒(x∈A∧y∈C)∧[(x∉B∧y∈C)∨(x∈B∧y∉C)∨(x∉B∧y∉C)]⇒x∈A∧(x∉B∧y∈C)⇒(x∈A∧x∉B)∧y∈C⇒x∈(A-B)∧y∈C⇒∈(A-B)×C。所以，(A×C-B×C)⊆(A-B)×C。综上所述，(A–B)×C=(A×C–B×C)。⑶正确。例如A=φ，A×A=φ，显然A⊆A×A。但是当A≠φ时，因为A×A是由集合A中的两个元素的序偶组成的集合，所以A⊆A×A一般不成立。4.证明(1)∀∈A×(B∪C)⇔(x∈A∧y∈(B∪C))⇔(x∈A∧(y∈B∨y∈C))⇔(x∈A∧y∈B)∨(x∈A∧y∈C)⇔(∈A×B)∨(∈A×C)⇔∈((A×B)∪(A×C))因此A×(B∪C)=(A×B)∪(A×C)。同理可证(2)。5.证明⑴∀∈(A×C)∪(B×D)⇔∈(A×C)∨∈(B×D)⇔∈(A×C)∨∈(B×D)⇔(x∈A∧y∈C)∨(x∈B∧y∈D)⇔(x∈A∨x∈B)∧(x∈A∨y∈D)∧(y∈C∨x∈B)∧(y∈C∨y∈D)⇒(x∈A∨x∈B)∧(y∈C∨y∈D)⇔x∈(A∪B)∧y∈(C∪D)⇔∈(A∪B)×(C∪D)。因此，(A×C)∪(B×D)⊆(A∪B)×(C∪D)。⑵设∀x∈A，若∈A×A，而A×A=B×B，所以，∈B×B，即x∈B，因此A⊆B；同理可证B⊆A；故A=B。习题4.21.解因为，A×B={(1,a),(2,a),(3,a)}，所以，R1=φ、R2={<1,a>}、R3={<2,a>}、R4={<3,a>}、R5={<1,a>,<2,a>}、R6={<1,a>,<3,a>}、R7={<2,a>,<3,a>}、R8={<1,a>,<2,a>,<3,a>}。2.解L={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>,<4,1>,<4,2>,<4,3>,<4,4>,<8,1>,<8,2>,<8,3>,<8,4>,<8,8>,<9,1>,<9,2>,<9,3>,<9,4>,<9,8>,<9,9>}；D={<1,1>,<1,2>,<1,3>,<1,4>,<1,8>,<1,9>,<2,2>,<2,4>,<2,8>,<3,3>,<3,9>,<4,4>,<4,8>,<8,8>,<9,9>}L∩D={<1,1>,<2,2>,<3,3>,<4,4>,<8,8>,<9,9>}L∪D={<1,1>,<1,2>,<1,3>,<1,4>,<1,8>,<1,9>,<2,1>,<2,2>,<2,4>,<2,8>,<3,1>,<3,2>,<3,3>,<3,9>,<4,1>,<4,2>,<4,3>,<4,4>,<4,8>,<8,1>,<8,2>,<8,3>,<8,4>,<8,8>,<9,1>,<9,2>,<9,3>,<9,4>,<9,8>,<9,9>}L-D={<2,1>,<3,1>,<3,2>,<4,1>,<4,2>,<4,3>,<8,1>,<8,2>,<8,3>,<8,4>,<9,1>,<9,2>,<9,3>,<9,4>,<9,8>}3.解X∪Y={a,b,c,d}，则X∪Y上的全域关系U、恒等关系I分别为U={,,,,,,,,,,,,,,,}；I={,,,}。4.解P∩Q={<1,2>,<2,3>}；P∪Q={<1,2>,<1,4>,<2,3>,<4,4>,<4,2>}；domP={1,2,4}，ranP={2,3,4}；domQ={1,2,4}，ranQ={2,3}；dom(P∪Q)={1,2,4}，ran(P∪Q)={2,3,4}。5.证明(1)对于任意元素x∈A，31 x∈dom(R1∪R2)⇔∃y(∈R1∪R2)⇔∃y(∈R1∨∈R2)⇔x∈dom(R1)∨x∈dom(R2)⇔x∈(dom(R1)∪dom(R2))故dom(R1∪R2)=domR1∪domR2(2)对于任意元素y∈By∈ran(R1∩R2)⇔∃x(∈R1∩R2)⇔∃x(∈R1∧∈R2)⇒∃x(∈R1)∧∃x(∈R2)⇔y∈ranR1∧y∈ranR2⇔y∈(ranR1∩ranR2)。故ran(R1∩R2)⊆ranR1∩ranR26.解R1={<1,1>,<1,2>,<2,1>,<2,2>}；R2={<2,3>,<4,1>}；R3={<0,0>,<0,1>,<0,2>,<0,4>,<0,6>,<0,8>,<1,1>,<2,2>,<4,4>,<6,6>,<8,8>}；R4={<0,1>,<1,1>,<1,2>,<1,3>,<2,1>,<2,3>,<4,1>,<4,3>,<6,1>,<8,1>,<8,3>}⎛111111⎞⎡100⎤⎡000⎤⎡000⎤⎜⎟⎢⎥⎢110⎥⎢000⎥⎜010000⎟⎢111⎥⎢⎥⎢⎥⎜⎟⎢110⎥⎢001⎥001000⎢101⎥MR1=⎢⎥，MR2=⎢⎥，MR3=⎜⎟，MR4=⎢⎥。⎢000⎥⎢100⎥⎜000100⎟⎢101⎥⎢000⎥⎢000⎥⎜000010⎟⎢100⎥⎢⎥⎢⎥⎜⎟⎢⎥⎢⎣000⎥⎦⎢⎣000⎥⎦⎜000001⎟⎢101⎥⎝⎠⎣⎦关系图如下：010000111111122222222444446366663388888R1R2R3R4图4-1习题4.31.解从关系复合的定义来求：R1·R2={<1,4>,<1,3>,<3,2>,<4,2>}；R2·R1={<1,3>,<2,3>}；R21=R1·R1={<1,1>,<1,2>,<3,3>,<4,3>}；R22=R2·R2={<2,2>,<3,3>,<3,4>}。2.解dom(R1·R2)⊆A；ran(R1·R2)⊆C。3.解(1)利用定义求解，R1={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,3>}；R2={<3,1>}；R1·R2={<1,1>,<2,1>,<3,1>}；R1·R2·R1={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}；R-11={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}；(2)利用矩阵求解，32 ⎡111⎤⎡000⎤⎢⎥⎢⎥M=111；M=000；R1⎢⎥R2⎢⎥⎢⎣101⎥⎦⎢⎣100⎥⎦⎡111⎤⎡000⎤⎡100⎤⎢⎥⎢⎥⎢⎥M=MoM=111o000=100；R1⋅R2R1R2⎢⎥⎢⎥⎢⎥⎢⎣101⎥⎦⎢⎣100⎥⎦⎢⎣100⎥⎦⎡100⎤⎡111⎤⎡111⎤⎢⎥⎢⎥⎢⎥MR1⋅R2⋅R1=MR1⋅R2oMR1=⎢100⎥o⎢111⎥=⎢111⎥；⎢⎣100⎥⎦⎢⎣101⎥⎦⎢⎣111⎥⎦⎡111⎤T⎢⎥MR−1=MR=110。11⎢⎥⎢⎣111⎥⎦关系图如图4-2：111232323R1·R2R2R1113232R1·R2·R1R1-1图4-24.解R={<1,2>,<2,3>,<3,1>,<4,5>,<5,4>}，R2={<1,3>,<2,1>,<3,2>,<4,4>,<5,5>,}，R3={<1,1>,<2,2>,<3,3>,<4,5>,<5,4>}，R4={<1,2>,<2,3>,<3,1>,<4,4>,<5,5>}，R5={<1,3>,<2,1>,<3,2>,<4,5>,<5,4>}，R6={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}，R7={<1,2>,<2,3>,<3,1>,<4,5>,<5,4>}=R1。所以，m=1、n=7可使得R1=R7。⎡10110⎤⎢⎥00101⎢⎥5.解MR=⎢00000⎥⎢⎥⎢00001⎥⎢⎣00110⎥⎦33 ⎡10110⎤⎡10110⎤⎡10111⎤⎢⎥⎢⎥⎢⎥001010010100110⎢⎥⎢⎥⎢⎥M2=⎢00000⎥o⎢00000⎥=⎢00000⎥R⎢⎥⎢⎥⎢⎥⎢00001⎥⎢00001⎥⎢00110⎥⎢⎣00110⎥⎦⎢⎣00110⎥⎦⎢⎣00001⎥⎦⎡10111⎤⎡10110⎤⎡10111⎤⎢⎥⎢⎥⎢⎥001100010100001⎢⎥⎢⎥⎢⎥M3=⎢00000⎥o⎢00000⎥=⎢00000⎥R⎢⎥⎢⎥⎢⎥⎢00110⎥⎢00001⎥⎢00001⎥⎢⎣00001⎥⎦⎢⎣00110⎥⎦⎢⎣00110⎥⎦⎡10111⎤⎡10110⎤⎡10111⎤⎢⎥⎢⎥⎢⎥000010010100110⎢⎥⎢⎥⎢⎥M4=⎢00000⎥o⎢00000⎥=⎢00000⎥R⎢⎥⎢⎥⎢⎥⎢00001⎥⎢00001⎥⎢00110⎥⎢⎣00110⎥⎦⎢⎣00110⎥⎦⎢⎣00001⎥⎦=M2，R因此，M5=M4oM=M2oM=M3，RRRRRR2k22k+13一般地，R=R,R=R,(k≥1)。6.证明⑴对于任意的∈(R-S)-1，则∈R-S，所以，∈R，但∉S，因此，再由逆关系的定义有，∈R-1，而∉S-1，故∈R-1-S-1。即(R-S)-1⊆R-1-S-1。同理可证R-1-S-1⊆(R-S)-1。综合可得(R-S)-1=R-1-S-1。⑵由集合的笛卡尔积和逆关系的定义，因为，对于任意的a∈A,b∈B都有，∈B×A，则∈A×B，所以，∈(A×B)-1，即B×A⊆(A×B)-1，另一方面，因为，对于任意的a∈A,b∈B都有，∈(A×B)-1，所以，则∈A×B，所以，∈B×A，即(A×B)-1⊆B×A。综合上述有，(A×B)-1=B×A。⑶用反证法证明φ-1=φ，假设存在a∈A,b∈B使得，∈φ-1，则∈φ，这与φ是空集矛盾。⑷先证明R⊆S⇒R-1⊆S-1。对于任意的a∈A,b∈B，若∈R-1，由逆关系的定义则∈R，而R⊆S，所以，∈S，因此，∈S-1，即R-1⊆S-1。再证明R-1⊆S-1⇒R⊆S。若∈R，则∈R-1，而R-1⊆S-1，所以，∈S-1，因此，∈S，即R⊆S。习题4.41.解如表4-2关系自反的反自反的对称的反对称的传递的R1NNYNYR2NYYNN34 R3NYNYN表4-22.解⑴R具有自反性，因为对于任意的x∈I，x(x-1)=x(x-1)，即∈R，所以R具有自反性；⑵因为R具有自反性，所以R不具有反自反性；⑶R具有对称性，因为对于任意的x,y∈I，若∈R，则x(x-1)=y(y-1)，所以y(y-1)=x(x-1)，即∈R，因此R具有对称性；⑷显然R不具有反对称性；⑸R具有传递性，设∈R，∈R，即x(x-1)=y(y-1)，y(y-1)=z(z-1)，显然有x(x-1)=z(z-1)，即∈R，所以R具有传递性。3.解(1)R={<0,0>,<0,1>,<0,2>,<0,4>,<1,0>,01<1,1>,<1,2>,<1,4>,<2,0>,<2,1>,<2,2>,<4,0>,<4,1>}，关系图如图4-3。⑵R具有对称性。44.解若A上关系R是反对称的，则R∩R-1关系矩阵M-12图4-3R∩R中最多只有主对角线上有非零值，即最多只有|A|个非零值。5.解答案可以有很多组，下面给出一组答案如下。(1)R={<1,1>}；(2)R={<1,2>,<2,1>,<3,1>}；(3)R={<2,2>,<3,3>}；(4)R={<1,2>,<2,3>,<1,3>}。6.证明因为，R1，R2为集合A上的自反关系，则对于任意的x∈A，有∈R1，且∈R2，因此，∈R1·R2，故R1·R2是A上的自反关系。习题4.51.解r(R1)=R1∪IA={,,,,}；−1s(R1)=R1∪R={,,,}；1t(R1)={,,}；r(R2)=R2∪IA={,,,,,}−1s(R2)=R2∪R={,,,,,,}2t(R2)={,,,,,,,,}关系矩阵如下：⎡010⎤⎡110⎤⎡010⎤⎡011⎤⎢⎥⎢⎥⎢⎥⎢⎥M=001，M=011，M=101，M=001，R1⎢⎥r(R1)⎢⎥s(R1)⎢⎥t(R1)⎢⎥⎢⎣000⎥⎦⎢⎣001⎥⎦⎢⎣010⎥⎦⎢⎣000⎥⎦⎡110⎤⎡110⎤⎡111⎤⎡111⎤⎢⎥⎢⎥⎢⎥⎢⎥M=001，M=011，M=101，M=111。R2⎢⎥r(R2)⎢⎥s(R2)⎢⎥t(R2)⎢⎥⎢⎣100⎥⎦⎢⎣101⎥⎦⎢⎣110⎥⎦⎢⎣111⎥⎦关系图如图4-4：35 bbacacR1R2bbbacacacr(R1)s(R1)t(R1)bbbacacacr(R2)s(R2)t(R2)图4-4⎡010⎤⎡100⎤⎡010⎤⎢⎥⎢⎥T⎢⎥2.解MR=⎢100⎥，MIA=⎢010⎥，MR−1=MR=⎢101⎥⎢⎣011⎥⎦⎢⎣001⎥⎦⎢⎣001⎥⎦⎡110⎤⎡010⎤⎢⎥⎢⎥则Mr(R)=MR∨MIA=⎢110⎥；Ms(R)=MR∨MR−1=⎢101⎥；⎢⎣011⎥⎦⎢⎣011⎥⎦⎡010⎤⎡010⎤⎡100⎤⎢⎥⎢⎥⎢⎥MR2=MRoMR=⎢100⎥o⎢100⎥=⎢010⎥，⎢⎣011⎥⎦⎢⎣011⎥⎦⎢⎣111⎥⎦⎡100⎤⎡010⎤⎡010⎤⎢⎥⎢⎥⎢⎥MR3=MR2oMR=⎢010⎥o⎢100⎥=⎢100⎥⎢⎣111⎥⎦⎢⎣011⎥⎦⎢⎣111⎥⎦⎡010⎤⎡010⎤⎡100⎤⎢⎥⎢⎥⎢⎥M4=M3oM=100o100=010=M2，RRR⎢⎥⎢⎥⎢⎥R⎢⎣111⎥⎦⎢⎣011⎥⎦⎢⎣111⎥⎦⎡110⎤⎢⎥M=M∨M2∨M3=110；t(R)RRR⎢⎥⎢⎣111⎥⎦⎡100⎤⎡010⎤⎡110⎤⎢⎥⎢⎥⎢⎥M=M∨M=010∨101=111；rs(R)Is(R)⎢⎥⎢⎥⎢⎥⎢⎣001⎥⎦⎢⎣011⎥⎦⎢⎣011⎥⎦36 ⎡110⎤⎡110⎤⎡110⎤⎢⎥⎢⎥⎢⎥M=M∨M−1=110∨111=111。sr(R)r(R)(r(R))⎢⎥⎢⎥⎢⎥⎢⎣011⎥⎦⎢⎣001⎥⎦⎢⎣011⎥⎦3.证明⑴因为，R1⊆R2，所以，IA∪R1⊆IA∪R2，即r(R1)⊆r(R2)。−1−1−1−1⑵因为，R1⊆R2，由习题4.3第6⑷题可得R⊆R，所以，R∪R⊆R∪R，即121122s(R1)⊆s(R2)。2233nn+⑶因为，R1⊆R2，所以，R⊆R,R⊆R,L,R⊆R(n∈I),L，则12121223n23nR∪R∪R∪L∪R∪L⊆R∪R∪R∪L∪R∪L，即11112222t(R1)⊆t(R2)。4.证明⑴由自反闭包的定义又r(R1)=IA∪R1⊆IA∪R1∪R2=r(R1∪R2)，同理有r(R2)=IA∪R2⊆IA∪R1∪R2=r(R1∪R2)，所以有r(R1)∪r(R2)⊆r(R1∪R2)；另一方面，∀∈r(R1∪R2)=IA∪R1∪R2，下面分两种情况来证明∈r(R)∪r(R)。12①如果a=b，则∈IA，所以∈r(R)∪r(R)；12②如果a≠b，则∈R1∪R2，因此，∈R1或R2，若∈R1，则∈r(R)，所以，∈r(R)∪r(R)，同理，若∈R，则1122∈r(R2)，所以，∈r(R1)∪r(R2)。故r(R1∪R2)⊆r(R1)∪r(R2)。综上所述，r(R1∪R2)=r(R1)∪r(R2)。⑵因为R1⊆R1∪R2，且R2⊆R1∪R2，所以由第3题有s(R1)⊆s(R1∪R2)，且s(R2)⊆s(R1∪R2)，因此，s(R1)∪s(R2)⊆s(R1∪R2)；−1另一方面，∀∈s(R∪R)=(R∪R)∪(R∪R)，则∈(R∪R)12121212−1或∈(R1∪R2)，①若∈(R1∪R2)，则∈R1或∈R2，所以，∈s(R1)或∈s(R2)，因此，∈s(R1)∪s(R2)；②若∈(R∪R)−1，则∈(R∪R)，所以，∈R或∈R，因此，121212−1−1∈R1或∈R2，所以，∈s(R1)或∈s(R2)，因此，∈s(R1)∪s(R2)。37 故s(R1∪R2)⊆s(R1)∪s(R2)。综上所述，s(R1∪R2)=s(R1)∪s(R2)。⑶对于任取的∈t(R1)∪t(R2)，则∈t(R1)或∈t(R2)。若∈t(R1)，则存在正整数mmm使得∈R，因此∈(R∪R)，所以，∈t(R1∪R2)；同理若∈t(R2)，112可证∈t(R1∪R2)。综上所述，t(R1)∪t(R2)⊆t(R1∪R2)。5.解R={}是集合A={x,y}上的二元关系，则st(R)={,}，而ts(R)={,,,}。因此st(R)≠ts(R)。6.证明rt(R)=r(R∪R2∪…∪Rn∪…)=I2nA∪R∪R∪…∪R∪…=(I2nA∪R)∪(IA∪R)∪…∪(IA∪R)∪…⊆(I2nA∪R)∪(IA∪R)∪…∪(IA∪R)∪…=tr(R)。反之，对于任意的∈tr(R)，则存在正整数n，使得∈(In2A∪R)，即∈IA∪R∪R∪…∪Rn，亦即∈rt(R)，所以，tr(R)⊆rt(R)。综上所述，tr(R)=rt(R)。习题4.61.解A上共有15个等价关系。由等价关系和划分是一一对应关系，而A共有如下的15个划分：π1={{1,2,3,4}}，π2={{1},{1,2,3,4}}，π3={{2},{1,3,4}}，π4={{3},{1,2,4}}，π5={{4},{1,2,3}}，π6={{1,2},{3,4}}，π7={{1,3},{2,4}}，π8={{1,4},{2,3}}，π9={{1,2},{3},{4}}，π10={{1,3},{2},{4}}，π11={{1,4},{2},{3}}，π12={{2,3},{1},{4}}，π13={{2,4},{1},{3}}，π14={{3,4},{1},{2}}，π15={{1},{2},{3},{4}}。与每个划分对应的等价关系由读者自行给出。2.证明要证明R是A上的等价关系，只需证明R是A上的自反关系。事实上，因为，∀a∈A，总存在一个元素b∈A，使∈R，而R是集合A中的对称关系，所以∈R，又因为R是A上的传递关系，有∈R且∈R时，可得∈R，即R是集合A中的自反关系。故R是等价关系。3.解⑴R={a,d,e}×{a,d,e}∪{b,c}×{b,c}={,,,,,,,,}∪{,,,}⑵关系图如图4-5。ab⎛10011⎞⎜⎟⎜01100⎟M=⎜01100⎟⎜⎟dec⎜10011⎟⎜⎟图4-5⎝10011⎠4.解⑴不是等价关系。例如设A={1,2,3}，R1={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}，而显然A2-R1={<1,3>,<2,3>,<3,1>,<3,2>}不是等价关系；⑵不是等价关系。例如A={1,2,3}，R1={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}，R2={<1,1>,<2,2>,<2,3>,<3,2>,<3,3>}，而显然R1-R2={<1,1>,<1,2>}不是等价关系；⑶不是等价关系，令A={1,2,3}，R1={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>,<3,1>}，R2={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}R1-R2={<2,3>,<3,2>,<1,3>,<3,1>}，r(R1-R2)=(R1-R2)∪IA={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>,<1,3>,<3,1>}，因为<1,3>∈R1-R2，<3,2>∈R1-R2，但<1,2>∉R1-R2，显然R1-R2不具有传递性，所以R1-R2不是等价关系。(4)不是等价关系，令A={1,2,3}，R1={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}，R2={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}，38 R1·R2={<1,1>,<1,2>,<2,2>,<2,1>,<3,3>,<2,3>,<3,1>,<3,2>}，因为<3,1>∈R1·R2，但<1,3>∉R1·R2，所以R1·R2不是等价关系。(5)不是等价关系，令A={1,2,3}，R1={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}，R2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}R1∪R2={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>}，因为<1,2>∈R1，<2,3>∈R2，但<1,3>∉R1·R2，显然R1∪R2不具有传递性，所以R1∪R2不是等价关系。5.解⑴若π1=π2，则π1∪π2是集合A的划分，其它情况π1∪π2不是集合A的划分；例如设A={1,2,3}，π1={{1},{2,3}},π2={{1,2},{3}}，而π1∪π2={{1},{1,2},{2,3},{3}}不是划分。⑵若π1=π2，则π1∩π2是集合A的划分，其它情况π1∩π2不是集合A的划分，例如设A={1,2,3}，π1={{1},{2,3}},π2={{1},{2},{3}}，而π1∪π2={{1}}不是集合A的划分；⑶若π1∩π2=φ，则π1-π2是集合A的划分，其它情况π1-π2不是集合A的划分，例如设A={1,2,3}，π1={{1},{2,3}},π2={{1},{2},{3}}，而π1-π2={{2,3}}不是集合A的划分；⑷因为(π1∩(π2―π1))∪π1=π1，所以(π1∩(π2―π1))∪π1是集合A的划分。6.证明(1)①对任意的x∈I，x2=x2，即∈R，所以R是自反的；②对任意的∈R，即x2=y2，则y2=x2，即∈R，所以R是对称的；③对任意的∈R，∈R,即x2=y2，y2=z2，显然x2=z2，亦即∈R，所以R是传递的；综合①、②、③可知R是等价关系。(2)R的等价类可以分为{[0],[1],[2],…},其中[0]={0}，[1]=[-1]={1,-1}，[2]=[-2]={2,-2}，…，[n]=[-n]={n,-n}，…。习题4.71.证明(1)自反性。因为对任意的x∈X，∈I-1X，所以∈IX∪R∪R=R，即R是自反的；(2)对称性。对于任意的∈IX∪R∪R-1，且x≠y，显然∈R∪R-1，则∈R，或∈R-1，因此，∈R-1，或∈R，从而有∈R∪R-1，所以∈I-1X∪R∪R=R，即R是对称的；综上所述，R是X上的相容关系。2.证明(1)对任意的x∈A，有∈R，所以R是自反的；(2)设任意的∈R，且x≠y，都有R，即R是对称的；综上所述，R是A上的相容关系。R的关系矩阵如下，关系图如图4-6：⎛111000⎞1⎜⎟6⎜111110⎟52⎜111100⎟M=⎜⎟，⎜011110⎟34⎜⎟010110图4-6⎜⎟⎜⎝000001⎟⎠最大相容类为：{1,2,3},{2,3,4},{2,4,5},{6}。习题4.81.解从R的定义中，显见R具有自反性、反对称性、传递性，所以R是A上的偏序关系，即是偏序集。COVA={<1,2>,<1,3>,<2,4>,<3,5,>,<4,5>}2.解(1)从哈斯图可以看出aR/b，dRa，cR/d，cR/b，bR/c，aRa，eRa39 (2)R的关系图如图4-9：(3)A的最大元为a，无最小元，极大元为a，极小元为d，e；(4)出集合A及其子集B1={c,d,e}，B2={b,c,d}，B3={a,c,d,e}的上界，下界，上确界，下确界如表1。5aa43ccbb2de1de图4-7图4-8图4-9上界下界上确界下确界A={a,b,c,d,e}a无a无B1={c,d,e}c,a无c无B2={b,c,d}adadB3={a,c,d,e}a无a无表13.填写表2，区分偏序集的子集B上的最大(小)元，极大(小)元，上(下)界，上(下)确界。b是B的…定义b∈B否存在性唯一性b∈B且b大于B中其最大元素是不一定存在存在则唯一它每个元素b∈B且b小于B中其最小元素是不一定存在存在则唯一它每个元素b∈B且b不小于B极大元素是不一定存在不一定唯一中其它每个元素b∈B且b不大于B极小元素是不一定存在不一定唯一中其它每个元素b∈A且b大于B中上界不一定不一定存在不一定唯一每个元素b∈A且b小于B中下界不一定不一定存在不一定唯一每个元素上确界B的上界中的最小者不一定不一定存在存在则唯一下确界B的下界中的最大者不一定不一定存在存在则唯一表24．解⑴是偏序集，不是其它集合；⑵是拟序集，不是其它集合；⑶是偏序集、全序集、良序集，不是拟序集；⑷是偏序集、全序集、良序集，不是拟序集；复习题四1．证明对于任意的b∈B，因为A非空，所以存在a∈A，且∈A×B，因为A×B=A×C，所以∈A×C，从而b∈C，因此B⊆C。同理可证C⊆B。故B=C。40 2．证明利用集合相等的定义去证，即分别证明IA·R⊆R，R⊆IA·R；⑴对于任意的∈IA·R，必存在z，满足∈IA，∈R，而∈IA⇔x=z，所以∈R，即IA·R⊆R；⑵对于任意的∈R，因为∈IA，所以∈IA·R，即R⊆IA·R；综上所述，IA·R=R。4．解①R不具有自反性，因为φ∈(A)，但φ∩φ=φ，所以<φ,φ>∉R，故R不具有自反性。②R不具有反自反性，因为{1}∈P(A)且{1}∩{1}={1}≠φ，所以<{1},{1}>∈R，故R不具有反自反性。③R具有对称性，∀x,y∈P(A)，若∈R，则x∩y≠φ，所以y∩x≠φ，因此∈R，故R具有对称性。④R不具有反对称性，设x={1,2}，y={1,3}，则x∩y=y∩x={1}≠φ，由R的定义易知，∈R且∈R，但x≠y，故R不具有反对称性。⑤R不具有传递性，设x={1}，y={1,2}，z={2}，则有x∩y={1}≠φ且y∩z={2}≠φ，所以∈R且∈R，但x∩z=φ，所以∉R，故R不具有传递性。5．证明设R是集合X上的一个自反关系，如果R是X上对称和传递的，则对于任意a,b,c∈X，若有∈R∧∈R，则∈R∧∈R，故得R反之，若∈R，∈R，必有∈R，则对任意a,b∈X，若∈R，而因为R是自反关系，所以∈R)，故∈R，即R是对称的。若∈R∧∈R，则∈R∧∈R，所以∈R，即R是可传递的。6．证明(1)因为R+=t(R)是传递的，所以，(R+)+=t(R+)=t(t(R))=t(R)=R+(2)因为R*=IA∪R+=IA∪(R∪R2∪R3∪…)R·R*=R·(IA∪(R∪R2∪R3∪…))=R·IA∪R·R∪R·R2∪…=R∪R2∪R3∪…=R+同理可证，R*·R=R+。(3)(R*)*=(R*)+∪I****A=t(R)∪IA=R∪IA(因为R是传递的)=R7．证明(1)自反性。对于任意的∀x∈A,∀y∈B，若∈A×B，因为R1和R2分别是A和B上的等价关系，所以有∈R1，∈R2，因此根据R3的定义有<,>∈R3，即R3是自反的；(2)对称性。设任意的<,>∈R3，根据R3的定义有∈R1且∈R2，而因为R1和R2都具有对称性，所以∈R1且∈R2，因此<,>∈R3，即R3是对称的；(3)传递性。设任意<,>∈R3，<,>∈R3，根据R3的定义有∈R1且∈R2，∈R1且∈R2，因为R1和R2都具有传递性，所以∈R1且∈R2，因此<,>∈R3，即R3是传递的。综上所述，R3是A×B上的等价关系。8．解(1)E=rts(R)。(2)要证明E=rts(R)是等价关系，只要证明ts(R)具有对称性即可，对任意的∈ts(R)，则存在正整数k使得∈(s(R))k，存在z1,z2,┅,zk∈A，满足∈s(R),∈s(R),┅,∈s(R)，因为s(R)是对称的，所以∈s(R),∈s(R),┅,∈s(R)，因此∈(s(R))，即∈ts(R)，亦即ts(R)是对称的。41 (3)因为R={<1,2>,<1,3>,<4,4>,<4,5>}，则s(R)={<1,2>,<1,3>,<2,1>,<3,1>,<4,4>,<4,5>,<5,4>}，ts(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}，显然rts(R)=ts(R)是等价关系。9．证明(1)①必要性。若R是一偏序关系，则R是自反的、反对称的和传递的，。而又R是传递的，可得R=t(R)；又因为R是自反的，所以IA⊆R，因而R=rt(R)。-1-1-1若R是偏序关系，则R也是偏序关系，所以IA⊆R。所以IA⊆R∩R。又∈R-1∩R⇔∈R-1∧∈R⇔∈R∧∈R，由R的反对称性，所以x=y，即∈I-1-1A。因而R∩R⊆IA。故IA=R∩R②充分性。若R-1∩R=IA且R=t(R)，则R是自反的、传递的。下面证明R是反对称的，若∈R，∈R，则∈R且∈R-1，所以∈R∩R-1=IA，即x=y。因而R是反对称的。故R是偏序关系。(2)①必要性。若R是拟序关系，则R是反自反的、反对称的和传递的，因为R是传递的，所以R=t(R)。下面再用反证法证明R-1∩R=φ；假设R∩R-1≠φ，则存在某一∈R-1∩R⇔∈R-1∧∈R⇔∈R∧∈R，由R的传递性可知，∈R，这与R的反自反性矛盾，所以R∩R-1=φ。②充分性。若R=t(R)，可得R是传递的。若R不是反自反的，则存在某一x∈A，使得∈R，所以∈R-1，这与R-1∩R=φ矛盾，因此R是反对称的。故R是拟序关系。第五章函数习题5.11．解（1）是X到Y的函数，其定义域为domf=A={1,2,3},其值域为ranf={a,c}.（2）是X到Y的函数，其定义域为domf=A={1,2,3},其值域为ranf=B={a,b,c}.（3）不是X到Y的函数，∵存在lfb和lfc与函数定义矛盾。（4）是X到Y的函数，其定义域为domf=A={1,2,3},其值域为ranf={b}.2．解因为，f:I→I+,由f(x)=|x|+2给出，，即x∈I,|x|≥0,则f(x)=|x|+2≥2故它的值域为ranf=N-{0,1}.3．解（1）f(A)=f({5})={<5,6>},f-1(B)=f-1({<2，3>})={2};(2)f(A)=f({2,3})={5,7},f-1(B)=f-1({1，3})={0,1};(3)f(A)=f((0,1))=(1/4,3/4),f-1(B)=f-1([1/4,1/2])=[0,1/2];(4)f(A)=f({0,1/2})={1,2/3},f-1(B)=f-1({1/2})={1}.4．解∵|A|=3,|B|=2,∴|BA|=8.即A→B的函数有8个，具体如下：f1={,,},f2={,,},f3={,,},f4={,,},f5={,,},f6={,,},f7={,,},f8={,,}.因此，BA={f1,f2,f3,f4,f5,f6,f7,f8}。习题5.21．解（1）是单射但不是满射；（2）既不是单射也不是满射；（3）是满射；（4）是满射，单射，双射。2．解（1）f：I→I,f(x)=x3;42 ⎧1,当n是奇数(2)f:N→{0,1},f(n)=⎨;⎩0,当n是偶数(3)f：R→R,f(x)=x2+1;(4)f：I→I,f(x)=x+1.3．解（1）f={<0,0>,<1,4>,<2,3>,<3,2>,<4,1>},如图显然可知，是双射。A⎯⎯f⎯→BA⎯⎯f⎯→B00001111222233334444图：3（1）的示意图图：3（2）的示意图(2)f={<0,0>,<1,4>,<2,2>,<3,0>,<4,4>}，由图可知，f即不是单射也不是满射。4．解f1={,},f2={,},f3={,},f4={,}.其中f2，f3是双射，而f1，f4既不是满射也不是单射。5．证明设任意n∈N,则至少∈N×N则f(n,1)=n∈N，g(n,1)=n∈N故f,g是满射.但f,g都不是单射，如f(2,2)=4=f(3,1),g(3,4)=g(2,6)=12。6．证明（1）对于,∈R×R，设f()=f()，即<(x+y)/2,(x-y)/2>=<(u+v)/2,(u-v)/2>，亦即(x+y)/2=(u+v)/2，(x-y)/2=(u-v)/2，解得x=u,y=v，故=，因此，f是单射；(2)证f是满射，既任意∈R×R,令f()=，则有<(x+y)/2,(x-y)/2>=,既有(x+y)/2=u，(x-y)/2=v只要取x=u+v，y=u-v,就可使上式成立，且因为∈R×R，所以，∈R×R。故f是满射。综合上述f是双射。7．解ψA(1)=ψA(2)=1;ψA(3)=ψA(4)=0;ΨB(1)=1;ψB(2)=ψB(3)=ψB(4)=0;ΨC(1)=ψC(2)=ψC(3)=ψC(4)=0;ΨM(1)=ψM(2)=ψM(3)=ψM(4)=1。8．证明（1）①x∈A且x∈B，则x∈A∪B，因此，ψA∪B(x)=1,ψA(x)+ψB(x)-ψA(x)ψB(x)=1+1-1×1=1，所以，ψA∪B(x)=ψA(x)+ψB(x)-ψA(x)ψB(x)；②x∈A，x∉B，则x∈A∪B，因此，ψA∪B(x)=1,ψA(x)+ψB(x)-ψA(x)ψB(x)=1+0-1×0=1，所以，ψA∪B(x)=ψA(x)+ψB(x)-ψA(x)ψB(x)；③x∉A，x∈B，同②可证ψA∪B(x)=ψA(x)+ψB(x)-ψA(x)ψB(x)；④x∉A，x∉B，则x∉A∪B，因此，ψA∪B(x)=0,ψA(x)+ψB(x)-ψA(x)ψB(x)=0+0-0×0=0，所以，ψA∪B(x)=ψA(x)+ψB(x)-ψA(x)ψB(x)。综合①②③④，对所有x∈U，都有ψA∪B(x)=ψA(x)+ψB(x)-ψA(x)ψB(x)。（2）若x∈A则x∉A，所以，ψ(x)=0=1−1=1−ψ(x)；AA若x∉A则x∈A，因此，ψ(x)=1=1−0=1−ψ(x)。AA43 （3）①x∉A，则x∉A-B，所以，ψA-B(x)=0，ψA(x)=0，故ψA(x)(1-ψB(x))=0×(1-ψB(x))=0=ψA-B(x);②x∈A且x∈B，则x∉A-B，所以，ψA-B(x)=0，ψA(x)=1，ψB(x)=1，故ψA(x)(1-ψB(x))=1×(1-1)=0=ψA-B(x);③x∈A，x∉B，则x∈A-B，所以，ψA-B(x)=1，ψA(x)=1，ψB(x)=0，故ψA(x)(1-ψB(x))=1×(1-0)=1=ψA-B(x)。习题5.31．解对于任意b∈B,因为f：A→B是双射，即f：A→B是满射，则存在a∈A使∈f，由逆关-1-1-1系定义有∈f；若∈f且∈f，则又由逆关系定义得∈f且∈f，又因为f：A→B−1是单射故x=x1。综上所述由函数定义知f是B到A的函数。2．解没有，因为f不是双射函数。若将函数f的定义域和值域分别改为[0,π]和[-1,1]，则f有逆函数。3．解g·f(x)=g(f(x))=g(2x+5)=(2x+5)+7=2x+12；f·g(x)=f(g(x))=f(x+7)=2(x+7)+5=2x+19;f·f(x)=f(f(x))=f(2x+5)=2(2x+5)+5=4x+15;g·g(x)=g(g(x))==g(x+7)=(x+7)+7=x+14;f·k(x)=f(k(x))=f(x-4)=2(x-4)+5=2x-3;g·h(x)=g(h(x))=g(x/3)=x/3+7.4．解f⋅f={,,}⋅{,,}={,,};f⋅f⋅f=f⋅(f⋅f)={,,}⋅{,,}={,,}。5．解（1）g·f(x)=g(f(x))=g(x2-2)=(x2-2)+4=x2+2;f·g(x)=f(g(x))=f(x+4)=(x+4)2-2=x2+8x+14.(2)g·f(x)=x2+2,不是单射，也不是满射和双射；f·g(x)=x2+8x+14也不是单射，满射和双射。6．证明（1）因为g·f：A→C是双射，则g·f：A→C是单射。假设a1,a2∈A且a1≠a2，f(a1)=f(a2)，而g：B→C是函数，则g·f(a1)=g·f(a2)，这与g·f：A→C是单射矛盾，故f是单射;(2)因为g·f：A→C是双射，则g·f：A→C是满射。所以，对于任意c∈C,存在a∈A,使g·f(a)=c即g(f(a))=c,又因为f：A→B是函数，故存在b=f(a)∈B，因此，存在b∈B使得g(b))=c，故g是满射.7．证明因为，f：A→B是双射，由定理2知f-1:B→A是双射，故f-1也存在逆函数(f-1)-1：A→B，故对任意a∈A，设f(a)=b，则f-1(b)=a，因此有(f-1)-1(a)=b，于是f(a)=(f-1)-1(a)，由a的任意性可知f=(f-1)-1。习题5.41．证明要证A≈N,只须证明存在N到A的双射函数即可。设f：N→A，f(n)=11n+3,对与任意n∈N，显然，f：N→A是单射。下面证明f：N→A是满射。事实上，任取a∈A，由A中元素的形式，则存在x∈N,使得a=11x+3,且f(x)=11x+3=a,故f是满射,即f是双射。综合上述，A≈N.2．解A={2n|n∈N},B={2n+1|n∈N},C={3n|n∈N}，A,B,C这三个集合均是N的子集且都N等势。事实上，可以作如下的三个函数。f:N→A,f(n)=2n,n∈N;g:N→B,g(n)=2n+1,n∈Nh:N→C,h(n)=3n,n∈N容易证明这三个都是双射函数。3．证明作函数f：[0,1]→[2,3]，f(x)=x+2,x∈[0,1]。因为，f是严格单调的函数，所以，f是单射，又任意x∈[2,3]，则x-2∈[0,1]，且f(x-2)=(x-2)+2=x，故f是满射，故[2,3]≈[0,1]44 4．解（1）作恒等函数任意a∈，IA(a)=a，显然IA是A上的双射函数，故A≈A（2）若A≈B，则存在双射函数f：A→B，由5.3节定理1和定理2知f：A→B存在逆函数，且−1f:B→A也是双射双射，故B≈A。（3）因为，A≈B,B≈C，则存在双射函数f:A→B和g:B→C，则f和g的复合函数g·f：A→C也是双射（5.3节定理5）即A≈C。5．证明因为A≈C,B≈D，则存在双射函数f:A→C和g:B→D。由此可定义函数h:A×B→C×D，对于任意∈A×C，h(a,b)=,其中c=f(a),d=g(b)。下面证明：h:A×B→C×D是单射。对,∈A×B.若h(a1,b1)=h(a2,b2)=，即f(a1)=f(a2)=c,g(b1)=g(b2)=d,而f和g都是单射，所以有a1=a2，b1=b2，即=。再证明h:A×B→C×D是满射。事实上对任意的∈C×D,则c∈C,d∈D,由于f,g都是满射，所以存在a∈A,b∈B使得f(a)=c,g(b)=d。即存在∈A×B，使得h(a,b)=，故h是A×B到C×D的满射。因此，h是A×B到C×D的双射，故A×B≈C×D。复习题五1．解（1）是函数，定义域是{1,2,3,4}，值域是{x,y,z}，非满射，也非单射；(2)不是函数；(3)是函数，定义域是{1,2,3,4}，值域是{x,y,z,w},是双射，故有逆函数，则逆函数是{,,,},则定义域{x,y,z,w}，值域{1,2,3,4}；(4)不是函数；(5)是函数，定义域是{1,2,3,4}，值域是{y},单射，非满射，更不是双射。2．解因为S=(A∩(B∪C))∪(B∩C)，所以ψS(x)=ψA∩(B∪C)(x)+ψB∩C(x)-ψA∩(B∪C)∩B∩C(x)=ψA(x)⋅ψB∪C(x)+ψB(x)⋅ψC(x)-ψA∩B∩C(x)=ψA(x)(ψB(x)+ψC(x)-ψB∩C(x))+ψB(x)⋅ψC(x)-ψA(x)⋅ψB(x)⋅ψC(x)=ψA(x)ψB(x)+ψA(x)ψC(x)-ψA(x)⋅ψB(x)⋅ψC(x)+ψB(x)⋅ψC(x)-ψA(x)⋅ψB(x)⋅ψC(x)=ψA(x)ψB(x)+ψA(x)ψC(x)+ψB(x)⋅ψC(x)-2ψA(x)⋅ψB(x)⋅ψC(x)。3．解使f是双射，需要满足的条件是m和n互素。这是因为要使f是双射，需要f是单射，因此，需要当x≠y时，f(x)≠f(y)，而nx=mk+r1，ny=ml+r2，(r1≤r2)这里f(x)≠f(y)就是r1≠r2，r2-r1≠0，即m(r2-r1)而由上式可得r2-r1=n(y-x)+m(k-l)要m(r2-r1)，需要mn(y-x)，因此需要m和n互素。4．证明因为f是A到B的满射，所以，对于任何的b∈B，都存在a∈A使得f(a)=b，因此，f-1({b})非空；对于任何的b-1-1-1-1-11,b2∈B，b1≠b2，则f({b1})∩f({b2})=φ。若不然，，则存在a∈f({b1})∩f({b2})，即a∈f({b1})且a∈f-1({b−12})，亦即有f(a)=b1，f(a)=b2，这与f是函数矛盾。下面证明Uf({b})=A。b∈B对于任何的b∈B，显然有f-1({b})⊆A，所以f−1({b})⊆AU①b∈B另一方面，由于f是A到B的函数，则对于任意的a∈A，都有b∈B使得f(a)=b，即a∈f-1({b})，因此−1A⊆Uf({b})②b∈B45 −1由①②可得Uf({b})=A。b∈B综上所述，ϕ={f-1({b})|b∈B}是A的一个划分。产生这个划分的等价关系R描述为：aRb当且仅当f(a)=f(b)5．证明对于任何的[a]∈B，都有a∈A使得g(a)=[a]，即g是满射；对于任何的a,b∈A，若要g(a)=g(b)，即要[a]=[b]，由等价类的性质，即需要aRb。6．解（1）假。例如，设A={a,b,c},B={x,y},C={1,2,3},尽管f={,}是单射,若g={,,},但f·g={,,}不是单射；（2）假。例如，设A={a,b,c},B={x,y},C={1,2},若设g={,,},尽管f={,}是满射,但f·g={,,}不是满射；（3）假。例如，设A={a,b,c},B={x,y,z,w},C={1,2,3}，若设g={,,},f={,,,},虽然f·g={,,}是单射，但f不是单射；（4）证明用反正法。设有a1,a2∈A且a1≠a2但g(a1)=g(a2)，而f:B→C是函数，所以f·g(a1)=f·g(a2)，这与f·g：A→C是单射矛盾。故g是单射。（5）证明因为，f·g是满射，所以，对于任意的c∈C,存在a∈A，使得f·g(a)=c，即f(g(a))=c。又因为g:A→B是函数，所以有b=g(a)∈B，使得f(b)=c，因此f是满射。（6）证明因为，f·g是双射，所以，f·g既是满射，又是是单射，由（4）、（5）可知f是满射，g是单射。7．⑴证明因为f是从A到B的一个函数，所以f(a)=f(a)，因此aRa，既R是自反的；对于任意的a,b∈A，若aRb，则f(a)=f(b)，所以f(b)=f(a)，因此bRa，即R是对称的；对于任意的a,b,c∈A，若aRb，bRc，则f(a)=f(b)，f(b)=f(c)，所以f(a)=f(c)，即aRc，因此R是传递的。⑵等价类是{A,A}。8．证明设f:A×B→B×A，f(a,b)=，对任意∈A×B。则任意a1,a2∈A,b1,b2∈B,则由函数f:A×B→B×A得，f(a1,b1)=,f(a2,b2)=,若f(a1,b1)＝f(a2,b2)，则＝，因此，b1=b2,a1=a2，所以=，故f是单射。若任意∈B×A,这里b∈B,a∈A，根据定义可知：的原象是∈A×B,则满足满射函数的定义，故f是满射函数。9．解对于任意的y∈f(X∩Y)，则存在x∈X∩Y使得y=f(x)，这时因为x∈X∩Y，则x∈X且x∈Y，因此，f(x)∈f(X)，f(x)∈f(Y)，所以，f(x)∈f(X)∩f(Y)，即f(X∩Y)⊆f(X)∩f(Y)。任取u∈f(X)∩f(Y)，则u∈f(X)，u∈f(Y)，因此，存在x∈X且y∈Y，使得u=f(x),u=f(y)，即f(x)=f(y)，而因为f:A→B是单射，所以有x=y，故x∈X∩Y，因此，f(x)∈f(X∩Y)，即f(X)∩f(Y)⊆f(X∩Y)。综上所述：f(X∩Y)=f(X)∩f(Y)。第六章习题6.11．解图G的图形如图6-1(a)，图H的图形如图6-1(b).46 bebaaecdcd图(a)图6-12．解⑴、⑵、⑶、⑸能构成无向图的度序列，其中⑴、⑵、⑶能构成无向简单图的度序列。3．解由握手定理可知，图G中所有结点度数之和3×3+2×2+3×1=16，所以G应该有8条边。4．解由握手定理可知，图G中所有结点度数之和为24，三个4度接点的度数之和为12，则其余度数的和也是12，而其余结点的度均为3，所以3度接点应该有4个，因此，图G有7个结点。5．解图中G≅G。结点之间的对应关系为ϕ:V(G1)→V(G2)：ϕ(g)=1,ϕ(a)=8,ϕ(h)=2,ϕ(b)=7,ϕ(i)=10,12ϕ(c)=4,ϕ(j)=3,ϕ(d)=9,ϕ(f)=6,ϕ(e)=5。6．解G≅G。因为G与G的结点间存在一一对应关系，边的方向一致，其对应关系为：1212f:V(G1)→V(G2)，f(a)=2,f(b)=5,f(c)=1,f(d)=4,f(e)=3。习题6.21．解⑴从a到f的链有:abcf,abef,abcef,abecf,adef,adecf,adebcf,adecbef,adebcef，共9条。⑵从a到f的路有：abcf,abef,abcef，abecf,adef,adecf,adebcf，共7条。⑶从a到f的短程线有:abcf,abef,adef,，共3条。距离为3。⑷所有从a出发的圈有:abeda,abceda,abcfeda。2．⑴证明设G中的两个奇度结点分别为u和v，若u与v不连通，即他们之间无通路，则G至少有两个连通分支。记一个连通分支G1，G2=G-G1，这时u、v分别属于G1和G2，于是G的子图G1和G2各含有一个奇度结点，这与握手定理的推断是矛盾的，因此u与v一定是连通的。⑵解若有向图G中只有两个奇度结点u和v，u与v不一定互相可达，也不一定一个可达另一个。例如：图G=(其中V={u,v,w}，E={(u,w),(v,w)})中，结点u、v的度数均为1，w度数为2，但u不可达v，v也不可达u。3．解图6-5所示的4个图中，(a)是强连通图,(a)、(b)、(d)是单向连通图,(a)、(b)、(c)、(d)是弱连通图。4．证必要性（⇒）。用反证法,假设e在某个圈C上,则G-e的连通分支与G的连通分支相同,这与e是割边矛盾.充分性（⇐）。用反证法,假设e=(u,v)不是割边,则在图G-e中u,v仍连通,即在图G-e中有u到v路P,则图G有圈P+e,这与e不在任何圈上矛盾。5．证必要性（⇒）。设u是连通图G的割点，则G-u至少有两个连通分支，设G1，G2是它的两个不同的连通分支，则存在v∈G1,w∈G2，使得v到w的每一条路都经过u。充分性（⇐）。若存在v，w∈V，使得v到w的每一条路都经过u，则u是图G的割点。若不然，则G-u中任何两个点都是连通的，即G-u连通，亦即图G中任何有别于点u的两个点v、w，都有一条路不经过u，这与题设矛盾。习题6.3v1v21．解由图G的邻接矩阵作出其图如图6-6。.⑴d（v1）=2d（v2）=3。⑵图G不是完全图。v4v347图6-6 ⎡2413⎤⎢⎥4234⑶因为A3=⎢⎥,而a(3)=4,所以,从v121到v2长为3的路有4条。⎢1301⎥⎢⎥⎣3412⎦⑷从v1到v2长为3的4条路分别为：v1v2v1v2，v1v2v3v2，v1v2v4v2，v1v4v1v2。2．解邻接矩阵为A的无向图G的图形如图6-7所示：v1v4v3v2v5v5v3v4v1v2图6-7图6-83．解⑴图G的邻接矩阵为⎡01010⎤⎢⎥00001⎢⎥A=⎢01010⎥⎢⎥00001⎢⎥⎢⎣10100⎥⎦⑵为了求G中长度为3的通路的数目，就要计算A3，为此先计算A2。⎡00002⎤⎡20200⎤⎢⎥⎢⎥1010002020⎢⎥⎢⎥23A=⎢00002⎥，A=⎢20200⎥⎢⎥⎢⎥1010002020⎢⎥⎢⎥⎢⎣02020⎥⎦⎢⎣00004⎥⎦55因∑∑a(3)=20，故G中长度为3的通路有20条。因为A3的主iji=1j=1对角线上的元素的和为12，所以G中长度为3的回路有12条。⑶因为⎡00001⎤⎡10100⎤⎢⎥⎢⎥1010001010⎢⎥⎢⎥(2)(3)(2)A=A∧A=⎢00001⎥,A=A∧A=⎢10100⎥⎢⎥⎢⎥1010001010⎢⎥⎢⎥⎢⎣01010⎥⎦⎢⎣00001⎥⎦48 ⎡01010⎤⎡00001⎤⎢⎥⎢⎥0000110100⎢⎥⎢⎥(4)(3)(5)(4)A=A∧A=⎢01010⎥,A=A∧A=⎢00001⎥⎢⎥⎢⎥0000110100⎢⎥⎢⎥⎢⎣10100⎥⎦⎢⎣01010⎥⎦所以G的可达性矩阵为⎡11111⎤⎢⎥11111⎢⎥(2)(3)(4)(5)P=A∨A∨A∨A∨A=⎢11111⎥⎢⎥11111⎢⎥⎢⎣11111⎥⎦因为P中的每个元素都是1，所以G是强连通的，当然也是单向连通的。4．解图6-9、图6-10的关联矩阵分别为⎡21110⎤⎡−11000⎤⎢⎥⎢⎥011001−1100M=⎢⎥，M=⎢⎥，56⎢00001⎥⎢00011⎥⎢⎥⎢⎥⎣00011⎦⎣00−1−1−1⎦5．解图6-9、图6-10的邻接矩阵分别为：⎡1201⎤⎡0100⎤⎢2000⎥⎢1001⎥A=⎢⎥，B=⎢⎥。⎢0001⎥⎢0002⎥⎢⎣1010⎥⎦⎢⎣0000⎥⎦习题6.41．解图(a)既是Euler图又是Hamilton图，(b)是Euler图但不是Hamilton图，图(c)是Hamilton图但不是Euler图，(d)既不是Euler图又不是Hamilton图。2．解当n=2k+1（k∈N,k≠0）时，Kn是Euler图.当n=2时,Kn仅存在Euler链而不存在Euler回路.3．解图6-12中的图(2)、(3)、(4)中有Hamilton圈，(1)、(5)中只有Hamilton路而没有Hamilton圈。(1)中的路为abcdejhgig；(2)中的圈为afidejhcbga；(3)中的圈为agkfeicbhdja；(4)中的圈为abrfgcdihja；(5)中的路为jabihfgkdec。4．证明设V={a,c,e,h,j,l,p}，则有ω(G-V1)=9>7=⎟V1⎜，所以它不是Hamilton图。15．解我们分别用a,b,c,d,e,f,g七个结点表示七个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连一条无向边，所得无向图如图6-14(a)。此图存在一条Hamilton圈：abdfgeca，于是按图6-14(b)所示是顺序安排座位即可。49 agaaflmbbgbchopncfdekicdefgej(a)(b)d图6-13习题6.51．解如图6-16,求得v1到v8的最短路是v1v3v6v7v8,其总长度为13.2．解首先观察图中的奇数度结点，此图中只有两个奇数度结点E和F。用标号法求E到F的最短路径，容易算出E到F的最短路径为EGF，其权为28。然后将最短路径上的边均重复依次（如图6-17(b)中虚线）。于是得欧拉图∗G。求从D点出发的一条欧拉回路，如DEGFGEBACBDCFD，其权为281。v29v58412v12v35v6v881114212v4v7图6-15v2(6,3)915v5868412v1(0,0)22v3(2,1)57v6(7,3)16v8(13,7)81511311842121111v4(8,6)20v7(11,6)图6-16B40EB40E506358506358A19DGA19DG30122320301223201010CFCF(a)(b)图6-173．解从a开始，可得哈密尔顿回路，如图（b），长度37，而最短哈密尔顿回路如（c）长度36。50 aaa1414886b6eb6ebe5b145675675710cdcdcd(a)(b)(c)图6-18复习题61．解因为G中有6个3度结点，其度数和为18，由握手定理可知，所有结点度数的和为24，所以其余结点的度数和为6，而其度数均小于3，因此最大只能为2，则其余结点至少有3个，故G中至少有9个结点。2．解因为n是奇数，所以Kn中每个结点均为偶度，因此G中每个奇度结点在补图G中仍为奇度结点，故G的补图G中有r个奇度结点。3．证明用结点v1,v2,L,v6分别表示6个人。若vi与vj彼此认识（i≠j）就在vi与vj之间连边(vi,vj)于是构成无向简单图G=。在G中，若vi与vj之间有边(vi,vj)，说明vi，vj所代表的人彼此不认识。有了图论模型,要证明命题,就是要证明,要么在图G中有三角形,要么在图G中有三角形。设在G中v1与三个以上的结点相邻,不妨v1与v2,v3,v4相邻,如图6-19G,v1v1v6vvv622v5v5v3vv34v4图G图G图6-19这时若v2,v3,v4中有某两个相邻，则在G中存在三角形，若v2,v3,v4中任何两个都不相邻，则在G中v2,v3,v4构成三角形。若在G中v1与三个以下的结点相邻，则可先在G中作类似的证明。4．解K4的所有非同构的子图如图6-20共18个，其中有11个是生成子图，生成子图中有6个是连通图。5．解图1同构于图2。只要作映射f:u1→v1,u2→v2,u3→v3,u4→v4,u5→v5,u6→v6即可.51 vv21ev3v4v5图6-23(a)(b)(c)(d)6．解首先要注意5阶自补图的边数应该是K的边数的一半,而K有10条边,所以5阶自补图应该有555条边;其次,不连通图的补图是连通的,因此,自补图是连通的.由以上分析,应先画出K的全部5条边的连通5生成子图，再利用同构的性质来判断哪些是自补图。K的全部5条边的连通生成子图如图6-22。其中，(a)5与(a)自身互为补图，(b)与(c)互为补图，(d)与(d)互为补图。从而可得(a)和(d)为自补图。7．解图6-23中的路有：v1v2,v1v4,v1v2v4,v1v4v2,v1v2v5,v1v4v3,v1v4v5,v1v2v4v3,v1v2v4v5,v1v2v5v4,v1v4v5v2,v1v4v2v5,v1v2v5v4v3,v2v4,v2v5,v2v1v4,v2v4v3,v2v4v5,v2v5v4,v2v1v4v3,v2v1v4v5,v2v5v4v3,v3v4,v3v4v5,v3v4v2v5,v3v4v1v2v5,v4v5,v4v2v5,v4v1v2v5共29条。图6-23中的4个圈分别为：v3ev3，v1v2v4v1,v2v4v5v2,v1v2v5v4v1。8．证明用反证法。假设G不连通，则G至少有两个连通分支G1、G2，设连通分支G1中有n1个结点，G2中有n2个结点，且n1+n2≤n。分别从G1和G2中任取一个结点u和v，由于G是简单图，从而G1和G2也是简单图。所以，deg(u)≤n1-1,deg(v)≤n2-1,故deg(u)+deg(v)≤n1+n2-2≤n-2，这与G中每对结点度数之和均大于等于n-1相矛盾。因此，G是连通图。9．解图6-24中的图D1,D2,D3就是符合题意的3个4阶有向简单图。10．解图6-25的关联矩阵M和邻接矩阵A分别为如下的矩阵：⎛−111−10⎞⎛0101⎞⎜⎟⎜⎟⎜1−1000⎟⎜1000⎟M=⎜0000−1⎟A=⎜0000⎟⎜⎟⎜⎟⎜⎝00−111⎟⎠⎜⎝0110⎟⎠⎡0101⎤⎢⎥001111．解⑴其邻接矩阵为：A=⎢⎥⎢0101⎥⎢⎥⎣0100⎦⎡0111⎤⎡0212⎤⎡0323⎤⎢⎥⎢⎥⎢⎥020101220413(2)A(2)=⎢⎥,A(3)=⎢⎥,A(4)=⎢⎥⎢0111⎥⎢0212⎥⎢0323⎥⎢⎥⎢⎥⎢⎥⎣0011⎦⎣0201⎦⎣0122⎦52 (2)(3)(4)由A,A，A，A可知从v1到v4长度为1，2，3，4的路径分别有1，1，2，3条。⎡0000⎤⎡0000⎤⎡2121⎤⎢⎥⎢⎥⎢⎥101103021210(3)AT=⎢⎥,ATA=⎢⎥,AAT=⎢⎥⎢0100⎥⎢0011⎥⎢2121⎥⎢⎥⎢⎥⎢⎥⎣1110⎦⎣0213⎦⎣1011⎦TTAA中第（2，3）个元素为1，说明从v2到v3引出的边能共同终止于同一结点的只有一个，v。AA4T中第（2，2）个元素为2，说明v2的引出度数为2。AA中第（2，3）个元素为0，说明没有结点引出的T边同时终止于v2和v3。AA中第（2，2）个元素为3，说明v2的引如度数为3。⎡0111⎤⎡0111⎤⎡0111⎤⎢⎥⎢⎥⎢⎥010101110111⑷A2=⎢⎥，A3=⎢⎥,A4=⎢⎥⎢0111⎥⎢0111⎥⎢0111⎥⎢⎥⎢⎥⎢⎥⎣0011⎦⎣0101⎦⎣0110⎦⎡0111⎤⎢⎥0111P=A∨A2∨A3∨A4=⎢⎥⎢0111⎥⎢⎥⎣0111⎦⎡0000⎤⎡0000⎤⎢⎥⎢⎥11110111⑸PT=⎢⎥,P∧PT=⎢⎥。所以，强连通子图的顶点集为：{v1},{v2,⎢1111⎥⎢0111⎥⎢⎥⎢⎥⎣1111⎦⎣0111⎦v3,v4}。12．解：不存在。因为G为欧拉图，因而G是连通图。若G中存在割边e={u,v}，则u，v分别属于G-e的两个连通分支G1与G2。设w为G1中的一个结点，可从w出发走一条欧拉回路C：从w开始，一旦行到u，沿割边到达v，则在G2中行遍后无法回到G1达到w，这于G是欧拉图矛盾。故G中无割边。13．解abjibcdlchdefghfihbka是图6-27中的一条Euler回路abcdABCDlHGFEkjihg图6-27图6-2853 14．解ABCDFCEFGAHGBH是图9中找出一条Euler路。15．解在图6-29中⑴与⑷两图为哈密尔顿图，⑵，⑶为半哈密尔顿图。在⑴中，abcdefghija为一条哈密尔顿回路。在⑷中abcdefghija为一条哈密尔顿回路。在⑶中abcdefghij为一条哈密尔顿通路。在⑵中，abcdefghijk为一条哈密尔顿通路。16．解图6-30中的图(a)、(b)、(c)、(d)分别是⑴、⑵、⑶、⑷题要求的实例。17．解图6-31中的图(a)、(b)能够一笔画出，但图(c)不能够一笔画出。图(a)的具体画法是：v1v8v9v3v10v11v5v12v7v2v9v10v4v11v12v6v7v1。图(b)的具体画法是：1,2,3,4,5,6,7,2,8,9,10,11,12,13,8,14,15,16,17,18,19,14,17,11,5,20。dadbebdacacbcacedb(b)(c)(d)图6-30图6-29第七章特殊图类习题7.11．解因m=n-1,这里m=6,所以n=6+1=7.2．解不正确。K与平凡图构成的非连通图中有4个结点3条边，但是它不是树。33．证明必要性。因为G中有n个结点，边数m=n-1，又因为G是连通的，由本节定理1可知，G为树，因而G中无回路。再证充分性。因为G中无回路，又因为边数m=n-1，由本节定理1，可知G为树，所以G是连通的。4．解因m=n-r,这里n=15,r=3,所以m=15-3=12，即G有12条边。5．解6个结点的所有不同构的树如图7-1所示。图7-16．证明由定理1，在任意的(n,m)树中，边数m=n−1；所以，由握手定理得n∑d(vi)=2m=2(n−1)①i=1⑴若T没有树叶，则由于T是连通图，所以T中任一结点均有d(v)≥2，从而i54 nd(v)≥2n②∑ii=1则①与②矛盾。⑵若树T仅有1片树叶，则其余n−1个结点的度数不小于2，于是n∑d(vi)≥2(n−1)+1=2n−1③i=1从而①、③相矛盾。综合⑴，⑵得知T中至少有两片树叶。7．解图7-2⑴中共有两棵非同构的生成树（如图7-3⑴，⑵）。图7-2⑵中共有3棵非同构的生成树（如图7-3⑶，⑷，⑸）。⑴⑵⑶⑷⑸图7-38．解在图7-4中共有8棵生成树，如图7-5⑴～⑻所示，第i生成树用T(i=1,2,L,8)表示。iW(T)=W(T)=8，W(T)=W(T)=6，W(T)=W(T)=W(T)=7，1625378W(T)=9。其中T2，T5是图中的最小生成树。4a1b322d4c图7-455 ababababdcdcdcdc⑴⑵⑶⑷ababababdcdcdcdc⑸⑹⑺⑻图7-59．解最小生成树T如图7-7所示，W（T）=18。11111199638726387210104545图7-6图7-7习题7.21．解不一定是。如图7-8就不是根树.2．解五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。由⑴可生成2棵非同构的根树，如图7-9⑷，⑸所示。⑷为3元树，⑸为4元树。由⑵可生成4棵非同构的根树，如图7-9⑹，⑺，⑻，⑼所示。⑹为2元树，⑺为2元树，⑻为3元树，⑼为2元树。由⑶可生成3棵非同构的根树，如图7-9⑽，⑴⑵⑶⑷⑾，⑿所图7-8⑸⑹⑺⑻56 ⑼⑽⑾⑿图7-9示。⑽为1元树，⑾，⑿为2元树。由此可知，五个结点共形成9棵非同构的根树。3．解不是。根树中最长路径的端点一个是树根，另一个是树叶，因为根树的高等于最长路径的长度，应从树根开始。4．证明设完全二元树T有n0个叶结点，n2分支结点，则T的结点数为n=n0+n2，边数m=2n2，有握手定理可得：2n2=n0+n2-1，所以，n2=n0-1，因此，n=n0+n2=2n0-1。即二元树有奇数个结点。5．解先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：2357811557811781011552323(a)(b)(c)101115213615101155781521785523781011235523(d)(e)(f)图7-11习题7.31．解图⑴是偶图，互补结点子集为：V={a,d,e,f},V={b,c,g}；图⑵是偶图，互补结点12子集为：V1={a,c,f},V2={b,d,e,g}；图⑶不是偶图。2．证明设G=是一棵树，任选v0∈V，定义V的两个子集如下：V={vd(v,v)为偶数},V2=V–V1。10现证明V1中任二结点之间无边存在。若存在一条边(u,v)∈E，u,v∈V1,由于树中任意两个结点之间仅存在惟一一条路，设v0到u的路为v0v1v2…vku，则v0v1v2…vku的长度为偶数，因(u,v)∈E，所以v0v1v2…vkuv是v0到v的一条通路，且该通路的长度k+2为奇数，从而v0v1v2…vkuv不是路，因此v必与某个vi(i=0,1,2,…,57 k)相同，从而vvi+1vi+2…vkuv是G中的一个圈，这与G是树矛盾。同理可证，V2中任意两个结点之间无边存在。故G中的每条边(u,v)∈E，必有u∈V1，v∈V2或u∈V2，v∈V1，因此G是具有互补结点子集V1和V2的偶图。aaefabcddfdeefgbcgbcg(1)(2)(3)图7-123．解将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，它的互补结点子集V1和V2分别表示n位男士和n位女士，由题可知，V1中的每个结点度数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件（t=2），因此存在从V1到V2的匹配，故可将男士和女士分配为n对，使得每对中的男士和女士彼此都认识。4．解不能。用结点表示五位教师（V1）和五门课（V2），在教师和他熟悉的课程之间连一条线，得到一个偶图G，其中，V1中的孙、李、周三个结点只与数学、物理两个结点相邻接，故不满足相异性条件，因此不存在从V1到V2的匹配，故不能按题设要求的安排。习题7.41．证明将图7-13所示的两个图改画为图7-14所示的两个图,可以看出图(1),(2)任何两边除在结点处相交外，无其它交叉点即可。因此,图7-13所示的两个图都是平面图.aabcdbcdeef(1)(2)图7-152．解图7-15⑴中有五个面，分别为F1:abea,F2:acea,F3:acda,F4:cdec,F5:abeda。它们的秩分别为r(F1)=r(F2)=r(F3)=r(F4)=3,r(F5)=4。图7-15⑵有两个面，其中有限面为F1:acfedea,无限面F2:acbcfea。它们的秩r(F1)=r(F2)=6。3．证明设该连通简单图的面数为r，由Euler公式可得，6-12+r=2，所以r=8，其8个面分别设为ri(i=1,2,8┅,8)。因是简单图，故每个面至少由3条边围成。即∑D(ri)≥3×8=24。而由本届定理1知，i=18∑D(ri)=2m=2×12=24。因此每个面只能由3条边围成。i=158 bcaabcdegfdefg⑴⑵图7-16图7-174．解去掉图7-16中的两条边，并给结点表上名称的图7-17⑴，在将图7-17⑴改画图7-17⑵，而显然图7-17⑵与K5是同胚的，由库拉图斯基定理知，图7-16所示的图为非面图。5．证明若G中无圈,则G为森林,结论显然成立,若G中有圈,假设G中有n个结点,m条边,并假设G的所有连通分支为G1,G2,…,Gk,每个Gi有ni个结点,mi条边,则有kkn=n，m=m∑i∑ii=1i=1由于G是简单图,所以每个Gi也是简单图,由本节定理2的推论可知mi≤3ni-6,i=1,2,…,k。从而有kkkm=∑mi≤∑（3ni−6）=3∑ni−6k=3n−6k≤3n−6i=1i=1i=1所以m≤3n-6。再用反证法证明，简单平面图G中至少有一个度数小于等于5的结点。n1如果G中每个结点的度数均大于等于6,由握手定理可知2m=∑deg（vi）≥6n,因此n≤m,3i=1代入m≤3n-6得m≤m-6,这显然的矛盾的。故G中至少有一个度数小于等于5的结点。6．证明设G是连通平面图。假设G中每一结点v都有deg(v)≥5。因为2m≥5n,所以n≤2m/5。于是，m≤3n-6≤6m/5-6，即5m≤6m-30。因此，m≥30，与题设m<30矛盾。所以G中必有一个结点的度小于或等于4。复习题71．解假设T有m条边，x个1度结点，则有：m=5+3+4+2+x-12m=5×2+3×3+4×4+2×5+x解得：x=19,m=32，即T有19个1度结点。2．证明因为，图G是连通图，所以，由本节定理2知图G存在生成树T，而生成树T的边数n-1是不超过图G的边数m的，即m≥n-1。3．证明设G的p个连通分支分别为，，┅，，由于森林的每个连通分支都是树，因此，有：m1=n1-1，m2=n2-1，┅，mp=np-1⑴又m1+m2+┅+mp=m;n1+n2+…+np=n⑵由（1），（2）得：m=n-p。4．证明因为，a是在T1中但不在T2中的一条边，所以，T2∪{a}有惟一的圈C，而T1是树，则圈C上一定有一边b不在T1中。因此，(T2-{b})∪{a}=T2∪{a}-{b}是G的生成树。下面证明，(T1-{a})∪{b}=T1∪{b}-{a}也是G的生成树，事实上，因为T1是树，所以T1中的边a是T1的割边，因此T1去掉边a后可得两个连同分支，设为T11和T12。又b不在T1中，所以T1∪{b}有惟一的圈C1，59 5．解设G中的k个连通分支为T,T,L,T，设结点v∈T,i=1,2,L,k。在G中添加边12kii(v,v),i=1,2,L,k−1，设所得新图为T，则T连通且无回路，因此T是树。所加边的条数k-1是使得ii+1G为树的最小数目。6．解取图7-18(a)中最小权的边为e1=(d,e);再在E-{e1}取中权最小的边e2=(d,a);在E-{e1,e2}中权最小的边有两条(a,e)和(b,c)但若选(a,e)就会有圈,因此取e3=(b,c)；最后取e4=(b,c)，则得最小树如图7-18(b)，最小生成树的权为W=4+5+6+7=22。aa616e75eb7b8544669c13dcd(a)(b)图7-187．解题目就是求图7-19⑴的最小生成树问题。因此，图7-19⑴的最小生成树为图7-19⑵所示，即是所求的通讯线路图。其权即是最小总造价，其权为：w(T)=1+3+4+8+9+23=48。abab2023231414153699fcfcg8g8281633e17ded⑴⑵图7-198．解高为2的所有不同构的二元树有7棵，如图7-20所示。其中有2棵完全二元树，图7-20中的⑸和⑺所示，有1棵满二元树，图7-20中⑺所示。⑴⑵⑶⑷⑸⑹⑺图7-209．证明方法1：设T结点数为n，分支点数为i。根据完全二元树的定义，可知下面等式均成立：n=i+t⑴m=2i⑵60 m=n−1⑶由式⑴，⑵，⑶易知m=2t−2。方法2：在完全二元树中，除树叶外，每个结点的出度为2。除树根外，每个结点的入度为1。由握手定理知nn+−2m=∑d(vi)+∑d(vi)i=1i=1=2(n−t)+n−1=3n−2t−1=3(m+1)−2t−1解得：m=2t−2。10．证明设完全二元树T有i个分支点，t片树叶，由T为完全二元树，则由7.2节定理3有i=t−1。又结点数n=i+t，所以t=(n+1)/2为T的树叶数。11．解对于图7-21所示的二元树，三种遍历方法的结果如下：先根遍历：vvvvvvvvvv0134625789中根遍历：vvvvvvvvvv3164058792后根遍历：vvvvvvvvvv364189752012．解设图7-22⑴所示的树为T，T是完全二元树。在每个分支结点引出的两条边上分别标上0（左）11和1（右），则得如图7-23⑴的树，将树根到每片树叶的通路上所标的数字构成的符号串组成集合B={0000,0001,001,0100,01010,01011,011,1}，则B,为前缀码。11设图7-22⑵中所示的树为T，T是二元树，但不是完全二元树。对于有一个儿子的分支结点引出的22边可随便标上0或1；有两个儿子的分支点标法同T，则得如图7-23⑵的树，所得前缀码为B。12B={00,0100,01010,011,11}2⑴⑵图7-22010101011001011001011010⑴⑵图7-2361 13．解：其实，W(T)等于T的各分支点的权之和，即W(T)=5+10+15+25=55。⑵由T形成的二元前缀码为B={000,001,01,10,11}。105552323⑴⑵2510151015557855782323⑶⑷图7-2414．解应该用较短的符号串传输出现频率高的数字，因而可用100乘各数字出现的频率作为权，求最优二元树，然后用这样的二元树产生前缀码传输上面给定的数字。具体做法如下：用100乘各频率得权w=30,w=20,w=15,w=10,w=10,w=6,w=5,w=4。将这些权由小到大排列01234567得到4，5，6，10，10，15，20，30。⑴所求最优二元树如图7-25所示。⑵用所求的最优二元树产生二元前缀码如图7-25所示。带权为w的树叶对应的符号串就为传输i的i符号串。数字0,1,2,3,4,5,6,7对应的符号串分别为01，11，001，100，101，0001，00000，00001．⑶用这样的符号串传输按上述比例出现的数字最少。1000160400101303020200100011515101023401965015467⑴⑵图7-254444410×0.3×2+10×0.2×2+10×0.15×3+10×0.1×3+10×0.1×34444+10×0.1×3+10×0.06×4+10×0.05×5+10×0.04×5=27400所以传输10000个上述比例出现的数字至少要用27400个二进制数字。15．证明设二部图G的互补结点子集为V1、V2，则m=|V1|⋅|V2|且|V1|+|V2|=n，我们知道两个数的和一62 定，只有当它们相等时积最大，即当|V221|=|V2|=n/2时，积|V1|⋅|V2|最大为n/4，亦即m≤n/4。16．解令V1={P1，P2，…，P7}，V2={a1，a2，…，a10}，以V1和V2的元素作结点，若Pi是aj的合格工作岗位，则在Pi和aj之间连一边，因此，可得二部图如图7-26。去掉图7-26边(P1,a4),(P1,a8),(P3,a7),(P1,a1),(P2,a2),(P5,a1),(P6,a2),(P6,a5)，则图7-26的子图如图7-27。而图7-27满足t(t=1)条件，所以，存在V1到V2的匹配M={(P1,a9),(P2,a7),(P3,a6),(P4,a3),(P5,a10),(P6,a1),(P7,a2)}，因此，图7-26中也存在V1到V2的匹配M={(P1,a9),(P2,a7),(P3,a6),(P4,a3),(P5,a10),(P6,a1),(P7,a2)}。这样安排使得所有的人都有工作。P4P1P3P2P5P6P7a3a4a6a7a8a9a10a1a2a5图7-26P4P1P3P2P5P6P7a3a4a6a7a8a9a10a1a2a5图7-27L1L2L3L4L5L6G1G2G3G4G5G6图7-2817．解以V1={L1,L2,L3,L4,L5,L6},V2={G1,G2,G3,G4,G5,G6}作为互补结点集，若Li和Gj互相满意对方，则在Li和Gj之间连一边，这样得到一个二部图如图7-28，由图7-28可以看出，此图满足满足t(t=2)条件，所以，存在V1到V2的匹配，因此，可使得每一个青年男女都能够找到自己满意的对象，其中一个分配方法是M={(L1,G1),(L2,G3),(L3,G4),(L4,G2),(L5,G6),(L6,G5)}。第八章代数系统习题8.11．解⑴是，⑵不是，⑶是，⑷不是。*2．解若﹡对o是可分配的，则有任意a,b,c∈I,均有63 a﹡(boc)=(a﹡b)o(a﹡c)=aboc=(ab⋅ac)=ab+ca而a﹡(boc)=a﹡(b⋅c)=ab⋅c≠ab+c故﹡对o是不可分配的。3．解⑴对于任意A∈P(S),因为A⊆S，所以，A∪S=S，因此，S是关于∪运算的零元；⑵对于任意A∈P(S),因为A⊆S，所以，A∩S=A，因此，S是关于∪运算的零元单。4．解⑴①因为x*y=xy-2x-2y+6，则y*x=yx-2y-2x+6=x*y，满足交换律；②任意x,y,z∈R有x*(y*z)=x*(yz-2y-2z+6)=x(yz-2y-2z+6)-2x-2(yz-2y-2z+6)+6=xyz-2xy-2xz+6x-2x-2yz+4y+4z-12+6=xyz-2xy-2xz-2yz+4x+4y+4z-6.(x*y)*z=(xy-2x-2y+6)*z=(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6=xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z).故满足结合律。(2)①设任意a∈R,存在e∈R,要e*a=ea-2e-2a+6=a，由于a的任意性则e=3。因此e=3是其单位元;②设任意b∈R,z∈R，要有z*b=zb-2z-2b+6=z，由于b的任意性则z=2，因此z=2是其零元。−1−1−1−1（3）因为*是满足交换律，对于x∈R，要存在x∈R，须有x*x=xx-2x-2x+6=e=3,当x≠2−12x−3−12x−3时，x=。即对于任意的x，当x≠2时x都是可逆的，且x=。x−2x−25．解f1,f2,f3都满足交换律，f4满足等幂率，f2有单位元a，f1有零元a，f3有零元b。fabfab12aaaaabbaabbaf3abf4abaabaabbaabab表8-2习题8.21．解构成代数系统的运算有（2），（3），（4）。2．解<{0},⊕>,<{0,2},⊕>,<{0,1,2,3},⊕>444习题8.3∗abcoαβγabcααaγcaββacγbbbcββc1cbcγγβγc1ccc(a)(b)表8-264 1．证明作函数f:{a,b,c}→{α,β,γ}，f(a)=α,f(b)=β,f(c)=γ.显然此映射是双射。由表8-2可知对于任意的x,y∈A都有有f(x∗y)=f(x)ºf(y)，故≌。2．解代数系统与不可能同构。因为，由同构的性质，如果两个代数系统同构，则两个系统的单位元对应，零元对应，而这里，代数系统的零元是0，而没有零元。故代数系统与不可能同构。复习题八1．解⑴有单位元e=<1,0>，因为，对于任意∈S，均有<<1,0>∗=<1⋅a,1⋅b+0>=，且，∗<1,0>==，故<1,0>单位元⑵对于∈S，要有逆元，需要有∈S使得，∗=∗=<1,0>事实上，1b即<1,0>=∗=，因此，ax=1，ay+b=0，当a≠0时可解得x=,y=−，且又有aa1b<,−>∗=<1,0>。故当a≠0时，形式的元素都可逆，且aa−11b()=<,−>。aa2．解因为a*b=b*a⇒a=b，则任意a∈A，而*是可结合的，则有a*(a*a)=(a*a)*a，因此a*a=a，即*满足等幂律.3．证明假设f:Q→Q-{0}是从到的同构，则两个系统的单位元对应，即有f(0)=1。因为f是从Q到Q-{0}的满射，所以，对于任意一个素数p∈Q-{0}必存在某个x∈Q，使得f(x)=p，又由于f是一个同构，因此有p=f(x)=f((x-1)+1)=f(x-1)×f(1)，而在Q-{0}中有无穷多个素数，因此，总可以找到一个素数p，使得x-1≠0，则f(x-1)不是1，这与p是素数矛盾。证毕。4．证明因为，a∗a=a，(a∗b)∗(c∗d)=(a∗c)∗(b∗d)，所以，a∗(b∗c)=(a∗a)∗(b∗c)=(a∗b)∗(a∗c)。5．证明对n用数学归纳法。当n=1时，由幂的定义则(a*b)1=a*b=(a1)*(b1)，所以结论成立。假设n=k时结论成立，即(a*b)k=ak*bk，下面考察n=k+1时，(a*b)k+1=(a*b)k*(a*b)=(ak*bk)*(a*b)=(ak*a)*(bk*b)=ak+1*bk+1。即n=k+1时，结论也成立。由归纳法原理，对于任意的正整数n,都有(a*b)n=an*bn。6．证明任意n1,n2∈N，只有如下的三种情况：①n1,n2都能表示成2的幂的形式，②n1,n2都不能表示成2的幂的形式，③一个能表示成2的幂的形式，而另一个不能。下面就这三种情况分别考虑。①设存在kk1k2k1k2k1+k21,k2∈N，使得n1=2，n2=2，则n1×n2=2×2=2∈N，且f(n1)=f(n2)=1，因此f(nk1+k2k1k21×n2)=f(2)=1=f(n1)×f(n2)=f(2)×f(2);②n1,n2都不能表示成2的幂的形式，则n1×n2也不能表示成2的幂的形式，所以，f(n1)=f(n2)=0，因此f(n1×n2)=0=f(n1)×f(n2)。③不妨设存在k∈N，使得nk1=2，，而n2不能表示成2的幂的形式，则n1×n2也不能表示成2的幂的形式，65 所以，f(n1)=1，f(n2)=0，因此，f(n1×n2)=0=f(n1)×f(n2)。综上所述，代数结构与<{0,1},×>同态。第九章特殊的代数系统习题9.11．解⑴是半群。显然，二元运算“o”在N上是封闭的，所以，是一个代数系统，另一方面，∀a,b,c∈N,有(aob)oc=max{a,b}oc=max{a,b,c}，而ao(boc)=aomax{b,c}=max{a,b,c}，因此，(aob)oc=ao(boc)，所以，运算“o”满足结合律的，故是半群；⑵是半群。显然，二元运算“o”在N上是封闭的，所以，是一个代数系统，另一方面，∀a,b,c∈N，有(aob)oc=boc=c，而ao(boc)=aoc=c，则(aob)oc=ao(boc)，所以，运算“o”满足结合律，故是半群；⑶是半群。显然，二元运算“o”在N上是封闭的，所以，是一个代数系统，另一方面，∀a,b,c∈N，有(aob)oc=(2ab)oc=2(2ab)c=4abc，ao(boc)=ao(2bc)=2a(2bc)=4abc，即(aob)oc=ao(boc)，所以，运算“o”满足结合律，故是半群。⑷不是半群。虽然，二元运算“o”在N上是封闭的，即是一个代数系统，但是对于5，3，6，因为，(5o3)o6=5−3o6=5−3−6=4，而5o(3o6)=5o3−6=5−3−6=2，即(5o3)o6≠5o(3o6)，所以，运算“o”不满足结合律，故不是半群。2．解⑴正确。因为，运算显然封闭。⑵正确。(aob)oc=(a+b+ab)oc=a+b+c+ab+ac+bc+abc，ao(boc)=ao(b+c+bc)=a+b+c+ab+ac+bc，即是(aob)oc=ao(boc)，所以°满足结合律。故是半群。⑶∀a∈N，有0oa=0+a+0a=a，又有ao0=a+0+a=a,66 即存在单位元是0，故是独异点。表1fabfab12aaaaabbaabbafabfab34abaaabbaabab3．解f,f,f都不能使<{a,b},∗>构成独异点，因为没有一个函数存在单位元。而134f2的单位元是a,<{a,b},f2>能构成独异点。4．解⑴是，因为M={2,3}关于min是封闭的，故是的子代数；⑵是的子半群；⑶不是，因为S的单位元是4，而4∉M,故不是的子独异点。习题9.20-11．解⑴是，因为实数乘法满足结合律，存在单位元a=1，任意元素a存在逆元素a；⑵是，因为有理数乘法满足结合律，存在单位元1，任意元素a存在逆元素a-1；（3）是，因为复数乘法满足结合律，存在单位元1,任意元素z的逆元素是z共轭复数；（4）是，因为多项式的加法满足结合律，多项式关于加法的单位元是0多项式，任意元素P(x)的逆元素是-P(x).（5）是,因为向量的加法满足结合律，n维实向量关于向量的加法的单位元是n维零向量，任意的n维实向量α的逆元素是-α。2．解可以构成群。⑴因为，对于任意的x,y,z∈I,(xoy)oz=(x+y−2)+z−2=x+y+z−4=x+(y+z−2)−2=xo(yoz)，所以，运算o满足结合律；，⑵关于运算o有单位元2，这是因为对于任意的a∈I,都有ao2=a+2−2=a，且2oa=2+a−2=a；⑶对于任意的a∈I，若要a有逆元b，需要有a°b=b°a=2，即需要a+b-2=b+a-2=2，事实上只要b=a-4即可。因此，对于任意的a∈I，a都可逆，且a的逆元是a-4。综上所述，由⑴，⑵，⑶得出结论I与运算o能构成群。−13．证明因为对于任意的a∈G,a∗a=1，所以a可逆,且a=a，因此，是群。要证明是Abel群，只需证明运算满足交换律，事实上，因为，对于任意的x,y∈G,x∗x=1,y∗y=1，所以(x∗x)∗(y∗y)=1=(x∗y)∗(x∗y)，因此，由结合律则有67 x∗(y∗x)∗y=x∗(x∗y)∗y，再由消去律得：y∗x=x∗y。故是Abel群。−1−1−14．证明当x=aobocoaob时，因为，0aoxoboa=a(a−1obocoa−1ob−1)oboa=boc，0−1−1−1所以，x=aobocoaob是方程aoxoboa=boc的解。下面方程的解是唯一的。0对于a,b,c∈G,若aoxoboa=boc解y，即aoyoboa=boc，由于群中的任何元素都可逆，则对上式两边同时左乘a-1，并两边同时右乘a-1ob-1则得，−1−1−1−1−1−1ao(aoyoboa)o(aob)=ao(boc)o(aob)−1−1−1由结合律则有，y=aobocoaob。证毕。5．证明设1是群G的单位元，若G中存在幂等元a，即a∗a=a因为群中的任何元素都可逆，因此，a也可逆，则有1=a∗a−1=(a∗a)∗a−1=a∗(a∗a−1)=a∗1=a故单位元为G中惟一的幂等元。6．解答案是A，因为存在同态映射f:R→R-{0},f(x)=ex，但不存在同构映射。习题9.31．解1，5，7，11为其生成元，任何与12互素的正整数都可作的生成元。2．证明设H是循环群G的子群，且G的生成元是a。若H={e}，则H是循环群。若H≠{e}，由于H非空，则必存在正整数m>0使am∈H。设m是使am∈H的最小的正整数，若对于任何的an∈H(n∈N)，则由带余除法有n=mk+r,0≤r是的子群。2．解群真子群有如下4个：<{1},∗>，<{1,5},∗>，<{1,7},∗>，<{1,11},∗>。习题9.5⎛10⎞⎛i0⎞⎛0i⎞⎛01⎞1．解⑴设E=⎜⎜⎟⎟,A=⎜⎜⎟⎟,B=⎜⎜⎟⎟,C=⎜⎜⎟⎟，则集合⎝01⎠⎝0−i⎠⎝i0⎠⎝−10⎠G={E,A,B,C,-E,-A,-B,-C}，G关于运算∗的运算表如下。表2G关于运算∗的运算表∗EABC-E-A-B-CEEABC-E-A-B-CAA-E-CB-AEC-BBBC-E-A-B-CEACC-BA-E-CB-AE-E-E-A-B-CEABC-A-AEC-BA-E-CB-B-B-CEABC-E-A-C-CB-AEC-BA-E由表1可以看出G关于运算∗是封闭的。而运算∗是矩阵的乘法运算，因此满足结合律。由表1可以看出G关于运算∗的单位元是E。由表1可以进一步看出关于运算∗，G中的每一个元素都有逆元，E-1=E,A-1=-A,B-1=-B,C-1=-C,(-E)-1=-E,(-A)-1=A,(-B)-1=B,(-C)-1=C。因此，是一个群。⑵G的所有子群是：<{E},∗>,<{E,-E},∗>,<{E,A,-A,-E},∗>,<{E,B,-B,-E},∗>,<{E,C,-C,-E},∗>。⑶证明显然<{E},∗>，<{E,-E},∗>是正规子群，下面证明<{E,A,-A,-E},∗>是正规子群。设H={E,A,-A,-E}，显然有EH=HE=(-E)H=H(-E)=AH=HA=(-A)H=H(-A)={E,A,-A,-E}。又BH={B,C,-C,-B}，HB={B,-C,C,-B}=BH，因此有H(-B)={B,-C,C,-B}=(-B)H。同理可得，CH=HC=H(-C)=(-C)H={C,-B,B,-C}。综上所述，对于任意的a∈G都有aH=Ha，即是正规子群。同理可证，<{E,B,-B,-E},∗>,<{E,C,-C,-E},∗>也是正规子群。2．解5，{3，7，11}，{0，4，8}。习题9.61．解I[i]对于普通加法和乘法能构成环。这是因为：⑴显然I[i]对加法+是封闭的，而复数的加法是满足交换律和结合律的，的单位元是0=0+0i，任意元素a+bi的逆元是-a-bi。所以，是可交换群。⑵I[i]对复数的加法是封闭的，且复数的乘法是满足结合律的，即是半群。⑶复数的乘法对复数的加法满足分配律。综合⑴⑵⑶，I[i]对于普通加法和乘法能否构成环。2．证明⑴首先证明<{a+b2a,b∈I},+,×>是一个环。设R={a+b2a,b∈I}对于任意的a+b2,c+d2∈R，因为，a,b,c,d∈I，所以，(a+c)，69 (b+d)，(ac+2bd)，(ad+bc)∈I，因此，(a+b2)+(c+d2)=(a+c)+(b+d)2∈R，(a+b2)(c+d2)=(ac+2bd)+(ad+bc)2∈R，故R对于加法和乘法都是封闭的。另一方面，实数的普通加法满足结合律和交换律，且关于加法单位元是0，每个元素都有逆元，就是相反数。实数的普通乘法也满足结合律。综合上述是一个环。⑵因为，实数的普通乘法也满足交换律，且R关于乘法有单位元1，又对于a+b2,c+d2∈R，若两者都不为零，则(a+b2)(c+d2)≠0，即无零因子。综合⑴⑵可知，是一个整环。3．证明设F={a+bi⎜a,b∈Q}，对于任意的a+bi,c+di∈F，因为，a,b,c,d∈Q，所以，a+c,b+d,ac-bd,ad+bc∈Q，因此，(a+bi)+(c+di)=(a+c)+(b+d)i∈F，且(a+bi)(c+di)=(ac-bd)+(ad+bc)i∈F，即F关于加法和乘法运算都是封闭的；而普通的加法和乘法都满足结合律和交换律；又关于加法+，F中有单位元0=0+0i，且每个元素a+bi都有逆元-a-bi。故是一个环。另一方面，中有单位元1=1+0i；又对于任何的非零元a+bi，因为，a,b不全为零，所以，a2+b2≠0，因此对于任何的非零元a+bi都有逆元。综上所述，是一个域。复习题九1．解⑴是半群，但不是独异点，更不是群；⑵不是半群；⑶不是半群，⎛10⎞⑷是群，其单位元是⎜⎜⎟⎟。⎝01⎠2．证明对于任意的a,b,c∈R,有(a∗b)∗c=(a+b+ab)∗c=a+b+ab+c+ac+bc+abc同时，a∗(b∗c)=a+b+c+ab+bc+ac+abc，故(a∗b)∗c=a∗(b∗c)，所以满足结合律，故是半群；又存在0∈R，且0∗a=a∗0=0+a+0a=a故0是单位元。综上所述，是独异点。3．证明对于任意的x,y∈S，因为，x∗y=xoaoy，其中a∈S,o为的二元运算，而是半群，又a∈S，所以，xoaoy∈S，即对∗运算是封闭的。又因为是半群，所以，有结合律，即对于任意的x,y,z∈S有，(x∗y)∗z=(xoaoy)oaoz=xoao(yoaoz)=x∗(yoaoz)=x∗(y∗z)故满足结合律，综上所述，是半群。4．证明对于任意a,b,c∈S，由于是半群，所以，有结合律，a*c=c*a且b*c=c*b，则70 (a∗b)∗c=a∗(b∗c)=a∗(c∗b)=(a∗c)∗b=(c∗a)∗b=c∗(a∗b)。5．证明对于任意a,b∈S，若a,b是的幂等元，则a∗a=a，b∗b=b，再由交换律和结合律则，(a∗b)∗(a∗b)=(a∗a)∗(b∗b)=a∗b故a*b也是的幂等元。6．证明对于任意的a,b,c,d,e,f∈S，有∗=，所以，是封闭的，又因为(∗)∗=<(a+c)+e,(b+d+2bd)+f+2(b+d+2bd)f>===∗(∗)因此，是半群；又取<0,0>∈S，所以，∗<0,0>=<0,0>∗=，故存在单位元<0,0>所以是独异点，且∗===∗即交换律成立，故是可交换独异点。7．证明因为，0×0=0∈{0}，所以，运算封闭，又结合律是显然的，故<{0},×>是子半群。但1∉{0},所以，<{0},×>不是子独异点。8．证明N4={0,1,2,3},则{0}，{1}，{0，1}，{0，2}，{0，1，2}，{0，1，2，3}都能与×4构成的子半群，其中<{0},×4>是独异点，但不是的子独异点。9．证明对于任意的a,b∈G，由题设则有，444333a∗b=(a∗b)=(a∗b)∗(a∗b)=a∗b∗a∗b因此，由消去律可得，a∗b3=b3∗a①555444同理，由a∗b=(a∗b)=(a∗b)∗a∗b=a∗b∗a∗b可得，44a∗b=b∗a②再由①②两式可得，44333b∗a=a∗b=(a∗b)∗b=(b∗a)∗b=b∗a∗b由消去律消去上式中的b3可得，b∗a=a∗b。故是可交换群。10．解群只有两个子群H1={0}和H2=N5，其中H1的左陪集和右陪集如下：71 0H1=H10={0},1H1=H11={1},2H1=H12={2},3H1=H13={3},4H1=H14={4}；H2的左陪集和右陪集如下：0H2=H20=1H2=H21=2H2=H22=3H2=H23=4H2=H24=N5。11．证明任取aH,bH∈G/H，因为，是可交换群，所以对于a,b∈G，有a*b=b*a又因为，是的正规子群，所以，任意的a∈G，都有aH=Ha由以上两式，则有，(aH)*(bH)=a(Hb)*H=a(bH)*H=(ab)(H*H)=(ab)H(bH)*(aH)=b(Ha)*H=b(aH)*H=(ba)(H*H)=(ba)H=(ab)H即(aH)*(bH)=(bH)*(aH)。由于aH,bH的任意性，所以，商群也是可交换群。12．证明⑴先证明f是双射。对任意的,,-1=a*x-1x1x2∈G若f(x1)≠f(x2)，即有a*x1*a2*a，由群的消去律可得x1=x2，所以，f是单射。又对于任意的y∈G，则有x=a-1*y*a∈G，使得f(x)=a*x*a-1=a*(a-1*y*a)*a-1=y。即f是满射，故f是双射。⑵再证f是同态映射。对于任意的x1,x2∈G有f(x∗x)=a∗(x∗x)∗a−1=(a∗x)∗(a−1∗a)∗(x∗a−1)121212=(a∗x∗a−1)∗(a∗x∗a−1)=f(x)∗f(x)1212综合⑴⑵可知，f是到其自身的同构映射。第十章格和布尔代数习题10.11．解⑴不是，因为L中的元素对{2,3}没有最小上界；⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a,b，都有最小上界和最大下界；⑶是，与⑵同理；⑷不是，因为L中的元素对{6,7}没有最小上界不存在最小上界。2．证明⑴因为，a≤b,所以，a∨b=b；又因为，b≤c,所以，b∧c=b。故a∨b=b∧c；⑵因为，a≤b≤c,所以，a∧b=a,b∧c=b,而a∨b=b，因此，(a∧b)∨(b∧c)=b；又a∨b=b,b∨c=c,而b∧c=b,因此，(a∨b)∧(b∨c)=b。即(a∧b)∨(b∧c)=(a∨b)∧(b∨c)。习题10.21．解由图1知：＜S1,≤＞不是＜L,≤＞的子格，这是因为，e∨f=g∉S1;＜S2,≤＞不是＜L,≤＞的子格，∵e∧f=c∉S2;＜S3,≤＞是＜L,≤＞的子格.2．解S24的包含5个元素的子格有如下的8个：S1={1,3,6,12,24},S2={1,2,6,12,24},S3={1,2,4,12,24},S4={1,2,4,8,24},S5={1,2,3,6,12},S6={1,2,4,6,12},S7={2,4,6,12,24},S7={2,4,8,12,24}.3．证明因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是的子集，即是的子代数，故是子格。72 24g812ef46cbd213a图1图24．证明由(10-4)有，a∧b≤a,由已知a≤c,由偏序关系的传递性有，a∧b≤c；同理a∧b≤d。由(10-5)和以上两式有，a∧b≤c∧d.5．证明因为由(10-4)有，a∧b≤a，因此，(a∧b)∨(c∧d)≤a∨(c∧d)①由分配不等式有，a∨(c∧d)≤(a∨c)∧(a∨d)②再由由(10-4)有，(a∨c)∧(a∨d)≤a∨c③由偏序关系的传递性和①②③则有，(a∧b)∨(c∧d)≤a∨c同理(a∧b)∨(c∧d)≤b∨d因此有，(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)。习题10.31．解⑴是，全上界是24，全下界是1；⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。2．解图3是两个格的哈斯图，其中图⑴是有补格但不是分配格的例子；图⑵是分配格但不是有补格的例子。11abcbac00⑴⑵图33．证明先证充分性。由已知条件知，对于任何的a,b,c∈L,有(a∨b)∧c≤a∨(b∧c)，因此和等幂律、交换律可得，(a∨b)∧c=((b∨a)∧c)∧c≤(b∨(a∧c))∧c=((a∧c)∨b)∧c≤(a∧c)∨(b∧c)①又因为，(a∧c)≤(a∨b)∧c且(b∧c)≤(a∨b)∧c，所以，(a∧c)∨(b∧c)≤(a∨b)∧c②73 由①②可得，(a∧c)∨(b∧c)=(a∨b)∧c再由交换律得到，c∧(a∨b)=(c∧a)∨(c∧b)③由此式容易证明c∨(a∧b)=(c∨a)∧(c∨b)④由③④可知它是分配格。再证必要性。因为是分配格，则(a∨b)∧c=(a∧c)∨(b∧c)≤a∨(b∧c)。4．证明因为，(a∧b)∧(a∨b)=(a∧b∧a)∨(a∧b∧b)=0∨0=0；同理有，(a∧b)∨(a∨b)=(a∨a∨b)∧(b∧a∨b)=1∨1=1；又因为补元素是唯一的，故(a∧b)=a∨b成立。习题10.41．解是布尔代数，因为是有补分配格。2．证明因为，是布尔代数，所以，运算-，∨,∧在B上都是封闭的，因此，由运算⊕的定义可知，运算⊕在B上也是封闭的。又运算∨,∧都满足交换律。因此，对于任意的a,b∈B,a⊕b=(a∧b)∨(a∧b)=((a∧b)∨a)∧((a∧b)∨b)=(b∨a)∧(a∨b)=(a∨b)∧(a∨b)由其对称性可知⊕满足交换律。下面证明运算⊕满足结合律，对于任意的a,b,c∈B由上式则有(a⊕b)⊕c=[(a∨b)∧(a∨b)]⊕c=([(a∨b)∧(a∨b)]∨c)∧((a∨b)∧(a∨b)∨c)=(a∨b∨c)∧(a∨b∨c)∧[(a∧b)∨(a∧b)∨c]=(a∨b∨c)∧(a∨b∨c)∧(a∨b∨c)∧(a∨b∨c)同理可得a⊕(b⊕c)=(a∨b∨c)∧(a∨b∨c)∧(a∨b∨c)∧(a∨b∨c)即，(a⊕b)⊕c=a⊕(b⊕c)，亦即⊕满足结合律。下面再证0是关于⊕的单位元。事实上对于任意的a∈B，a⊕0=(a∧0)∨(a∧0)=(a∧1)∨0=a。最后证明任意的a∈B关于运算⊕都可逆，且其逆元就是a自身，事实上a⊕a=(a∧a)∨(a∧a)=0∨0=0综上所述，是交换群。74 复习题十1．证明显然，a,b∈B，所以，B非空。对于任意的x,y∈B，则a≤x≤b,a≤y≤b，由格的保序性和等幂律则有，a≤x∨y≤b,a≤x∧y≤b即集合B对于运算∨和∧是封闭的。因此，是的子格。而子格也是格，故也是一个格。2．证明因为，是一个格，由格的分配不等式则得（(a∧b）∨(a∧c)）∧((a∧b)∨(b∧c))≥(a∧b)∨(a∧b∧c)=a∧b①（a∧b）∨(a∧c)≤a∧(b∨c)②（a∧b）∨(b∧c)≤b∧(a∨c)③由②③和格的保序性可得，((a∧b)∨(a∧c))∧((a∧b)∨(b∧c))≤(a∧(b∨c))∧(b∧(a∨c)=a∧b∧(b∨c)∧(a∨c)=a∧b④由①④和反对称性则有，((a∧b)∨(a∧c))∧((a∧b)∨(b∧c))=a∧b。3．证明因为是格，对任意a,b,c∈L,(a∧b)∨(b∧c)∨(c∧a)≤[((a∧b)∨b)∧((a∧b)∨c)]∨(c∧a)=[b∧((a∧b)∨c)]∨(c∧a)≤[b∧(a∨c)∧(b∨c)]∨(c∧a)=[b∧(a∨c)]∨(c∧a)≤(b∨(c∧a))∧((a∨c)∨(c∧a))=(b∨(c∧a))∧(a∨c)≤(b∨c)∧(b∨a)∧(a∨c)=(a∨b)∧(b∨c)∧(c∨a)。4．证明因为有限格都是有界格，而有界格必存在最大元素和最小元素，故有限格一定有最大元素和最小元素。5．证明因为，a≤b,所以，a∨b=b；因此有，a∨(b∧c)≤(a∨b)∧(a∨c)=b∧(a∨c)。6．证明因为，h将运算∨传送到运算∪，将运算“-”传送到运算“＇”，所以，对于任意的x,x1,x2∈B1有：h(x1∨x2)=h(x1)∪h(x2)①h(x)=(h(x))′②所以，对于任意的a,b∈B1,而a∧b=(a∨b)，因此有：h(a∧b)=h((a∨b))=(h(a∨b))′=(h(a)∪h(b))′=((h(a))′∪(h(b))′)′=h(a)∩h(b)。即h将运算∧传送到运算∩。7．证明由习题10.4第2题可知是一个交换群。由于，在布尔代数中∧是可结合的且是可交换的，由∗运算的定义可知，∗是可结合的且是可交换的。由∗运算的定义可知可进一步看出，关于∗运算的单位元是布尔代数的全上界1。事实上，对于任意的a∈B,有a∗1=a∧1=a因此，要证明是一个含幺交换环，只需证明∗对⊕满足分配律。事实上，对于任意的a,b,c∈B,a∗(b⊕c)=a∧[(b∧c)∨(b∧c)]=(a∧b∧c)∨(a∧b∧c)(a∗b)⊕(a∗c)=(a∧b)⊕(a∧c)75 =((a∧b)∧(a∧c))∨((a∧b)∧(a∧c))=((a∧b)∧(a∨c))∨((a∨b)∧(a∧c))=(a∧b∧a)∨(a∧b∧c)∨(a∧a∧c)∨(a∧b∧c)=(a∧b∧c)∨(a∧b∧c)即a∗(b⊕c)=(a∗b)⊕(a∗c)综上所述，是一个含幺交换环。76'