⑸(p(q)((((q(( q((r))是5层公式，这是因为一层：p(q，(q，(r二层：q((r三层：(q(( q((r)四层：(((q(( q((r))2．解 ⑴A=(p(q)(q是2层公式。真值表如表2-1所示：表2-1p q 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 ⑵是3层公式。真值表如表2-2所示：表2-2p q 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 ⑶是3层公式。真值表如表2-3所示：表2-3p q r 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 ⑷是4层公式。真值表如表2-4所示：3．解 ⑴真值表如表2-5所示：表2-5p q 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1所以其成真赋值为：00，10，11；其成假赋值为01。⑵真值表如表2-6所示：表2-6p q r 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。
⑶真值表如表2-7所示，所以其成真赋值为：00，11；成假赋值为：01，10，。4．解 ⑴设，其真值表如表2-8所示：表2-8p q 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 故为重言式。⑵设A=(p(q)(((p(q)，其真值表如表2-9所示：表2-9p q p(q p(q ((p(q) A 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 故A=(p(q)(((p(q)为矛盾式。⑶设A=(p(q)(((p(q)，其真值表如表2-10所示：表2-10p q 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 故A=(p(q)(((p(q)为可满足式。⑷设，其真值表如表2-11所示：表2-11p q r 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 故为重言式。
习题1.31．解 ⑴真值表如表2-12所示：表2-12p q 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 由真值表可以看出和所在的列相应填入值相同，故等值。⑵真值表如表2-13所示：表2-13p q 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出和所在的列相应填入值相同，故等值。⑶真值表如表2-14所示：表2-14p q 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 由真值表可以看出(p和(p(q)((p((q)所在的列相应填入值相同，故等值。⑷真值表如表2-15所示：p q r q(r p((q(r) p(q (p(q)(r 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 表2-15由真值表可以看出p((q(r)和(p(q)(r所在的列相应填入值相同，故等值。
2．证明 ⑴(p(q)(( ((p(q)( (p(q)(( p((q)( p( (q((q)( p。⑵(p(q)((q(p)(((p(q) (((q(p)(((p((q)(((p( p)(( q((q)((q( p)(( p(q)(((p((q)。⑶由⑵可得，((p(q)(((( p(q)(((p((q))((( p((q)((p(q)((q((p)(((p(q)((p(q。⑷p((q(r)(( p(((q( r)(( q(((p( r)( q(( p (r)。⑸⑹3．解 ⑴((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-16p q (p (q p(q (q ((p A 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 所以公式是重言式。⑶真值表如表2-17所示，所以公式是矛盾式。
表2-170 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 ⑷真值表如表2-18所示，所以公式是重言式。表2-180 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 ⑸真值表如表2-19所示，所以公式仅为可满足式。表2-190 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 ⑹真值表如表2-20所示，所以公式是重言式。表2-20p q r p(q r(q p(r (p(q)((r(q) (p(r)(q A 0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 15．解 ⑴设p：他努力学习；q：他会通过考试。则命题符号化p(q。
其否定((p(q)( p((q。所以语句的否定：他学习很努力但没有通过考试。⑵设p：水温暖；q：他游泳。则命题符号化p(q。其否定((p(q)( p((q。所以语句的否定：当且仅当水不温暖时他游泳。⑶设p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化p((q((r)其否定(( p((q((r)) ((((p((q((r))( 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：明天我将去上海。命题符号化。2．解 ⑴⑵⑶3．证明 因为，{}是功能完备联结词集，所以，含有{}外的其他联结词的公式均可以转换为仅含{}中的联结词的公式。又因为即含有的公式均可以转换为仅含{}中的联结词的公式。因此，含{}外其他联结词的公式均可以转换为仅含{}中的联结词的公式。故{}是功能完备联结词集。4．证明 是极小功能完备集，因而只需证明中的每个联结词都可以用( 表示，就说明是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，(p(((p(p)(p(p，p(q((((p(q)(((p(q)((p(q)((p(q)。对于证明是极小功能完备集，可类似证明。习题1.51．解 ⑴；⑵2．解 ⑴即为其析取范式。即为其合取范式。⑵即为其合取范式。(p((q(r)((p(((q(r)(((q((r))(((p(q(r)(((p((q((r) 即为其析取范式。⑶即为其合取范式。为其析取范式。⑷即为其析取范式和合取范式。3．解 ⑴即为其主合取范式。
其主析取范式为(3(p(q。⑵。故其主析取范式为((0,1,2,3)=((p((q)(((p(q)((p((q)((p(q)。⑶即为其主合取范式。其主析取范式为((2,4,5,6,7) ( ((p(q((r)((p((q((r)((p((q(r)((p(q((r)((p(q(r)。⑷即为其主合取范式。其主析取范式为。4．解 ⑴真值表如表2-21所示, 所以其极小项是p((q，极大项为p(q，p((q，(p((q。表2-21p q 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 其主析取范式是：p((q，主合取范式为：(p(q)(( p((q)(((p((q)。⑵真值表如表2-222所示, 所以其极小项是(p(q, p((q, p(q, 极大项为p(q。表2-22p q 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 其主析取范式是：((p(q)((p((q)((p(q)，主合取范式为：p(q。⑶真值表如表2-23所示，所以其极小项是(p(q(r,p((q((r, p((q(r, p(q((r,p(q(r,表2-23p q r 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 极大项为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-24p q r 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 15．解 ⑴((p(q)(((((p((q))(((p(q)((p(q)( q( ((p(q)((p(q)，故⑴为可满足式。⑵故⑵为重言式。⑶((p((q(r))(((p(q)((p(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)(((q((r)(0。
故⑶为矛盾式。⑷故仅为可满足式。6．证明 ⑴右边已经是主合取范式。而左边主合取范式已是(p((q，因此，((p( q)((p((q，证毕。⑵右边(p( q)((p((q)已经是主合取范式。p(p((q((q)( (p( q)((p((q)。因此，。⑶左边p((q(r)((p(((q(r)((p((q(r，而右边(((p(q)(r((p((q(r，因此，。习题1.61．解 设p：这里有演出；q：这里通行是困难的；r：他们按照指定时间到达。前提：p(q, r((q,r结论：(p证明①r P②r((q P③(q T①②假言推理④p(q P⑤(p T③④拒取式2．⑴证明①s P②s(p P③p T①②假言推理④p(q P⑤q T③④假言推理⑵证明①r P附加前提引入②r(q P③q T①②假言推理④p((q P⑤(p T③④拒取式⑥(p(s P⑦s T⑤⑥假言推理⑧r(s T①⑦CP⑶证明①p P否定结论引入②p(q P③q T①②假言推理④q(r P⑤r T③④假言推理⑥(r(s P⑦(r T⑥化简⑧r((r T⑤⑦合取⑷证明①p P附加前提引入②(p(q P③q ①②析取三段论④r((q P⑤(r ③④拒取式⑥p((r ①⑥CP⑸证明①p P附加前提引入②p((q(r) P③q(r T①②假言推理④q P附加前提引入⑤r T③④假言推理⑥(r(s)(t P⑦(r((s(t T⑥蕴涵等价式⑧(s(t T⑤⑦析取三段论⑨(h((s((t) P⑩(s(t (h T⑨假言易位⒒ h T⑧⑩假言推理⒓ q(h T④⒒CP13. p((q(h) T①⒓CP3．解 推理不正确。
在①到②化简时，只能对整个公式进行而不是子公式。4．解 正确。⑴P，⑵P附加前提引入；⑶T①②析取三段论；⑷P；⑸T③④假言推理；⑹P；⑺T⑤⑥假言推理；⑻T②⑦CP。5．解 设p：张三努力工作，q：李四高兴，r：王五高兴，s：刘六高兴前提：p((q(r)，q((p，s((r结论：p((s证明：①p P附加前提引入②p((q(r) P③q(r T①②假言推理④q((p P⑤(q T①④拒取式⑥r T③⑤析取三段论⑦s((r P⑧(s T⑥⑦拒取式⑨p((s T①⑧CP6．解 设：p：天下雪；q：马路结冰；r：汽车开得快；s：马路塞车。前提：p(q，q((r，(r(s，(s结论：(p证明①p(q P②q((r P③p((r ①②推理三段论④(r(s P⑤p(s ③④推理三段论⑥(s P⑦(p ⑤⑥拒取式复习题11．解 ⑴ 设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：李春会唱歌。命题符号化((p((q)(((p(q)。而((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的极小项为：；；；；；；；。相应的，A的极大项对应于其真值表中的成假赋值，成假赋值对应二进制数转化为十进制数就是A的极大项的下标。由此可得，A的极大项为：；；；；；；；。
⑵由问题⑴得到了A的极小项和极大项，于是与A等值的主析取范式和主合取范式可以直接得到，分别为：；。⑶从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． 证明 ⑴⑵⑶⑷6．解 ⑴公式的真值表如表2-27所示：表2-27p 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0从真值表可见，公式所在列的填入值有1也有0，故仅为可满足式。(p((q)(((q((p)(((p((q)((q((p)(((2,3)为其主合取范式，可见公式仅为可满足式。
⑵公式真值表如表2-28所示：表2-28p q r 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 p((p(q(r)((p(p(q(r(1(((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.从真值表可见，公式所在的列的填入值均为1，由等值演算，以及求出的主析取范式均说明公式是重言式。7．⑴证明①p P附加前提引入②p((q(r) P③q(r T①②假言推理④q P附加前提引入⑤q((r(s) P⑥r(s T④⑤假言推理⑦q(s T③⑥假言三段论⑧p((q(s) T①⑦CP⑵证明①(w P②u(w P③(u T①②拒取式④(s(u P⑤(s T③④析取三段论⑥(r(s P⑦(r T⑤⑥析取三段论⑧(p(q)(r P⑨((p(q) T⑦⑧拒取式⑩(p((q) T⑨德(摩根律⑶证明①p P附加前提引入②p(q(r P③q(r T①②假言推理④q((p P⑤(q T①④拒取式⑥r T③⑤析取三段论⑦s((r P⑧(s T⑥⑦拒取式⑨p((s T①⑧CP8．解①p(r P②p T①化简③p(q P④q T②③假言推理⑤((q(s) P⑥(q((s T⑤德(摩根律⑦(q T⑥化简⑧(q(q T④⑦合取由⑧得到矛盾，可见p(q，((q(s)，p(r不能同时成立。
9．解 设p：小王曾经到过受害人的房间，q：小王11点以前离开，r：小王犯了谋杀罪，s：看门人看到小王。符号化：(((p((q)(r)(p((q(s)((s)(r。⑴形式构造推理证明前提：(p((q)(r，p，q(s，(s结论：r证明①(s P②q(s P③(q T①②拒取式④p P⑤p((q T③④合取⑥(p((q)(r P⑦ T⑤⑥假言推理⑵真值表技术：真值表如表2-30所示，设A=(((p((q)(r)(p((q(s)((s)。表2-29p q r s (q (s p((q (p((q)(r q(s A 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 由真值表可以看出：(((p((q)(r)(p((q(s)((s)(r，所以，(((p((q)(r)(p((q(s)((s)(r成立。
⑶等值演算方法(((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）将回答‘是’，他的回答对吗？”设：强盗A回答“对”；：强盗B回答“对”；：这扇门（A）是生门。因为，两个强盗一个总说真话，而另一个强盗一个总说假话，因此该问题符号化为：((p(q)(r。((p(q)(r((((p(q)((p((q))(r(((p(q(r)((p((q(r)逻辑学家的提问可知，r和q都为真，由公式可以看出这时(p为真，即p为假。所以，当被问强盗A回答“否”，则逻辑学家开启所指的门从容离去。当被问强盗A回答“对”，则逻辑学家开启另一扇门从容离去。第二章 谓词逻辑习题2.11．解 ⑴个体：离散数学；谓词：…是一门计算机基础课程。
⑵个体：田亮；谓词：…是一名优秀的跳水运动员。⑶个体：大学生；谓词：…要好好学习计算机课程；量词：所有。⑷个体：推理；谓词：…是能够由计算机来完成的；量词：一切。2． 解 ⑴设：x是舞蹈演员；a：小芳。命题符号化：。⑵设：x是一位有名的哲学家；a：苏格拉底。命题符号化：。⑶设：x作完了他的作业家；a：张三。命题符号化：。⑷设：x身体很好；a：我。命题符号化：。3．解 ⑴选取个体域为整数集合。设：x的平方是奇数；：x是奇数。命题符号化：。⑵选取个体域为所有国家的集合。设：x在南半球；：x在北半球。命题符号化：。⑶选取个体域为所有人的集合。设：x在中国居住；：x是中国人。命题符号化：⑷选取个体域为所有人的集合。设：x是艺术家；：x是导演；：x是演员。命题符号化：(x(M(x)(F(x)(G(x))。⑸选取个体域为所有猫的集合。设M(x)：x是好猫；F(x)：x捉耗子。命题符号化：(x(M(x)((x(F(x)(M(x))。4．解 ⑴①设：x喜欢开汽车；：x喜欢骑自行车。命题符号化：。②设：x喜欢开汽车；：x喜欢骑自行车；：x是人。命题符号化：。⑵①设：x必须学好数学。命题符号化：。②设：x必须学好数学；：x是学生。
命题符号化：。⑶①设：x的平方是质数；：x是质数。命题符号化： 。②同①。③设：x的平方是质数。命题符号化：。习题2.21．解 ⑴(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．解 ⑴。⑵。3．解 ⑴((xP(x)((yQ(x))(F(s,z)；⑵(y(P(s,y)(((zQ(s,z)(R(s,y,v)))((x(rS(x,t,r)。离散数学习题七答案4．解 ⑴的真值分别为：0，1，0。⑵的真值分别为：0，1，0。⑶的真值分别为：1，1，1。⑷的真值分别为：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))可真可假。因此，仅为可满足式。习题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)((x(A(x)((B(x)((x(C(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))((x(P(x)((xQ(x)(((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)((x(Q(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))()(1(1(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⑶证明①((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)：是学生；N(x)：是教师；F(x)：是骗子；R(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)：是学术会成员；N(x)：是工人；R(x)：是专家；Q(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②化简⑥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)((y Q(y)(((xP(x)((yQ(y)((xP(x)((yQ(y)因此，原公式为逻辑有效式。7．⑴证明 (z(A(x)(B(x))((x((A(x)(B(x))((x(A(x)((x B(x))(((xA(x)((x B(x))((xA(x) ((x B(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)证明①(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=；⑵：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, k(N}；⑶ C={x( x=5n, n(I}。3．解 ⑴：1，2，3，4，6，9，12，18，36；⑵：a，b；⑶：1，，。习题3.21．解 互不相同。⑴是不包含任何元素的空集，⑵是以空集(为元素的单元素集合，⑶是以0为元素的单元素集合，但和⑵的集合中的元素不同。2．证明 若，则；反之，若，则 ，，因此，。3．解 ⑴设，则；⑵设，则；⑶设，则；⑷设，则。4．解 ⑴M(T；⑵N(P；⑶P(T=( 。5．解 由题意可得：；；；。⑴A((B((C(D)) = A(B(C(D ={0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64}；⑵A((B((C(D))=(；⑶因为，A(C={0,1,2,3,6,7,8,9,12,15,18,21,24,27,30},所以，B- A(C={4,5}；⑷，=；6．解 ⑴、⑵的文氏图如图1-1所示，图中阴影部分表示所求集合。7．解 ⑴所求集合的集合成员表如表1-1所示。表1-1A B 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1 ⑵所求集合的集合成员表如表1-2所示。
表1-2A B C 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 08．证明 ⑴===⑵===⑶A- (B(C)==9．证明 ⑴⑵。 因为，，则，所以，，因此，。⑵⑶。 ，。⑶⑴。因为，，所以，B=( (B=因此。习题3.31．解 ⑴(((=0； ⑵({(}(=1； ⑶({1,2,{3,{2,1}}}(3； ⑷({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+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, x能被6整除}，则，，因此，=20-1=19。习题3.41．解 ⑴20=2(7+6；⑵58=2(27+4；⑶3=0(8+3；⑷57=3(19+0。2．解 ⑴因为,。所以，14和35的最大公因数为7，即(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，即(34,58)=2，且由以上各式可推得2=12(34-7(58。⑶因为，，。所以，180和252的最大公因数为36，即(180,252)=36，且由以上各式可推得36=3(180-2(252。⑷因为，，，。所以128和77互素，即(128,77)=1，且由以上各式可推得1=5(77-3(128。3．解 ⑴因为，，所以(108,72)=36，因此LCM(108,72)=108(72/36=216。⑵因为，，，所以(245,175)=35，因此LCM(245,175)=245(175/35=1225。⑶因为，，，所以(252,180)=36，因此LCM(252,180)=252(180/36=1260。⑷因为，，，，，所以(64,81)=1，因此LCM(64,81)=64(81=5184。4．证明 ⑴设，则存在整数、，使得 ，因为是、的最大公因数，所以，、。因此，①另一方面，因为是、的最大公因数，所以、，因此，与互素，否则与有大于1的公因数，则d2(c，d2(d1，又，由整除的传递性，所以，。
因此，与有大于1的因数，这与(a,c)=1矛盾。由于与互素，且，由定理6，则，又，因此②由于、都是正整数，由①②可得。⑵因为b,c都和a互素，则(a,b)=1，(a,c)=1，由⑴则有(a, bc)=1，即bc也和a互素。5．证明 设(a,b)=d，则d(a，d(b。因为c>0，所以，cd(ac，cd(bc。另一方面，因为(a,b)=d，所以存在s,t(I,使得sa+tb=d，此式两边同乘c得sac+tbc=cd因此，对于任何的正整数e, 若e(ac，e(bc，则e(cd。又因为cd>0，故cd是ac和bc的最大公因数，即(ac,bc)= cd= c((a,b)。6.证明 因为a(m，所以存在整数，使得又b(m，即，而、互素，由定理6，则有。因此，存在整数q1，使得，代入既可得即abm。7.证明 设（）,由，，则。同理，由，，则。即为、的公倍数，又是、的最小公倍数，因此，，即，所以mk。复习题31. 解 ⑴S5={3，5},,所以，X中不含元素3,5。故。⑵因为, 所以,因此或。⑶因为，X(S2=S1，所以，S1-S2(X，因此，X=S3或S1。
⑷S2={2，4，6，8},，所以X中不含元素2,4,6,8,所以X=S3或,但X(S4，故X=S5。⑸因为X(S1，所以，X=S2, S3, S4, S5，而X(S3=(，即X中无奇数，所以，X=S2。2.解 是可以作到的。如，，则.3.解 ⑴，则；⑵，则；⑶，则；⑷={{1，2}}，则。4.证明 对于任意的X(P(B)，则，又,，所以X(P(A)，由的任意性可知, .5.解 ⑴可构成个子集。⑵其中有个子集中元素个数为奇数。6.⑴证明 左边======右边,故原题得证.⑵证明==7.解 ⑴=；⑵=；⑶=；⑷=；⑸=。8. 证明 若，对于任意的x(B，⑴若x(A，则x(A(B，所以，x(A(B，则x(A(C，由可得x(A(C，而，则x(A(C，所以x(C；因此，B(C。⑵若x(A，则x(A(B，又x(B，所以，x(A(B，由且，可得，x(A(B，因此，x(A(C，但且，所以，x(C，因此，B(C。采用同样的方法可证。故。9.方法⑴证明 对于任意的x((A-B)((B-A)，则或，即有,或者；当时,且，当时,亦有且，故有。因此，同理可证综上知,方法⑵作集合成员表如表1-4所示可见与对应填入值相同故.表1-4A B A-B B-A 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 0 方法(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；又；，则|A∩B|=6+3-8=1，所以|A-B|=|A|-|A∩B|=3-1=2；==8-2=6。12.证明 因为(a，b)=d，则存在整数、，使得又因为a，b不全为0，所以(a，b)=d，因此，、所以，、都是整数，由此可得所以，对于任意的正整数c，若，则c(1，因此。反之，因为d是a，b的正因数，所以、都是整数，又，则存在整数、，使得两边乘以得因此，对于任何的正整数c，若c(a，c(b，则c(d，故（a，b）=d。第四章 关系习题4.11.解 A(B={(a,1),(a,2),(b,1),(b,2),({a,b},1),({a,b},2)}，B(A={(1,a), (1,b), (1, {a,b}),(2, a), (2, b), (2, {a,b})}，B ( B={(1,2),(1,2),(2,1),(2,2)} ，B3={(1,1,1),(1,1,2),(1,2,1),(1,2,2), (2,1,1),(2,1,2),(2,2,1),(2,2,2)} 。
2.解 P(A)={, {x}, {y}, {x, y}}，因此，P(A)(A={<, x>, <, 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=⑵正确。因为，(<x, y>( (A-B)(C(x(A-B)∧yC(xA∧xB∧yC(xA∧yC∧xB∧yC(<x, y>A(C∧<x, y>B(C(<x, y>(A(C-B(C) 。所以，(A-B)(C((A(C-B(C) 。又因为，(<x, y>((A(C-B(C)(<x, y>(A(C∧<x, y>(B(C( (xA∧yC)∧[(x(B∧y(C)((x(B∧y(C)( (x(B∧y(C)]( xA∧(x(B∧y(C) ( (xA∧x(B)∧y(C( x(A-B)∧yC(<x, y>( (A-B)(C。
所以，(A(C-B(C)((A-B)(C。综上所述，(A–B)(C=(A(C–B(C)。⑶正确。例如A=，A(A=，显然AA(A。但是当A≠时，因为A(A是由集合A中的两个元素的序偶组成的集合，所以AA(A一般不成立。4.证明 (1)(<x, y>A((B∪C)((xA∧y(B∪C))((xA∧(yB∨yC))((xA∧yB)∨(xA∧yC)((<x, y>A(B) ∨(<x, y>A(C)(<x, y>((A(B) ∪(A(C))因此A((B∪C)=(A(B)∪(A(C)。同理可证(2)。5.证明 ⑴(<x, y>(A(C)∪(B(D)(<x, y>(A(C)∨<x, y>(B(D)(<x, y>(A(C)∨<x, y>(B(D)((xA∧yC)∨(xB∧yD)((xA∨xB)∧(xA∨yD)∧(yC∨xB)∧(yC∨yD)((xA∨xB)∧(yC∨yD)(x(A∪B)∧y(C∪D)(<x, y>(A∪B)((C∪D)。因此，(A(C)∪(B(D)((A∪B)((C∪D)。
⑵设(xA，若<x, x>A(A，而A(A=B(B，所以，<x, x>B(B，即xB，因此AB；同理可证BA；故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={<a, a>, <a, b>, <a, c>, <a, d>, <b, a>, <b, b>, <b, c>, <b, d>, <c, a>, <c, b>, <c, c>, <c, d>, <d, a>, <d, b>, <d, c>, <d, d>}；I={<a, a>, <b, b>, <c, c>, <d, d>}。
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)对于任意元素xA，xdom(R1∪R2)((y(<x, y>R1∪R2)((y(<x, y>R1∨<x, y>R2)(xdom(R1)∨xdom(R2)(x(dom(R1)∪dom(R2))故dom(R1∪R2)=domR1∪domR2(2)对于任意元素yByran(R1∩R2)((x(<x, y>R1∩R2)((x(<x, y>R1∧<x, y>R2)((x(<x, y>R1)∧(x (<x, y>R2) (yranR1∧yranR2(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>}，，，。关系图如下：习题4.31.解 从关系复合的定义来求：R1·R2={<1, 4>, <1, 3>, <3, 2>, <4, 2>}；R2·R1={<1, 3>, <2, 3>}；R12=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> }；R1-1={<1, 1>,<1, 2>,<1, 3>,<2, 1>,<2, 2>,<3, 1>, <3, 2>, <3, 3>}；(2)利用矩阵求解，；；；；。关系图如图4-2：4.解 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。5.解=，因此，，一般地，。6.证明 ⑴对于任意的<a,b>((R-S)-1，则<b,a>(R-S，所以，<b,a>(R，但<b,a>(S，因此，再由逆关系的定义有，<a,b>(R-1，而<a,b>(S-1，故<a,b>(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>(B×A，则<a,b>(A×B，所以，<b, a>((A×B)-1，即B×A((A×B)-1，另一方面，因为，对于任意的a(A,b(B都有，<b,a>((A×B)-1，所以，则<a,b>(A×B，所以，<b, a>(B×A，即(A×B)-1(B×A。综合上述有，(A×B)-1=B×A。⑶用反证法证明-1=，假设存在a(A,b(B使得，<b,a>(-1，则<a,b>(，这与是空集矛盾。
⑷先证明R(S(R-1(S-1。对于任意的a(A,b(B，若<b,a>(R-1，由逆关系的定义则<a,b>(R，而R(S，所以，<a,b>(S，因此，<b,a>(S-1，即R-1(S-1。再证明R-1(S-1(R(S。若<a,b>(R，则<b,a>(R-1，而R-1(S-1，所以，<b,a>( S-1，因此，<a,b>(S，即R(S。习题4.41.解 如表4-2关系 自反的 反自反的 对称的 反对称的 传递的 R1 N N Y N Y R2 N Y Y N N R3 N Y N Y N2.解 ⑴R具有自反性，因为对于任意的xI，x(x-1)=x(x-1)，即<x, x>R，所以R具有自反性；⑵因为R具有自反性，所以R不具有反自反性；⑶R具有对称性，因为对于任意的x, yI ，若<x, y>R，则x(x-1)=y(y-1)，所以y(y-1)=x(x-1)，即<y, x>R，因此R具有对称性；⑷显然R不具有反对称性；⑸R具有传递性，设<x, y>R，<y, z>R，即x(x-1)=y(y-1)，y(y-1)=z(z-1)，显然有x(x-1) =z(z-1)，即<x, z>R，所以R具有传递性。
3.解 (1)R={<0, 0>, <0, 1>, <0, 2>, <0, 4>, <1, 0>,<1, 1>, <1, 2>, <1, 4>, <2, 0>, <2, 1>, <2, 2>,<4, 0>, <4, 1>}，关系图如图4-3。⑵R具有对称性。4.解 若A上关系R是反对称的，则R∩R-1关系矩阵MR∩R-1中最多只有主对角线上有非零值，即最多只有|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，有 <x, x>(R1，且<x, x>(R2，因此，<x, x>R1·R2，故R1·R2是A上的自反关系。
习题4.51.解 r(R1)=R1∪IA={<a, a>, <a, b>, <b, b>, <b, c>,<c, c>}；s(R1)=R1∪={<a, b>, <b, a>, <b, c>, <c, b>}；t(R1)={<a, b>, <a, c>, <b, c>}；r(R2)=R2∪IA={<a, a>, <a, b>,<b, b>,<b, c>, <c, a>, <c, c> }s(R2)=R2∪={<a, a>, <a, b>, <a, c>,<b, a>,<b, c>, <c, a>, <c, b>}t(R2)={<a, a>,<a, b>,<a, c>,<b, a>,<b, b>,<b, c>, <c, a>, <c, b>, <c, c>}关系矩阵如下：，，，，，，，。
关系图如图4-4：2.解 ，，则；；，，；；。3.证明 ⑴因为，R1R2，所以，IA∪R1IA∪R2，即r(R1)(r(R2)。⑵因为，R1R2，由习题4.3第6⑷题可得，所以，，即s(R1)(s(R2)。⑶因为，R1R2，所以，，则，即t(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)；另一方面，，下面分两种情况来证明。①如果a=b，则<a,b>(IA，所以；②如果a≠b，则，因此，，若，则，所以，，同理，若，则，所以，。故r(R1∪R2) ( r(R1)∪r(R2)。综上所述，r(R1∪R2)=r(R1)∪r(R2)。⑵因为R1R1∪R2，且R2R1∪R2，所以由第3题有s(R1)s(R1∪R2) ，且s(R2)s(R1∪R2)，因此，s(R1)∪s(R2)s(R1∪R2)；另一方面，，则或，①若，则或，所以，或，因此，；②若，则，所以，或，因此，或，所以，或，因此，。故s(R1∪R2)( s(R1)∪s(R2)。
综上所述，s(R1∪R2)=s(R1)∪s(R2)。⑶对于任取的<a, b>( t(R1)∪t(R2)，则<a, b>( t(R1)或<a, b>(t(R2)。若<a, b>( t(R1)，则存在正整数m使得，因此，所以，<a, b>( t(R1∪R2)；同理若<a, b>(t(R2)，可证<a, b>( t(R1∪R2)。综上所述，t(R1)∪t(R2)t(R1∪R2)。5.解 R={<x, y>}是集合A={x, y}上的二元关系，则st(R)={<x, y>, <y, x>}，而ts(R)={<x, y>, <y, x>, <x, x>, <y, y>}。因此st(R)(ts(R)。6.证明 rt(R)=r(R∪R2∪…∪Rn∪…)= IA∪R∪R2∪…∪Rn∪…=( IA∪R)∪(IA∪R2)∪…∪(IA∪Rn)∪…(( IA∪R)∪(IA∪R)2∪…∪(IA∪R)n∪…=tr(R)。反之，对于任意的<a, b>(tr(R)，则存在正整数n，使得<a, b>((IA∪R)n，即<a, b>(IA∪R∪R2∪…∪Rn，亦即<a, b>( 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上的自反关系。事实上，因为，(aA，总存在一个元素bA，使<a, b>R，而R是集合A中的对称关系，所以<b, a>R，又因为R是A上的传递关系，有<a, b>R且<b, a>R时，可得<a, a>R，即R是集合A中的自反关系。
故R是等价关系。3.解 ⑴R={a, d, e}({a, d, e}∪{b, c}({b, c}={<a, a>, <a, d>, <a, e>,<d, a>, <d, d>, <d, e>,<e, a>, <e, d>, <e, e>}∪{<b, b>, <b, c>, <c, b>, <c, c>}⑵关系图如图4-5。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>}，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)①对任意的xI，x2=x2，即<x, x >R，所以R是自反的；②对任意的<x, y>R，即x2=y2，则y2=x2，即<y, x>R，所以R是对称的；③对任意的<x, y>R，<y, z>R,即x2=y2，y2=z2，显然x2=z2，亦即<x, z>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)自反性。因为对任意的xX，<x, x>IX，所以<x, x>IX∪R∪R-1=R，即R是自反的；(2)对称性。对于任意的<x, y>IX∪R∪R-1，且x(y，显然<x, y>R∪R-1，则<x, y>R，或<x, y>R-1，因此，<x, y>R-1，或<x, y>R，从而有<y, x>R∪R-1，所以<y, x>IX∪R∪R-1=R，即R是对称的；综上所述，R是X上的相容关系。2.证明 (1)对任意的xA，有<x, x>R，所以R是自反的；(2) 设任意的<x, y>R，且x(y，都有<y, x>R，即R是对称的；综上所述，R是A上的相容关系。R的关系矩阵如下，关系图如图4-6：，最大相容类为：{1,2,3},{2,3,4},{2,4,5},{6}。
习题4.81.解 从R的定义中，显见R具有自反性、反对称性、传递性，所以R是A上的偏序关系，即<A, R>是偏序集。COVA={<1, 2>, <1, 3>, <2, 4>, <3, 5, >, <4, 5>}2.解 (1)从哈斯图可以看出，dRa，，，，aRa，eRa(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。上界 下界 上确界 下确界 A={a, b, c, d, e} a 无 a 无 B1={c, d, e} c, a 无 c 无 B2={b, c, d} a d a d B3={a, c, d, e} a 无 a 无 表13.填写表2，区分偏序集<A，≤>的子集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的下界中的最大者 不一定 不一定存在 存在则唯一4．解 ⑴是偏序集，不是其它集合；⑵是拟序集，不是其它集合；⑶是偏序集、全序集、良序集，不是拟序集；⑷是偏序集、全序集、良序集，不是拟序集；复习题四1．证明 对于任意的bB，因为A非空，所以存在aA，且<a, b>A(B，因为A(B=A(C，所以<a, b>A(C，从而bC，因此BC。
同理可证CB。故B=C。2．证明 利用集合相等的定义去证，即分别证明IA·RR，RIA·R；⑴对于任意的<x, y>IA·R，必存在z，满足<x, z>IA，<z, y>R，而<x, z>IA(x=z，所以<z, y>R，即IA·RR；⑵对于任意的<x, y>R，因为<x, x>IA，所以<x, y>IA·R，即RIA·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)，若<x, y>R，则x∩y≠，所以y∩x≠，因此<y, x>R，故R具有对称性。④R不具有反对称性，设x={1, 2}，y={1, 3}，则x∩y=y∩x={1}≠，由R的定义易知，<x, y>R且<y, x>R，但x≠y，故R不具有反对称性。
⑤R不具有传递性，设x={1}，y={1, 2}，z={2}，则有x∩y={1}≠且y∩z={2}≠，所以<x, y>R且<y, z>R，但x∩z=，所以<x, z>R，故R不具有传递性。5．证明 设R是集合X上的一个自反关系，如果R是X上对称和传递的，则对于任意a,b,c(X，若有<a, b>R∧<a, c>R，则<b, a>R∧<a, c>R，故得<b, c>R反之，若<a, b>R，<a, c>R，必有<b, c>R，则对任意a,bX，若<a, b>R，而因为R是自反关系，所以<a, a>R)，故<b, a>R，即R是对称的。若<a, b>R∧<b, c>R，则<b, a>R∧<b, c>R，所以<a, c>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*)+∪IA=t(R*)∪IA=R*∪IA(因为R*是传递的)=R*7．证明 (1)自反性。对于任意的(xA, (yB，若<x, y>A(B，因为R1和R2分别是A和B上的等价关系，所以有<x, x>R1，<y, y>R2，因此根据R3的定义有<<x, y>, <x, y>>R3，即R3是自反的；(2)对称性。设任意的<<x1, y1>, <x2, y2>>R3，根据R3的定义有<x1, x2>R1且<y1, y2>R2，而因为R1和R2都具有对称性，所以<x2, x1>R1且<y2, y1>R2，因此<<x2, y2>, <x1, y1>>R3，即R3是对称的；(3)传递性。设任意<<x1, y1>, <x2, y2>>R3，<<x2, y2>, <x2, y2>>R3，根据R3的定义有<x1, x2>R1且<y1, y2>R2，<x2, x3>R1且<y2, y3>R2，因为R1和R2都具有传递性，所以<x1, x3>R1且<y1, y3>R2，因此<<x1, y1>, <x3, y3>>R3，即R3是传递的。
综上所述，R3是A(B上的等价关系。8．解 (1) E=rts(R)。(2)要证明E=rts(R)是等价关系，只要证明ts(R)具有对称性即可，对任意的<x, y>(ts(R)，则存在正整数k使得<x, y>((s(R))k，存在z1, z2, ┅, zkA，满足<x, z1>(s(R), <x, z2>s(R), ┅, <x, zk>s(R)，因为s(R)是对称的，所以<z1, x>(s(R), <z2, x>s(R), ┅, <zk, x>(s(R)，因此<y, x>((s(R))k ，即<y, x>(ts(R)，亦即ts(R)是对称的。(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是自反的，所以IAR，因而R=rt(R)。若R是偏序关系，则R-1也是偏序关系，所以IAR-1。所以IAR-1∩R。又<x, y>R-1∩R(<x, y>R-1∧<x, y>R(<y, x>R∧<x, y>R，由R的反对称性，所以x=y，即<x, y>IA。因而R-1∩RIA。故IA= R-1∩R②充分性。若R-1∩R=IA且R=t(R)，则R是自反的、传递的。下面证明R是反对称的，若<x, y>R，<y, x>R，则<x, y>R且<x, y>R-1，所以<x, y>R∩R-1=IA，即x=y。因而R是反对称的。故R是偏序关系。(2)①必要性。若R是拟序关系，则R是反自反的、反对称的和传递的，因为R是传递的，所以R=t(R)。下面再用反证法证明R-1∩R=；假设R∩R-1≠，则存在某一<x, y>R-1∩R(<x, y>R-1∧<x, y>R(<y, x>R∧<x, y>R，由R的传递性可知，<x, x>R，这与R的反自反性矛盾，所以R∩R-1=。
②充分性。若R=t(R)，可得R是传递的。若R不是反自反的，则存在某一xA，使得<x, x>R，所以<x, x>R-1，这与R-1∩R=矛盾，因此R是反对称的。故R是拟序关系。第五章 函数( I+,由f(x)= |x|+2给出，,|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={<x,a>,<y,a>,<z,a>}, f2={<x,a>,<y,a>,<z,b>}, f3={<x,a>,<y,b>,<z,a>},f4={<x,a>,<y,b>,<z,b>}, f5={<x,b>,<y,a>,<z,a>}, f6={<x,b>,<y,a>,<z,b>},f7={<x,b>,<y,b>,<z,a>}, f8={<x,b>,<y,b>,<z,b>}.因此，BA={f1, f2, f3, f4, f5, f6, f7, f8}。
习 题5.21．解 （1）是单射但不是满射；（2）既不是单射也不是满射；（3）是满射；（4）是满射，单射，双射。2．解 （1）f：I(I, f(x)= x3;(2) ;(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>},如图显然可知，是双射。(2) f={<0,0>,<1,4>,<2,2>,<3,0>,<4,4>}，由图可知，f即不是单射也不是满射。4．解 f1={<a,0>,<b,0>}, f2={<a,0>,<b,1>}, f3={<a,1>,<b,0>}, f4={<a,1>,<b,1>}.其中f2，f3是双射，而f1，f4既不是满射也不是单射。5．证明 设任意n∈N,则至少<n,0>∈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）对于<x,y>,<u,v>∈R×R，设f(<x,y>)=f(<u,v>)，即<(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，故<x,y>=<u,v>，因此，f是单射；(2)证f是满射，既任意<u,v>∈R×R,令f(<x,y>)=<u,v>，则有<(x+y)/2, (x-y)/2>=<u,v>,既有(x+y)/2=u，(x-y)/2= v只要取x=u+v，y=u-v,就可使上式成立，且因为<u,v>∈R×R，所以，<x,y>∈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．证明ψ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)。综合①②③④，对所有ψA(B(x)= ψA(x)+ ψB(x)-ψA(x)ψB(x)。（2）若x∈A则x(A，所以，；若x(A则x∈，因此，。离散数学习题七答案（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使<a,b>∈f，由逆关系定义有<b,a>∈f-1；若<y,x>∈f-1且<y,x1>∈f-1，则又由逆关系定义得<x,y>∈f且<x1,y>∈f，又因为f：A(B是单射故x=x1。综上所述由函数定义知是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={<a,b >,<b,a>,<c,a >}({<a,b >,<b,a>,<c,a>}={<a,a>,<b,b>,<c,b>};f(f(f= f((f(f)= {<a,b>,<b,a>,<c,a>}({<a,a>,<b,b>,<c,b>}={<a,b>,<b,a>,<c,a>}。
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]4．解 （1）作恒等函数任意a∈，IA(a)=a，显然IA是A上的双射函数，故A≈A（2）若A≈B，则存在双射函数f：A→B，由5.3节定理1和定理2知f：A→B存在逆函数，且: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,b>∈A×C，h(a,b)=<c,d>,其中c=f(a),d=g(b)。下面证明：h:A×B→C×D是单射。对<a1,b1>,<a2,b2>∈A×B.若h(a1,b1)=h(a2,b2)= <c,d>，即f(a1)=f(a2)=c,g(b1)=g(b2)=d,而f和g都是单射，所以有a1=a2，b1=b2，即<a1,b1>=<a2,b2>。再证明h:A×B→C×D是满射。事实上对任意的<c,d>∈C×D,则c∈C,d∈D,由于f,g都是满射，所以存在a∈A,b∈B使得f(a)=c,g(b)=d。即存在<a,b>∈A×B，使得h(a,b)= <c,d>，故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},是双射，故有逆函数，则逆函数是{<z,1>,<w,2>,<x,3>,<y,4>},则定义域{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是双射，需要满足的条件和(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)，需要m ( n(y-x) ，因此需要m和证明是到的满射(B，都存在a(A使得f(a)=b，因此，f-1({b})非空；对于任何的b1, b2(B，b1(b2，则f-1({b1})(f-1({b2})=(。若不然，，则存在a(f-1({b1})(f-1({b2})，即a(f-1({b1})且a(f-1({b2})，亦即有f(a)=b1，f(a)=b2，这与f是函数矛盾。下面证明。对于任何的b(B，显然有f-1({b})(A，所以①另一方面，由于f是到的(A，都有b(B使得f(a)=b，即a(f-1({b})，因此②由①②可得。综上所述，(={f-1({b})(b(B}是A的一个划分。证明(B，都有a(A使得g(a)=[a]，(A，若要g(a)=g(b)，即要[a]=[b]，由等价类的性质，即需要aRb。6．解 （1）假。例如，设A={a,b,c}, B={x,y}, C={1,2,3}, 尽管f={< x, 1>,< y, 2>}是单射f·g={<a, 1>,<b, 1>,<c, 2>}不是单射；是满射f·g={<a, 1>,<b, 1>,<c, 1>}不是满射；f·g={<a, 1>,<b, 2>,<c, 3>}是单射是单射；(A且a1(a2但g(a1)=g(a2)，(C是函数，f·g(a1)= f·g(a2)，这与f·g：A(C是单射矛盾。
故g是单射f·g是满射，(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既是满射，是单射是满射，是单射。f是从到的一个函数，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是传递的。⑵等价类是(B→B(A，f(a,b)=<b,a>，对任意<a,b>(A(B。则任意a1,a2(A,b1,b2(B,则由函数f:A(B→B(A得，f(a1,b1)=<b1,a1>,f(a2,b2)=<b2,a2>,若f(a1,b1)＝f(a2,b2)，则<b1,a1>＝<b2,a2>，因此，b1=b2, a1=a2，所以<a1,b1>=< a2,b2>，故f是单射。
若任意<b,a>∈B×A,这里b∈B,a∈A，根据定义可知：<b,a>的原象是<a,b>∈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，因此，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).2．解 ⑴、⑵、⑶、⑸能构成无向图的度序列，其中⑴、⑵、⑶能构成无向简单图的度序列。3．解 由握手定理可知，图G中所有结点度数之和，所以G应该有8条边。4．解 由握手定理可知，图G中所有结点度数之和为24，三个4度接点的度数之和为12，则其余度数的和也是12，而其余结点的度均为3，所以3度接点应该有4个，因此，图G有7个结点。
5．解 图中。结点之间的对应关系为(: V(G1)(V(G2)：((g)=1, ((a)=8, ((h)=2, ((b)=7, ((i)=10, ((c)=4, ((j)=3, ((d)=9, ((f)=6, ((e)=5。6．解 。因为与的结点间存在一一对应关系，边的方向一致，其对应关系为：f: 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, E> (其中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.31．解 由图G的邻接矩阵作出其图如图6-6。.⑴ d（v1）=2 d（v2）= 3。⑵ 图G不是完全图。⑶因为,而,所以,从v1到v2长为3的路有4条。⑷从v1到v2长为3的4条路分别为：v1v2 v1v2，v1v2v3v2，v1v2v4 v2，v1v4v1v2。2．解 邻接矩阵为A的无向图G的图形如图6-7所示：3．解 ⑴ 图G的邻接矩阵为⑵ 为了求G中长度为3的通路的数目，就要计算A3，为此先计算A2。，因， 故G中长度为3的通路有20条。因为A3的主对角线上的元素的和为12，所以G中长度为3 的回路有12条。⑶ 因为,,所以G的可达性矩阵为因为P中的每个元素都是1，所以G是强连通的，当然也是单向连通的。4．解 图6-9、图6-10的关联矩阵分别为，，5．解 图6-9、图6-10的邻接矩阵分别为：，。习题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．证明 设，则有((G-V1)=9>7=(V1(，所以它不是Hamilton图。5．解 我们分别用a, b, c, d, e, f, g七个结点表示七个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连一条无向边，所得无向图如图6-14(a)。此图存在一条Hamilton圈：abdfgeca，于是按图6-14(b)所示是顺序安排座位即可。习题6.51．解 如图6-16,求得v1到v8的最短路是v1v3v6v7v8,其总长度为13.2．解 首先观察图中的奇数度结点，此图中只有两个奇数度结点E和F。用标号法求E到F的最短路径，容易算出E到F的最短路径为EGF，其权为28。然后将最短路径上的边均重复依次（如图6-17(b)中虚线）。于是得欧拉图。求从D点出发的一条欧拉回路，如，其权为281。3．解 从a开始，可得哈密尔顿回路，如图（b），长度37，而最短哈密尔顿回路如（c）长度36。
复习题61．解 因为G中有6个3度结点，其度数和为18，由握手定理可知，所有结点度数的和为24，所以其余结点的度数和为6，而其度数均小于3，因此最大只能为2，则其余结点至少有3个，故G中至少有9个结点。2．解 因为n是奇数，所以Kn中每个结点均为偶度，因此G中每个奇度结点在补图中仍为奇度结点，故G的补图中有r个奇度结点。3． 证明 用结点分别表示6个人。若与彼此认识（）就在与之间连边于是构成无向简单图。在中，若与之间有边，说明，所代表的人彼此不认识。有了图论模型,要证明命题,就是要证明,要么在图中有三角形, 要么在图中有三角形。设在中v1与三个以上的结点相邻,不妨v1与v2,v3, v4相邻,如图6-19,这时若v2,v3, v4中有某两个相邻，则在中存在三角形，若v2,v3, v4中任何两个都不相邻，则在中v2,v3, v4构成三角形。若在中v1与三个以下的结点相邻，则可先在中作类似的证明。4．解 K4的所有非同构的子图如图6-20共18个，其中有11个是生成子图，生成子图中有6个是连通图。5．解 图1同构于图2。只要作映射f : u1→v1, u2→v2, u3→v3, u4→v4,u5→v5, u6→v6即可.6．解 首先要注意5阶自补图的边数应该是的边数的一半,而有10条边,所以5阶自补图应该有5条边;其次,不连通图的补图是连通的,因此, 自补图是连通的.由以上分析,应先画出的全部5条边的连通生成子图，再利用同构的性质来判断哪些是自补图。
的全部5条边的连通生成子图如图6-22。其中，(a)与(a)自身互为补图，(b)与(c)互为补图，(d)与(d)互为补图。从而可得(a)和(d)为自补图。7．解 图6-23中的路有：v1v2, v1v4, v1v2v4, v1v4v2, v1v2v5, v1v4v3, v1v4 v5, v1v2v4 v3, v1v2v4 v5, v1v2 v5 v4, v1v4v5v2, v1v4v2v5, v1v2v5v4v3, v2v4, v2v5, v2v1v4, v2v4v3, v2v4v5, v2v5v4, v2v1v4v3, v2v1v4v5, v2v5v4v3, v3v4, v3v4v5, v3v4v2v5, v3v4v1v2v5, v4v5, v4v2v5, v4 v1v2v5共29条。图6-23中的4个圈分别为：v3ev3，v1v2v4v1, v2v4v5v2, v1v2 v5 v4 v1。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分别为如下的矩阵：11．解 ⑴其邻接矩阵为：(2)由 ，，可知从到长度为1，2，3，4的路径分别有1，1，2，3条。(3)中第（2，3）个元素为1，说明从v2到v3引出的边能共同终止于同一结点的只有一个，。中第（2，2）个元素为2，说明的引出度数为2。中第（2，3）个元素为0，说明没有结点引出的边同时终止于和。中第（2，2）个元素为3，说明的引如度数为3。⑷ ，⑸ 。所以，强连通子图的顶点集为：{v1},{v2, 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回路14．解 ABCDFCEFGAHGBH是图9中找出一条Euler路。15．解 在图6-29中⑴与⑷两图为哈密尔顿图，⑵，⑶为半哈密尔顿图。在⑴中，为一条哈密尔顿回路。在⑷中为一条哈密尔顿回路。在⑶中为一条哈密尔顿通路。在⑵中，为一条哈密尔顿通路。16．解 图6-30中的图(a) 、(b)、 (c) 、(d)分别是⑴、⑵、⑶、⑷题要求的实例。17．解 图6-31中的图(a) 、(b) 能够一笔画出，但图(c) 不能够一笔画出。图(a)的具体画法是：v1 v8 v9 v3 v10 v11 v5 v12 v7 v2 v9 v10 v4 v11 v12 v6 v7 v1。图(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。第七章 特 殊 图 类与平凡图构成的非连通图中有4个结点3条边，但是它不是树。3．证明 必要性。因为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所示。6．证明 由定理，在任意的树中，边数；所以，由握手定理得 ①⑴若没有树叶，则由于是连通图，所以中任一结点均有，从而 ②则与矛盾。若树叶，则其余个结点的度数于2，于是 ③从而、相矛盾。⑴，⑵得知T中至少有两片树叶。表示。，，，。其中T2，T5是图中的最小生成树。9．解 最小生成树T如图7-7所示，W（T）=18。习题7.21．解 不一定是。如图7-8就不是根树.2．解 五个结点可形成3棵非同构的无向树，如图7-9⑴，⑵，⑶所示。由⑴可生成2棵非同构的根树，如图7-9⑷，⑸所示。⑷为3元树，⑸为4元树。由⑵可生成4棵非同构的根树，如图7-9⑹，⑺，⑻，⑼所示。⑹为2元树，⑺为2元树，⑻为3元树，⑼为2元树。由⑶可生成3棵非同构的根树，如图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=2 n0-1。即二元树有奇数个结点。5．解 先根遍历：abdfgechi中根遍历：fdgbeahci后根遍历：fgdebhica6．解：习题7.31．解 图⑴是偶图，互补结点子集为：；图⑵是偶图，互补结点子集为：；图⑶不是偶图。2．证明 设G=<V, E>是一棵树，任选v0∈V，定义V的两个子集如下：, V2 = V – V1。现证明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,…, k)相同，从而vvi+1 vi+2…vkuv是G中的一个圈，这与G是树矛盾。同理可证，V2中任意两个结点之间无边存在。
故G中的每条边(u,v)∈E，必有u∈V1，v∈V2或u∈V2，v∈V1，因此G是具有互补结点子集V1和V2的偶图。3．解 将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所示的两个图都是平面图.2．解 图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)。因是简单图，故每个面至少由3条边围成。即。而由本届定理1知，。因此每个面只能由3条边围成。4．解 去掉图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条边,则有由于G是简单图,所以每个Gi也是简单图,由本节定理2的推论可知mi≤3ni-6, i=1, 2, …,k。从而有所以m≤3n-6。再用反证法证明，简单平面图G中至少有一个度数小于等于5的结点。如果G中每个结点的度数均大于等于6,由握手定理可知,因此,代入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个连通分支分别为<n1，m1>，<n2，m2>，┅，<np，mp>，由于森林的每个连通分支都是树，因此，有：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，5．解 设G中的k个连通分支为，设结点。在G中添加边，设所得新图为T，则T连通且无回路，因此T是树。所加边的条数k-1是使得G为树的最小数目。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。7．解 题目就是求图7-19⑴的最小生成树问题。因此，图7-19⑴的最小生成树为图7-19⑵所示，即是所求的通讯线路图。其权即是最小总造价，其权为：。8．解 高为2的所有不同构的二元树有7棵，如图7-20所示。其中有2棵完全二元树，图7-20中的⑸和⑺所示，有1棵满二元树，图7-20中⑺所示。
9．证明 方法1：设T结点数为n，分支点数为i。根据完全二元树的定义，可知下面等式均成立：⑴⑵⑶由式⑴，⑵，⑶易知。方法2：在完全二元树中，除树叶外，每个结点的出度为2。除树根外，每个结点的入度为1。由握手定理知解得：。10．证明 设完全二元树T有i个分支点，t片树叶，由T为完全二元树，则由7.2节定理3有。又结点数，所以为T的树叶数。11．解 对于图7-21所示的二元树，三种遍历方法的结果如下：先根遍历：中根遍历：后根遍历：12．解 设图7-22⑴所示的树为，是完全二元树。在每个分支结点引出的两条边上分别标上0（左）和1（右），则得如图7-23⑴的树，将树根到每片树叶的通路上所标的数字构成的符号串组成集合，则为前缀码。设图7-22⑵中所示的树为，是二元树，但不是完全二元树。对于有一个儿子的分支结点引出的边可随便标上0或1；有两个儿子的分支点标法同，则得如图7-23⑵的树，所得前缀码为。13．解：其实，等于T的各分支点的权之和，即。⑵ 由T形成的二元前缀码为。14．解 应该用较短的符号串传输出现频率高的数字，因而可用100乘各数字出现的频率作为权，求最优二元树，然后用这样的二元树产生前缀码传输上面给定的数字。
具体做法如下：用100乘各频率得权 。将这些权由小到大排列得到4，5，6，10，10，15，20，30。⑴ 所求最优二元树如图7-25所示。⑵ 用所求的最优二元树产生二元前缀码如图7-25所示。带权为的树叶对应的符号串就为传输i的符号串。数字0,1,2,3,4,5,6,7对应的符号串分别为01，11，001，100，101，0001，00000，00001．⑶用这样的符号串传输按上述比例出现的数字最少。所以传输10000个上述比例出现的数字至少要用27400个二进制数字。15．证明 设二部图G的互补结点子集为V1、V2，则m=(V1(((V2(且(V1(+(V2(=n，我们知道两个数的和一定，只有当它们相等时积最大，即当(V1(=(V2(=n/2时，积(V1(((V2(最大为n2/4，亦即m( n2/4。16．解 令V1= { P1，P2，…，P7}，V2={ a1，a2，…，a10}，以V1和V2的元素作结点，若Pi是aj的合格工作岗位，则在P i和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)}。这样安排使得所有的人都有工作。17．解 以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．解 若﹡对是可分配的，则有任意a,b,c∈,均有a﹡(bc)=(a﹡b)(a﹡c)= abac =( ab( ac )= ab+c而a﹡(bc)=a﹡(b(c)= ab(c≠ab+c 故﹡对 是不可分配的。
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-2 z +6)=x(yz-2y-2 z +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-2 z-2b+6= z ，由于b的任意性则z=2，因此z=2是其零元。（3）因为*是满换律，对于x∈R，要存在∈R，须有x*= x-2x-2+6= e=3, 当x(2时，。
即对于任意的x，当x(2时x都是可逆的，且。5．解 f1,f2,f3都满换律，f4满足等幂率，f2有单位元a，f1有零元a，f3有零元b。习题8.21．解 构成代数系统的运算有（2），（3），（4）。2．解习题8.31．证明 作函数f:{a,b,c}→{(, (, (}，f(a)= (,f(b)= (,f(c)= (.显然此映射是双射。由表8-2可知对于任意的x,y(A都有有f(xy)=f(x) of(y)，故<A, *>≌<B, o>。2．解 代数系统不可能同构。因为，由同构的性质，如果两个代数系统同构，则两个系统的单位元对应，零元对应，而这里，代数系统<R,(>的零元是0，而<R,+>没有零元。故代数系统不可能同构。复习题八1．解 ⑴有单位元e=<1,0>，因为，对于任意<a,b>∈S，均有<，且，，故<1,0>单位元⑵对于<a,b>∈S，要<a,b>有逆元，需要有<x,y>∈S使得，<a,b>(<x,y>=<x,y>(<a,b>=<1,0>事实上，即<1,0>=<a,b>(<x,y>=<ax,ay+b>，因此，ax=1，ay+b=0，当a(0时可解得，且又有。
故当a(0时，形式的元素都可逆，且。2．解 因为a*b=b*aa=b，则任意a∈A，而*是可结合的，则有a*(a*a)=(a*a)*a，因此a*a=a，即*满足等幂律.3．证明 假设f: Q→Q-{0}是从<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．证明 因为，，，所以，。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的幂的形式，而另一个不能。下面就这三种情况分别考虑。①设存在k1,k2∈N，使得n1=2k1，n2=2k2，则n1×n2=2k1×2k2=2k1+k2 ∈N，且f(n1)= f(n2)=1，因此f(n1×n2)=f(2k1+k2)=1=f(n1)×f(n2) =f(2k1)×f(2k2);②n1,n2都不能表示成2的幂的形式，则n1×n2也不能表示成2的幂的形式，所以，f(n1)= f(n2)=0，因此f(n1×n2)=0=f(n1)×f(n2)。③不妨设存在k∈N，使得n1=2k，，而n2不能表示成2的幂的形式，则n1×n2也不能表示成2的幂的形式，所以，f(n1)= 1，f(n2)=0，因此，f(n1×n2)=0=f(n1)×f(n2)。综上所述，代数结构 与同态。第九章 特殊的代数系统习题9.11．解 ⑴是半群。显然，二元运算“”在N上是封闭的， 所以，是一个代数系统，另一方面，有，而，因此，，所以，运算“”满足结合律的，故是半群；⑵是半群。
显然，二元运算“”在N上是封闭的， 所以，是一个代数系统，另一方面，，有，而，则，所以，运算“”满足结合律，故是半群；⑶是半群。显然，二元运算“”在N上是封闭的， 所以，是一个代数系统，另一方面，，有，，即 ，所以，运算“”满足结合律，故是半群。⑷不是半群。虽然，二元运算“”在N上是封闭的，即是一个代数系统，但是对于5，3，6，因为，，而，即，所以，运算“”不满足结合律，故不是半群。2．解 ⑴正确。因为，运算显然封闭。⑵正确。，，即是，所以(满足结合律。故是半群。⑶，有，又有即存在单位元是0，故是独异点。3．解 都不能使<{a,b},(>构成独异点，因为没有一个函数存在单位元。而的单位元是a, <{a,b},>能构成独异点。4．解 ⑴是，因为M={2,3}关于min是封闭的，故<M ,min>是<S,min>的子代数；⑵<M ,min>是<S,min>的子半群；⑶不是，因为S的单位元是4，而4M,故<M ,min>不是<S,min>的子独异点。习题9.21．解 ⑴是，因为实数乘法满足结合律，存在单位元a0=1，任意元素a存在逆元素a-1；⑵是，因为有理数乘法满足结合律，存在单位元1，任意元素a存在逆元素a-1；（3）是，因为复数乘法满足结合律，存在单位元1,任意元素z的逆元素是z共轭复数；（4）是，因为多项式的加法满足结合律，多项式关于加法的单位元是0多项式，任意元素P(x)的逆元素是-P(x).（5）是, 因为向量的加法满足结合律，n维实向量关于向量的加法的单位元是n维零向量，任意的n维实向量(的逆元素是-(。
2．解 可以构成群。⑴因为，对于任意的，所以，运算满足结合律；，⑵关于运算有单位元2，这是因为对于任意的都有，且；⑶对于任意的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与运算能构成群。3．证明 因为对于任意的，所以a可逆,且，因此，<G,*>是群。要证明<G,*>是Abel群，只需证明运算满换律，事实上，因为，对于任意的，所以， 因此，由结合律则有，再由消去律得：。故<G,*>是Abel群。4．证明 当时，因为，=，所以，是方程的解。下面方程的解是唯一的。对于若解y，即，由于群中的任何元素都可逆，则对上式两边同时左乘a-1，并两边同时右乘a-1b-1则得，由结合律则有，。证毕。5．证明 设1是群G的单位元，若G中存在幂等元a，即因为群中的任何元素都可逆，因此，a也可逆，则有故单位元为G中惟一的幂等元。6．解 答案是A，因为存在同态映射f:R(R-{0},f(x)=ex，但不存在同构映射。
习题9.31．解 1，5，7，11为其生成元，任何与12互素的正整数都可作<N12,+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<m则有ar=an-mk=ana-mk=an(am)∈H，而因为m是使am∈H的最小的正整数，且0≤r<m，所以r=0。这样n=mk, an= amk= (am) ，再由an∈H的任意性知，H中的任意元素都是am的幂，故H=（am）,即循环群的任何子群都是循环群。习题9.41．证明 ①显然H(G；②证明运算*关于H的封闭性。任取a,b(H，对于任意的x ( G有，则，因此，；③设1是G中的单位元，因为对于任意的x ( G有故，；④任取a(H(G，对于任意的x(G，则由H的定义有, x*a=a*x ，由于群的元素都有逆元，因此a也有逆元。等式x*a=a*x两边同时左乘、并同时右乘a的逆元a-1则有，，即，亦即。综合①、②、③、④，<H,*> 是<G,*> 的子群。
2．解 群真子群有如下4个：<{1},(>，<{1,5},(>，<{1,7},(>，<{1,11},(>。习题9.51．解 ⑴设，则集合G={E, A, B, C,-E,-A,-B,-C }，G关于运算(的运算表如下。表2 G关于运算(的运算表( E A B C -E -A -B -C E E A B C -E -A -B -C A A -E -C B -A E C -B B B C -E -A -B -C E A C C -B A -E -C B -A E -E -E -A -B -C E A B C -A -A E C -B A -E -C B -B -B -C E A B C -E -A -C -C B -A E C -B A -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,(>是一个群。⑵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，即<H,(>是正规子群。同理可证，<{E, B, -B,-E },(>,<{E, C, -C,-E },(>也是正规子群。
2．解 5，{3，7，11}，{0，4，8}。习题9.61．解I[i]对于普通加法和乘法能构成环。这是因为：⑴显然I[i]对加法+是封闭的，而复数的加法是满换律和结合律的，<I[i], +>的单位元是0=0+0i，任意元素a+bi的逆元是-a-bi。所以，<I[i], +>是可交换群。⑵I[i]对复数的加法是封闭的，且复数的乘法是满足结合律的，即<I[i], (>是半群。⑶复数的乘法对复数的加法满足分配律。综合⑴⑵⑶，I[i]对于普通加法和乘法能否构成环。2．证明 ⑴首先证明是一个环。设对于任意的,，因为， a,b,c,d(I，所以，(a+c)，(b+d)，(ac+2bd)，(ad+bc)(I，因此，，=(R，故R对于加法和乘法都是封闭的。另一方面，实数的普通加法满足结合律和交换律，且关于加法单位元是0，每个元素都有逆元，就是相反数。实数的普通乘法也满足结合律。综合上述<R,+,( >是一个环。⑵因为，实数的普通乘法也满换律，且R关于乘法有单位元1，又对于,，若两者都不为零，则 ，即<R,+,( >无零因子。综合⑴⑵可知，<R,+,( >是一个整环。
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。故<F,+,(>是一个环。另一方面，<F,(>中有单位元1=1+0i；又对于任何的非零元a+bi，因为，a,b不全为零，所以，a2+b2(0，因此对于任何的非零元a+bi都有逆元。综上所述，<F,+,(>是一个域。复习题九1．解 ⑴<G,*> 是半群，但不是独异点，更不是群；⑵不是半群；⑶不是半群，⑷是群，其单位元是。2．证明 对于任意的有同时，，故，所以满足结合律，故是<R,*>半群；又存在，且故0是单位元。综上所述，<R,*>是独异点。3．证明 对于任意的，因为，，其中为的二元运算， 而是半群，又，所以，，即对运算是封闭的。
又因为是半群，所以，有结合律，即对于任意的有，故<S,*>满足结合律，综上所述，<S,*>是半群。4．证明 对于任意，由于<S,*>是半群，所以，<S,*>有结合律，a*c=c*a且b*c=c*b，则。5．证明 对于任意，若a,b是<S,*>的幂等元，则a(a=a，b(b=b，再由交换律和结合律则，故a*b也是<S,*>的幂等元。6．证明 对于任意的，有，所以，<S,*>是封闭的，又因为因此，<S,*>是半群；又取，所以，，故存在单位元<0,0>所以<S,*>是独异点，且即交换律成立，故<S,*>是可交换独异点。7．证明 因为，0×0=0∈{0}，所以，运算封闭，又结合律是显然的，故<{0},×>是子半群。但所以，<{0},×>不是子独异点。8．证明 则{0}，{1}，{0，1}，{0，2}，{0，1，2}，{0，1，2，3}都能与×4构成<N4,×4>的子半群，其中<{0},×4>是独异点，但不是<N4,×4>的子独异点。
9．证明 对于任意的a,b∈G，由题设则有，因此，由消去律可得，①同理，由可得，②再由①②两式可得，由消去律消去上式中的b3可得，。故<G,*>是可交换群。10．解 群<N5,+5>只有两个子群H1={0}和H2= N5，其中H1的左陪集和右陪集如下：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，因为，<G,*>是可交换群，所以对于a,b∈G，有a*b= b*a又因为，<H,*>是<G,*>的正规子群，所以，任意的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的任意性，所以，商群<G/H,*>也是可交换群。12．证明 ⑴先证明f是双射。对任意的 若，即有a*x1*a-1= a*x2*a-1，由群的消去律可得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是同态映射。对于任意的有综合⑴⑵可知，f是<G,*>到其自身的同构映射。第十章 格和布尔代数习题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=gS1;＜S2,≤＞不是＜L,≤＞的子格， ∵e∧f=cS2;＜S3,≤＞是＜L,≤＞的子格.2．解 S24的包含5个元