北华大学08-09学年离散数学试卷B答案
一、回答下列问题（每小题5分，共25分） 1. 什么子群称为正规子群？
设(H,o)是群(S,o)的一个子群，如果对任意的a?S都有 2分
aH?Ha，则称(H,o)是(S,o)的一个正规子群。 3分
2. 命题公式A为重言式的充分必要条件是什么？
答：命题公式A为重言式当且仅当A的合取范式中每个质析取式至少同时含有一个命题变元及其否定。 5分
n（或 命题公式A为重言式当且仅当A的主析取范式含全部的2个最小项。 5分） 3. 关系R满足什么条件时，称为对称的；非对称的；既不是对称的也不是非对称的？
答：设R是集合A上的关系，
1）若有(x,y)?R （或xRy），必有(y,x)?R （或yRx），则称R是对称的。 ………2分 2）若有(x,y)?R （或xRy）且x?y，必有(y,x)?R （或
yRx），则称R是非对称的。 ………2分
3）既不满足1）也不满足2），则称R既不是对称的也不是非对称的。 ………1分 4.什么样的集合为可数集合？
答：凡与自然数集N有相同基数之集为可数集。 ………5分
5. 如果T是（n，m）树，则m=？
答：m=n-1 ………5分
二、计算（每小题10分，共20分）
1. 用等值演算法证明 P?(Q?P)??P?(P?Q)。 证明：P?(Q?P) ………1分
?P?(?Q?P) ………1分 ??P?(?Q?P) ………1分 ??P?P??Q ………1分 ?1??Q ………1分
?1
?P?(P?Q)
?P?(P?Q) ………1分 ?P?(?P?Q) ………1分 ?P??P?Q ………1分 ?1?Q ………1分
?1 ………1分 ?P?(Q?P)??P?(P?Q)
1,2,3,4}，求出?(A)，\?\是?(A)上的关系。 2. 设A?{B?{{1},{2},{2,3},{3,4},{1,3,4},{1,2,3,4}}，试求B的上
界，下界，上确界，下确界。
解：
???????,??1,?2??,3??,4?,?1,2??,1,3??,1,4?,?2,3?,?2,4?,?3,4??,1,2,3?,?1,2,4?,?2,3,4??,1,3,4?,?1,2,3,4??6分
1,2,3,4}， 1分 . B的上界是{B的下界是?， 1分.
B的上确界是{1,2,3,4}， B的上确界是?，
三、（本题10）
证明：如果R是偏序，则R?1也是偏序。证明：设R是A上的一个关系 因R是偏序，?x,y,z?A
当?x,y??R,?y,z??R，则必有?x,z??R 于是，?y,x??R?1，?z,y??R?1,?z,x??R
即R?1是传递的. 若?x,x??R,那么?x,x??R?1
即R?1是自反的. 若?x,y??R,那么?x,y??R?1 即R?1是非对称的.
?R?1也是拟序关系.
1分. 1分. 4分 3分 3分
四、（本题10分）
证明在任何有向完全图中，所有结点引入次数之和等于所有结点引出次数之和。
证明：设有向图G具有m条边，则该m条边对应2m个结点。2分 而每条边对应一个出度和一个入度， 故m条边对应m个出度，m个入度， 2分 m个出度恰是所有结点的引出次数之和。 2分 同理，m个入度恰是所有结点的引入次数之和。 2分 即所有结点引出次数之和=m=所有结点引入次数之和. 2分
五. 证明（本题10分）
设f是群(S,o)到群(G,?)的同态变换，kerf是f的同态核，则(kerf,o)是(S,o)的子群。
证明：由f是群(S,o)到群(G,?)的同态变换，知
f(e)?e1,e?S,e1?G, 3分
设任意a,b?kerf ，则
f(aob)?f(a)?f(b)?e1?e1?e1,
故 aob?kerf. 4分
?1?1?1对任意a?kerf，知f(a)?[f(a)]?e1?e1,
即a?1?kerf. 4分
由子群判定知(kerf,o)是(S,o)的子群。
六、（本题5分）
判断下面论述是否为真：“?是无理数，且如果3是无理数，则也是无理数。另外，只有6能被2整除，6才能被4整除。” 解 A: ?是无理数, T 真值为1 B: 3是无理数, F 真值为0 C: 2也是无理数, T 真值为1
D: 6能被2整除, T 真值为1
E: 6才能被4整除, F 真值为0 3分 A??B?C???D?E?
2?1?1?0
?0
所以此论述为假。 2分
七.（本题10分）
证明在有向完全图中，所有结点引入次数平方和等于所有结点引出次数平方和。
证明：设G是具有n个结点的有向完全图，对每个vi有
uuursuuudeg(vi)?deg(vi)?n?1, 4分 uuursuuu222[deg(v)]?[deg(v)]?(n?1), 3分 从而 ii共有n个结点，于是有
nuuursuuu222[deg(v)]?[deg(v)]?n(n?1). 4分 ??iini?1i?1
新离散数学试卷B答案
