资源描述：
《《离散数学》综合复习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.《离散数学》综合复习资料参考答案一、判断题1．命题逻辑中任何命题公式的主析取范式如果存在一定是唯一的。（）2．A、B、C是任意集合，如果AÍB及BÎC，则AÍC。（）3．整数集是不可数集。（）4．代数系统中，如果二元运算*是封闭的、可结合的，则是半群。（）5．任意平面图最多是四色的。（）6．A、B是任意命题公式，如果ØAÛØB，一定有AÛB。（）7．R是集合A上的二元关系，若R是反自反的，则Rc也是反自反的。（）8、命题逻辑中任何命题公式的主合取范式一定存在。（）9、A、B、C为任意集合，已知AÇB=AÇ
2、C，必须有B=C。（）10、自然数集合是无限的。（）11、命题联结词{Ø，Ù，Ú}是最小联结词组。（）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）他或者骑自行车上班，或者乘公
3、共汽车上班5．判断公式Ø(P«Q)®Ø(PÙQ)的类型（重言式、矛盾式、可满足）6．设代数系统，其中A={a,b,c}，*是A上的二元运算，运算表如下表，求该代数系统的幺元，所有可逆元素的逆元。*eabeeabaabe页脚.bbea1．设树T有17条边，有12片树叶，2个3度结点，求4度结点数。2．设A={1,2}，试构成集合P(A)´A。9.设*运算是有理数集Q上的二元运算，对于任意的a,bÎQ，a*b=a+b-a´b，问运算*是否可交换、可结合的？v1v2v4v310.试求下面有向图的强分图、单侧分图和弱分图。1
4、1、将下列命题符号化（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，判定*运算是否可结合的、可交换？v1v3v2v5v413、试求下面有向图的强分图、单侧分图和弱分图三、证明题1．设是一个独异点，并且对于G中的每一个元素x都有x*x=e，其中e是幺元，证明是一个阿贝
5、尔群。2．设G是具有n个结点的简单无向图，如果G中每对结点的度数之和均大于等于n-1，那么G是连通的。3．试用推理规则证明：A®B，(ØBÚC)ÙØC，Ø(ØAÙD)ÞØD页脚.1．若集合A上的关系R和S是自反、对称和传递的，试证明RÇS也是自反、对称和传递的。2．证明任何图中，度数为奇数的结点必定是偶数个。3．试证明：A®(BÙC),(E®ØF)®ØC,B®(AÙØS)ÞB®E4．若R是集合A上的相容关系，试证明RC也是A上的相容关系。5．证明任意一棵无向树至少有两片树叶（退化树除外）页脚.《离散数学》综合复习资料参考答案一
6、、判断题题目12345678910答案√××√√√√××√题目111213答案×√√二、基本题1、解：原式ÛØ(ØPÚQ)Ú(QÚØP)Û(PÙØQ)Ú(QÚØP)Û(PÙØQ)ÚØ(ØQÙP)Û(PÙØQ)ÚØ(PÙØQ)ÛT所以公式为重言式2、解：P(A)={Æ,{1},{{1}},{1,{1}}}P(A)-{Æ}={Æ,{1},{{1}},{1,{1}}}-{Æ}={{1},{{1}},{1,{1}}}3、解：设树根的度数为x，因为有17条边，所以结点数=17+1=18，由握手定理得：12*1+4*4+1*3+1*x=2
7、*17解得x=3所以树根度数为3。4、解：1)ØP®Q2)QÑR或(QÙØR)Ú(ØQÙR)5、解：原式Û((P®Q)Ù(Q®P))®(ØPÚØQ)ÛØØ((ØPÚQ)Ù(ØQÚP))Ú(ØPÚØQ)Û((ØPÚQ)Ù(ØQÚP))Ú(ØPÚØQ)Û(ØPÚQÚØPÚØQ)Ù(ØQÚPÚØPÚØQ)ÛTÙTÛT所以公式为重言式6、解：幺元为：e，a的逆元为b，b的逆元为a。7、解：设有x个4度结点，因为有17条边，所以结点数=17+1=18，由握手定理得：12*1+2*3+x*4=2*17解得：x=4，所以有4个4度结点。8、
8、解：P(A)={Æ,{1},{2},{1,2}}P(A)´A={<Æ,1>,<Æ,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}9、解：因为a*b=a+b-a´b=b+a-b´a=b*a所以运算是可交换的。a*(
