离散数学 练习题及答案[重要知识]

1、例3 给出下列公式的真值表 PRQP)( RQPQP RQP A 000 100 010 110 001 101 011 111 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 成真指派：100，101，110，111 1重点辅导 例4 试求下面公式的主析取（主合取）范式，并写 出成真指派和成假指派。 ()()PQQP ()()PQQP ()PQQP ()()()PQQPPPQQ ()()()PQPQPQ 0,2,3 1 ()PQ 成真指派：00，10，11 成假指派：01 2重点辅导 例5 试证 PQQPPQ)( ()()QPPPQ 证明证明

2、)(QPPQ )()(QQPPQ )(QPPQ PQ PQ ()QPPQ 3重点辅导 例1 符号化下列命题 a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。 ),()()(yxHyWyxMx 4重点辅导 例2 证明 )( )( ),( )( )axA xB xx B xxA x 1)( )( ) 2)( )( ) 1) 3)( ) 4)( ) 3) 5)( ) 2)4) 6)( ) 5) xA xB xP A uB uUS xB xP B uUS A uT xA xEG 证明证明 5重点辅导 例1 求集合的幂集 )(xxP )(P ) ,(P ,

3、 , , 6重点辅导 例2 n 个元素的集合上，可以定义多少个关系？ 设集合X,Y, |X|=m, |Y|=n，可以定义多少个 从X到Y的函数？ )2( 2 n nm (|Y|X| ) 7重点辅导 例例3 对任意两个集合对任意两个集合A, B,试证试证 BABAA)( 证明证明 对于任意的x )(BAAx )(BxAxAxxx )(BAxAxxx )(BAxAxxx )(BxAxAxxx BxAxxx BAx 因为 x 是任意的,所以有 )()(BAxBAAxx的真值为T, BABAA)(因此 8重点辅导 例4 判断关系的性质 100 010 011 1 R M a bc 1 R R1 是自反

4、的、反对称、传递的。 , 1 ccbbbaaaR 9重点辅导 例5 求关系的闭包 ,cbaX ,ccbbaaR X IRRr)( ,cbbaR ,cbba,ccbbaa C RRRs)( ,bcabcbba 解： 10重点辅导 例5（续） ,cbaX ,cbbaR )3()2( )(RRRRt ,cacbba ,cacbba , )2( caR )3( R 11重点辅导 例7 设 A=1,2,3, 求出A上所有的等价关系 解：先求A的各种划分： 1 2 3 5 1 2 3 2 1 2 3 3 1 2 3 4 1 2 3 1 设对应于 i 的等价关系为Ri ,则： R1=, = = IA R2=

5、, IA R3=, IA R4=, IA R5=, , IA 12重点辅导 例8 画出哈斯图 RcbaP, a b c ,ca ,cb ,cba ,ba 13重点辅导 例9 求极大（小）元，最大（小）元、上（下） 界，上（下）确界 a b c d e f g h i jk 极大元：j,k 极小元:a,b,e 最大元：无 最小元：无 B=a,b,c,d,e,f,g 上界： h,i,j,k 下界：无 无上（下）确界 14重点辅导 例10 判断函数的类型 1 x 1 y 2 y 3 y 2 x 3 x 2 x 3 x 1 x 3 y 2 y 1 y 4 x 入 射 映射函数 双(入、满)射满射 4

6、y 1 y 2 x 3 x 1 x 2 y 3 y 4 y 1 x 2 x 3 x 1 y 2 y 3 y 15重点辅导 例11 求复合函数 ,3 , 2 , 1qpYX , baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 16重点辅导 例12 求复合函数 ,3 , 2 , 1qpYX ,baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 17重点辅导 例: 求幺元、零元、逆元 N, I, Q, R上的普通加法 + 和乘法 * +：幺元 0，a-1 = -a； *：幺元 1，零元 0， a-1 = 1/a； 命题公

7、式集合上的 和 ：幺元F，零元T ：幺元T，零元F 幂集P(S)上的和 ：幺元 ，零元S ：幺元S，零元 18重点辅导 例1 G 是一个有是一个有 15 条边的简单图，条边的简单图， 有有 13 条边，请问条边，请问 G 中有多少个结点中有多少个结点? G 解： 共有共有 15 + 13 = 28 条边，条边，GG 是一个完全图，它的是一个完全图，它的 结点数与结点数与 G 相同，设为相同，设为 n，根，根 据定理据定理4， GG n(n-1)/2 = 28 n = 8 19重点辅导 例3 请画出请画出 4 个顶点个顶点 3 条边的所有可能不同构条边的所有可能不同构 的无向简单图？的无向简单图

8、？ 20重点辅导 例4 若无向图若无向图 G 中恰有两个奇数度结点，则中恰有两个奇数度结点，则 这两个结点必是连通的。这两个结点必是连通的。 设 G 中两个奇数度结点分别为 u ,v。 若 u 与 v 不连通,则至少有两个连通 分支 G1 和 G2，u G1,v G2。 于是 G1 和 G2 各含一个奇数度结点， 这与握手原理的推论矛盾， 因此 u 与 v 必是连通的。 证明 试证试证 21重点辅导 例6 判断下列图哪些是 E 图、H图？ E E非 HH非 22重点辅导 例7 证明 设设 G 有有 r 个面，个面， 当当v = 3, e = 2时，时， 3v-6 显然成立。显然成立。 若若 e 3, 则每一个面至少由则每一个面至少由 3 条边围成，所以条边围成，所以 re32 er 3 2 eevrev 3 2 2 3 2 e v ev 3663 ve 设 G 是一个有 v 个结点, e 条边的连通简单平面 图，若 v 3，则有 v。 证 明 23重点辅导 例10 求图的最小生成树 A C B D E 1 2 3 4 5 6 7 A B CD E 12 46 24重点