《离散数学 Discrete Mathematics》课程教学资源（习题集）中科院计算机技术研究所1999年硕士研究生入学考试试题

中科院计算机技术研究所1999年硕士研究生入学考试试题 离散数学 (8分)求与公式(x2 or not xl)->x3逻辑等值的主合取范式和主析取范式 二(8分)判断下列各公式是:1永真式2永假式3其它 (1)(p>(q->r)->(q~>(p->r) (2)(not p or q)(p and(p and g)) ()(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(xy)-> exist y any X P(xy)是否谓词演算的有效式?证明你的结论 四(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分)①是个群,HK是其子群在G上定义二元关系R anya.binG,aRb存在 h, k in k,使得b=h*a+k证明R是G上的等价关系 ②在①中,若H=mKF=nG|=mnm与n互素,且R的某个等价类在G的乘法 运算下构成G的一个子群,则R=G*G 八(8分)把平面分成β个区域,每两个区域都相邻,问β最大为几? 九(11分)设G为非平凡有向图V(G)为G的结点集合,若对vG)的任意非空子集S G中起始结点在S中终止结点在V(G)S中的有向边都至少有k条,则称G是k边 连通的证明:非平凡有向图G是强连通的充要条件是他是1边连通的 十(12分)设G是一无向加权图且各边的权不相等VE分别是G的结点集合和边的集合 (V1,V2)是V的划分,即 VI or v2= V. VI and v2=null且Vl!=nuV2!-nu,则Vl与V2 间的最短边一定在G的最小生成树上

中科院计算机技术研究所 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 的最小生成树上