第二题,我能解出a分别是-3和6,但不知道大于小于号怎么取,谁能教教我?&
百人會姿态15
a小于-3 a大于6
我知道答案，但不明白为什么这么取
大于取两边小于取中间
为您推荐：
其他类似问题
扫描下载二维码[离散数学试题]离散数学试题及答案_离散数学试题-牛宝宝文章网
[离散数学试题]离散数学试题及答案 离散数学试题
离散数学试题及答案离散数学试题与答案试卷一一、填空
20% （每小题2分）+1．设 A?{x|(x?N)且(x?5)},B?{x|x?E且x?7}（N：自然数集，E 正偶?数） 则 A?B?
。2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。3．设P，Q 的真值为0，R，S的真值为1，则?(P?(Q?(R??P)))?(R??S)的真值=
。4．公式(P?R)?(S?R)??P的主合取范式为。5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x)
在I下真值为
。6．设A={1，2，3，4}，A上关系图为则 R2 =
。7．设A={a，b，c，d}，其上偏序关系R的哈斯图为则 R=
。8．图的补图为
。9．设A={a，b，c，d} ，A上二元运算如下：那么代数系统&A，*&的幺元是
，它们的逆元分别为
。10．下图所示的偏序集中，是格的为
。二、选择 20% （每小题 2分）1、下列是真命题的有（
{a}?{{a}}；
B．{{?}}?{?,{?}}；C．
??{{?},?}；
D． {?}?{{?}}。2、下列集合中相等的有（
）A．{4，3}??；B．{?，3，4}；C．{4，?，3，3}；D． {3，4}。3、设A={1，2，3}，则A上的二元关系有（）个。A． 23 ；
C． 23?3；
D． 32?2。4、设R，S是集合A上的关系，则下列说法正确的是（
）A．若R，S 是自反的， 则R?S是自反的；B．若R，S 是反自反的， 则R?S是反自反的；C．若R，S 是对称的， 则R?S是对称的；D．若R，S 是传递的， 则R?S是传递的。5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下R?{?s,t?|s,t?p(A)?(|s|?|t|}则P（A）/ R=（
）A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{?}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（
）7、下列函数是双射的为（
）A．f : I?E ,
f (x) = 2x ；
B．f : N?N?N,
f (n) = &n , n+1& ；C．f : R?I ,
f (x) = [x] ；
D．f :I?N, f (x)
| x | 。（注：I―整数集，E―偶数集， N―自然数集，R―实数集）8、图 中 从v1到v3长度为3 的通路有（
）条。A． 0； B．
3。9、下图中既不是Eular图，也不是Hamilton图的图是（
）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（
）个4度结点。A．1； B．2； C．3； D．4 。三、证明 26%１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当& a, b& 和&a , c&在R中有&.b , c&在R中。（8分）２、f和g都是群&G1 ,★&到& G2, *&的同态映射，证明&C , ★&是&G1, ★&的一个子群。其中C={x|x?G1且f(x)?g(x)}
(8分)３、G=&V, E&
(|V| = v，|E|=e ) 是每一个面至少由k（k?3）条边围成的连通平面e?k(v?2)k?2图，则， 由此证明彼得森图（Peterson）图是非平面图。（11分）四、逻辑推演 16%用CP规则证明下题（每小题 8分）1、A?B?C?D,D?E?F?A?F2、?x(P(x)?Q(x))??xP(x)??xQ(x)五、计算 18%1、设集合A={a，b，c，d}上的关系R={&a , b & ,& b , a & ,& b, c & , & c , d &}用矩阵运算求出R的传递闭包t (R)。
（9分）2、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
（９分）试卷一答案：一、填空
20% （每小题2分）1、{0，1，2，3，4，6}； 2、(B?C)?A；3、1； 4、(?P?S?R)?(?P??S?R)； 5、1；6、{&1,1&, &1,3&, &2,2&, &2,4& }；7、{&a.b&,&a,c&,&a,d&,&b,d&,&c,d&} ? IA
；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2分）三、证明 26%1、 证：“?”
?a,b,c?X若&a,b&,&a,c&
? R由R对称性知&b,a&,&c,a?
? R，由R传递性得 &b,c& ? R“?” 若&a,b&
? R，&a,c&
? R有 &b,c& ? R 任意 a,b?X，因&a,a&
? R若&a,b&
? R 所以R是对称的。若&a,b&
? R，&b,c&
? R ??b,c??R ?
即R是传递的。 2、 证f(b?1?a,b?C)?f?1?1，g(b?1?1有)?g?1f(a)?g(a),f(b)?g(b)?1，?1又(b),(b)?f(b?1)?f?1(b)?g?1?1(b)?g(b)?f(a★b)?f(a)*f(b)?g(a)*g(b)?g(a★b)?a★b?1?C?& C , ★&
是 & G1 , ★&的子群。3、 证：r2e?①设G有r个面，则2?v?e?r?v?e?2ek即得e??d(F)?rkii?1，即r?2ek。而 v?e?r?2故k(v?2)k?2。（8分）e?k(v?2)k?2②彼得森图为k?5,e?15,v?10，这样不成立，所以彼得森图非平面图。（3分）二、 逻辑推演 16%1、 证明：①A
P（附加前提） ②A?B T①I ③A?B?C?D P④C?D T②③I ⑤D T④I ⑥D?E T⑤I ⑦D?E?F P⑧F T⑥⑦I ⑨A?F CP2、证明①?xP(x) P（附加前提） ②P(c) US① ③?x(P(x)?Q(x)) P④P(c)?Q(c) US③ ⑤Q(c) T②④I ⑥?xQ(x) UG⑤ ⑦?xP(x)??xQ(x) CP三、 计算 18%1、 解：??0100??MR??1010??1???R2?MR?MR?0??0001?M???0?0000??
， ??0??000??MR3?MR2?MR?0??1??0??0??1??0??0??0?1??0?0??0??0??1?0??0???1??1??0??0?110011001??1?1??0??，MR4?MR3?MRMt(R)?MR?MR2?MR3?MR4? t (R)={&a , a& , &a , b& , & a , c& , &a , d & , &b , a & , & b ,b & , & b , c . & ,& b , d & , & c , d & }2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。试卷二试题与答案一、填空 20% （每小题2分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为“虽然你努力了，但还是失败了”的翻译为
。 2、论域D={1，2}，指定谓词P则公式?x?yP(y,x)真值为
。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是
。3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=（列举法）。R的关系矩阵MR=。5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=
；A上既是对称的又是反对称的关系R=
。6、设代数系统&A，*&，其中A={a，b，c},则幺元是
；是否有幂等
；是否有对称性
。7、4阶群必是 群或
群。8、下面偏序格是分配格的是 。9、n个结点的无向完全图Kn的边数为
，欧拉图的充要条件是
。10、公式(P?(?P?Q))?((?P?Q)??R的根树表示为。二、选择 20% （每小题2分）1、在下述公式中是重言式为（
）A．(P?Q)?(P?Q)；B．(P?Q)?((P?Q)?(Q?P))；C．?(P?Q)?Q；
D．P?(P?Q)。2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（
），成真赋值的个数为（
）。A．0；
D．3 。S3、设S?{?,{1},{1,2}}，则 2 有（
）个元素。A．3；
D．8 。4、 设S?{ 1,
2, 3 }，定义S?S上的等价关系R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由
R产 生的S?S上一个划分共有（
）个分块。A．4；
D．9 。5、设S?{ 1,
2, 3 }，S上关系R的关系图为则R具有（
）性质。A．自反性、对称性、传递性；
B．反自反性、反对称性；C．反自反性、反对称性、传递性；
D．自反性 。6、设 ?,? 为普通加法和乘法，则（
）?S,?,??是域。A．S?{x|x?a?b3,C．S?{x|x?2n?1,a,b?Q}
B．S?{x|x?2n,a,b?Z} n?Z}
D．S?{x|x?Z?x?0}= N 。7、下面偏序集（
）能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有（
）条。A．1；
D．4 。9、在如下各图中（
）欧拉图。10、设R是实数集合，“?”为普通乘法，则代数系统&R ，×& 是（
）。A．群；
B．独异点；
C．半群 。三、证明 46%1、 设R是A上一个二元关系，S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）3、 若f:A?B是从A到B的函数，定义一个函数g:B?2对任意b?B有Ag(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2A的单射。（10分）4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）m?12(n?1)(n?2)?25、 设G是具有n个结点的无向简单图，其边数Hamilton图（8分），则G是四、计算 14%1、 设&Z6,+6&是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出&Z6,+6&的所有子群及其相应左陪集。（7分）2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷二答案： 一、 填空 20%（每小题2分）1、?P?Q；P?Q2、T
3、B31?B?{a4,a5,a6,a7,a8}4、R={&2,2&,&2,3&,&2,4&,&2,5&,&2,6&,&3,2&,&3,3&,&3,4&,&3,5&,&3,6&,&4,5&,&4,6&,&5,2&,&5,?11111???11111???00011????11111???3&,&5,4&,&5,5&,&5,6&}；?00000?
5、R={&1,2&,&1,3&,&2,1&}；R={&1,1&,&2,2&,&3,3&}
6、a ；否；有
7、Klein四元群；循环群 8、 B
9、12n(n?1)；图中无奇度结点且连通 10 、二、三、 证明 46%1、（9分）（1） S自反的?a?A，由R自反，?(?a,a??R)?(?a,a??R)，??a,a??S（2） S对称的 ?a,b?A?a,b??S?(?a,c??R)?(?c,b??R)?(?a,c??R)?(?c,b??R)??b,a??S（3） S传递的?S定义?R对称?R传递?a,b,c?A?a,b??S??b,c??S?(?a,d??R)?(?d,b??R)?(?b,e??R)?(?e,c??R)?(?a,b??R)?(?b,c??R)?R传递??a,c??S?S定义 由（1）、（2）、（3）得；S是等价关系。 2、11分证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述符号化为：前提：?x(P(x)?Q(x))、S(a)?P(a)
结论：?x(S(x)?Q(x))
??3分①S(a)?P(a) ②?x(P(x)?Q(x))P P③P(a)?Q(a) ④P(a) ⑤Q(a). ⑥S(a) ⑦S(a)?Q(a) ⑧?x(S(x)?Q(x) ３、１0分US② T①I
T③④I T①I T⑤⑥I EG⑦??11分证明 ：?b1,b2?B,(b1?b2)?f满射??a1,a2?A使f(a1)?b1,f(a2)?b2,且f(a1)?f(a2),由于f是函数,?a1?a2 又g(b1)?{x|(x?A)?(f(x)?b1)},g(b2)?{x|(x?A)?(f(x)?b2)}?a1?g(b1),a2?g(b2)但a1?g(b2),a2?g(b1)?g(b1)?g(b2)由b1,b2任意性知,g为单射。4、8分证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。5、8分证明： 证G中任何两结点之和不小于n。反证法：若存在两结点u，v 不相邻且d(u)?d(v)?n?1,令V1?{u,v}，则G-V1是具有n-2个结点的简单图，它的边数m?'m?'12(n?1)(n?2)?2?(n?1),可得12四、，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。所以G为Hamilton图.计算 14%1、 7分解：子群有&{[0]},+6&；&{[0],[3]},+6&；&{[0],[2],[4]},+6&；&{Z6},+6& {[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]} {[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]} {[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]} Z6的左陪集：Z6 。2、 7分(n?2)(n?3)?1试卷三试题与答案一、 填空 20% （每空 2分）f(x)?x?1,g(x)?2x， 1、 设 f，g是自然数集N上的函数?x?N,则f?g(x)?。2、 设A={a，b，c}，A上二元关系R={& a, a & , & a, b &,& a, c &, & c, c&}
,则s（R）=
。3、 A={1，2，3，4，5，6}，A上二元关系T?{?x,y?|x?y是素数}，则用列举法T=
；T的关系图为；T具有
性质。4、 集A合A?{{?,2},{2}}的幂集2= 。5、 P，Q真值为0 ；R，S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的真值为
。6、 wff?((P?Q)?R)?R的主合取范式为
。7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词wff?x(P(x)??y(O(y)?N(y,x)))的自然语言是。8、 谓词wff?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为。二、 选择 20% （每小题 2分）1、 下述命题公式中，是重言式的为（
）。A、(p?q)?(p?q)；
B、(p?q)?((p?q))?(q?p))；C、?(p?q)?q；
D、(p??p)?q。2、 wff?(p?q)?r的主析取范式中含极小项的个数为（
）。A 、2；
E、 8 。3、 给定推理①?x(F(x)?G(x))②F(y)?G(y)③?xF(x)④F(y)⑤G(y)⑥?xG(x)??x(F(x)?G(x))??xG(x) P US① P ES③ T②④I UG⑤推理过程中错在（
）。A、①-&②;
B、②-&③; C、③-&④; D、④-&⑤;
E、⑤-&⑥4、 设S1={1，2，?，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件X?S1且X?S3下X与（
）集合相等。A、 X=S2或S5 ；
B、X=S4或S5；C、X=S1，S2或S4；
D、X与S1，?，S5中任何集合都不等。5、 设R和S是P上的关系，P是所有人的集合，R?{?x,y?|x,y?P?x是y的父亲}，S?{?x,y?|x,y?P?x是y的母亲}则S?1?R表示关系 （
）。A、{?x,y?|x,y?P?x是y的丈夫}；B、{?x,y?|x,y?P?x是y的孙子或孙女}；C、 ?；
D、{?x,y?|x,y?P?x是y的祖父或祖母6、 下面函数（
）是单射而非满射。A、f:R?R,B、f:Z?}。 f(x)??x?2x?1； 2?R,f(x)?lnx；C、f:R?Z,D、f:R?R,f(x)?[x],[x]表示不大于x的最大整数f(x)?2x?1。++； 其中R为实数集，Z为整数集，R，Z分别表示正实数与正整数集。7、 设S={1，2，3}，R为S上的关系，其关系图为则R具有（
）的性质。A、 自反、对称、传递；
B、什么性质也没有；C、反自反、反对称、传递；
D、自反、对称、反对称、传递。8、 设S?{?,{1},{1,2}}，则有（
）?S。A、{{1,2}} ；B、{1,2 } ；
D、{2} 。9、 设A={1 ,2 ,3 }，则A上有（
）个二元关系。A、2
； C、210、全体小项合取式为（
）。A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。 3223； D、232。三、 用CP规则证明 16% （每小题 8分）?A?F 1、A?B?C?D,D?E?F2、?x(P(x)?Q(x))??xP(x)??xQ(x)四、（14%）集合X={&1,2&, &3,4&, &5,6&,? }，R={&&x1,y1&,&x2,y2&&|x1+y2 = x2+y1} 。1、 证明R是X上的等价关系。 （10分）2、 求出X关于R的商集。（4分）五、（10%）设集合A={ a ,b , c , d }上关系R={& a, b & , & b , a & , & b , c & , & c , d &}
要求 1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明f?g也是函数。2、（10分）设函数g:S?T入射函数。答案：五、 填空 20%（每空2分）1、2(x+1)；2、{?a ,a?,?a ,b?,?a ,c?,?c ,c?,?b ,a?,?c ,a?}；3、{?2,1?,?3,1?,?5,1?,?4,2?,?6,2?,?6,3??； f:T?S，证明 f:T?S有一左逆函数当且仅当f是4、反对称性、反自反性；4、{?,{{?,2}},{{2}},{{?,2},{2}}}；5、1；6、(P??Q?R)?(?P?Q?R)?(P?Q?R)；7、任意x，如果x是素数则?x?y?z?u(?P(x,z)??P(y,z)?Q(x,y,u))。存在一个y，y是奇数且y整除x ；8、六、 选择 20%（每小题 2分）七、 证明 16%(每小题8分)1、①A②A?B③A?B?C?D④C?D⑤D⑥D?E⑦D?E?F P（附加前提） T①I P T②③I T④I T⑤I P⑧F ⑨A?F
2、T⑥⑦I CP??xP(x)??xQ(x)??(?x)P(x)??xQ(x)本题可证?x(P(x)?Q(x))??(?xP(x)??xQ(x)① ?(?xP(x)) ②?x(?P(x)) ③?P(a)④?x(P(x)?Q(x)) ⑤P(a)?Q(a) ⑥Q(a) ⑦?xQ(x)⑧?(?xP(x)??xQ(x) 八、 14% （1）1、?2、证明：P（附加前提） T①E ES② P US④ T③⑤I EG⑥ CP自反性：??x,y??X,由于x?y?x?y ??x,y?,?x,y???R?R自反对称性：??x1,y1??X,??x2,y2??X当??x1,y1?,?x2,y2???R时 即x1?y2?x2?y1也即x2?y1?x1?y2 故??x2,y2?,?x1,y1???R?R有对称性??x3,y3??X3、传递性：??x1,y1??X,??x2,y2??X当??x1,y1?,?x2,y2???R且??x2,y2?,?x3,y3???R时?x1?y2?x2?y1即??x2?y3?x3?y2(1)?(2)(1)(2)x1?y2?x2?y3?x2?y1?x3?y2即x1?y3?x3?y1故??x1,y1?,?x3,y3???R?R有传递性由（1）（2）（3）知：R是X上的先等价关系。 2、X/R={[?1,2?]R}九、 10%?0??1??0??0?100001000??0?1??0??；
关系图 ?1??0??0??0?0??1?0??0??MR1、MR2?MR?MR2、MR3?MR2?MR?0??1??0??0??1??0??0??0?1??0?0??0?? 0??1??M?0?0???1??1??0??0?MR4?MR3?MRR21100MR5?MR3,MR6?MR4,?1100Mt(R)?MR?MR2?MR3?MR41??1?1??0??? t (R)={&a , a& , &a , b& , & a , c& , &a , d & , &b , a & , & b ,b & , & b , c . & , & b , d & , & c ,d & }。六、 20%f?g?{?x,y?|x?domf?x?domg?y?f(x)?y?g(x)}1、（1）?{?x,y?|x?domf?domg?y?f(x)?g(x)}令h?f?g?domf?g?domh?{x|x?domf?domg,f(x)?g(x)}（2）h?{?x,y?|x?domf?domg?y?h(x)?f(x)?g(x)}对x?domh若有y1,y2使得y2?h(x)?f(x)?g(x)y1?h(x)?f(x)?g(x),由于f(或g)是函数,有y1?y2即?x?domh有唯一y使得y?h(x) ?f?g也是函数。2、证明："?"若f有一左逆g,则对?t?Tg?f(t)?t故g?f是入射,所以f是入射。"?"f是入射,f:T?S定义如下:?|t?T,使f(t)?s令g(s)?c?Tt或c且若f(t)?s?s?f(T),由f入射,此时令g(s)?t,若s?f(T)则对?s?S,g(s)只有一个值则g?f(t)?g(s)?t,故g是f的左逆元。 即若f入射,必能构造函数g,使g为f左逆函数试卷四试题与答案一、 填空 10% （每小题 2分）1、 若P，Q，为二命题，P?Q真值为0 当且仅当
。2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，L(x,y):x?y则命题的逻辑谓词公式为
。3、 谓词合式公式?xP(x)??xQ(x)的前束范式为
。4、 将量词辖域中出现的
和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则被称为存在量词消去规则，记为ES。二、 选择 25% （每小题 2.5分）1、 下列语句是命题的有（
）。A、 明年中秋节的晚上是晴天；
B、x?y?0；C、xy?0当且仅当x和y都大于0； D、我正在说谎。2、 下列各命题中真值为真的命题有（
）。A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数；3、 下列符号串是合式公式的有（
）A、P?Q；B、P?P?Q；C、(?P?Q)?(P??Q)；D、?(P?Q)。4、 下列等价式成立的有（
）。A、P?Q??Q??P；B、P?(P?R)?R；C、 P?(P?Q)?Q；
D、P?(Q?R)?(P?Q)?R。5、 若A1,A2?An和B为wff，且A1?A2???An?B则（
）。A、称A1?A2???An为B的前件；
B、称B为A1,A2?An的有效结论C、当且仅当A1?A2???An?B?F；D、当且仅当A1?A2???An??B?F。6、 A，B为二合式公式，且A?B，则（
）。**A、A?B为重言式；
B、A?B；**C、A?B；
E、A?B为重言式。7、 “人总是要死的”谓词公式表示为（
）。（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。A、M(x)?Mortal(x)；
B、M(x)?Mortal(x)C、?x(M(x)?Mortal(x))；D、?x(M(x)?Mortal(x))8、 公式A??x(P(x)?Q(x))的解释I为：个体域D={2}，P(x)：x&3, Q(x)：x=4则A的真值为（
）。A、1；
C、可满足式；
D、无法判定。9、 下列等价关系正确的是（
）。A、?x(P(x)?Q(x))??xP(x)??xQ(x)；B、?x(P(x)?Q(x))??xP(x)??xQ(x)；C、?x(P(x)?Q)??xP(x)?Q；D、?x(P(x)?Q)??xP(x)?Q。10、 下列推理步骤错在（
）。①?x(F(x)?G(x))②F(y)?G(y)③?xF(x)④F(y)⑤G(y)⑥?xG(x) P US① P ES③ T②④I EG⑤A、②；B、④；C、⑤；D、⑥三、 逻辑判断30%1、 用等值演算法和真值表法判断公式A?((P?Q)?(Q?P))?(P?Q)的类型。（10分）2、 下列问题，若成立请证明，若不成立请举出反例：（10分）（1） 已知A?C?B?C，问A?B成立吗？ （2） 已知?A??B，问A?B成立吗？3、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）四、计算10%1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题(A1?(A2?(A3??A1)))?(A2??A4)的真值。（5分）2、 利用主析取范式，求公式?(P?Q)?Q?R的类型。（5分）五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域D={a , b , c}，求证：?xA(x)??xB(x)??x(A(x)?B(x))。 答案：十、 填空 10%（每小题2分）1、P真值为1，Q的真值为0；2、?x(F(x)?L(x,0)??y(F(y)?L(y,x))；3、?x(?P(x)?Q(x))；4、约束变元；5、?xA(x)?A(y)，y为D的某些元素。十一、 选择 25%（每小题2.5分）十二、 逻辑判断 30% 1、（1）等值演算法A?((P?Q)?(Q?P))?(P?Q)?(P?Q)?(P?Q)?T（2）真值表法所以2、（1）不成立。若取C?T则A?T?TB?T?T有A?C?B?C?T但A与B不一定等价，可为任意不等价的公式。 （2）成立。
证明：?A??B充要条件?A??B?TT?(?A??B)?(?B??A)?(A??B)?(B??A)即：?(?B?A)?(?A?B)?(A?B)?(B?A)?A?B 所以A?B?T故
A?B。3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提：P?(?(R?S)??Q),①P?(?(R?S)??Q) ②P③?(R?S)??Q ④?R ⑤?R??S ⑥?(R?S) ⑦?Q罢工不会停止是有效结论。 四、计算 10%P,?R
结论：?QP P T①②I P T④I T⑤E T③⑥I(1?(1?0?0)))?(1?1)?(1?(1?0)?1（1）解：?(1?0)?1?1?1?1?(P?Q)?Q?R??(?P?Q)?(Q?R)（2）?(P??Q)?(Q?R)?P??Q?Q?R?F它无成真赋值，所以为矛盾式。五、谓词逻辑推理 15%解：M(x):x是人;F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y?x(M(x)??y(F(y)?H(x,y)))
?x(M(x)??y(G(y)??H(x,y))) ??x(F(x)??G(x))证明：⑴?x(M(x)??y(F(y)?H(x,y))) ⑵M(a)??y(F(y)?H(a,y)) ⑶M(a)⑷?y(F(y)?H(a,y))⑸?x(M(x)??y(G(y)??H(x,y))) ⑹M(a)??y(G(y)??H(a,y)) ⑺?y(G(y)??H(a,y)) ⑻?y(H(a,y)??G(y)) ⑼F(z)?H(a,z) ⑽H(a,z)??G(z) ⑾F(z)??G(z) ⑿?x(F(x)??G(x))十三、?xA(x)??xB(x)?(A(a)?A(b)?A(c)?(B(a)?B(b)?B(c)?(A(a)?B(a))?(A(a)?B(b))?(A(a)?B(c))?(A(b)?B(a))?(A(b)?B(b))?(A(b)?B(c))?(A(c)?B(a))?(A(c)?B(b))?(A(c)?B(c))?(A(a)?B(a))?(A(b)?B(b))?(A(c)?B(c)P ES⑴ T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾证明10%??x(A(x)?B(x))试卷五试题与答案一、填空15%（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有
个5度结点。2、n阶完全图，Kn的点数X (Kn) =
。3、有向图中从v1到v2长度为2的通路有
条。4、设[R，+，?]是代数系统，如果①[R，+]是交换群 ②[R，?]是半群③
则称[R，+，?]为环。5、设[L,?,?]是代数系统，则[L,?,?]满足幂等律，即对?a?L有
。二、选择15%（每小题3分）1、 下面四组数能构成无向简单图的度数列的有（
）。A、（2，2，2，2，2）；
B、（1，1，2，2，3）；C、（1，1，2，2，2）；
D、（0，1，3，3，3）。2、 下图中是哈密顿图的为（
）。3、 如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（
B、假。4、 下列偏序集（
）能构成格。5、 设s?{1,12,2,13,3,14,4}，*为普通乘法，则[S，*]是（）。A、代数系统； B、半群； C、群；
D、都不是。三、证明 48%1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设[B,?,?,?,0,1]是布尔代数，定义运算*为a*b?(a?b)?(a?b)，求证[B，*]是阿贝尔群。四、计算22%1、在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T。（5分）2） 求T对应的二元前缀码。（5分）2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。答案：一、填空（15%）每空3 分1、 6；2、n；3、2；4、+对?分配且?对+分配均成立；5、a?a?a且a?a?a。二、选择（15%）每小题3分三、证明（48%）1、（10分）证明：用n个顶点v1，?，vn表示n个人，构成顶点集V={v1，?，vn}，设E?{uv|u,v?V,且u,v是朋友（u?v）}，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2） 若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，?，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8由图论基本定理知：?每个面用3条边围成。4（10分） 证：设循环群[A，?]的生成元为a，同态映射为f，同态像为[f（A），*]，于是?a,anmdeg(F)?2?m?24，而deg(Fi)?3，所以必有deg(Fi)?3，即?A都有f(a?a)?f(a)*f(a) nmnm对n=1有f(a)?f(a)n=2,
有f(a)?f(a?a)?f(a)*f(a)?(f(a))若n=k-1时
有f(akk?122)?(f(a))k?1k?1 k?1对n=k时，f(a)?f(a?a)?f(a)*f(a)?(f(a))nk?1*f(a)?(f(a)) k这表明，f(A)中每一个元素均可表示为(f(a))，所以[f(A),*]为f(a) 生成的循环群。5、证：（1） 交换律：?a,b?B有 a*b?(a?b)?(a?b)?(b?)?(b?a)?b*a（2） 结合律：?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?b?a?b?b)?c?a?b??a?b??b?a?c??b?c?a?b?c?a?b???b???b?c 而：a*(b*c)?a*((b?c)?(b?c))?(a?(b?c)?(b?c))?((a?(b?c)?(b?c))?a?(b?c)?(b?)??b???b?c?a?b?c?a?b???b???b?c ?(a*b)*c?a*(b*c)（3） 幺：?a?B有a*0?(a?0)?(a?0)?a?0?a0*a?(0?a)?(0?a)?0?a?a?0是[B，*]幺元。（4） 逆：?a?B
a*a?(a?a)?(a?a)?0?0?0?a是a的逆元。综上所述：[B，*]是阿贝尔群。四、计算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉树为：（2）（5分）最佳前缀码为：000，001，01，10，112、（12分）图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF复制道路EG、GF，得图G，则G是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：‘‘35+8+20+20+8+40+30+50+19+6+12+10+23=281。试卷六试题与答案一、 填空 15% （每小题 3分）1、 n阶完全图结点v的度数d(v) =
。2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则N k =
。3、 算式 ((a?(b*c)*d)?(e*f)的二叉树表示为。4、 如图给出格L，则e的补元是。5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，是
。二、选择 15% （每小题 3分）1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（
）。A、群；B、环；C、域；D、格。2、设[{a , b , c}，*]为代数系统，*运算如下：则零元为（
）。A、a；
D、没有。则幺元3、如右图相对于完全图K5的补图为（
）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（
）4度结点。A、1；
D、4。5、设[A，+，?]是代数系统，其中+，?为普通加法和乘法，则A=（
）时，[A，+，?]是整环。A、{x|x?2n,n?Z}；
B、{x|x?2n?1,n?Z}；4C、{x|x?0,且x?Z}；
D、{x|x?a?b5,a,b?R}。三、证明 50%n21、设G是（n,m）简单二部图，则m?4。（10分）12(n?1)(n?2)2、设G为具有n个结点的简单图，且m?，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，?]的加法运算和乘法运算。如下：（144、 [L,?,?]是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）四、10%设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数[{0,1},?,?,?]上的一个布尔表达式，试写出E(x1,x2,x3)的析取范式和合取范式（10分）五、10%如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答案：一、填空 15%（每小题3分）1、n-1；2、n(k+1)-2m；3、如右图；4、0 ；5、臂力小者 二、选择 15%（每小题 3分）三、证明 50% （1）证：设G=（V，E）V?X?Y,X?n121,Y?n2n2,n1?n2?n)?2对完全二部图有n1?nm?n1?n2?n1(n?n1)??n?n1n??(n1?n2n24当2时，完全二部图(n,m)的边数m有最大值4故对任意简单二部图(n,m)有（2）m?n24。证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然n1?n2?n?n1?1n2?1?n1?n?1n2?n?1?m?n1(n1?1)2?n2(n2?1)2?(n?1)(n1?n2?2)2?(n?1)(n?2)2与假设矛盾。所以G连通。（3） （1）[{0，1}，+，?]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0
??结合律成立。幺：幺元为0。 逆：0，1逆元均为其本身。②[{0，1}，?]是半群乘：由“? ”运算表知封闭群： （0?0）?0=0?（0?0）=0 ；（0?0）?1=0?（0?1）= 0；（0?1）?0=0?（1?0）=0 ； （0?1）?1=0?（1?1）=0；（1?1）?1=1?（1?1）=0 。③?对+的分配律
?x,y?{0,1}Ⅰ
0?（x+y）=0=0+0=(0?x)+(0?y)；Ⅱ
1?（x+y）当x=y
则?0?0??(1?0)?(1?0)?1?(x?y)?1?0?0???????(1?x)?(1?y)?1?1??(1?1)?(1?1)?；当x?y（x?y?1）则?1?0??(1?1)?(1?0)?1?(x?y)?1?1?1???????(1?x)?(1?y)0?1(1?0)?(1?1)????所以?x,y,z?{0,1}均有z?(x?y)?(z?x)?(z?y)同理可证：(x?y)?z?(x?z)?(y?z)所以?对+ 是可分配的。由①②③得，[{0，1}，+，?]是环。（2）[{0，1}，+，?]是域因为[{0，1}，+，?]是有限环，故只需证明是整环即可。①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1?1=1≠0因此[{0，1}，+，?]是整环，故它是域。4、证：（1 ）“≤”是偏序关系，
≤ 自然偏序
?a,b?L①反自反性：由代数格幂等关系：a?a?a?a?a。 ②反对称性：?a,b?L
即：a?b?a,则
a?a?b?b?a?b
b?a ③传递性：a?b,b?c则： a?c?(a?b)?ca?b即a?b?ab?a?b， a?b?a?a?(b?c)
结合律?a?b
b?c即b?c?b?a
a?b即a?b?a?a?c（2）?x,y?L在L中存在{x,y}的下（上）确界设x,y?L则：x?y?inf{x,y}事实上：x?(x?y)?(x?x)?y?x?y ?x?y?x同理可证:x?y?y若{x , y }有另一下界c，则c?(x?y)?(c?x)?y?c?y?c?c?x?y
?x?y是{x , y }最大下界，即x?y?inf{x,y}同理可证上确界情况。 四、14% 解：函数表为：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?2?x3)?(x1?x2?x3)?(x1?x2?x3)五、10%解： 用库斯克（Kruskal）算法求产生的最优树。算法为：w(v1,v7)?1w(v7,v2)?4w(v7,v3)?9w(v3,v4)?3w(v4,v5)?17w(v1,v6)?23选e1?v1v7选e2?v7v2选e3?v7v3选e?v3v4选e?v4v5选e?v1v6结果如图：树权C(T)=23+1+4+9+3+17=57（万元）即为总造价 试卷七试题与答案一、填空 15% （每小题 3分）1. 任何(n,m) 图G = (V,E) , 边与顶点数的关系是
。 2. 当n为
时,非平凡无向完全图Kn是欧拉图。 3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有
个1度顶点。4. n阶完全图Kn的点色数X(KN)=
。5. 一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是
。二、 选择 15% （每小题 3分）1、下面四组数能构成无向图的度数列的有(
A、 2,3,4,5,6,7；
B、 1,2,2,3,4；
C、 2,1,1,1,2；
D、 3,3,5,6,0。2、图
的邻接矩阵为(
?1??0?1??A、?1011000000??1??1??1?11????0?；B、??1111??0??111??0?1111????111?；C、??1101001000??0??1??0?11????0?；D、??1111000000??1?1??0??。3、下列几个图是简单图的有(
)。A. G1=(V1,E1), 其中 V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；B. G2=(V2,E2)其中V2=V1,E2={&a,b&,&b,c&,&c,a&,&a,d&,&d,a&,&d,e&}； C. G=(V3,E3), 其中V3=V1,E3={ab,be,ed,cc}；D. G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。4、下列图中是欧拉图的有(
)。5、G?(2,?)，其中S?{1,2,3}，?为集合对称差运算，则方程{1,2}?x?{1,3}的解为（
）。A、{2,3}；
B、{1,2,3}；
C、{1,3}；
D、?。S三、 证明 34%1、 证明：在至少有2 个人的人群中，至少有2 个人，他的有相同的朋友数。（8分） 2、 若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、 证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分） 4、 证明循环群的同态像必是循环群。（10分）四、 中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1点。五、 根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。六、 10%设B4={e , a , b , ab }，运算*如下表，则&B4,*&是一个群（称作Klein四元群 答案：十四、 填空 15%（每小题3分）1、v?V?d(v)?2m；2、奇数；3、5；4、n；5、臂力小者
十五、 选择 15%（每小题 3分）十六、 证明 34%1、（10分）证明：用n个顶点v1，?，vn表示n个人，构成顶点集V={v1，?，vn}，设E?{uv|u,v?V,且u,v是朋友（u?v）}，无向图G=（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2） 若G中有一个孤立点，则G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中顶点数到值只能是1，2，?，n-1这n-1个数，因而取n-1个值的n个顶点的度数至少有两个结点度数是相同的。2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。3、（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8 由图论基本定理知：?deg(F)?2?m?24Fi)?3，所以必有，而deg(deg(Fi)?3，即每个面用3条边围成。4、（10分） 证：设循环群[A，?]的生成元为a，同态映射为f，同态像为&f（A），*&，于是?a,anm?A都有f(a?a)?f(a)*f(a)nmnm对n=1有f(a)?f(a)n=2,
有f(a)?f(a?a)?f(a)*f(a)?(f(a)) 若n=k-1时
有f(akk?122)?(f(a))k?1k?1k?1对n=k时，f(a)?f(a?a)?f(a)*f(a)?(f(a))nk?1*f(a)?(f(a))k这表明，f(A)中每一个元素均可表示为(f(a))，所以&f(A),*&是以f(a) 生成元的循环群。十七、 中国邮递员问题 14%解：图中有4个奇数结点，d(v1)?3,
,d(v5)?5 （1） 求v1,v2,v3,v5任两结点的最短路d(v1v2)?3,
,d(v1v5)?4,
d(v2v3)?2,
d(v3v5)?4p1?v1v2,
p2?v1v2v3,
p3?v1v7v5,
p5?v2v6v5,
p6?v3v7v5再找两条道路使得它们没有相同的起点和终点，且长度总和最短：p3?v1v7v5,
p4?v2v3,‘‘（2） 在原图中复制出p3,
p4，设图G，则图G中每个结点度数均为偶数的图G存在欧拉回路C?v1v7v3v2v4v5v6v2v7v5v.3v2v1v7v5v1，欧拉‘回路C权长为43。十八、 根树的应用13%解：用100乘各频率并由小到大排列得权数w1?5,w2?5,w3?5,w4?10,w5?10,w6?15,w7?20,w8?30（1） 用Huffman算法求最优二叉树：（2） 前缀码用 00000传送 5；00001传送 6；0001传送 7；100传送 3；101传送 4；001传送 2；11传送 1；01传送 0 （频率越高传送的前缀码越短）。十九、证明：（1） 乘：由运算表可知运算*是封闭的。（2） 群：即要证明(x*y)*z?x*(y*z)，这里有43=64个等式需要验证但：①
e是幺元，含e的等式一定成立。②ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。 ③剩下只需验证含a、b等式，共有23=8个等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b；
(a*b)*b=ab*b=a=a*(b*b)=a*e=a；(a*a)*a=e*a=a=a*(a*a)=a*e=a ；
(a*a)*b=e*b=b=a*(a*b)=a*ab=b；(b*b)*a=e*a=a=b*(b*a)=b*ab=a；
(b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b ；
(b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。（3） 幺： e为幺元（4） 逆：e -1=e ；a -1=a ；b -1=b ； (ab) -1=ab 。所以&B4,*&为群。试卷八试题与答案 10%一、 填空 15% （每小题 3分）1、 n阶完全图Kn的边数为
。2、 右图
的邻接矩A=
。4、 完全二叉树中，叶数为nt，则边数m=
。5、 设& {a,b,c}, * &为代数系统，* 运算如下：；a、b、c的逆元分别为
。二、 选择 15% （每小题 3分）1、 图
相对于完全图的补图为（
）。阵图2、 对图G
则k(G),?(G),?(G)分别为（
）。A、2、2、2；
B、1、1、2；
C、2、1、2；
D、1、2、2 。3、 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（
）片树叶。A、3；
D、64、 设&A，+，?&是代数系统，其中+，?为普通的加法和乘法，则A=（
）时&A，+，?&是整环。A、{x|x?2n,n?Z}；
B、{x|x?2n?1,n?Z}；C、{x|x?0,且x?Z}；
D、{x|x?a?b5,a,b?R}。5、 设A={1，2，?，10 }，则下面定义的运算*关于A封闭的有（
）。A、 x*y=max(x ,y)；
B、x*y=质数p的个数使得x?p?y；C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公约数)；D、x*y=lcm(x ,y)
（lcm(x ,y) 表示x和y的最小公倍数）。三、 证明 45%m?n21、设G是（n,m）简单二部图，则4。（8分）12(n?1)(n?2)2、设G为具有n个结点的简单图，且m?则G是连通图。（8分）3、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，?]的加法运算和乘法运算。如下：证明它是一个环，并且是一个域。（15分）四、 生成树及应用 10%1、（10分）如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY
YEAR的编码信息。五、 5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。答案：二十、 填空 15%（每小题3分）?0??0?01?n(n?1)?1、2；2、?0101101011??1?0??0??；3、；4、2(nt?1)；5、a，c，a、b、没有二十一、 选择 15%（每小题 3分）二十二、 证明 45%1、 （8分）：设G=（V，E），V?X?Y,X?n121,Y?n2n2)?2,则n1?n2?n n2对完全二部图有n1?nm?n1?n2?n1(n?n1)??n?n1n??(n1?n24当2时，完全二部图(n,m)的边数m有最大值4。故对任意简单二部图(n,m)有m?n24。2、 （8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然n1?n2?n。?n1?1n2?1?n1?n?1n2?n?1?m?n1(n1?1)2?n2(n2?1)2?(n?1)(n1?n2?2)2?(n?1)(n?2)2与假设矛盾。所以G连通。m?'11?1023、（14分）（1）当n=11时，G?G?K11K11边数?55条，因而必有G或G的边数大于等于28，不妨设G的边数m?28，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则kkmi?ni?1,i?1?k ,kki?ni?n?11,?mi?mi?1i?1?28?m??mi?1??(ni?1i?1)?n?k?11?k矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3 。于是Gm?gg?2(n?k?1)的每个面至少由g (g?3)条边围成，由点、边、面数的关系28?m?gg?2(11?k?1)?33?1，得：(11?(k?1))?3(11?(1?1))?3?11?3?2?27而 28?27矛盾，所以G为非平面图。（2）当n&11时，考虑G的具有11个顶点的子图G，则G或G必为非平面图。 如果G为非平面图，则G为非平面图。 如果G为非平面图，则G为非平面图。 4、 （15分）'''''1）[{0，1}，+，?]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1
；（0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0
??结合律成立。幺：幺元为0。 逆：0，1逆元均为其本身。所以，&{0，1}，+&是Abel群。②&{0，1}，?&是半群乘：由“? ”运算表知封闭群： (0?0)?0=0?（0?0）=0 ；（0?0）?1=0?（0?1）=1；（0?1）?0=0?（1?0）=1 ；（0?1）?1=0?（1?1）=0；（1?1）?1=1?（1?1）=0 ；?③?对+的分配律对?x,y?{0,1}Ⅰ
0?（x+y）=0=0+0=(0?x)+(0?y)Ⅱ
1?（x+y）当x=y
则?0?0??(1?0)?(1?0)?1?(x?y)?1?0?0???????(1?x)?(1?y)?1?1??(1?1)?(1?1)?当x?y（x?y?1）则?1?0??(1?1)?(1?0)?1?(x?y)?1?1?1???????(1?x)?(1?y)?0?1??(1?0)?(1?1)?所以?x,y,z?{0,1}均有z?(x?y)?(z?x)?(z?y)同理可证：(x?y)?z?(x?z)?(y?z)所以?对+ 是可分配的。由①②③得，&{0，1}，+，?&是环。（2）&{0，1}，+，?&是域因为&{0，1}，+，?&是有限环，故只需证明是整环即可。①乘交环： 由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1?1=1≠0因此[{0，1}，+，?]是整环，故它是域。二十三、树的应用 20%1、（10分）解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价 五、（10分）由二叉树知H、A、P、Y、N、E、W、R对应的编码分别为000、001、010、011、100、101、110、111。显然{000，001，010，011，100，101，110，111}为前缀码。 英文短语HAPPY NEW YEAR 的编码信息为 000 001 010 010 011 100 101 001 001 101 001 111六、5%试卷九试题与答案一、 填空 30% （每空 3分）1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A=
。2、 集合A={?,{?}}的幂集P(A) =
。3、 设A={1，2，3，4}，A上二元关系R={&1，2&，&2，1&，&2，3&，&3，4&}画出R的关系图。4、 设A={&1,2&,&2 , 4 &,&3 , 3 &} , B={&1,3&,&2,4&,&4,2&},则A?B=
。5、 设|A|=3，则A上有
个二元关系。6、 A={1，2，3}上关系R= 时，R既是对称的又是反对称的。7、 偏序集?A,R??的哈斯图为则，R?= 。8、 设|X|=n，|Y|=m则（1）从X到Y有
个不同的函数。（2）当n , m满足
时，存在双射有
个不同的双射。9、 2是有理数的真值为
。 10、自Q：我将去上海，R：我有时间，公式(Q?R)?(R?Q)的 然语言为
。 11、主公式(Q?P)?(?P?Q)的 合取范式是
。 12、则若S?{S1 ,S2 ,?,
Sm}是集合A的一个分划， 它应满足
。二、 选择 20% （每小题 2分）1、 设全集为I，下列相等的集合是（
）。 A、A?{x|x是偶数或奇数}；
B、B?{x|? y(y?I?x?2y)}；C、C?{x|? y(y?I?x?2y?1)}；
D、D?{x|0,1,?1,2,?2,3,?3,4,?4,?}。 2、 设S={N，Q，R}，下列命题正确的是（
）。 A、2?N,N?S
B、N?Q,Q?S
则N?S； C、N?Q,Q?R
D、??N,??S
则??N?S。 3、 设C={{a},{b},{a,b}}，则S?C?S与?SS?C分别为（
）。A、C和{a,b}；B、{a,b}与?；C、{a,b}与{a,b}；D、C与C 4、 下列语句不是命题的有（
）。A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； D、太阳系以外的星球上有生物；
E、你打算考硕士研究生吗？ 5、 (P?Q)?R的合取范式为（
）。A、(P??Q)?R
；B、(P?R)?(?Q?R)
； C、(P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R)D、(P?Q?R)?(P??Q?R)?(P??Q?R)?(?P??Q?R)。6、 设|A|=n，则A上有（）二元关系。A、2n ；
D、nn ； E、2nn。7、 设r为集合A上的相容关系，其简化关系图（如图）， 则 [I]
r产生的最大相容类为（
）；A、{x1,x2}； B、{x1,x2,x3}； C、{x4,x5}； D、{x2,x4,x5}[II] A的完全覆盖为（
）。A、{x1,x2,x3,x4,x5}；
B、{{x1,x2},{x1,x2,x3},{x4,x5}}； C、{{x1,x2,x3},{x2,x4,x5}}； D、{{x1,x2},{x3},{x4,x5}}。 8、 集合A={1，2，3，4}上的偏序关系图为则它的哈斯图为（
）。9、 下列关系中能构成函数的是（
）。A、{?x,y?|(x,y?N)?(x?y?10)}；B、{?x,y?|(x,y?R)?(y?x)}；C、{?x,y?|(x,y?R)?(y22?x)}；{?x,y?|(x,y?I)?(x?ymod3)}。
D、10、N是自然数集，定义f:N?N,
mod3（即x除以3的余数），则f是（
）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、 简答题 15%1、(10分)设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“?”为S上整除关系，问：（1）偏序集?S　,??,?}的极小元、最小元、极大元、最大元是什么? 的Hass图如何？（2）偏序集{S　2、（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数f(x,y)?x?y，特定谓词F(x,y):x?y，问公式A??x?y?z(F(x,y)?F(f(x,z),f(y,z))的涵义如何？真值如何？四、 逻辑推理 10%或者逻辑难学，或者有少数学生不喜欢它；如果数学容易学，那么逻辑并不难学。因此，如果许多学生喜欢逻辑，那么数学并不难学。五、10%设X={1,2,3,4,5}，X上的关系R={&1,1& , & 1 , 2 & , &2 , 4 & , & 3 , 5 & , & 4 , 2 & }，用Warshall方法，求R的传递闭包t (R)。六、证明 15%1、 每一有限全序集必是良序集。（7分）2、 设g?f是复合函数，如果g?f满射，则g也是满射。（8分） 答案二十四、1、2、3、见右图；填空 20%（每小题2分）；；4、{& 1 , 2 & , & 2 , 4 & , &3 , 3 & , & 1，3 &，&2,4& ,&4,2&}、{& 1 , 4 & , & 2 ,2 & }；5、29；
6、{& 1 , 1 & , & 2 , 2 & , &3 , 3 & ；7、{&a,b&,&a,d&,&a,e&,&b,d&,&b,e&,&a,c&,&a,f&,&a,g&,&c,f&,&c,g&}8、mn 、n=m、n!；9、假；10、我将去上海当且仅当我有空； 11、；；12、二十五、 选择 20%（每小题 2分）。二十六、 简答题 15% 1、（10分） （1）≤={&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&}covS={&1,2&,&1,3&,&2,4&,&2,6&,&3,6&,&4,8&,&4,12&,&6,12& ,&8,24&,&12,24&} Hass图为2、（5分）
（2）极小元、最小元是1，极大元、最大元是 24。解：公式A涵义为：对任意的实数x,y,z，如果x&y
(x-z) & (y-z)
A的真值为： 真（T）。二十七、 逻辑推理 10%解：设P：逻辑难学；Q：有少数学生不喜欢逻辑学；R：数学容易学 符号化：证：①②③④⑤二十八、 （10分）
P T①E P T②③I T④E解：1时， [1,1]=1, A =2时，A[1,2]=A[4,2]=1A=3时，A的第三列全为0，故A不变4时A[1,4]=A[2,4]=A[4,4]=1A=5时，A的第五行全为0，故A不变。所以t (R)={&1,1&, &1,2&,&1,4&,&2,2&,&2,4&,&3,5&,&4,2&,&4,4&}。二十九、 证明 15%1、（7分）证明：设若，全序集。 ，在B中不存在最小元素，由是全序集。不是良序集，那么必有一子集于B是一有限集合，故一定可找出两元素x ,y是无关的，由于所以x ,y必有关系，矛盾。故2、（8分）证明：设射，故必有使得， 由于必是良序集。 满使得，，由复合函数定义知，存在，必使又因为g是函数，必对任，任每个z在g作用下都是Y中元素的一个映象，由Z的任意性，所以g是满射。试卷十试题与答案一、 填空 10% （每小题 2分）P?Q真值为1，1、 若P，Q为二命题，当且仅当
。2、 对公式(?yP(x,y)??zQ(x,z))??xR(x,y)中自由变元进行代入的公为
。3、 ?xF(x)??(?xG(x))的前束范式式为
。4、 设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，则被称为全称量词消去规则，记为US。5、 与非门的逻辑网络为。二、 选择 30% （每小题 3分）1、 下列各符号串，不是合式公式的有（
）。A、(P?Q)??R；
B、((P?Q)?(R?S)；C、P?Q??R；
D、(?(P?Q)?R)?S。2、 下列语句是命题的有（
）。A、2是素数；B、x+5 & 6；C、地球外的星球上也有人；D、这朵花多好看呀！。3、 下列公式是重言式的有（
）。A、?(P?Q)；B、(P?Q)?Q；C、?(Q?P)?P；D、(P?Q)?P4、 下列问题成立的有（
）。A、 若A?C?B?C，则A?B； B、若A?C?B?C，则A?B；C、若?A??B，则A?B；
D、若A?B，则?A??B。5、 命题逻辑演绎的CP规则为（
）。A、 在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为B?C形式，那么将B作为前提，设法演绎出C；D、设?(A)是含公式A的命题公式，B?A，则可用B替换?(A)中的A。6、 命题“有的人喜欢所有的花”的逻辑符号化为（
）。设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢yA、?x(M(x)??y(F(y)?H(x,y)))；B、?x(M(x)??y(F(y)?H(x,y)))；C、?x(M(x)??y(F(y)?H(x,y)))；D、?x(M(x)??y(F(y)?H(x,y)))。7、 公式?x?y(P(x,y)?Q(y,z))??xP(x,y)换名（
）。A、?x?u(P(x,u)?Q(u,z))??xP(x,y)；B、?x?y(P(x,u)?Q(u,z))??xP(x,u)；C、?x?y(P(x,y)?Q(y,z))??xP(x,u)；D、?u?y(P(u,y)?Q(y,z))??uP(u,y)。8、 给定公式?xP(x)??xP(x)，当D={a,b}时，解释（
）使该公式真值为0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=19、 下面蕴涵关系成立的是（
）。A、?xP(x)??xQ(x)??x(P(x)?Q(x))；B、?xP(x)??xQ(x)??x(P(x)?Q(x))；C、?xP(x)??xQ(x)??x(P(x)?Q(x))；D、?x?yA(x,y)??y?xA(x,y)。10、下列推理步骤错在（
）。①?y?yF(x,y)②?yF(z,y)③F(z,c)④?xF(x,c)⑤?y?xF(x,y) P US① ES② UG③ EG④A、①→②；B、②→③；C、③→④；D、④→⑤。三、 逻辑判断 28%1、（8分）下列命题相容吗？A?B,
A2、（10分）用范式方法判断公式 (P?Q)?(P?R),P?Q?R 是否等价。3、（10分）下列前提下结论是否有效？今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。四、 计算 12%1、（5分）给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：(Q?R)?(P??R)的真值。2、（7分）给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式?y?xL(x,y)的真值。五、 逻辑推理20%1、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。2、（10分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。答案三十、 填空 15%（每小题3分）?x(F(x)??G(x))；1、P，Q的真值相同；2、(?yP(u,y)??zQ(u,z))??xR(x,v)；3、4、?xA(x)?A(y)；5、三十一、 选择 30%（每小题 3分）。
三十二、 逻辑判断 28%1、（8分）①A?B②A③B④?(B?C)⑤?B??C⑥?B⑦F P P T①②I P T④E T⑤I T③⑥I所以A?B,
A不相容。2、（10分）(P?Q)?(P?R)?(?P?Q)?(?P?R)?((?P?Q)?(R??R))?((?P?R)?(Q??Q))?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?M100?M101?M110P?Q?R??P?(Q?R)?(?P?Q)?(?P?R)?((?P?Q)?(R??R))?((?P?R)?(Q??Q))?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(?P?Q?R)?(?P?Q??R)?(?P?Q?R)?M100?M101?M110所以两式等价。3、设P：今天天晴，Q：今天下雨，R：我不看书，S：我看电影符号化为：P?Q ,
P?S,S?R??R?Q①P?S②S?R③P?R④?R??P⑤P?Q⑥?P?Q⑦?R?Q结论有效。三十三、 计算 12% P P T①②I T③I P T⑤E T④⑥I1、（5分）解：P，Q是真命题，R是假命题。(Q?R)?(P??R)?(1?0)?(1?1)?0?1?02、（7分）?y?xL(x,y)??y(L(2,y)?L(3,y))?(L(2,2)?L(3,2))?(L(2,3)?L(3,3))?(1?0)?(0?1)?0?0?0三十四、1、（10分）解：设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数符号化：前提：?x(Q(x)?R(x))，?x(Q(x)?I(x))结论：?x(R(x)?I(x)) ①?x(Q(x)?I(x))②Q(c)?I(c)③?x(Q(x)?R(x))④Q(c)?R(c)⑤Q(c)⑥R(c)⑦I(c)⑧R(c)?I(c)⑨?x(R(x)?I(x)) P ES① P US③ T②I T④⑤I T②I T⑥⑦I EG⑧ 逻辑推理 20%2、解：F(x)：x是病人，G(x)：x是医生，H(x)：x是骗子，L(x,y)：x相信y符号化：前提：?x(F(x)??y(G(y)?L(x,y)))?x(F(x)??y(H(y)??L(x,y)))结论：?x(G(x)??H(x)) ⑴?x(F(x)??y(G(y)?L(x,y))) ⑵F(a)??y(G(y)?L(a,y)) ⑶F(a)⑷?y(G(y)?L(a,y))⑸?x(F(x)??y(H(y)??L(x,y))) ⑹F(a)??y(H(y)??L(a,y)) ⑺?y(H(y)??L(a,y)) ⑻?y(L(a,y)??H(y)) ⑼G(z)?L(a,z) ⑽L(a,z)??H(z) ⑾G(z)?H(z) ⑿?x(G(x)??H(x)) 卷十一试题与答案P ES⑴ T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾一、 填空 20% （每小题 2分）1、
称为命题。 2、命题P→Q的真值为0，当且仅当
。 3、一个命题含有4个原子命题，则对其所有可能赋值有
种。 4、所有小项的析取式为
。 5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y. 则?x(E(x)??y(D(x,y)?E(y)))的汉语翻译为。6、设S={a，b,
则S6的集合表示为
。 7、P（P(?)）=
。 8A?B、=。9、设R为集合A上的关系，则t（R）=
。10、若R 是集合A上的偏序关系，则R满足
。二、 选择 20% （每小题 2分）1、 下列命题正确的有（
）。A、 若g,f是满射，则g?f是满射； B、若g?f是满射，则g,f都是满射；C、若g?f是单射，则g,f都是单射；D、若g?f单射，则f是单射。2、 设f，g是函数，当（
）时，f=g 。A、?x?domf
f(x)?g(x)；
B、domg?domf 且
f?g；C、f与g的表达式相同；
D、domg?domf,rangef?rangef。3、 下列关系，（
）能构成函数。A、f?{?x1,x2?|x1,x2?N且x1?x2?10}；B、f?{?x1,x2?|x1,x2?R,x1?x2}；C、f?{?x1,x2?|x1,x2?N,x2为小于x1的素数的个数D、f?{?x,x?|x?R}}； 2。4、 下列函数（
）满射；（
）单射；（
）；一般函数（
）。A、f:N?N,f(x)?x?2；
B、f:N?N,f(x)?x(mod3)（x除以3的余数）；f:N?{0,1},?1x?偶数集f(x)???0x?奇数集；D、f:R?R,2C、f(x)?2x?5。5、 集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（
）。6、 设集合A={1，2，3，4，5}上偏序关系的Hass图为则子集B={2，3，4}的最大元（
）；最小元（
）；极大元（
）；极小元（
）；上界（
）；上确界（
）；下界（
）；下确界（
）。A、 无，4，2、3，4，1，1，4，4；
B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4； D、无，4，2、3，4，1，1，4，无。7、 设R，S是集合A上的关系，则下列（
）断言是正确的。A、 R,S自反的，则R?S是自反的；B、若R,S对称的，则R?S是对称的；C、若R,S传递的，则R?S是传递的；D、若R,S反对称的，则R?S是反对称的8、 设X为集合，|X|=n，在X上有（
）种不同的关系。A、n2；
D、2n2。9、 下列推导错在（
）。①?x?y(x?y)②?y(z?y)③(z?Cz)④?x(x?x) P US① ES② UG③A、②；
D、无。10、“没有不犯错误的人”的逻辑符号化为（
）。设H（x）：x是人，
P（x）：x犯错误。A、?x(H(x)?P(x))；
B、?(?x(H(x)??P(x)))；C、?(?x(H(x)??P(x)))； D、?x(H(x)?P(x))。三、 命题演绎28%1、（10分）用反证法证明(P?Q)?(P?R)?(Q?S)?S?R。2、（8分）用CP规则证明P?(Q?R),R?(Q?S)?P?(Q?S)。3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。四、 8%将wff?x(?(?yP(x,y))?(?zQ(z)?R(x)))化为与其等价的前束范式。五、8%A={a,b,c,d}，R={&a,b&,&b,c&,&b,d&,&c,b&}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。六、证明16%1、 （8分）设A={1，2，3，4}，在 P（A）上规定二元关系如下：R?{?s,t?|s,t? P（A）?(|s|?|t|)}证明R是P（A）上的等价关系并写出商集P（A）/R。2、 （8分）设f是A到A的满射，且f?f?f，证明f=IA 。答案一、 填空 20%（每小题2分）1、 能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式；5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；7、；8、；9、；10、自反性、反对称性、传递性二、选择 20%（每小题 2分）三、命题演绎 28%1、（10分）证明：⑴ P（附加前提）⑵ T⑴E⑶ P⑷ T⑶E⑸ P⑹ T⑷⑸E⑺ T⑹E⑻ T⑺I⑼ T⑵⑻I⑽ P⑾ T⑽E⑿ T⑾E⒀ T⑼⑿I2、（8分）① P（附加前提）② P③ T①②I④ P⑤ T③④I⑥ T⑤E⑦ CP3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数，前提：结论：⑴ P⑵ US⑴ C(x)：x是虚数。⑶ ⑷⑸⑹ ⑺ ⑻ ⑼ ⑽⑾⑿四、 8% 解：五、8%解：P US⑶P US⑸ T⑹E T⑵⑺I T⑷⑺IT⑻⑼I T⑽E UG⑾所以t（R）={&a,b&,&a,c&,&a,d&,&b,b&,&b,c&,&b,d&,&c,b&,&c,c&,&c,d&}关系图为六、证明16%1、（8分）证明：⑴⑵⑶ P（A），由于P（A），若P（A），若：，所以，则，即R自反的。 ，，即：，R是对称的。所以R是传递的。由⑴⑵⑶知，R是等价关系。P（A）/R = {[2、（8分） ]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}证明：因为f是满射，所以即所以卷十二试题与答案 ，又，存在使得
，又因为f是函数，所以，所以
由a的任意性知：f=IA
。五、 填空 20% （每空 2分）1、 设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x ≤ y = x|y , 则x?y=
。2、 设A?{x|x?2,n?N}，定义A上的二元运算为普通乘法、除法和加法，则代数系统&A,*&中运算*关于
运算具有封闭性。3、 设集合S={α，β，γ，δ，δ}，S上的运算*定义为 n则代数系统&S，*&中幺元是
，β左逆元是
， 无左逆元的元素是
。4、 在群坯、半群、独异点、群中
满足消去律。 5、 设&G,*&是由元素a?G生成的循环群，且|G|=n，则G =
。 6、 拉格朗日定理说明若&H , *&是群&G,*&的子群，则可建立G中的等价关系R=
。若|G|=n, |H|=m 则m和n关系为
。 7、 设f是由群&G,☆&到群&G?,*&的同态映射，e?是G?中的幺元，则f的同态核Ker(f )=
。六、 选择 20% （每小题 2分）1、设f是由群&G,☆&到群&G?,*&的同态映射，则ker (f)是（
）。A、G?的子群； B、G的子群 ； C、包含G?；
D、包含G。2、设 &A ，+ ，?&是环，?a,b?A，a?b的关于“+”的逆元是（
）。A、(-a)?(-b)； B、(-a)?b； C、a?(-b)； D、a?b 。3、设 &A ，+ ，?&是一代数系统且&A ，+ &是Abel群，如果还满足（
）&A ，+ ，?&是域。A、&A ，?&是独异点且?对+可分配；B、&A-{?} ，?&是独异点，无零因子且?对+可分配； C、&A-{?} ，?&是Abel群且无零因子 ； D、&A-{?} ，?&是Abel且?对+可分配。4、设&A ，+ ，?&是一代数系统，+、?为普通加法和乘法运算，当A为（
）时，&A ，+ ，?&是域。{x|x?a?b35,a,b均为有理数}；A、 {x|x?a?b5,a,b均为有理数} ；B、C、{x|x?ab,a,b?I?,且a?kb}
D、{x|x?0，x?I}。5、设&A, ?&是一个格，由格诱导的代数系统为?A
）成立。A、?A,?,??满足?对?的分配律；B、?a,b?A,a?b?a?b?b；C、 ?a,b,c?A,若a?b?a?c
则b?c ；D、?a,b?A,有a?(a?b)?b且
a?(a?b)?b。6、设&A, ?&是偏序集，“?”定义为：?a,b?A,a?b?a|b，则当A=（
）时，&A, ?&是格。A、{1,2,3,4,6,12}； B、{1,2,3,4,6,8,12,14}； C、{1,2,3,?，12}； D、{1,2,3,4}。7、设?A
,??是由格&A, ?&诱导的代数系统，若对?a,b,c?A，当b?a时，有（
）&A, ?&是模格。A、a?(b?c)?b?(a?c)；
B、c?(a?c)?a?(b?c)；C、a?(b?c)?b?(a?c)；
D、c?(a?c)?b?(a?c)。8、在（
）中，补元是唯一的。A、有界格； B、有补格；
C、分配格；
D、有补分配格。9、在布尔代数?A
,?,??中，b?c?0当且仅当（
）。A、b?c；
D、c?b。10、设?A
,?,??是布尔代数，f是从An到A的函数，则（
） 。A、 f是布尔代数； B、f能表示成析取范式，也能表示成合取范式；C、若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式；D、若f是布尔函数，它一定能表示成析（合）取范式。三、8%设A={1，2}，A上所有函数的集合记为AA, ?是函数的复合运算，试给出AA上运算?的运算表，并指出A中是否有幺元，哪些元素有逆元。 A四、证明42%1、 设&R,*&是一个代数系统，*是R上二元运算，?a,b?R是幺元且&R,*&是独异点。（8分）na*b?a?b?a?b，则02、 设&G,*&是n阶循环群，G=(a)，设b=ak，k?I?则 元素b的阶为d，这里d=GCD ( n ,k )。（10分）3、 证明如果f是由&A,☆&到&B,*&的同态映射，g是由&B,*&到&C,△&的同态映射，则g?f是由&A,☆&到&C,△&的同态映射。（6分）4、 设&A ，+ ，?&是一个含幺环，且任意a?A都有a?a=a，若|A|≥3则&A ，+ ，?&不可能是整环。（8分）5、 K={ 1, 2 , 5 , 10 , 11 , 22 , 55 ,110 }是110的所有整因子的集合，证明：具有全上界110?x?K,x??110x）。和全下界1的代数系统& K , LCM , GCD , @ &是一个布尔代数。（（10分）五、布尔表达式 10%设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x1?x3)是布尔代数?{0,1},?,?,的一个布尔表达式，试写出其析取范式和合取范式。（10分） 答案：?上一、填空 20%（每空2分）1、LCM（x,y）；2、乘法；3、α、δ，γ、δ；4、群；5、G?{a,a,?a2n?1，an?e}；?16、{?a,b?|a?G,b?G,a*b?H}、m/n；7、{x|x?G
f(x)?e?}三、8%解：因为|A|=2，所以A上共有2=4个不同函数。令A2A?{f1,f2,f3,f4}，其中：f1(1)?1,f(2)?2;f(1)?1,f(2)?1;f(1)?2,f(2)?2;f4(1)?2,f4(2)?1f1为AA中的幺元，f1和f4有逆元。四、证明 42%1、（8分）证明：[幺]
?a?R ，0*a?0?a?0?a?a,a*0?a?0?a?0即 0*a?a*0?a[群] ?a,b,c?R(a*b)*c?(a?b?a?b)*c?a?b?a?b?c?(a?b?a?b)?c?a?b?c?a?b?a?c?b?c?a?b?ca*(b*c)?a?b?c?a?b?a?c?b?c?a?b?c所以(a*b)*c?a*(b*c)?0为幺元 [乘] ?a,b?R，由于+，?在R封闭。所以a*b?a?b?a?b?R即*在R上封闭。因此 ， 〈R，*〉是独异点。2、（10分）证明：（1）?d?GCD(n,k),设n?d?n1,k?d?k1?e?ank1dn1k1kn1n ?an1e?a?b1 （2）若b的阶不为n1，则b阶m&n1，且有n1?l?makm(l?1)，则有bm?e，即?e,adk1?e，即adn1k1e?ank1e?e，?k1有因子l，这与d?GCD(n,k)矛盾。n由（1）、（2）知，元素b的阶为d3、（6分）?a,b?A,g?f(a☆b)?g(f(a☆b))?g(f(a)*f(b))?g(f(a))△g(f(b))?g?f(a)△g?f(b)所以g?f是由&A,☆&到&c,△&的同态映射。4、（8分）证明：反证法：如果&A ，+ ，?&是整环，且|A|≥3，则?a?A,a??,a?1且a?a?a即有a??,a?1??且a?(a?1)?a?a?a?a?a??，这与整环中无零因子矛盾。所以&A ，+ ，?&不可能是整环。5、（10分）（1） 代数系统&K , LCM , GCD, @& 是由格&K , | &诱导的，其Hasst图为Hass图中不存在与五元素格所以&K,|&格是分配格。 （2）?x?K,?x??100/x如:22??11022?5,和同构的子格。使得:LCM(x,x?)?110,GCD(x,x?)?1LCM(22,5)?110,GCD(22,5)?1即任元素都有补元，所以&K,|&有补格。 &K , LCM , GCD,’&是布尔代数。五、布尔表达式 10%E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?3)?(1?x2?x3)析取范式：?(x1?x2?3)?(x1?2?x3)?(x1?x2?x3)合取范式：E(x1,x2,x3)?(x1?x?2x3)?(x1?x2?x3) 试卷十三试题与答案七、 填空 10% （每小题 2分）1、Z??{x|x?Z?x?0}，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是
。 2、代数系统&A,*&中，|A|&1，如果e和?分别为&A,*&的幺元和零元，则e和?的关系为
。3、设&G,*&是一个群，&G,*&是阿贝尔群的充要条件是
。4、图的完全关联矩阵为
。5、一个图是平面图的充要条件是
。八、 选择 10% （每小题 2分）1、 下面各集合都是N的子集，（
）集合在普通加法运算下是封闭的。A、{x | x 的幂可以被16整除}；
B、{x | x 与5互质}；C、{x | x是30的因子}；
D、{x | x是30的倍数}。2、 设G1??{0,1,2},??，G2??{0,1},*?，其中?表示模3加法，*表示模2乘法，则积代数G1?G2的幺元是（
）。A、&0,0&；
B、&0,1&；
C、&1,0&；
D、&1,1& 。3、 设集合S={1,2,3,6}，“≤”为整除关系，则代数系统& S , ≤ &是（
）。A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统。4、 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=（
）。A、n?k；
B、n(k+1)；
C、n(k+1)-m；
D、n(k+1)-2m 。5、 一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有（
）个4度结点。A、1；
D、4 。三、判断10% （每小题 2分）1、（
）设S={1,2}，则S在普通加法和乘法运算下都不封闭。2、（
）在布尔格&A,≤&中，对A中任意原子a，和另一非零元b，在a?b或a?b中有且仅有一个成立。3、（
）设S?{x|x?Z?x?0}?N，+,?为普通加法和乘法，则&S，+，?&是域。4、（
）一条回路和任何一棵生成树至少有一条公共边。5、（
）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i = t-1。四、证明 38%1、（8分）对代数系统&A,*&，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）&A,*&中的每个元素在右逆元必定也是左逆元。（2）每个元素的逆元是唯一的。2、（12分）设?A
,?,??是一个布尔代数，如果在A上定义二元运算☆，为a☆b?(a?b)?(a?b)，则&A,☆&是一阿贝尔群。3、（10分）证明任一环的同态象也是一环。4、（8分）若G??V,E?e?k(v?2)k?2(V?v,E?e)是每一个面至少由k(k≥3)条边围成的连通平面图，则。五、应用 32%1、 （8分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？2、 用washall方法求图的可达矩阵，并判断图的连通性。（8分）3、 设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）4、 用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（8分）答案：三十五、 填空 10%（每小题2分）1、1， 不存在；2、e??；3、?a,b?G有(a*b)*(a*b)?(a*a)*(b*b)； 4、3, 35三十六、 选择 10%（每小题 2分）三十七、 判断 10%三十八、 证明 38% 1、（8分）证明：（1）设a,b,c?A，b是a的右逆元，c是b的右逆元，由于b*(a*b)?b*e?b，e?b*c?b*(a*b)*c?(b*a)*(b*c)?(b*a)*e?b*a所以b是a的左逆元。（2）设元素a有两个逆元b、c，那么b?b*e?b*(a*c)?(b*a)*c?e*c?ca的逆元是唯一的。 2、（12分）证明：[乘]??，?，?在A上封闭，? 运算☆在A上也封闭。 [群] ?a,b,c?A(a☆b)☆c?((a?b)?(a?b))☆c?(((a?b)?(a?b))?)?((a?b)?(a?b)?c)?(a?b?c)?(a?b?c)?((?b)?(a?b)?c)?(a?b?c)?(a?b?c)?(((a?b)?(?b))?c)?(a?b?c)?(a?b?c)?(a?b?c)?(?b?c)同理可得:a☆(b☆c)?(a?b?c)?(a?b?c)?(a?b?c)?(a?b?c)?(a☆b)☆c?a☆(b☆c)
即☆满足结合性。[幺] ?a?A,a☆0?0☆a?(0?a)?(0?a)?0?(1?a)?0?a?a 故全下界0是A中关于运算☆的幺元。[逆] ?a?A,(a☆a)?(a?a)?(a?a)?0?0?0 即A中的每一个元素以其自身为逆元。[交] a☆b?(a?b)?(a?b)?(b?a)?(b?a)?b☆a 即运算☆具有可交换性。 所以&A, ☆&是Abel群。 3、(10分) 证明:设?A,?,??是一环,且?f(A),?,??是关于同态映射f的同态象。 由?A,??是Abel群，易证?f(A),??也是Abel群。?A,??是半群，易证?f(A),??也是半群。现只需证：?对?是可分配的。?b1,b2,b3?f(A),则必有相应的a1,a2,a3使得:f(ai)?bi,i?1,2,3
于是b1?(b2?b3)?f(a1)?(f(a2)?f(a3))?f(a1)?(f(a2?a3))?f(a1?(a2?a3))?f((a1?a2)?(a1?a3))?f(a1?a2)?f(a1?a3)?(f(a1)?f(a2))?(f(a1)?f(a3))?(b1?b2)?(b1?b3)同理可证(b2?b3)?b1?(b2?b1)?(b3?b1) 因此?f(A),?,??也是环。 5、（8分）证明：设G有r个面，r??i?1deg(ri)?2e,而deg(ri)?k2rk(1?i?r)k(v?2)k?2?2e?kr即r?2ek而v?e?r?2,故v?e??2即e??。三十九、 应用32% 1、（8分）解：?(G)即为最少考试天数。用Welch-Powell方法对G着色：v9v3v7v1v2v4v5v8v6 第一种颜色的点 v9v1v4v6，剩余点v3v7v2v5v8 第二种颜色的点 v3v7v5，剩余点v2v8 第三种颜色的点 v2v8 所以?(G)≤3任v2v3v9构成一圈，所以?(G)≥3 故?(G)=3所以三天下午即可考完全部九门课程。 2、（8分） ?0??1A(G)??0??0?解：000111001??0?1??0???0??1A??0??0i? 1：A[2，1]=1，?000111001??0??1??1A??1?0???10??；
i?2： A[4，2]=1，?000111011??1?1??1??000111011??1?1??1???0??1A??0??1i?3： A[1，3]=A[2，3]=A[4，3]=1，??1??1A??1??1i?4： A[k，4]=1，k=1，2，3，4，?111??111?111??111??p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。 3、（8分）解：用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为 此图中的Hamilton回路即是圆桌安排座位的顺序。Hamilton回路为a b d f g e c a。4、（8分）解：(1)W(T)?2?4?3?4?5?3?9?2?7?2?8?2?83（1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为{，001，01，10，11} 。试卷十四试题与答案九、 填空 10% （每小题 2分）1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统，S是布尔格?A,??，中所有原子的集合，则?A,?,?,??～
。2、 集合S={α，β，γ，δ}上的二元运算*为那么，代数系统&S, *&中的幺元是
, α的逆元是
。3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：[i]?3[j]?[(i?j)mod3]，则+的运算表为
； 3&Z+,+3&是否构成群
。4、 设G是n阶完全图，则G的边数m=
。5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行
次这个加法指令。十、 选择 20% （每小题 2分）1、 在有理数集Q上定义的二元运算*，?x,y?Q有x*y?x?y?xy，则Q中满足（
）。A、 所有元素都有逆元；
B、只有唯一逆元；C、?x?Q,x?1时有逆元x?1；
D、所有元素都无逆元。2、 设S={0，1}，*为普通乘法，则& S , * &是（
）。A、 半群，但不是独异点； B、只是独异点，但不是群；C、群；
D、环，但不是群。3、图给出一个格L，则L是（
）。A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。3、 有向图D=&V , E& ，则v1到v4长度为2的通路有（条。A、0；
）4、 在Peterson图图。 中，至少填加（
）条边才能构成EulerA、1；
D、5 。十一、 判断 10% （每小题 2分）1、 在代数系统&A,*&中如果元素a?A的左逆元ae存在，则它一定唯一且a?1?1?ae。（
） ?12、 设&S,*&是群&G,*&的子群，则&G,*&中幺元e是&S,*&中幺元。（
）3、 设A?{x|x?a?b3,a,b均为有理数}， +,?为普通加法和乘法，则代数系统&A，+，?&是域。（
）4、 设G=&V ,E &是平面图，|V|=v, |E|=e，r为其面数，则v-e + r=2。（
）5、 如果一个有向图D是欧拉图，则D是强连通图。（
）四、证明 46%??A，使得x?*x?e， 1、 设&A,*&，是半群，e是左幺元且?x?A,?x则&A , *&是群。（10分）2、 循环群的任何非平凡子群也是循环群。（10分）3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末aH?bH??，要末aH?bH。（8分）4、 设&A ,+ ,?&，是一个含幺环，|A|&3，且对任意?a?A，都有a?a?a，则&A ,+ ,?&不可能是整环（这时称&A，+，?&是布尔环）。（8分）5、 若图G不连通，则G的补图G是连通的。（10分）五、布尔表达式 8% 设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数?{0,1},?,?,?上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用 16%1、 构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、 假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。（10分）答案四十、 填空 10%（每小题2分）1、&P (S), ?,?,~&；2、是；14、2n(n?1)；5、9四十一、 选择 10%（每小题 2分）四十二、 判断 10%（每小题2分）四十三、 证明 46%1、（10分）证明：（1）?a,b,c?A,若a*b?a*c则b?c事实上:?a*b?a*c??a?使a?*(a*b)?a?*(a*c)(a?*a)*b?(a?*a)*c,?e*b?e*c即:b?c(2) e 是&A，*&之幺元。事实上：由于e是左幺元，现证e是右幺元。?x?A,x*e?A,?x?使x?*(x*e)?(x?*x)*e?e*e?e?x?*x由(1)即x*e?x,?e为右幺元β，γ3、 ；（3）?x?A,则x?1?A?)*x?x*(x?*x)?x*e?x?e*x事实上:?x?A(x*x??e故有x?*x?x*x??ex*x??x有逆元x由（2），（3）知：&A,*&为群。 2、（10分）证明：设&G,*&是循环群,G=(a)，设&S,*&是&G,*&的子群。且S?{e},S?G，则存在最小正整数m，ml使得：a?S，对任意a?S，必有l?tm?r,0?r?m,lrt?0，mt故：ar?al?tm?a*al?tm?a*(a)lm?t?S
即：a?a*(a)?Slmtrm所以a?S但m是使a?S的最小正整数，且0?r?m，所以r=0即：a?(a)这说明S中任意元素是a的乘幂。 所以&G,*&是以a为生成元的循环群。 3、（8分）证明：对集合aH和bH，只有下列两种情况： （1）aH?bH??； （2）aH?bH??对于aH?bH??，则至少存在h1,h2?H，使得ah1?bh2，即有a?bh2h1，这时任意ah?aH，有ah?bh2h1h?bH，故有aH?bH 同理可证：bH?aH所以 aH?bH 4、（8分）证明：反证法：如果&A，+，?&，是整环，且有三个以上元素，则存在a?A,a??,a?1且a?a?a 即有：a??,a?1??但a?(a?1)?a?a?a?a?a??这与整环中无零因子条件矛盾。因此&A，+，?&不可能是整环。 5、（10分）证明：因为G=& V，E&不连通，设其连通分支是G(V1),?,G(Vk)种情况：（1） u , v，分别属于两个不同结点子集Vi，Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)在不G中，故u , v 在G中连通。（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w),(w , v )均在G中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在G中也是连通的。五、布尔表达式 8%(k?2)，?u,v?V，则有两?1?1mm函数表为：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 1 110 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函数。 c:B?A是f的逆十三、 选择 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、AA=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)?C、(A?B?C)?(A?B?C)?(A?B?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}；C、R?{?x,y?|x?R?y?R?x?y}。 22三、 15%用Warshall算法，对集合A={1，2，3，4，5}上二元关系R={&1,1&,&1,2&,&2,4&,&3,5&,&4,2&}求t（R）。四、15%集合C?{a?bi|i??1,a,b是任意实数，a?0}，C*上定义关系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}，B（B70）；4、A1?A2???An(Ai?Ai或Ai)，全集，?；5、反自反性、对称性、传递性；6、有限；7、双射。二、选择 15%（每小题 3分）三、Warshall算法 15%?1??0??0??0??1??0??0?MR解：i? 1时，MR[1,1]=1, A =MRi?2时，M[1,2]=M[4,2]=1?1??0?0??0?A=?1??0??0?i?3时，A的第三列全为0，故A不变i?4时，M[1,4]=M[2,4]=M[4,4]=1?1??0?0??0?A=?0?1??0?0??0?A=??1??0??0?
i?5时，M[3,5]=1 ，这时 0??0?1??0??0?所以t (R)={&1,1&, &1,2&,&1,4&,&2,2&,&2,4&,&3,5&,&4,2&,&4,4&} 。四、 5%证明：对称性：?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),传递性：若?a?bi?C,**aa?0*??a?bi,a?bi??R e?fi?C则*c?di?C,当?a?bi,c?di??R且?c?di,e?fi??Rac?0,ce?0,?acce?0即ae?0??a?bi,e?fi??R所以R是C*上等价关系。R两等价类：?1?{z|z?a?bi,a?0}右半平面；左半平面。 ?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?domf而f?g则x?domg且y?rangeg?x?domf且y?rangeg则?|y??rangef即?x,y???fy??y??x,y???g但?x,y??g由g是函数知即?x,y??f?x?domf且y?rangef?f?g欢迎您转载分享：
更多精彩：