1、离散数学试题与答案试卷一一、填空 20% （每小题 2 分）1设 7|),5()(| xExBxNxA且且 （N：自然数集，E + 正偶数） 则 B 。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为 。3设 P，Q 的真值为 0，R ，S 的真值为 1，则)()(P的真值= 。4公式 )的主合取范式为。5若解释 I 的论域 D 仅包含一个元素，则 )()(xPx 在 I 下真值为。6设 A=1，2，3，4，A 上关系图为则 R2 = 。7设 A=a，b，c ，d，其上偏序关系 R 的哈斯图为则 R= 。8图 的补图为 。9设 A=a，b，c ，d ，A 上二元运算如下：* a b c
2、 dA BCabcda b c db c d ac d a bd a b c那么代数系统 的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10下图所示的偏序集中，是格的为 。二、选择 20% （每小题 2 分）1、下列是真命题的有（ ）A a； B ,；C ,； D 。2、下列集合中相等的有（ ）A4，3 ；B ，3，4；C4， ，3，3 ；D 3，4。3、设 A=1，2，3，则 A 上的二元关系有（ ）个。A 23 ； B 32 ； C 3； D 2。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（ ）A若 R，S 是自反的， 则 SR是自反的；B若 R，S 是反自反的， 则 是
3、反自反的；C若 R，S 是对称的， 则 是对称的；D若 R，S 是传递的， 则 S是传递的。5、设 A=1，2，3，4，P （ A） （A 的幂集）上规定二元系如下 |(|),|tspts则 P（A）/ R=（ ）AA ；BP(A) ；C1，1，2，1 ，2，3，1 ，2，3，4；D ，2，2，3，2，3，4，A6、设 A= ，1 ，1，3， 1，2，3则 A 上包含关系“ ”的哈斯图为（ ）7、下列函数是双射的为（ ）Af : I E , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : R I , f (x) = x ； Df :I N, f (x) = | x |
4、 。（注：I整数集，E偶数集， N自然数集，R 实数集）8、图 中 从 v1 到 v3 长度为 3 的通路有（ ）条。A 0； B 1； C 2； D 3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（ ）10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该树有（ ）个 4度结点。A1； B2； C3； D4 。三、证明 26%、R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当和在 R 中有在 R 中。 （8 分）、f 和 g 都是群到的同态映射，证明是的一个子群。其中 C= )(|1xgfx且 (8 分)、G= (|V| =
5、 v，|E|=e ) 是每一个面至少由 k（k 3）条边围成的连通平面图，则 2(ke， 由此证明彼得森图（Peterson）图是非平面图。 （11 分）四、逻辑推演 16%用 CP 规则证明下题（每小题 8 分）1、 FAEDCBA,2、 )()()( xQxPQxP五、计算 18%1、设集合 A=a，b，c ，d上的关系 R= , , , 用矩阵运算求出 R 的传递闭包 t (R)。 （9 分）2、如下图所示的赋权图表示某七个城市 721,v 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （分）试卷二试题与答案一、填空 20% （每小
6、题 2 分）1、 P：你努力，Q：你失败。 “除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。2、论域 D=1，2，指定谓词 PP (1,1) P (1,2) P (2,1) P (2,2)T T F F则公式 ),(xyP真值为 。2、 设 S=a1 ，a 2 ，a 8，B i 是 S 的子集，则由 B31 所表达的子集是。3、 设 A=2，3，4，5，6上的二元关系 |,是 质 数xyxR，则 R= （列举法） 。R 的关系矩阵 MR=。5、设 A=1，2，3，则 A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系 R= 。6、设代数
7、系统 ，其中 A=a，b，c,则幺元是 ；是否有幂等 性 ；是否有对称性 。7、4 阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n 个结点的无向完全图 Kn 的边数为 ，欧拉图的充要条件是。10、公式 RQPP)()( 的根树表示为。二、选择 20% （每小题 2 分）1、在下述公式中是重言式为（ ）* a b cabca b cb b cc c bA )()(QP；B )()()( PQP；C ； D 。2、命题公式 )()( 中极小项的个数为（ ） ，成真赋值的个数为（ ） 。A0； B1； C2 ； D3 。3、设 ,S，则 S 有（ ）个元素。A3； B6； C7 ； D8
8、。4、 设 ,21，定义 上的等价关系 , | cbdaSdcSbadcbaR 则由 R 产 生的 S上一个划分共有（ ）个分块。A4； B5； C6 ； D9 。5、设 3,21，S 上关系 R 的关系图为则 R 具有（ ）性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 。6、设 , 为普通加法和乘法，则（ ） ,S是域。A ,3|QbaxS B ,2|ZbanxC ,12Zn D 0= N 。7、下面偏序集（ ）能构成格。8、在如下的有向图中，从 V1 到 V4 长度为 3 的道路有（ ）条。A1； B2； C 3； D4 。9、在如下各图
9、中（ ）欧拉图。10、设 R 是实数集合， “”为普通乘法，则代数系统 是（ ） 。A群； B独异点； C半群 。三、证明 46%1、 设 R 是 A 上一个二元关系， ),(),(|, RbccaAcbaS 且有对 于 某 一 个试证明若 R 是 A 上一个等价关系，则 S 也是 A 上的一个等价关系。 （9 分）2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11 分）3、 若 BAf:是从 A 到 B 的函数，定义一个函数 ABg2:对任意 Bb有)()(|)( bxfxbg，证明：若 f 是 A 到 B 的满射，则 g 是从 B 到 A2
10、的单射。 （ 10 分）4、 若无向图 G 中只有两个奇数度结点，则这两个结点一定连通。 （8 分）5、 设 G 是具有 n 个结点的无向简单图，其边数2)(12nm，则 G 是Hamilton 图（8 分）四、计算 14%1、 设是一个群，这里+ 6 是模 6 加法，Z 6=0 ，1，2 ，3，4 ，5 ，试求出的所有子群及其相应左陪集。 （7 分）2、 权数 1，4，9，16，25，36，49，64，81，100 构造一棵最优二叉树。 （7 分）试卷二答案：试卷三试题与答案一、填空 20% （每空 2 分）1、 设 f，g 是自然数集 N 上的函数 xgxfx2)(,1)(, ，则 )(x
11、 。2、 设 A=a，b，c，A 上二元关系 R= , , , 则 s（R）= 。3、 A=1，2，3，4，5，6，A 上二元关系 |,是 素 数yxT，则用列举法T= ；T 的关系图为；T 具有 性质。4、 集合 2,A的幂集 A= 。5、 P，Q 真值为 0 ；R，S 真值为 1。则)()()( SRQPSRwf 的真值为 。6、 f的主合取范式为 。7、 设 P（x）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y。则谓词 ),()()(yNOyPwf 的自然语言是。8、 谓词 ),(),(),( uyxQzyxzyf 的前束范式为。二、选择 2
12、0% （每小题 2 分）1、 下述命题公式中，是重言式的为（ ） 。A、 )()(qp； B、 )()()( pqpq；C、 ； D、 。2、 rwf)(的主析取范式中含极小项的个数为（ ） 。A 、2； B、 3； C、5； D、0； E、 8 。3、 给定推理 )(xGFxP )yUS (P ) ES (yGTI )xUG)()(xGF推理过程中错在（ ） 。A、-; B、-; C、-; D、-; E、-4、 设 S1=1， 2，8，9，S 2=2，4，6，8 ，S 3=1，3，5，7，9，S 4=3，4，5，S5=3， 5，在条件 31X且 下 X 与（ ）集合相等。A、 X=S2 或
13、S5 ； B、X=S 4 或 S5；C、X=S 1，S 2 或 S4； D、X 与 S1，S 5 中任何集合都不等。5、 设 R 和 S 是 P 上的关系，P 是所有人的集合， ,|的 父 亲是 yxyx，, 的 母 亲是则 R1表示关系 （ ） 。A、 ,|的 丈 夫是 ；B、 , 的 孙 子 或 孙 女是 yxPyx ；C、 ； D、 ,|的 祖 父 或 祖 母是 yx。6、 下面函数（ ）是单射而非满射。A、 12)(,: xfRf ；B、 Zln；C、 的 最 大 整 数表 示 不 大 于 xxfZRf ,)(,:；D、 12。其中 R 为实数集，Z 为整数集， R+，Z +分别表示正
14、实数与正整数集。7、 设 S=1，2 ，3，R 为 S 上的关系，其关系图为 则 R 具有（ ）的性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。8、 设 2,1,S，则有（ ） S。A、1,2 ； B、1,2 ； C、1 ； D、2 。9、 设 A=1 ,2 ,3 ，则 A 上有（ ）个二元关系。A、2 3 ； B、3 2 ； C、 32； D、 23。10、全体小项合取式为（ ） 。A、可满足式； B、矛盾式； C、永真式； D、A，B ，C 都有可能。三、用 CP 规则证明 16% （每小题 8 分）1、 FEDC,2、 )()()( xQxPQxP四、 （14%） 集合 X=, , , ，R=,|x1+y2 = x2+y1 。1、 证明 R 是 X 上的等价关系。 （10 分）2、 求出 X 关于 R 的商集。 （4 分）五、 （10%）设集合 A= a ,b , c , d 上关系 R= , , , 要求 1、写出 R 的关系矩阵和关系图。 （4 分）2、用矩阵运算求出 R 的传递闭包。 （6 分）
