<0,0,0> <0,0,1> <0,1,0> <0,1,1> <1,0,0> <1,0,1> <1,1,0> <1,1,1>
析取范式为：
f 0 1 0 1 0 1 1 1 ??x??x)?(x?x??x)?(x??x?x)?(x?x?x?)?(x?x?x) 合取范式为： E(x1,x2,x3)?(x123123123123123??x)?(x??x?x) E(x1,x2,x3)?(x1?x2?x3)?(x1?x23123
三、回答问题
完全图Kn是否是欧拉图？是否是哈密尔顿图？为什么？
答：解 因为欧拉图和哈密尔顿图分别要求有欧拉回路和哈密尔顿回路，所以要求n?3。
完全图Kn的每个结点的度数为n-1，而当一个图的所有结点度数均为偶数时，该图为欧拉图，所以当n-1为偶数，即n（n?3）为奇数时Kn是欧拉图。
Kn的任意两个结点的度数和为2(n?1)，当n?3时，有2(n?1)?n，此时Kn是哈密尔顿图。
四、画图
对于下图，利用克鲁斯克尔算法求一棵最小生成树。
答：最小生成树为
11
五、计算
一棵树有两个结点度数为2 ，1个结点度数为3，3个结点度数为4 ，其余结点度数为1。问该树有几个度数为1的结点。
答：解 该树有n个度数为1的结点。则有
n?2?2?3?4?3?2(n?2?1?3?1)
解之，得n=9
答：该树有9个度数为1的结点。
六、证明
|E|?m，证明：m?图G?(V,E)是无向简单图，其中|V|?n，n(n?1)。 22证明 因为G是简单图，所以图G中没有环和平行边，任意两结点间最多有一条边，故m?Cn?n(n?1)。 2答：证明 因为G是简单图，所以图G中没有环和平行边，任意两结点间最多有一条边，故
2m?Cn?n(n?1) 2 七、证明
已知
G?(VN,VT,P,?),VN?{?,B,C},VT?{a,b,c},P:(1)??a?BC(2)??aBC(3)CB?BC(4)aB?ab(5)bB?bb(6)bC?bc(7)cC?ccnnn求证 ??abc
*
答：证明 ??a*n?1?(BC)n?1 （用生成式（1））
?an(BC)n （用生成式（2））
nnn ?aBC （用生成式（3））
*nn?1n ?abBC （用生成式（4））
12
nnn ?abC （用生成式（5））
* ?anbncCn?1 （用生成式（6））
nnn ?abc （用生成式（7））
*
八、设计
设计一台有限状态机M，它的输出是已经输入符号数的模3数（即设计模3计数器）。 答：解 M?(Q,S,R,f,g,A) 其中 Q?{A,B,C},S?{a},?R{0 ,1f(A,a)?B,f(B,a)?C,f(C,a)?a
g(A,a)?1,g(B,a)?2,g(C,a)?0状态图为：
九、计算
给定码C={00000,10001,01100,10101}，求码C中任两个码字的海明距和dmin(C)。 答：
解 H(00000,10001)=2,H(00000,01100)=2,H(00000,10101)=3, H(10001,01100)=4,H(10001,10101)=1,H(01100,10101)=3
dmin(C)?1
复习题四
一、填空
1、设A和B为有限集，|A|=m，|B|=n，则有
个从A到B的关系，有
13
个从A到B
的函数，其中当m?n时有 个入射，当m=n时，有 个双射。
2、集合A?{n2|n?N} 是 （是/不是）可数的。 二、计算
1、用推导法求下列公式的主合取范式和主析取范式：((?P?Q)?R) 答：
???P?Q?R???P??Q?R???P??Q??R????P?Q?R????P??Q?R??
2设A?{1,2,3,4},A上二元关系R?{?1,2?,?2,2?,?2,4?,?3,4?}，求其自反闭包、对称闭包、传递
闭包。
答：自反闭包r(R)?{?1,2?,?2,2?,?2,4?,?3,4?,?1,1?,?3,3?,?4,4?} 对称闭包s(R)?{?1,2?,?2,2?,?2,4?,?3,4?,?2,1?,?4,2?,?4,3?} 传递闭包r(R)?{?1,2?,?2,2?,?2,4?,?3,4?,?1,4?} 三、证明
1、设A,B,C是三个集合，证明：(A?B)?C?(A?C)?B 答：(A?B)?C?(A?B)??C?(A??C)?B?(A?C)?B 2证明等价式：(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
答：(?x)(A(x)?B(x))?(?x)(?A(x)?B(x))?(?x)?A(x)?(?x)B(x)
???P?Q??R??????P?Q??R????P??Q??R?
???P?R????Q?R?????P??Q??Q??R????P??P???Q?R?? ???P?Q?R???P??Q?R????P??Q?R??
??(?x)A(x)?(?x)B(x)?(?x)A(x)?(?x)B(x)
四、将下列命题推理符号化并给出形式证明：
已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。所以李四和王五的彩票都中奖了。
答：P：张三的彩票中奖了。Q：李四的彩票中奖了。 R：你知道张三的彩票中奖。S：王五的彩票中奖了。
P?Q,P?R,Q?S,?R?Q?S
证明：(1)?R(2)P?R(3)?P(4)P?Q(5)Q(6)Q?S(7)S(8)Q?S
P P
T(1)(2)I P
T(3)(4)I P
T(5)(6)I T(5)(7)I
五、设复数集合C?{a?bi|a,b?R,a?0}，定义C上二元关系R：?a?bi,c?di??R当且仅当
ac?0，证明：R为等价关系。
答：证明：对于?a?bi,c?di,e?fi?C，有a,c,e?0
14
因为aa?0，所以?a?bi,a?bi??R，故R是自反的。
ce?0,得ae?0，所以?c?di,a?bi??R，故R是若?a?bi,c?di??R，则ac?0且ce?0,即ac?对称的。
若?a?bi,c?di??R，?c?di,e?fi??R则ac?0,即ca?0，所以?a?bi,e?fi??R，故R是传递的。
综上：R为等价关系。
六、证明：若A?B和C?D，则A?B?C?D。
答：证明：因为A?B和C?D，所以可作双射f:A?B,g:C?D。
定义h:A?B?C?D，对于??a,b??A?B,有c=f(a),d?g(b),?c,d??C?D 对??a1,b1?,?a2,b2??A?B,?a1,b1???a2,b2?， 设c1=f(a1),c2?f(a2),d1?g(b1),d2?g(b2)，
当a1?a2时，由于f:A?B是双射，所以c1?f(a1)?f(a2)?c2，得?c1,d1???c2,d2?；当
b1?b2时，由于g:C?D是双射，所以d1?g(c1)?g(c2)?d2，得?c1,d1???c2,d2?。故h:A?B?C?D是入射。
对??c,d??C?D，因为f:A?B,g:C?D均为双射，所以?a?A,b?B使得c?f(a),d?g(b)，
?a,b??A?B。故h:A?B?C?D是满射。
综上，故h:A?B?C?D是双射。有A?B?C?D。
七、设集合G?{2m3n|m,n?I}，?是普通乘法，证明：?G,??是一个群。 答：对?a,b?G,设a?2m13n1,b?2m23n2
a?b?2m13n1?2m23n2?2m1?m23n1?n2?G，所以×封闭。 对?a,b,c?G,设a?2m13n1,b?2m23n2,c?2m33n3
(a?b)?c?(2m13n1?2m23n2)?2m33n3?2m13n1?(2m23n2?2m33n3)?a?(b?c)，所以?可结合。 ?a?G,a?2030?2m1?03n1?0?2m13n1?20?m130?n1?2030?a?a，所以2030为幺元。 ?a?G,a?2?m13?n1?2m1?m13n1?n1?2030?2?m1?m13?n1?n1?2?m13?n1?a，所以a?1?2?m13?n1。 综上：?G,??是群。
八、设实数集合R，+和x是普通加法和乘法，定义映射f:R?R，?x?R,f(x)?ex，证明
f是从?R,??到?R,??的单一同态。
答：因为对于?x,y?R有f(x?y)?ex?y?ex?ey?f(x)?f(y)，所以f是从?R,??到?R,??的
同态。
对于?x,y?R,x?y有f(x)?ex?ey?f(y)，所以f是从R到R的入射。
故f是从?R,??到?R,??的单一同态。
复习题五
一、填空
1、实数集合R 是 （是/不是）可数的。
15