《软件所1996离散》由会员分享，可在线阅读，更多相关《软件所1996离散（2页珍藏版）》请在金锄头文库上搜索。
1、中国科学院软件所中国科学院软件所一九九六年招收硕士学位研究生入学考试试题试题名称：离散数学数理逻辑部分一.(10 分).试求的主合取范式和主析取范式。)()(QPRP二.证明:1).(5 分).PPQP)(2).(7 分).BxxABxxA)()(三.(10 分).办案人员得到下列线索: 1).不是张某就是王某杀了厂长,而且两人不会合谋. 2).张某不可能在半夜作案. 3).王某说半夜厂长家灯亮着. 4).王某若没作案,则他不会说谎. 5).若厂长家半夜灯亮着,则案发生在半夜. 请你根据线索找出作案者,形式化证明你的结论.代数结构部分四.(10 分）.设,.记 S 上的恒同映射为.BAf:CB
2、g:ACh:SI证明:如果,则 f, g ,h 均为双射,并求AIfghBIghfCIhfg出.111,hgf五.G 是1,2,3上的置换群，|G|=6.1). (4 分).已知，试 G 列出的全部元素。GG 213123,2311232). (5 分).令，在 F 上定义关系，对任意, 1 , 03 , 2 , 1:|ffF,存在，使对任何，均有，Fff21,21RffGg 3 , 2 , 1x)()(21xgfxf证明 R 是 F 上的等价关系。 3). (3 分).求 R 所确定的等价类。六.设是集合 A 上的二元运算，对任意，满足.,Acba,1).，)()(cbacba)()(cba
3、cba2).，abbaabba3).，aaba)(aaba)(现定义 A 上关系，证明：ababa 1). (5 分).是 A 上的序关系2). (7 分).对任何，均有一个最小上界和一个最大下界。Aba,ba图论部分七.(10 分).设 T 是树，且，则 T 中至少 k 有个结点的度数（或kT )(次数）为 1。八.(2 分).设 G 是无向完全图，若对 G 的每条边指定一个方向，所得到的图称为竞赛图，证明：无有向回路（或有向圈）的竞赛图 D:中，对任意,。)(,DVvu)()(vdud九.(12 分).证明：设是简单无向连通图，且)(),(GEGVG，则 G 中存在一条不小于的通路（或轨道） 。2| )(|GV2
