离散数学重修习题集
重修习题集
第一、二章
1）判断下列公式哪些是合式公式，哪些不是合式公式。
⑴ (P∧Q→R)
⑵ (P∧(Q→R)
⑶ ((?P→Q)?(R∨S))
⑷ (P∧Q→RS)
⑸ ((P→(Q→R))→((Q→P)?Q∨R))。
解：⑴⑶⑸是合式公式；⑵⑷不是合式公式。
2）设 P：天下雪。
Q：我将进城。
R：我有时间。
将下列命题符号化。
⑴天没有下雪，我也没有进城。
⑵如果我有时间，我将进城。
⑶如果天不下雪而我又有时间的话，我将进城。
解：⑴?P∧?Q
⑵R→Q
⑶?P∧R→Q
3）用符号形式写出下列命题。
⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。
⑵我今天进城，除非下雨。
⑶仅当你走，我将留下。
解：
⑴P：上午下雨；Q：我去看电影；R：我在家读书；S：我在家看报；原命题符号化为：（?P→Q）∧（P→R∨S）。
⑵P：我今天进城；Q：天下雨；原命题符号化为：?Q→P。⑶P：你走；Q：我留下；原命题符号化为：Q→P。
4）用等价演算证明下列命题公式是否为重言式。
⑴(P∧(P→Q))→Q
??(P∧(?P∨Q))∨Q
?(?P∨(P∧?Q))∨Q
?((?P∨P)∧(?P∨?Q))∨Q
?(?P∨?Q)∨Q
?T
⑵(?Q∧(P→Q))→?P
?(?Q∧(?P∨Q))→?P
??(?Q∧(?P∨Q))∨?P
-1 -
重修习题集
?(Q∨(P∧?Q))∨?P
?(?P∨Q)∨(P∧?Q)
??(P∧?Q)∨(P∧?Q)
?T
⑶(?P∧(P∨Q))→Q
?(?P∧Q)→Q
??(?P∧Q)∨Q
?P∨?Q∨Q
?T
⑷((P→Q)∧(Q→R))→(P→R)
??((?P∨Q)∧(?Q∨R))∨(?P∨R)
?(P∧?Q)∨(Q∧?R)∨(?P∨R)
?(P∧?Q)∨((?P∨Q∨R)∧(?P∨?R∨R))
?(P∧?Q)∨(?P∨Q∨R)
?(?P∨Q∨R∨P)∧(?P∨Q∨R∨?Q)
?T
5）写出下列命题公式的对偶式。
⑴ ?(?P∧?Q)∧R的对偶式是：?(?P∨?Q)∨R
⑵(P∨?Q)∧(R∨P)对偶式是(P∧?Q)∨(R∧P)
⑶P→((Q→R)∧(P∧?Q))
??P∨((?Q∨R)∧(P∧?Q))
?(?P∨?Q)∧(?P∨?Q∨R)
所以P→((Q→R)∧(P∧?Q))的对偶式是(?P∧?Q)∨(?P∧?Q∧R)⑷(P?Q)→R
??(P?Q)∨R
??(P→Q)∨?(Q→P)∨R
??(?P∨Q)∨?(?Q∨P)∨R
?(P∧?Q)∨(?P∧Q)∨R
所以(P?Q)→R的对偶式是(P∨?Q)∧(?P∨Q)∧R
6）写出下列命题公式的主析取范式和主合取范式
⑴(P→Q)∧(Q→R)
?(?P∨Q)∧(?Q∨R)
?((?P∨Q)∧?Q)∨((?P∨Q)∧R)
?(?P∧?Q)∨(?P∧R)∨(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)(主析取范式)?
∑0,1,3,7
-2 -
重修习题集
?∏2,4,5,6
?(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∧R)∨(?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)(主析取范式)
?∑1,3,5,6,7
?∏0,2,4
?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨R)(主合取范式)
7）推理理论证明题：
⑴P∧Q，(P?Q)→(T∨S)?(T∨S)
证明:
⑴P∧QP
⑵PT⑴
⑶QT⑴
⑷P→QT⑶
⑸Q→PT⑵
⑹(P→Q)∧(Q→P)T⑷⑸
⑺P?QT⑹
⑻(P?Q)→(T∨S)P
⑼T∨ST⑺⑻
⑵?(P→Q)→?(R∨S)，(Q→P)∨?R,R?P?Q
证明:
⑴RP
⑵(Q→P)∨?RP
⑶Q→PT⑴⑵析取三段论
⑷R∨ST⑴附加律
⑸?(P→Q)→?(R∨S)P
⑹P→QT⑷⑸拒取式
⑺(P→Q)∧(Q→P)T⑶⑹合取引入
⑻P?QT⑹双条件等价式
⑶?P∨?S，R→S??P∨?R
证明:
⑴?(?P∨?R)P(附加前提)
⑵P∧RT⑴条件等价式
-3 -
重修习题集
⑶PT⑵化简律
⑷RT⑵化简律
⑸R→SP
⑹ST⑷⑸假言推理
⑺?P∨?SP
⑻?PT⑹⑺析取三段论
⑼?P∧P(矛盾)T⑶⑻合取引入
⑷P→(Q∧R)，?Q∨S，(T→?U)→?S?Q→T证明:
⑴QP(附加前提)
⑵?Q∨SP
⑶ST⑴⑵析取三段论
⑷(T→?U)→?SP
⑸?(T→?U)T⑶⑷拒取式
⑹?(?T∨?U)T⑸条件等价式
⑺T∧UT⑹德·摩根律
⑻TT⑺化简律
⑼Q→TCP规则
⑸证明下面各命题推得的结论是有效的：如果今天是星期三，那么我
有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离
散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻
辑测验。
证明：设P：今天是星期三。
Q：我有一次离散数学测验。
R：我有一次数字逻辑测验。
S：离散数学课老师有事。
该推理就是要证明：P→(Q∨R)，S→?Q，P∧S?R⑴P∧SP
⑵PT⑴化简律
⑶ST⑴化简律
⑷S→?QP
⑸?QT⑶⑷假言推理
⑹P→(Q∨R)P
⑺Q∨RT⑵⑹假言推理
⑻RT⑸⑺析取三段论
8）将下列命题符号化。并讨论它们的真值。
(1)有些实数是有理数。
解：设R(x)：x是实数。Q(x)：x是有理数。
“有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
-4 -
重修习题集
它的真值为：真。
(2)凡是人都要休息。
解：设R(x)：x是人。S(x)：x要休息。
“凡是人都要休息。”符号化为：(?x)(R(x)→S(x))它的真值为：真。
(3)每个自然数都有比它大的自然数。
解：设N(x)：x是自然数。G(x,y)：x比y大。
“每个自然数都有比它大的自然数。”符号化为：(?x)(N(x)→(?y)(N(y)∧G(y,x)))它的真值为：真。
(4)乌鸦都是黑的。
解：设A(x)：x是乌鸦。B(x)：是黑的。
“乌鸦都是黑的。”符号化为：(?x)(A(x)→B(x))它的真值为：真。
(5)不存在比所有火车都快的汽车。
解：设A(x)：x是汽车。B(x)：是火车。K(x,y)：x比y快。
“不存在比所有火车都快的汽车。”符号化为：?(?x)(A(x)∧(?y)(B(y)→K(x,y)))它的真值为：真。
(6)有些大学生不佩服运动员。
解：设S(x)：x是大学生。L(x)：是运动员。B(x,y)：x佩服y。
”符号化为：(?x)(S(x)∧L(y)∧?B(x,y))“有些大学生不佩服运动员。
它的真值为：真。
(7)有些女同志既是教练员又是运动员。
解：设W(x)：x是女同志。J(x)：x是教练员。L(x)：x是运动员。 “有些女同志既是教练员又是运动员。”符号化为：(?x)(W(x)∧J(x)∧L(x))它的真值为：真。
(8)除2以外的所有质数都是奇数。
解：设A(x)：x是质数。B(x)：x是奇数。C(x,y)：x不等于y。
“除2以外的所有质数都是奇数。”符号化为：(?x)(A(x)∧C(x,2)→B(x))它的真值为：真。
9）谓词推理理论
⑴(?x)(F(x)→(G(y)∧R(x)))，(?x)F(x)?(?x)(F(x)∧R(x))证明：
⑴ (?x)F(x)P
⑵F(c) ES⑴
⑶(?x)(F(x)→(G(y)∧R(x)))P
⑷F(c)→(G(y)∧R(c))US⑶
⑸G(y)∧R(c)T⑵⑷假言推理
⑹R(c) T⑸化简律
-5 -
重修习题集
⑺ F(c)∧R(c)T⑵⑹合取引入
⑻(?x)(F(x)∧R(x))EG⑺
⑵(?x)(F(x)→G(x))，(?x)(R(x)→?G(x))?(?x)(R(x)→?F(x))证明：
⑴(?x)(R(x)→?G(x))P
⑵R(c)→?G(c)US⑴
⑶(?x)(F(x)→G(x))P
⑷F(c)→G(c)US⑶
⑸?G(c)→?F(c)T⑷假言易位式
⑹R(c)→?F(c)T⑵⑸假言三段论
⑺(?x)(R(x)→?F(x))UG⑹
⑶(?x)(F(x)∨G(x))，(?x)(G(x)→?R(x))，(?x)R(x)?(?x)F(x)证明：
⑴ (?x)R(x)P
⑵R(c) US⑴
⑶(?x)(G(x)→?R(x))P
⑷G(c)→?R(c)US⑶
⑸ ?G(c)T⑵⑷拒取式
⑹(?x)(F(x)∨G(x))P
⑺F(c)∨G(c)US⑹
⑻F(c) T⑸⑺析取三段论
⑼(?x)F(x) UG⑻
⑷(?x)(F(x)→R(x))?(?x)F(x)→(?x)R(x)
证明：
⑴ (?x)F(x)P(附加前提)
⑵F(c) US⑴
⑶(?x)(F(x)→R(x))P
⑷F(c)→R(c)US⑶
⑸R(c) T⑵⑷假言推理
⑹(?x)R(x) UG⑸
⑺(?x)F(x)→(?x)R(x)CP
⑸(?x)(F(x)∨G(x))，?(?x)(G(x)∧R(x))?(?x)R(x)→(?x)F(x)证明：
⑴ (?x)R(x)P(附加前提)
⑵R(c) US⑴
⑶?(?x)(G(x)∧R(x))P
⑷(?x)?(G(x)∧R(x))T⑶量词否定等价式
⑸?(G(c)∧R(c)) US⑷
-6 -
重修习题集
⑹ ?G(c)∨?R(c)T⑸德摩根律
⑺?G(c) T⑵⑹析取三段论
⑻(?x)(F(x)∨G(x))P
⑼F(c)∨G(c)US⑻
⑽F(c) T⑺⑼析取三段论
⑾(?x)F(x) UG⑽
⑿(?x)R(x)→(?x)F(x)CP
⑹(?x)(F(x)∨G(x))?(?x)F(x)∨(?x)G(x)
证明：
⑴?((?x)F(x)∨(?x)G(x)) P(附加前提)
⑵?(?x)F(x)∧?(?x)G(x)) T⑴德摩根律
⑶(?x)?F(x)∧(?x)?G(x)) T⑵量词否定等价式
⑷(?x)?F(x) T⑶化简律
⑸?F(c) ES⑷
⑹(?x)?G(x)) T⑶化简律
⑺?G(c) US⑹
⑻(?x)(F(x)∨G(x))P
⑼F(c)∨G(c)US⑻
⑽F(c) T⑺⑼析取三段论
⑾F(c)∧?F(c)(矛盾)T⑸⑽合取引入
⑺(?x)(F(x)∨G(x))，(?x)(G(x)→?R(x))，(?x)R(x)?(?x)F(x)
证明：
⑴ ?(?x)F(x)P(附加前提)
⑵(?x)?F(x) T⑴量词否定等价式
⑶?F(c) ES⑵
⑷(?x)(F(x)∨G(x))P
⑸F(c)∨G(c)US⑷
⑹G(c) T⑶⑸析取三段论
⑺(?x)(G(x)→?R(x))P
⑻G(c)→?R(c)US⑺
⑼?R(c) T⑹⑻假言推理
⑽(?x)R(x) P
⑾R(c) US⑽
⑿R(c)∧?R(c)(矛盾)T⑼⑾合取引入
⑻(?x)(F(x)→?G(x))，(?x)(G(x)∨R(x))，(?x)?R(x)?(?x)?F(x)证明：
⑴ (?x)?R(x) P
⑵?R(c) ES⑴
-7 -
重修习题集
⑶?(?x)?F(x) P(附加前提)⑷(?x)F(x) T⑶量词否定等价式 ⑸F(c) US⑷⑹(?x)(F(x)→?G(x))P ⑺F(c)→?G(c)US⑹⑻?G(c) T⑸⑺假言推理⑼(?x)(G(x)∨R(x))P ⑽G(c)∨R(c)US⑼⑾R(c) T⑻⑽析取三段论⑿
R(c)∧?R(c)(矛盾)T⑵⑾合取引入⑼证明下面推理。每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。解：首先将命题符号化：
Q(x)：x 是有理数。 | R(x)：x 是实数。 Z(x)：x 是整数。 | 本 |
题要证明：(?x)(Q(x)→R(x)),(?x)(Q(x)∧Z(x))?(?x)(R(x)∧Z(x))证明：⑴(?x)(Q(x)∧Z(x))P ⑵Q(c)∧Z(c)ES⑴
⑶Q(c) T⑵化简律
⑷Z(c) T⑵化简律
⑸(?x)(Q(x)→R(x)) P
⑹Q(c)→R(c) US⑸
⑺R(c) T⑶⑹假言推理⑻R(c)∧Z(c)T⑷⑺合取引入⑼(?x)(R(x)∧Z(x)) EG⑻
第三章
1）确定下列集合的幂集合。
⑴?a,b?
⑵??a,?b,c???
⑶??a,b?,?a,c??
⑷P(?)
⑸P(P(?))
解：⑴??,?a?,?b?,?a,b??
⑵??,??a,?b,c????
⑶??,??a,b??,??a,c??,??a,b?,?a,c???
-8 -
重修习题集
⑷??,????
⑸??,???,?????,????????
2）设全集E=?1,2,3,4,5,6?，A=?1,4?，B=?1,2,5?，C=?2,4?。求下列各集合。
⑴ A∩~B
⑵(A∩B)∪~C
⑶~ (A∩B)
⑷A?B
解：⑴A∩~B=?1,4?∩?3,4,6?=?4?
⑵(A∩B)∪~C=(?1,4?∩?1,2,5?)∪?1,3,5,6?=?1?∪?1,3,5,6?=?1,3,5,6?⑶~(A∩B)=~?1?=?2?3,4,5,6?
⑷A?B=(A∪B)－(A∩B)=?1,2,4,5?－?1?=?2,4,5?
3）设A,B,C,D是任意集合（*参考）
证明：
⑴A∪(B∩C)=(A∪B)∩(A∪C)
证明： x?A∪(B∩C)?x?A∨x?B∩C
?x?A∨(x?B∧x?C)
?(x?A∨x?B)∧(x?A∨x?C)
?(x?A∨x?B)∧(x?A∨x?C)
?x?A∪B∧x?A∪C
?x?(A∪B)∩(A∪C)
所以A∪(B∩C)=(A∪B)∩(A∪C)
⑵A∩(B∪C)=(A∩B)∪(A∩C)
证明： x?A∩(B∪C)?x?A∧x?B∪C
?x?A∧(x?B∨x?C)
?(x?A∧x?B)∨(x?A∧x?C)
?x?A∩B∨x?A∩C
?x?(A∩B)∪(A∩C)
所以A∩(B∪C)=(A∩B)∪(A∩C)
⑶~ (~A)=A
证明： x?~(~A)??(x?~A)??(?x?A)?x?A所以~(~A)=A
⑷A∪E=E
证明：x?A∪E?x?A∨x?E?x?A∨T?T?x?E
所以A∪E=E
⑸A∩~A=?
证明：x?A∩~A?x?A∧x?~A?x?A∧?(x?A)?F?x??所以A∩~A=?
⑹ A∪(A∩B)=A
-9 -
重修习题集
证明：x?A∪(A∩B)?x?A∨x?A∩B?x?A∨(x?A∧x?B)?x?A (吸收律)所以A∪(A∩B)=A
⑺~(A∩B)=~A∪~B
证明：x?~(A∩B)??(x?A∩B)??(x?A∧x?B)??x?A∨?x?B?x?~A∨x?~B?x?~A∪~B
所以~(A∩B)=~A∪~B
4）判断下列结论是否正确。
⑴若A∪B=A∪C，则B=C
不正确。反例，令A=?1,2,3?，B=?1,2?，C=?1?。A∪B=?1,2,3?=A∪解：
C，但B≠C。
⑵若A∩B=A∩C，则B=C
解：不正确。反例，令A=?1?，B=?1,2?，C=?1,2,3?。A∩B=?1?=A∩C，但B≠C。
5）设A=?a,b?，B=?1,2,3?，求：A×B，B×A，A×A，B×B和(A×B)∩(B×A)。
解：A×B=??a,1?,?a,2?,?a,3?,?b,1?,?b,2?,?b,3??
B×A=??1,a?,?1,b?,?2,a?,?2,b?,?3,a?,?3,b??
A×A=??a,a?,?a,b?,?b,a?,?b,b??
B×B=??1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?,?3,1?,?3,2?,?3,3??
(A×B)∩(B×A)=?
6）证明下列各题。
⑴如果A×A＝B×B，那么A＝B
证明：x?A?x?A∧x?A??x,x??A×A??x,x??B×B?x?B∧x?B?x?B，所以A＝
B
⑵如果A×B＝A×C且A≠?，那么B＝C
因为A≠?，?x?A，以下证明B＝C
y?B?x?A∧y?B??x,y??A×B??x,y??A×C?x?A∧y?C?y?C，所以B＝C⑶(A∩B)×(C∩D)＝(A×C)∩(B×D)
证明：?x,y??(A∩B)×(C∩D)?x?A∩B∧y?C∩D
?x?A∧x?B∧y?C∧y?D
?x?A∧y?C∧x?B∧y?D
??x,y??A×C∧?x,y??B×D
??x,y??A×C∩B×D
所以(A∩B)×(C∩D)＝(A×C)∩(B×D)
7）用列举法表示A到B的二元关系R，写出关系矩阵，画出关系图。 ⑴A=?1,2,3,4,5?，B=?a,b,c?，R=??1,a?,?1,b?,?2,b?,?3,a??
⑵A=?a,b,c?，B=?1,2,3,4,5?，R=??a,2?,?c,4?,?c,5??
-10 -
重修习题集
⑶A=?0,1,2?，B=?0,2,4?，R=??a,b?|a?A∧b?B∧a×b?A∩B?，其中×是普通乘法。
⑷A=?1,2,3,4,5?，B=?1,2,3?，R=??a,b?|a?A∧b?B∧a=b2?解答：
?1??0
⑴MR=?1??0??0110000??0?0? ?0??0?
R关系图如图4.20所示。
⑵ ?01000???MR=?00000??00011???
R关系图如图4.21所示。
?111???⑶MR=?110??100???
R关系图如图4.22所示。
?1??0
0⑷MR=???0??000??00?00? ?10??00?
R关系图如图4.23所示。
8）设A=?1,2,3?，A上二元关系定义为：
-11 -
重修习题集
R=??1,1?,?1,2?,?1,3?,?3,3??
S=??1,1?,?1,2?,?2,1?,?2,2?,?3,3??
T=??1,1?,?1,2?,?2,2?,?2,3??
?(空关系)
A×A(全域关系)
判断上述关系是否是⑴自反的，⑵对称的，⑶传递的，⑷反对称的。
解：各关系的自反性、对称性、传递性和对称性如表4.2所示。9）设A=?1,2,3,4?，A上二元关系R定义为：
R=??1,2?,?2,1?,?2,3?,?3,4??
⑴求R的自反闭包、对称闭包和传递闭包。
⑵用R的关系矩阵和四阶单位阵求R的自反闭包、对称闭包和传递闭包的关系矩阵。再由关系矩阵写出它们的集合表达式。
⑶根据R的关系图，画出R的自反闭包，对称闭包和传递闭包的关系图，再由关系图写出它们的集合表达式。
解答：
⑴
r(R)=??1,2?,?2,1?,?2,3?,?3,4?,?1,1?,?2,2?,?3,3?,?4,4??
s(R)=??1,2?,?2,1?,?2,3?,?3,4?,?3,2?,?4,3??
R2=R?R=??1,1?,?1,3?,?2,2?,?2,4??
R3=R2?R=??1,2?,?1,4?,?2,1?,?2,3??
R4=R2?R=??1,1?,?1,3?,?2,2?,?2,4??=R2
t(R)=R∪R2∪R3∪
R4=??1,1?,?1,2?,?1,3?,?1,4?,?2,1?,?2,2?,?2,3?,?2,4?,?3,4??⑵解： ?0?1MR=??0??0?100??010?001??000?? ?0?1Mr(R)= MR∨MIA=??0??0??1100???0010?
∨???0001???0000???000??1??100??1=0010?????001???0100??110?011??001??
r(R)=??1,2?,?2,1?,?2,3?,?3,4?,?1,1?,?2,2?,?3,3?,?4,4??
-12 -
重修习题集
?0?1TMs(R)=MR∨MR=??0??0??0100???010??1∨?0001????0000???
?0??1
?0??0?100??0??000??1=0100?????010???0100??010?
101??010??s(R)=??1,2?,?2,1?,?2,3?,?3,4?,?3,2?,?4,3??
MR2?0??1?MR?MR=?0??0?100??010?001??000???100??1??010??0=001??0?
??000???0
10
01
00
00MR3=MR2
MR4=MR3?1?0?MR=??0??0??0?1?MR=??0??0?010??101?000??000??101??010?000??000????0??1?0??0??0??1?0??0?
?1??1??0??0?010??101?000??000??0??0101????0??1010?= 1??0000??????0?0000???010??101?
000??000???100??1??010??0=001??0???000???0111??111?
001??000??Mt(R)=MR∨MR2∨MR3∨MR4
t(R)=??1,1?,?1,2?,?1,3?,?1,4?,?2,1?,?2,2?,?2,3?,?2,4?,?3,4??
⑶R的关系图如图4.30所示，R的自反闭包、对称闭包和传递闭包的关系图如图
4.31、图4.32和图4.33所示。
10）设R是A上的二元关系，证明：
⑴R是对称的当且仅当s(R)=R
⑵R是传递的当且仅当t(R)=R
证明：⑴?设R是对称的，下证s(R)=
R
-13 -
重修习题集
令R′=R
①R′=R是对称的。
②因为R?R=R′，所以R?R′。
③有任意对称二元关系R′′且R?R′′，下证R′?R′′因为R′=R?R′′，所以R′?R′′
?设s(R)=R，下证R是对称的。
由对称闭包的定义，显然R是对称的。
⑵?设R是传递的，下证t(R)=R
令R′=R
①R′=R是传递的。
②因为R?R=R′，所以R?R′。
③有任意传递二元关系R′′且R?R′′，下证R′?R′′因为R′=R?R′′，所以R′?R′′
?设t(R)=R，下证R是传递的。
由传递闭包的定义，显然R是传递的。
11）设R和S是A上的二元关系，R?S，证明：⑴r(R)?r(S)
⑵s(R)?s(S)
⑶t(R)?t(S)
证明：
⑴
r(R)=IA∪R?IA∪S=r(S )，即r(R)?r(S)。
⑵
先证RC?SC，?a,b??RC??b,a??R??b,a??S??a,b??SC，所以RC?SC s(R)=R∪RC?S∪SC=s(S) ，所以s(R)?s(S)。
⑶
R?S?t(S)，t(S)是包含R的传递关系，而t(R)是包含R的最小的传递关系。所以t(R)?t(S)
12）设R和S是A上的二元关系，证明：
⑴r(R∪S)=r(R)∪r(S)
⑵s(R∪S)=s(R)∪s(S)
证明：⑴r(R∪S)=R∪S∪IA=(R∪IA)∪(S∪IA)=r(R)∪r(S)
⑵s(R∪S)=(R∪S)∪(R∪S)C=(R∪RC)∪(S∪SC)=s(R)∪s(S)
13）设A=?1,2,3,4,5?，A上的等价关系R定义为：
R=??1,2?,?2,1?,?3,4?,?4,3??∪IA
画出关系图，找出所有等价类，总结等价类和关系图的关系。
解：R的关系图如图4.34所示。
[1]R=[2]R=?1,2?，[3]R=[4]R=?3,4?，[5]R=?5?
-14 -
重修习题集
关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每
一个等价类导出了关系图的一个连通分支。
14）集合A是自然数集合的子集，A上的整除关系R是偏
序关系。定义为R=??x,y?|x?A∧y?A∧x整除y?。求出下列集合A上的盖住关系COVA，画出哈斯图，指出该偏序关系是否为全序关系。 ⑴A=?3,9,27,54?
⑵A=?1,2,3,4,6,8,12,24?
⑶A=?1,3,5,9,15,18,27,36,45,54?
⑷A=?1,2,3,4,5,6,7,8,9,10,11,12?
解：⑴R=??3,9?,?3,27??3,54?,?9,27?,?9,54??27,54??∪IA集合A上的盖住关系COVA=??3,9?,?9,27??27,54??
哈斯图如图4.39所示。
R是全序关系。
⑵
R=??1,2?,?1,3?,?1,4?,?1,6?,?1,8?,?1,12?,?1,24?,?2,4?,
?2,6?,?2,8?,?2,12?,?2,24?,?3,6?,?3,12?,?3,24?,?
4,8?,
?4,12?,?4,24?,?6,12?,?6,24?,?8,24?,?12,24??∪I
A
COVA=??1,2?,?1,3?,?2,4?,?2,6?,?3,6?,?4,8?,?4,12?,
?6,12?,?8,24?,?12,24??
哈斯图如图4.40所示。
R不是全序关系。
⑶ R=??1,3?,?1,5?,?1,9?,?1,15?,?1,18?,?1,27?,?1,36?,?1,45?,?1,54?,
?3,9?,?3,15?,?3,18?,?3,27?,?3,36?,?3,45?,?3,54?,?5,15?,?5,45?,?9,18?,?9,27?,?9,36?,?9,45?,?9,54?,?15,45?,?18,36?,?18,54?,?27,54??∪IA
COV
A=??1,3?,?1,5?,?3,9?,?3,15?,?5,15?,?9,18?,?9,27?,?9,45?,?15,45?,?18,36?, ?18,54?,?27,54??
哈斯图如图4.41所示。
不是全序关系。
-15 -
重修习题集
⑷
R=??1,2?,?1,3?,?1,4?,?1,5?,?1,6?,?1,7?,?1,8?,?1,9?,?1,10?,?1,11?,?1,12?,?2,4?,?2,6?,?2,8?,?2,10?,?2,12?,?3,6?,?3,9?,?3,12?,?4,8?,?4,12?,
?5,10?,?6,12??∪IA
COVA=??1,2?,?1,3?,?1,5?,?1,7?,?1,11?,?2,4?,?2,6?,?3,6?,?3,9?,
?4,8?,?4,12?,?5,10?,?6,12??
哈斯图如图4.42所示。
不是全序关系。
15）求出下列各偏序集?A,??的盖住关系COVA，画出哈斯图，找出A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。
⑴A=?a,b,c,d,e?，?=??a,b?,?a,c?,?a,d??a,e?,?b,e?,?c,e??d,e??∪IAB1=?b,c,d ?，B2=?a,b,c,d?，B3=?b,c,d,e?
⑵A=?a,b,c,d,e?，?=??c,d??∪IA
B1=?a,b,c,d,e?，B2=?c,d?，B3=?c,d,e?
⑶A=P(?a,b,c?)，?=??x,y??x?P(A)∧y?P(A)∧x?y?
B1=??,?a?,?b??，B2=??a?,?c??，B3=??a,c?,?a,b,c??
解：⑴COVA=??a,b?,?a,c?,?a,d?,?b,e?,?c,e?,?d,e??
哈斯图如图4.43所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.3所示。
-16 -
重修习题集
⑵COVA=??c,d??
哈斯图如图4.44所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.4所示。
⑶A=P(?a,b,c?)=??,?a?,?b?,?c?,?a,b?,?a, c?,?b, c?,?a,b,c??
?=???,?a??,??,?b??,??,?c??,??,?a,b??,??,?a,c??,??,?b,c??,??,?a,b,c??,
??a?,?a,b??,??a?,?a,c??,??a?,?a,b,c??,??b?,?a,b??,??b?,?b,c??,??b?,?a,b
,c??,
??c?,?a,c??,??c?,?b,c??,??c?,?a,b,c??,??a,b?,?a,b,c??,??a,c?,?a,b,c??,??b,c ?,?a,b,c???∪IA
COV
A=???,?a??,??,?b??,??,?c??,??a?,?a,b??,??a?,?a,c??,??b?,?a,b??,??b?,?b,c??,??c?,?a,c??,??c?,?b,c??,??a,b?,?a,b,c??,??a,c?,?a,b,c??,??b,c?,?a,b,c???
哈斯图如图
4.45
所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.5所示。
-17 -
重修习题集
第五章
1）设代数系统<A,?>，其中A=?a,b,c?，?是A上的二元运算，分别由下列表给出。试分别讨论交换性、幂等性、单位元和逆元。
277解：代数系统<N7,＋7>的幺元为0，无零元，0逆元是0，1和6，2和5，3
-18 -
重修习题集
和4互为逆元。
3）写出代数系统<N7,×7>的幺元和零元，各元素的逆元。
解：代数系统<N7,×7>的幺元为1，零元为0，0无逆元，1的逆元为1，6的逆元为6，2和4，3和5互为逆元。
6）设<Z,?>是代数系统，?的定义分别为：
⑴a?b=|a+b|，⑵a?b=ab，⑶a?b=a+b?1，⑷a?b=a+2b
问：哪些运算在Z上是封闭的？哪些运算是可交换的？哪些运算是可结合的？
解：Z为整数集合，
⑴因为
①整数加法运算在Z上封闭，绝对值运算在Z上也封闭。
②?a,b?Z，a?b=|a+b|=|b+a|=b?a
③当a＝1，b＝2，c＝-3时，(a?b)?c=||a+b|+c|=0，a?(b?c)=|a+|b+c||=2，(a?b)?c≠a?(b?c)。
所以，?运算在Z上封闭，可交换，但不可结合。
⑵因为
①当b＜0时，a?b=ab不一定是整数，例如a＝2，b＝-1，a?b=2-1?Z， ②?a,b?Z，a?b=ab，b?a=ba，a?b不一定等于b?a，例如a＝2，b＝1时，a?b=ab=2，b?a=ba=1。a?b≠b?a。
③当a=2，b=1，c=2，(a?b)?c=(ab)?c=(21)?2=22=4，a?(b?c)=a?(bc)=2?(12)=2，(a?b)?c≠a?(b?c)。
所以?运算在Z上不封闭，不可交换，不可结合。
⑶因为
①整数加法和减法运算在Z上封闭，
②?a,b?Z，a?b=a＋b-1=b＋a-1=b?a
③?a,b,c?Z，(a?b)?c=(a＋b-1)＋c-1=a＋b＋c-2=a＋(b＋c-1)-1。所以，?运算在Z上封闭，可交换，可结合。
⑷因为
①整数加法和乘法运算在Z上封闭。
②?a,b?Z，a?b=a＋2b，b?a=b＋2a。a?b不一定等于b?a，如a＝1，b＝2时。a?b=a＋2b=5，b?a=b＋2a=4，a?b≠b?a。
③?a,b,c?Z，(a?b)?c=(a＋2b)＋2c，a?(b?c)=a＋2(b＋2c)=a＋2b＋4c，当a＝0，b＝0，c＝1时，(a?b)?c=2，a?(b?c)=4，(a?b)?c≠a?(b?c)。 所以，?运算在Z上封闭，不可交换，也不可结合。
7）设Z是整数集合，Z上的二元运算*定义为：a*b=ab+2(a+b+1)。证明代数系统<Z,*>是半群。
证明：由于任意两个整数经加、减、乘运算后，其结果仍然是整数。所以运算*对于是封闭的。
-19 -
重修习题集
现证*是可结合运算。由于
(a*b)*c=(ab+2(a+b+1))*c
=(ab+2(a+b+1))c+2(ab+2(a+b+1)+c+1)
=abc+2ac+2bc+2c+2ab+4a+4b+2c+6
=abc+2(ab+bc+ca)+4(a+b+c)+6
a*(b*c)=a*(bc+2(b+c+1))
=a(bc+2(b+c+1))+2(a+bc+2(b+c+1)+1)
=abc+2ab+2ac+2a+2a+2bc+4b+4c+6
=abc+2(ab+bc+ca)+4(a+b+c)+6
所以 (a*b)*c=a*(b*c)。由此证得*是可结合运算，<Z,*>是半群。
8）Z是由所有整数组成的集合，对于下列*运算，哪些代数系统<Z,*>是半群?
⑴ a*b=ab
⑵a*b=a
⑶a*b=a+ab
⑷a*b=max(a,b)
解：⑴不是半群。因为运算*不满足结合律。
例如，(2*3)*2=23*2=(23)2=26，而2*(3*2)=2*32=29，所以(2*3)*2≠2*(3*2)。⑵是半群。*的封闭性是显然的，由于(a*b)*c=a*c=a,
a*(b*c)=a*b=a，所以*是可结合运算，<Z,*>是半群。
⑶不是半群，因为运算*不满足结合律。易见
(a*b)*c=(a+ab)*c=a+ab+(a+ab)c=a+ab+ac+abc而
a*(b*c)=a*(b+bc)=a+a(b+bc)=a+ab+abc
所以(a*b)*c≠a*(b*c)，*不是可结合运算。
⑷是半群。*的封闭性是显然的，由于(a*b)*c=a*(b*c)=max(a,b, c)，所以*是可结合运算，<Z,*>是半群。
9）Z是整数集合，运算*定义为a*b=a+b+ab。证明<Z,*>是独异点。
证明：*对于Z的封闭性是显然的。下面证明*是可结合运算，由于
(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abc
a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc所以有 (a*b)*c=a*(b*c)
由此可知*是可结合运算。又由于
0*a=a*0=0+a+a·0=a
所以0是幺元，<Z,*>是独异点。
10）<A,*>是半群，对于A中任意两个不同的元素a和b都有a*b≠b*a，证明a*b*a=a。
证明：由题设可知，当a≠b时，必有a*b≠b*a，也即当a*b=b*a时，必有a=b。由于<A,*>是半群，*是可结合运算，所以对于A中任意元素a，都有
-20 -
重修习题集
(a*a)*a=a*(a*a)
由此可知 a*a=a
又由于(a*b*a)*a=a*b*(a*a)=a*b*a，而a*(a*b*a)=(a*a)*b*a=a*b*a，所以有(a*b*a)*a=a*(a*b*a)，由此证得a*b*a=a。
11）设R是实数集，R上的二元运算*定义为：a*b=a+b+ab。
⑴证明<R,*>是独异点，并写出其幺元和零元。
⑵设A是所有不等于?1的实数构成的集合，即A=R???1?，证明<A,*>是群。证明：
⑴由于实数经加法和乘法运算后，其运算结果仍为实数，所以运算*对于R是封闭的。
再证明*是可结合运算。由于
a*b=a+b+ab=a(b+1)+(b+1)?1=(a+1) (b+1)?1从而有
(a*b)*c=((a+1)(b+1)?1)*c=(((a +1)(b+1)?1)+1)(c+1)?1=(a +1)(b+1)(c +1)?1a*(b*c)=a*((b +1)(c+1)?1)=(a +1)(((b +1)(c+1)?1)+1)?1=(a +1)(b+1)(c+1)?1 于是(a*b)*c=a*(b*c)。所以*是可结合运算。
在<R,*>中，对于任何实数a，都有
0*a=a*0=0+a+0·a=a
故0是<R,*>中的幺元，<R,*>是独异点。
对于<R,*>中任何实数a，都有
(?1)*a=a*(?1)=(?1)+a+(?1)·a=?1
即?1是<R,*>中的零元。
⑵首先证明*对于A是封闭的。由于
a*b=(a+1)(b+1)?1
所以当a和b为不等于?l的实数时，a+1≠0，b+1≠0，也即有(a+1)(b+1)≠0，由此可知
a*b=(a+1)(b+1)?1≠?1
因此*对于A是封闭的。0是<A,*>中的幺元。
现证明A中的每一个元素都有逆元。对于A中任意元素a(a是不等于?1的实数)，都有
11a*(?1)=(a+1)(?1+1)?1=0 a?1a?1
1由于0是幺元，所以a的逆元是?1。a?1
综上证明，<A,*>是群。
12）集合A=?1,2,3,4?，A上的二元运算*定义如下，哪些代数系统<A,*>是群?
⑴a*b=a+b；
-21 -
重修习题集
⑵*是模5乘法；
⑶a*b=ab。
解：
⑴不是群。因为普通加法对于A是不封闭的。
⑵是群。因为A=N5??0?，5是素数，所以<A,?5>是群。
(3)不是群。因为*不是封闭运算。也不是可结合运算。
14）证明<Z,+>是群。
证明：由于任意两个整数相加仍然是整数，所以加法对于整数集Z是封闭的；加法满足结合律；0是幺元；任意整数i的逆元是?i。由此可知<Z,+>是群。
15）证明群中不存在零元。
证明：因为零元没有逆元，所以群中不存在零元。
16）设<G,*>是群，如果对于群G中任意元素a,b，都有(a*b)?1=a?1*b?1，证明<G,*>是阿贝尔群。
证明：由群的性质和定理7.1.5可知
(b*a)?1=a?1*b?1
由题设可知
(a*b)?1=a?1*b?1
所以有
(a*b)?1=(b*a)?1
由逆元的惟一性可知 a*b=b*a，<G,*>是阿贝尔群。
17）设<G,*>是群，如果对于群G中任意元素a,b，都有(a*b)3=a3*b3和(a*b)5=a5*b5，证明<G,*>是阿贝尔群。
证明：由题设可知(a*b)3=a3*b3，则
a*b*a*b*a*b=a*a*a*b*b*b
从左边消去a和右边消去b后可得
b*a*b*a=a*a*b*b
即
(b*a)2=a2*b2
又由题设可知(a*b)5=a5*b5，则
a*b*a*b*a*b*a*b*a*b=a*a*a*a*a*b*b*b*b*b从左边消去a和右边消去b后可得
(b*a)4=a4*b4
由已证得(b*a)2=a2*b2，所以有
a2*b2*a2*b2=a4*b4
再从左边消去a2和右边消去b2后可得
b2*a2=a2*b2
又由于
(b*a)2=a2*b2=b2*a2
-22 -
重修习题集
利用已知结果知
a*b=b*a
所以<G,*>是阿贝尔群。
18）设<G,*>是群，e是幺元，如果对于G中任意元素a，都有a*a=e，证明<G,*>是阿贝尔群。
证明：对于群G中任意元素a,b，由题设条件a2=e,b2=e；由*运算的封闭性可知，a*b?G，所以(a*b)2=e，于是有
(a*b)2=e=e*e=a2*b2
利用已知结果知，<G,*>是阿贝尔群。
第七章
1）设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点？
解：当其余结点都为2度时，结点数最少。根据定理9.1.1列方程：3×4+4×3+2×x=2×16。解方程得：x=4。无向图G中的结点数为：4+3+4=11。所以，G中至少有11个结点。
2）.设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。
证明：图G中：5度结点数可能为：0，1，2，3，4，5，6，7，8，96度结点数可能为：9，8，7，6，5，反证法，设6度结点小于5个且
5度结点小于6个，则只可能有5个5度结点，4个6度结点(其他情况结点数的和小于9)。此时，各结点度数之和为：5×5+4×6=25+24=49。与结点度数之和为偶数(边数两倍)矛盾。
所以，G中至少有5个6度结点或至少有6个5度结点。
-23 -
因篇幅问题不能全部显示，请点此查看更多更全内容