2001级 高级语言程序设计 笔试试卷.doc

江苏技术师范学院20 —20 学年第 学期 《离散数学》试卷（1）参考答案与评分标准 一、单项选择题（本大题共5道小题，每小题2分，共10分） 1．设A={1,2,3},B={1,2,3,4,5},C={2,3}, 则(AB)- C =（ C ）。A.{1,2} B.{2,3} C.{1,4,5} D.{1,2,3} 2．在自然数集N上定义二元运算*如下，满足交换律的是（ C ）。A. a*b=a-b B. a*b=a+2b C. a*b=min{a,b} D. a*b=a 3．设集合A={a,b,c},A上的关系R={a,a,b,b}具备下列性质（ D ）。A.等价性 B.自反性 C.反自反性 D.反对称性 4．当且仅当为下面条件中的哪一个时，无向简单图G是哈密顿图？（ D ）。A. G的每对结点的度数不大于顶点的个数 B. G的每对结点的度数大于顶点的个数C. G的每对结点的度数小于顶点的个数 D. G的每对结点的度数不小于顶点的个数 5．设B(x)：x是金子；F(x)：x会发光；则金子都会发光可符号化为：（ B ）。A. B. C. D. 二、填空（本大题共10空，每空2分，共20分） 设p：我们勤奋，q：我们好学，r：我们取得好成绩。命题“只要勤奋好学，我们就能取得好成绩”符号化为 p?q?r 。 若连通的简单图中所有结点的度数为 偶数 ，则该图一定是欧拉图。 群Z6,+6的所有子群是：_Z6,+6，{0,2,4},+6，{0,3},+6，{0},+6_。 n个结点的无向完全图的边数m为 n(n-1)/2 。 集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R的性质为 对称性 。 {,{}} 。 一个图G有24条边，若每个结点的度均为2，则G有 24 个结点。 设F(x):x是鱼，G(x)：x会游泳；“没有不会游泳的鱼”符号化为 (（F(x)→G(x)）或x（F(x)∧G(x)） 。 偏序关系是指：满足 自反性、反对称性、传递性 的关系。 P()={,{a},{},{{}},{a,},{a,{}},{,{}},{a,,{}}}　。 三、判断题（本大题共10小题，每小题1分，共10分） 正确的打“√”，错误的打“×” （√）若A={Ф},B=P（A） ,则有{Ф}B及{Ф}B 。 （×）设A,B为无限集，则A-B是空集。 （×）对集合A,B,C,D，有（AB） (CD) = (AC) (BD)。 （×）简单图G有n个结点，m条边,若m=n-1,则它一定是树。 （×）集合R上的关系满足对称性与传递性，则一定满足自反性。 （×）群中既有零元又有单位元，还有等幂元。 （×）对哈密顿图，奇度结点的个数均为偶数。 （√）阿贝尔（Abel）群是交换群。 （√）命题公式是重言式。 （×）如果1+1＝3，则雪是黑的。这句话不是命题。 四、证明题（本大题共4小题，每小题6分，共24分） 1.设A、B、C是三个集合，证明：AB=A(B-A) 证明：A(B-A)=A(B)=(AB)(A)=(AB)U= AB　　（6分） 2.在命题逻辑中符号化下述命题，并构造推理的证明。 若明天是星期一或星期三，我就有课。 若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。 解：设 p:明天是星期一, q:明天是星期三，r:我有课，s:我备课 （1分） 前提: (p?q)?r, r?s, ?s 结论: ?p??q （1分） 证明 ① r?s 前提引入 ② ?s 前提引入 ③ ?r ①②拒取式 ④ (p?q)?r 前提引入 ⑤ ?(p?q) ③④拒取式 ⑥ ?p??q ⑤置换 结论有效, 即明天不是星期一和星期三。 （4分） 3.设9阶无向图的每个顶点的度数为5或6，证明它至少有5个6度顶点或者至少有6个5度顶点。 证明： （6分） 方法一 讨论所有可能的情况. 设有a个5度顶点和b个6度顶点 (1)a=0, b=9; (2)a=2, b=7; (3)a=4,