中科院计算机技术研究所1999年硕士研究生入学考试试题 离散数学

一.(8分)求与公式(x2 or not x1)->x3 逻辑等值的主合取范式和主析取范式.

二.(8分)判断下列各公式是: 1.永真式 2.永假式 3.其它
(1) (p->(q->r))->(q->(p->r))
(2) (not p or q)<->(p and(p and q))
(3) (not p or q)and not(q or not r)and not(r or not p or not q)
(4) (q and p)->(p or q)

三.(9分)问any x exist y P(x,y)->exist y any x P(x,y)是否谓词演算的有效式?证明你的结论.

四.(9分)将下列推理符号化并给出形式证明:
鸟会飞,猴子不会飞;所以,猴子不是鸟.

五.(12分)令X={x1,x2,...,xm},Y={y1,y2,...,yn},问:
(1) 有多少不同的由X到Y的关系?
(2) 有多少不同的由X到Y的影射?
(3) 有多少不同的由X到Y的单射，双射?

六.(8分)设e是奇数阶交换群G的单元位,试证:G的所有元素之积为e.

七.(15分) ①<G,*>是个群,H,K 是其子群,在G上定义二元关系R:
any a,b in G,aRb <=>存在 h,k in k,使得 b=h*a*k,证明:R是G上的等价关系.
② 在①中,若|H|=m,|K|=n,|G|=mn,m与n互素,且R的某个等价类在G的乘法
运算下构成G的一个子群,则R=G*G.

八.(8分)把平面分成β个区域,每两个区域都相邻,问β最大为几?

九.(11分)设G为非平凡有向图,V(G)为G的结点集合,若对V(G)的任意非空子集S,
G中起始结点在S中,终止结点在V(G) S中的有向边都至少有k条,则称G是k边
连通的.证明:非平凡有向图G是强连通的充要条件是他是1边连通的.

十.(12分)设G是一无向加权图且各边的权不相等,V,E分别是G的结点集合和边的集合,
(V1,V2)是V 的划分,即V1 or V2 = V, V1 and V2=null,且 V1!=null,V2!=null,则V1与V2
间的最短边一定在G的最小生成树上.

中科院计算机技术研究所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<=m}|
=Π(i=1 to m) |{f(xk)|f(xk) in y }|=n^m.
(3) 若m!=n,则双射的个数为0
若m=n,则双射的个数为m!
若m>n,则单射个数0
若m<n,从y中任取m个元素有n!/((n-m)!m!)种方法,此m个元素与x中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不是最小生成树.矛盾.