中科院计算机所1999年硕士入学考试离散数学答案
中科院计算机所1999年硕士入学考试离散数学答案中科院计算机技术研究所1999年硕士研究生入学考试试题
离散数学 参考答案
一.主合取范式: (not x1 or not x2 or x3)and(x1 or not x2 or x3) and (x1 or x2 or x3)
主析取范式: (x1 and not x2 and not x3)or(x1 and x2 and x3)or(x1 and not x2 and
x3) or (not x1 and x2 and x3)or (not x1 and not x2 and x3)
二.(1) 1
(2) 3
(3) 2
(4) 1
三.不是.取一特定解释域 I 如下.[P(x,y)] I ="x<=y",论域D=N(自然数集)则显然有
[any x exist y P(x,y)] I =t
[exist y any x P(x,y)] I =f
故给定公式在 I 中为假,因此它不是谓词公式的有效式.
四.
(1) any x(bird(x)->fly((x)) //前提1
(2) any x(monkey(x)->not fly(x)) //前提2
(3) bird(a)->fly(a) //(1)脱帽
(4) monkey(a)->not fly(a) //(2)脱帽
(5) not fly(a)->not bird(a) //逆否律(3)
(6) monkey(a)->not bird(a) //传递律(4)(5)
(7) any x(monkey(x)->not bird(x)) //(6)戴帽
五.解:
(1) 一个x到y的关系对应于x*y的一个子集.因此,不同的x到y的关系数=|φ(x*y)|=2^(mn)
(2)不同的由x到y的映射个数=|{f|f: x->y}|=|{(f(x1),f(x2),...,f(xm) )|,f(xi) in y, 1=
=Π(i=1 to m) |{f(xk)|f(xk) in y }|=n^m.
(3) 若m!=n,则双射的个数为0
若m=n,则双射的个数为m!
若m>n,则单射个数0
若m
m!种不同的双射,共有单射Cn(m)*m!种.
六.证明:由于G为奇数阶交换群,由拉格朗日定理,其中不可能有2阶元,因此
any a in G(a!=e),a!=a^(-1),即a与a^(-1)是两个不同元素(a!=e),因此G的所有元素之积
=e*a1*a1^(-1)*a2*a2^(-1)*...*am*am^(-1)=e
a1 in G-{e},a2 in G-{a1,a^(-1),e},...,am in G-{e,a1,a1^(-1),a2,a2^(-1),...,a(m-1),a(m-1)^(-1)
|G|=2m+1
七.(1)1. 自反性:any a in G 有:a=e*a*e.(e 为单位元) ,而H,k为 G的子群,从而 e in H ,e in k
so: aRa.
2. 对称性:若aRb,=>存在 h in H ,k in K 使 b=h*a*k=>a=h^(-1)*k^(-1),由于 H,K
为G的子群=>h^(-1) in H ,k^(-1) in K,所以 bRa.
3.传递性:若aRb,bRc=>存在 h1,h2 in H ,k1,k2 in K ,使b=h1*a*k1,c=h2*b*k2,由于
H,K为G的子群,得h2*h1 in H,k1* k2 in K,使c=(h2*h1)*a*(k1*k2),所以aRc,
因此 R 是等价关系.
(2)设是 的子群的那个 的等价关系为
[a]R={x|x in G and aRx}={x|x in G 且存在h in H,k in K ,使 x=h*a*k}={h*a*k| h in H,k inK}
由于该等价类为 的子群,故对任意的h1,h2 in H 有(h1*a*k1)*(h2*a*k2)^(-1) in [a]R
取k1=k 2则得any R1,R2 in H有h1*a^2*h2^(-1) in [a]R
从而可以从中推出h1*a^(2r)*h2^(-1) in [a]R
由于G 为有限群,必存在某个 r 使a^(2r)=e 此时 ,有any h1,h2 in H,h1*h2^(-1) in [a]R
即H 为[a]R的子群.
同理, 为 K 的子群,所以 m| |[a]R| , n| |[a]R|而m 与 n 互素=>mn| |[[a]R|即|G| | |[a]R|
又[a]R 为G 的子群,因此|[a]R| | |G|,从而|G|=|[a]R| , 从而[a]R=G,即 any g in G
有aRg,而R 为等价关系.
any g1,g2 in G, 由对称性 aRg1=>g1Ra
由传递性,aRg1,aRg2=>g1Ra,aRg2 =>g1Rg2
So:R=G*G
八.在每个区域放一个结点,当两区域相临时就在响应的两个结点间连一条线,如此构造了
一个平面图且是完全图kβ.而最大的平面完全图为k4,所以,β最大为四.
九.必要性:设G是强连通的,此时若从s到v-s没有有向边,则s中的任一顶u到v-s中的任一顶
v均没有有向道路,从而与G是强连通的矛盾.所以,从s到v-s至少有一条有向边.
充分性:设G是一边连通的,any u,v in V(G)
则{u}到V(G)-{u}至少有一条有向边,设为uu1.而{u,u1} 到V(G)-{u ,u1}至少有一条有向边
uu2或u1u2.无论那种情况都有从u到u2的有向道路.因G中结点数有限,通过如上递归地
求解,一定有u到v的有向道路.所以G是强连通的.
十.设e是v1与v2间的最短边,G的最小生成树为T.若e不在T中,则T+e有唯一的圈c,因
T是G的最小生成树,所以,c上除e之外一定有另一条v1与v2间的边e1,而ω(e1)>ω(e).
T+e-e1是连通图且与T的边数相同,所以,T+e-e1也是G的生成树,而ω(T+e-e1)=
ω(T)+ω(e)-ω(e1)<ω(T).所以T不是最小生成树.矛盾. 祝你好运