离散数学考试试题a

一.(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的最小生成树上. 离散数学参考答案 一.主合取范式: (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 中为假,因此它不是谓词公式的有效式. 四...