《离散数学》综合复习资料2423.pdf

《离散数学》综合复习资料 一、判断题 1、命题逻辑中任何命题公式的主析取范式如果存在一定是唯 一的。（ ） 2、 A、 B、C 是任意集合，如果 AÍ B 及 BÎ C，则AÍ C。（ ） 3、整数集是不可数集。（ ） 4、代数系统<S,*>中，如果二元运算*是封闭的、可结合的， 则<S,*>是半群。（ ） 5、任意平面图最多是四色的。（ ） 6、 A、B 是任意命题公式，如果 ØAÛØB，一定有AÛB。（ ） 7、R 是集合 A 上的二元关系，若 R 是反自反的，则 Rc 也是反 自反的。（ ） 8、命题逻辑中任何命题公式的主合取范式一定存在。（ ） 9、 A、 B、C 为任意集合，已知 AÇ B=AÇ C，必须有B=C。（ ） 10、自然数集合是无限的。（ ） 11、命题联结词{Ø ，Ù ，Ú }是最小联结词组。（ ） 第 1 页 共 1 页 12、任一无限集必含有可数子集。（ ） 13、有限整环必是域。（ ） 二、基本题 1、判断公式(P® Q)® (ØQ® ØP)的类型（重言式、矛盾式、 可满足） 2、 设 A={1,{1}}，计算P(A)-{Æ } 3、 设树 T 有 17 条边，除树根外有 12 片树叶，4 个 4 度结 点，1 个 3 度结点，求树根的度数。 4、 设 P：“天下雨”，Q：“他骑自行车上班”，R：“他乘 公共汽车上班”，试符号化下列命题：1）除非下雨，否则他就骑 自行车上班2）他或者骑自行车上班，或者乘公共汽车上班 5、 判断公式 Ø (P« Q)® Ø (PÙQ)的类型（重言式、矛盾 式、可满足） 6、 设代数系统<A,*>，其中A={a,b,c}，*是 A 上的二元运 算，运算表如下表，求该代数系统的幺元，所有可逆元素的逆 元。*eabeeabaabebbea 7、 设树 T 有 17 条边，有 12 片树叶，2 个 3 度结点，求 4 度 结点数。 8、 设 A={1,2}，试构成集合P(A)´ A。 9、 设*运算是有理数集 Q 上的二元运算，对于任意的 a,bÎ Q，a*b=a+b-a´ b，问运算*是否可交换、可结合的？ v1v2v4v3 第 1 页 共 1 页 10、试求下面有向图的强分图、单侧分图和弱分图。 11、将下列命题符号化（1）他即聪明又用功。（PÙQ） （2）仅当你走我才留下。（Q ® P）（3）所有老的国家选手都 是运动员。（ ("x)(R(x)® Q(x))）（4）某些教练是年老的，但是 健壮的。（($x)(P(x)ÙQ(x) ÙR(x))） 12、设A 是一个非空集合，*是 A 上的二元运算，对于任意 a,bÎ A，有a*b=b，判定*运算是否可结合的、可交换？ v1v3v2v5v4 13、试求下面有向图的强分图、单侧分图和弱分图 三、证明题 1、设<G,*>是一个独异点，并且对于 G 中的每一个元素x 都 有 x*x=e，其中 e 是幺元，证明<G,*>是一个阿贝尔群。 2、 设 G 是具有 n 个结点的简单无向图，如果 G 中每对结点 的度数之和均大于等于 n-1，那么G 是连通的。 3、 试用推理规则证明：A ® B，(ØBÚC) ÙØC，Ø (Ø AÙD)Þ Ø D 4、 若集合 A 上的关系 R 和 S 是自反、对称和传递的，试证 明RÇ S 也是自反、对称和传递的。 5、 证明任何图中，度数为奇数的结点必定是偶数个。 6、 试证明：A ® (BÙC),(E® ØF)® ØC,B® (AÙØS)Þ B® E 第 1 页 共 1 页 7、 若 R 是集合 A 上的相容关系，试证明 RC 也是A 上的相容 关系。 8、 证明任意一棵无向树至少有两片树叶（退化树除外） 《离散数学》综合复习资料参考答案 一、判断题题