广东工业大学离散数学A.doc

广东工业大学试卷用纸，共 5 页，第 1 页学学 院：院： 专专 业：业： 学学 号：号： 姓姓 名名： 装 订 线广东工业大学考试试卷广东工业大学考试试卷 ( ( A A ) )课程名称课程名称: : 离散数学 考试时间考试时间: : 20072007 年年 1 1 月月 2626 日日 ( (第第 2121 周周 星期五星期五 ) )题 号一二三四五六七八九十总分评卷得分评卷签名复核得分复核签名一、单项选择题一、单项选择题(本大题共本大题共 8 小题，每小题小题，每小题 2 分，共分，共 16 分分) 1、设 p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才 乘公共汽车上班”的符号化形式为 [ ]A. p→q B. q→pC .p→┐q D. ┐p→q2、设解释 I 如下，个体域 D={a,b}, F(a,a)= F (b,b)=0, F(a,b)=F(b,a)=1，在 解释 I 下，下列公式中真值为 1 的是 [ ]A. Vx ヨ yF(x,y) B. ヨ xVyF(x,y)C. VxVyF(x,y) D. ┐ヨ x ヨ yF(x,y)3、设 R1、R2为集合 A 上的任意关系，下列命题为真的是 [ ]Ａ 若 R1、R2反自反，则 R1 R2反自反oB 若 R1、R2传递，则 R1 R2传递oC 若 R1、R2自反，则 R1R2自反oD 若 R1、R2对称，则 R1R2对称o4、设 G 为完全二部图 K2,3，下面命题中为真的是 [ ]A. G 为欧拉图 B. G 为哈密尔顿图 C. G 为平面图 D. G 为正则图5、对于任意集合 X, Y, Z，则 [ ]A. X∩Y=X∩Z =>Y=Z B. X∪Y=X∪Z =>Y=Z C. X－Y=X－Z =>Y=Z D. X⊕Y=X⊕Z =>Y=Z 广东工业大学试卷用纸，共 5 页，第 2 页6、下面等式中唯一的恒等式是 [ ]A. (A∪B∪C)-(A∪B)=C B. A⊕A=AC. A-(B×C)=(A-B)×(A-C) D. A×(B-C)=(A×B)-(A×C) 7、设 R 为实数集，定义* 运算如下：a*b=|a+b+ab|，则 * 运算满足 [ ] A. 结合律 B. 交换律 C. 有幺元 D. 幂等律 8、对于集合 A＝｛0、1、2、3、4、5、6、7、8、9、10｝ ，不封闭的二元运算是[ ] A x*y=max(x,y) B x*y=x－yC x*y=(x+y)mod 9 D x*y=min(x,y)二、填空题二、填空题(本大题共本大题共 10 小题，每空小题，每空 3 分，共分，共 24 分分) 9、含 n 个命题变项的重言式的主合取范式为_________________________。

10、设个体域为整数集合 Z，命题 Vx ヨ y(x+y=3)的真值为___________ 11、以 1，1，1，2，2，3 为度数序列的非同构的无向树共有___________棵 12、已知 n 阶无向简单图 G 有 m 条边，则 G 的补图 G 有__________条边 13、设 R={，，，}，则domR⊕ranR=_____________________14. 设 A={1, 2, 3, 4}，则 A 上有____________个不同的双射函数 15. 设 σ=(1345)(2678)是 8 元置换，则 σ-1=___________ 16、集合 A＝｛1、2、3、4｝上的恒等关系是_________________________三、三、 简答及证明简答及证明(本大题共本大题共 6 小题，每小题小题，每小题 10 分，共分，共 60 分分) 17、(10 分)设 G 为 n(n≥3)阶无向简单图，证明 G 或 G 的补图必连通 18、(10 分)设 A，B，C 为集合，证明：A∩(B－C)=(A－C)∩(B－C)19、(10 分)右图是偏序图的哈斯图 1)X 和≤的集合表达式 2)指出偏序集的极大元、极小元、最大元、最小元 20、(10 分)设 Z 为整数集，在 Z 上定义二元运算*如下：x，y Z，x*y＝x＋y－2请证明（Z，*） 是群。

21、(10 分)在命题逻辑中构造下面推理的证明前提：p→s，q→r，┐r，p∨q 结论：r 22、(10 分) 用狄克斯特洛算法求下图中从 a 到 f 的最短 通路写出求解过程）第 19 题图163233516adcebf广东工业大学试卷用纸，共 5 页，第 3 页uGivGjxGju v Gi课程名称课程名称: : 离散数学离散数学 A A 卷标准答案卷标准答案 一、单项选择题一、单项选择题(本大题共本大题共 8 小题，每小题小题，每小题 2 分，共分，共 16 分分)12345678 AACCDDBB二、填空题二、填空题(本大题共本大题共 8 小题，每空小题，每空 3 分，共分，共 24 分分)1.无（或没有，或空） 2. 1（或 T，或真） 3. 2 4. [n(n-1)/2]-m 5. {2,{2}} 6. 4!（或 24） 7. 24（或 16） 8.{(1,1),(2,2),(3,3),(4,4)} 三、(10 分) 证明：证明：如果图 G 是连通图，问题得证。

2 分 如果 G 不是连通图，不妨设图 G 由 K 个连通分支 G1,G2,…,Gk构成现证 G 的补图是 连通图 2 分 在补图中任取两点 u 和 v，由于补图和原图有相同的顶点，所以 u 和 v 也是图 G 的点 下面分两种情况讨论 1. u 和 v 分别是不同的连通分支 Gi和 Gj的点（见下图 1） 易知，连接 u 和 v 的边在补图中， 即在补图中，u 和 v 之间有通路相连 3 分图 1 图 2 2. u 和 v 是同一连通分支 Gi中的点（见上图 2） 则可在另一连通分支 Gj中任取一点 x， 易见边 ux 和边 vx 是补图中的边，由此可知点 u 和 v 之间在补图中 有通路 uxv 相连 3 分 综上所述，补图是连通图 四、(10 分) 证明：①￢s P 1 分②p→s P 1 分③￢p T①② 1 分④pq P 1 分⑤q T③④ 1 分⑥q→r P 1 分广东工业大学试卷用纸，共 5 页，第 4 页⑦r T⑤⑥ 1 分T 规则应用正确：2 分； P 规则应用正确：1 分； 五、(10 分) 解： 1.X＝{a,b,c,d,e,f} 2 分≤={(a,b)，(a,c)，(a,d)，(a,e)，(a,f)，(b,e)，(c，e), (c,f)，(d,f)}∪Ix 4 分，其中错一个、多一个、漏一个元素均扣 0.5 分，直至 4 分扣完。

2.极大元 e； 1 分 极小元 a； 1 分 最大元不存在； 1 分 最小元 a 1 分 六、(10 分) 证明：①由已知，运算显然封闭； 2 分 ②对x，y，z Z 有： (x*y)*z=(x+y-2)*z=(x+y-2)+z-2=x+y+z-4 1 分x*(y*z)=x*(y+z-2)=x+(y+z-2)-2=x+y+z -4 1 分 所以，*满足结合律； ③对x  Z 有：x*2=x+2-2=0， 1 分 且 2*x=2+x-2=0 1 分 所以，存在单位元：2 ④对x  Z 有：x*(4-x)=x+4-x-2=2， 1 分 且(4-x)*x=4-x+x-2=2 1 分 所以，对x  Z 有 x 的逆元是：4-x 1 分 由①②③④可知， （Z，*）是群。

1 分 七、(10 分) b c d e f ③∞5∞∞2 分 9④∞∞2 分 7⑤∞1 分 ⑦11 1 分 ⑩1 分 故 a 到 f 的最短通路是 a-b-d-c-f（或 a-b-d-e-c-f） ， 2 分 其权为 10 1 分八、(10 分) 前提：x(F(x)→G(x))，x(G(x) H(x)→I(x))，F(a)，H(a) 2 分 结论：I(a) 。