《《离散数学》作业》由会员分享，可在线阅读，更多相关《《离散数学》作业（2页珍藏版）》请在金锄头文库上搜索。
1、 离散数学作业第 1 页 共 2 页离散数学离散数学作业作业 一、选择或填空一、选择或填空 1下列公式中哪些是永真式？( ) A.(PQ)(QR) B.P(QQ) C.(PQ)P D.P(PQ) 2设全体域 D 是正整数集合，确定下列命题的真值：A. xy (xy=y) ( ) B. xy(x+y=y) ( ) C. xy(x+y=x) ( ) D. xy(y=2x) ( ) 3有 n 个结点的树，其结点度数之和是( )。4举出集合 A 上的既是等价关系又是偏序关系的一 个例子。( ) 5群的等幂元是( )，有( )个。 6下面给出的集合中，哪一个不是前缀码( )。 A. a，ab，110，a
2、1b11 B. 01，001，000，1 C. 1，2，00，01，0210 D. 12，11，101，002，00117下列哪些公式为永真蕴含式？( )A.Q=QP B.Q=PQ C.P=PQ D.P(PQ)=P 8设 P：我生病，Q：我去学校，则下列命题可符号 化为( )。（1）若我生病，则我不去学校 (2) 当 且仅当我生病时，我才不去学校9任一有向图中，度数为奇数的结点有( )个。10集合 A 上的等价关系的三个性质是什么？( )11群A,*的等幂元有( )个，是( )， 零元有( )个。12一个图的欧拉回路是一条通过图中( )的回 路。 13设有下列公式，请问哪几个是永真蕴涵式?(
3、) A.P=PQ B. PQ=P C. PQ=PQ D.P(PQ)=Q E. (PQ)=P F. P(PQ)=P 14判断下列命题哪几个为正确？( ) A. ， B. ， C. D. E. a,ba,b,a,b 15设 a 是 10 阶群的生成元， 则 a4是( )阶元素， a3是( )阶元素。 16设 G 是一个哈密尔顿图，则 G 一定是( )。 A. 欧拉图 B. 树 C. 平面图 D. 连通图 17设 G 是一棵树，则 G 的生成树有( )棵。 A. 0 B. 1 C. 2 D. 不能确定 18设无向图 G 有 16 条边且每个顶点的度数都是 2， 则图 G 有( )个顶点。A. 10
4、B. 4 C. 8 D. 16 19，是三个集合，则下列哪几个推理正确： A. AB，BC= AC B. AB，BC= AB C. AB，BC= AC 20设 S=，上的关系 1，2 ， 2，1 ， 2，3 ， 3，4 ，求(1)R R o (2) R-1 。 21一棵无向树的顶点数 n 与边数 m 关系是( )。22设 A=3，6，9，A 上的二元运算*定义为： a*b=mina，b，则在独异点中，单位元是( )， 零元是( )。 23设 G 是有 n 个结点 m 条边的连通平面图，且有 k 个 面，则 k 等于:A. m-n+2 B. n-m-2 C. n+m-2 D. m+n+2。 24
5、设无向图 G 有 18 条边且每个顶点的度数都是 3，则 图 G 有( )个顶点。A. 10 B. 4 C. 8 D. 12 25、A，B，C 是三个集合，则下列哪个推理正 确?( ) (1) AB，BC AC (2) AB，BC AB (3) AB，BC AC 26、判断下列命题哪个正确?( ) (1) , (2) , (3) (4) = 27、设 T 是一棵树，则 T 是一个( ). (1) 欧拉图 (2) 哈密尔顿图 (3) 连 通图 28、下列公式中哪个不是蕴涵式?( ) (1) PPQ (2) PQ P (3) PQPQ (4) P(PQ)Q 39、下面给出的集合中，哪一个不是前缀码
6、( ). (1) a，ab，110，a1b11 (2) 01，001，000，1 (3) 1，2，00，01，0210 (4) 12，11，101，002，0011 30 6 阶有限群的任何子群一定不是( ). (1) 2 阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 31、在有 n 个顶点的连通图中，其边数( ).(1) 最多有 n-1 条 (2) 至少有 n-1 条 (3) 最多有 n 条 (4) 至少有 n 条 32、下列哪一种图不一定是树?( ) (1) 无简单回路的连通图 (2) 有 n 个顶点 n-1 条边的连通图 (3) 每对顶点间都有通路的图 (4) 连 通但删去一条边便
7、不连通的图 33、下面给出的集合中，哪一个是前缀码?( )离散数学作业第 2 页 共 2 页(1) 0，10，110，101111 (2) 01，001，000，1 (3) b，c，aa，ab，aba (4) 1，11，101，001，0011 34、有限布尔代数的元素的个数一定等于( ). (1) 偶数 (2) 奇数 (3) 4 的倍 数 (4) 2 的正整数次幂 35、在自然数集 N 上，下列哪种运算是可结合的?( ) (1) a*b=a-b (2) a*b=maxa,b (3) a*b=a+2b (4) a*b=|a-b| 36、判断下列命题哪个为真?( ) (1) A-B=B-A A=
8、B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若 A 的一个元素属于 B，则 A=B二、求下列各公式的主析取范式和主合取范式二、求下列各公式的主析取范式和主合取范式 1 PQ 2 Q( PR) 3 PQ 4 (PQ) (RP) 5 PQ 6 Q(PR) 7 (PQ)(PR)三、证明三、证明 1PQ， PR, QS = RS 2A(CB)，BA，DC = AD3PQ，QR，R，SP=S 4BD，(EF)D，E=B 5A(BC)，C(DE)，F(DE), A=BF 6、A(BC)，C(DE)，F(D E),A BF. 7、BD，(EF)D，E B. 8、A(CB)，B
9、A，DC A D. 9、PQ，QR，RS P.四、设，是三个集合，证明四、设，是三个集合，证明 1(AB)(AC)=A(BC) 2AB=AC，B=C，则 C=BAA3A(BC)(AB)(AC) 4A(BC)(AB)C 5(AB)(AC)=A(BC) 五、证明五、证明 1设 e 和 0 是关于 A 上二元运算*的单位元和零元， 如果|A|1，则 e0。 2任一图中度数为奇数的结点是偶数个。 3设群G，除单位元外每个元素的阶均为 2， 则G，是交换群。 4在一个连通简单无向平面图 G=V，E，F中若|V|3，则 |E|3|V6。5单位元有惟一逆元。6设是一个群，则对于a,bG，必有惟一的 xG，使
10、得 ax=b。7设代数系统是一个群，则 G 除单位元以外无其 它等幂元。8若连通简单无向平面图 G 有 n 个结点，m 条边，k 个 面，且每个面至少由 k(k3)条边围成，则 mk(2)(2)。 9证明在元素不少于两个的群中不存在零元。 10素数阶循环群的每个非单位元都是生成元。 11设 G=V，E是一个连通且|V|=|E|+1 的图，则 G 中有一个度为 1 的结点。 12给定无向连通简单平面图 G=，且|V|=6, |E|=12, 则对于任意 fF, deg(f)=3。 13证明在一个群中单位元是惟一的。 14在一个群G，*中，若 G 中的元素 a 的阶是 k， 即 | a |=k，则 a-1的阶也是 k。 15若有 n 个结点的连通图中恰有 n-1 条边，则图中至 少有一个结点度数为 1。 16、设 e 和 0 是关于 A 上二元运算*的单位元 和零元，如果|A|1，则 e0. 17、设 T=是一棵树，若|V|1，则 T 中至少存在两片树叶. 18、若 n 阶连通图中恰有 n-1 条边，则图中至 少有一个顶点度数为 1. 19、证明对于连通无向简单平面图，当边数 e30 时，必存在度数4 的顶点.
