中科院计算机技术研究所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分) ①是个群,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的最小生成树上.
