PDF《离散数学 2017 年10 月真题及答案解析》

5 小题,每小题

6 分,共30 分. 26. 用列真值表的方法说明下列逻辑等价式成立 答案:解:分别列出两个命题公式的真值表如下: 解析:逻辑等价式必须具有相同的真值表,这是等价式的充分必要条件. 27. 用等值演算法推导命题公式 的主析取范式. 答案: 解析:利用等值式的运算规律与置换原则转换成主析取范式. 28. 设解释Ⅰ为:个体域 D={a,b},F(x)与G(x)为2个一元谓词,且F(a)=0,F(b)=1,G(a)=1, G(b)=0.在Ⅰ下,求命题公式 的真值.

9 答案:解:在解释 I 下29. 29. 设集合 S={1,2,3},题29 图为 S 上的二元关系 R 的关系图 (1)写出 R 的集合表达式;

(2)写出 R 的关系矩阵. 答案:(1)由题

29 图二元关系 R 的关系图可得,R={〈1,1〉,〈2,2〉,〈3,3〉,〈1, 2〉,〈2,1〉,〈2,3〉,〈3,1〉}(2)R 的关系矩阵为 解析:根据二元关系 R 的关系图的集合表达式方法与关系矩阵构造方法即得. 30. 求下述集合等式成立的充要条件,并证明结论 . 答案:(1) 成立的充要条件是 .(2)现在证明以上结论.证明: 解析:根据集合的运算规律证明即可 证明题:本大题共

3 小题,每小题

7 分,共21 分. 31. 设n阶无向简单图 G=,其中边数满足:E>(n-1)(n-2)/2,证明 G 是连通图. 答案:证明:假设 G 不是连通图,不妨设 G 有两个连通分支 G1和G2,且V1=N1,V2=N2,易见 N1+N2=N,由于 N1≥1,N2≥1,所以 N1*N2-( N1+N2)+1≥0 (*)而E1≤N1(N1-1)/2, E2≤N2(N2-1)/2,从而E=E1+E2≤N1(N1-1)/2+ N2(N2-1)/2 由式(*)可得,N1(N1-1)/2+ N2(N2-1)/2≤[(N1+N2)2-3(N1+N2)+2]/2=(N-1)(N-2)/2,即E≤(N-1)(N-2)/2 这 与题设条件E>(N-1)(N-2)/2 矛盾,故G是连通图. 解析:根据连通图的定义及边数计算公式即可证明. 32. 证明下列谓词公式为永真式: . 答案:证明:利用谓词等值式 ,可得易见,这是一个永真式.所以, 为永真式. 解析:利用谓词等值式即可转换为易于判断的永真式. 33. 设a、b、c 均为奇数,证明一元二次方程 ax2+bx+c=0 无有理数根.

10 答案:证明:设AX2+BX+C=0 有有理数根,不失一般性,设根为 P/Q,这里 P,Q 均为整数, 且Q≠0,并且 P,Q 不能同时为偶数,于是 A(P/Q)2+B(P/Q)+C=0 AP2+BPQ+CQ2=0P,Q 的奇偶 性有四种情况,而A、B、C 均为奇数,于是可得下表:由此可见,AP2+BPQ+CQ2 均为奇数, AP2+BPQ+CQ2=0 不成立.所以,一元二次方程 AX2+BX+C=0 无有理数根. 解析:利用命题公式真值表的结构来证明. 综合应用题:本大题共

2 小题,每小题

7 题,共14 分. 34. 无向树 T 有8片树叶,2 个3度分支点,其余的分支点都是

4 度,求T的阶数,并画出全 部非同构的这种树. 答案:解:设4度结点有 X 个,由握手定理可得 2(8+2+X-1)=5*1+3*2+4X 解方程得 X=2,即T为12 阶,全部的非同构树共有

6 棵,如下所示: 解析:先利用握手定理求出树的阶数,再按照要求画出非同构树. 35. 设为偏序关系,其中O为整除关系,即ab 当且仅当 a 整除 b.已知 A={1,2,3,5,6,15,30},画出这个偏序关系的哈斯图,并判断其是否为格. 答案:解:根据各元素的关系,可以画出哈斯图如下:从图上可见,任意两个元素都有上确界 和下确界存在,故为格. 解析:根据偏序关系的定义,画出哈斯图,再根据格的定义确定是否为格.