1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)析取范式：
?(x1?x2?x3)?(x1?x2?x3)
合取范式：E(x1,x2,x3)?(x1?x?2x3)?(x1?x2?x3)?(x1?x2?x3)
六、 树的应用 16%
1、（6分）解：
2、（10分）解：
根据权数构造最优二叉树：
传输它们的最佳前缀码如上图所示，happy new year的编码信息为：
10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：
试卷十五试题与答案
十二、 填空 20% （每空 2分）
1、 如果有限集合A有n个元素，则|2A|= 。 2、 某集合有101个元素，则有 个子集的元素为奇数。
3、 设S={a1，a2,?，a8}，Bi是S的子集，由B17表达的子集为 ，
子集{a2,a6,a7}规定为 。
4、 由A1，A2,?，An，生成的最小集的形式为 ，它们的并为 集，它们的交为 集。 5、 某人有三个儿子，组成集合A={S1,S2,S3}，在A上的兄弟关系
具有 性质。
6、每一个良序集必为全序集，而 全序集必为良序集。
7、若f:A?B是函数，则当f是A?B的 ，f:B?A是f的逆函数。
c十三、 选择 15% （每小题 3分）
1、 集合B?{?,{?},{?,{?}}}的幂集为（ ）。 A、{{?},{{?},?},?}；
{?,{?},{{?}},{{?,{?}}},{?,{?}},{?,{?,{?}}},{{?},{?,{?}}},B}；B、
C、{?,{?},{{?}},{?,{?}},{?,{?}},{?,{?,{?}}},{{?},{?,{?}}},B}；
{?}}},{{?},{?,{?}}},?,B} D、{{?}{?,{?}},{?,{?，2、 下列结果正确的是（ ）。
A、(A?B)?A?B；B、(A?B)?A??；C、(A?B)?B?A；
D、??{?}??；E、??{?}??；F、A⊕A=A 。 3、 集合A?B的最小集范式为（ ）（由A、B、C生成）。
(A?B?C)?(A?B?C)?(A?B?C)?A
、
(A?B?C)?(A?B?C)?(A?B?C) ； B、
(A?B)?(A?B)?(A?B)；
(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)C、
(A?B)?(A?B)?(A?B)。 ； D、
4、 在（ ） 下有A?B?A。
A、A?B；B、B?A；C、A?B；D、A??或B?? 5、 下列二元关系中是函数的有（ ）。
A、R?{?x,y?|x?N?y?N?x?y?10}； B、R?{?x,y?|x?R?y?R?y?x}；
2R?{?x,y?|x?R?y?R?x?y}。 C、
2三、 15%
用Warshall算法，对集合A={1，2，3，4，5}上二元关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t（R）。
四、15%
，a?0}，C*上定义关系 集合C?{a?bi|i??1,a,b是任意实数R?{?a?bi,c?di?|ac?0}，则R是C*上的一个等价关系，并给出R等价类的几何
说明。
*2五、计算 15%
1、 设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关
系。 （4分）
2、 设
Ｚ
为
整
数
集
，
关
系
R?{?a,b?|a,b?Z?a?b(modk)}为Z上等价关系，
求R的模K等价关系的商集Z/R，并指出R有秩。（5分） 3、 设A={1，2，3，4，5}，A上的偏序关系为
求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。（6分）
六、证明 20%
1、 假定f:A?B,g:B?C，且g?f是一个满射，g是个入射，则f是满射。（10分） 2、 设f，g是A到B的函数，f?g且domg?domf，证明f?g。（10分） 答案
一、填空 20%（每空2分）
????1、2n；2、2100；3、{a4，a8}，B01000110（B70）；4、A1?A2???An(Ai?Ai或Ai)，
全集，?；5、反自反性、对称性、传递性；6、有限；7、双射。
二、选择 15%（每小题 3分）
题目 答案
三、Warshall算法 15%
1 B 2 3 4 D 5 B B，E A ?1??0MR??0??0?0?解：1000??0010?0001??1000?0000??
i? 1时，MR[1,1]=1, A =MR i?2时，M[1,2]=M[4,2]=1
?1??0?0??0?0A=?1010??0010?0001??1010?0000??
i?3时，A的第三列全为0，故A不变 i?4时，M[1,4]=M[2,4]=M[4,4]=1
?1??0?0??0?0A=??1??0?0??0?0A=?四、 5% 证明：
1010??1010?0001??1010?0000?? i?5时，M[3,5]=1 ，这时 1010??1010?0001??1010?0000??
所以t (R)={<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>} 。
对称性：?a?bi?C,c?di?C且?a?bi,c?di??R,ac?0
**?ca?0,??c?di,a?bi??R。
*?a?bi?C(a?0),aa?0??a?bi,a?bi??R 自反性：
传递性：若?a?bi?C,*c?di?C*,e?fi?C*
当?a?bi,c?di??R且?c?di,e?fi??R则ac?0,ce?0,?acce?0即ae?0所以R是C*上等价关系。
R两等价类：?1?{z|z?a?bi,a?0}右半平面；
??a?bi,e?fi??R
?2?{z|z?a?bi,a?0}左半平面。
五、计算 15%
1、（4分）R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 。 2、（5分）Z/R={[0]，[1]，?，[k-1]} ，所以R秩为k。
3、（6分）{3，4，5}：上界：1，3；上确界：3；下界：无；下确界：无；
{1，2，3}：上界：1；上确界：1；下界：4；下确界：4。
六、证明 20%
1、（10分）证明：?b?B，由于g是入射，所以存在唯一c?C使g(b)?c，又g?f满射，对上述c存在a?A，使得g?f(a)?c，也即g(f(a))?c，由g单射，所以f(a)?b即：?b?B均存在a?A使得f(a)?b，所以f满射。
2、（10分）证明：
??x,y??g则x?domg且y?rangeg?x?domf且y?rangeg对上述x?domf则?|y??rangef即?x,y???f而f?g??x,y???g但?x,y??g由g是函数知y??y?x?domf且y?rangef即?x,y??f?f?g