一、判断题
1. 命题逻辑中任何命题公式的主析取范式如果存在一定是唯一的。（ 2. A、B、C是任意集合，如果AyB及BwC,则AyC。（ 3. 整数集是不可数集。（
）
）
）
）
4. 代数系统vS”*＞中，如果二元运算*是封闭的、可结合的，则＜S,*＞是半群。（ 5. 任意平面图最多是四色的。（
）
）
）
6. A、B是任意命题公式，如果「Ao「B, —定有AoB。（
7. R是集合A上的二元关系，若R是反自反的，则“也是反自反的。（ 8. 命题逻辑中任何命题公式的主合取范式一定存在。（ 9. A、B、C为任意集合，已知AnB=AnC,必须有B二C。（ 10. 自然数集合是无限的。（
） ）
）
）
11＞命题联结词{「，A, ▽}是最小联结词组。（ 12、 任一无限集必含有可数子集。（ 13、 有限整环必是域。（
）
）
二、基本题
1. 判断公式（PTQ）T（「QT「P）的类型（重言式、矛盾式、可满足） 2. 设 A={1,{1}},计算 P（A）-{0}
3. 设树T有17条边，除树根外有12片树叶，4个4度结点，1个3度结点，求树根的 度
数。
4. 设P： “天下雨”，Q： “他骑自行车上班”，R： “他乘公共汽车上班”，试符号化
下列 命题：
1） 除非下雨，否则他就骑自行车上班 2） 他或者骑自行车上班，或者乘公共汽车上班
5. 判断公式「（P^Q）T「（PAQ）的类型（重言式、矛盾式、可满足）
6. 设代数系统＜A,*＞,其中A={a,b,c}, *是A上的二元运算，运算表如下表，求该代数 系统
的幺元，所有可逆元素的逆元。
* e a
e e a
a a b
b b e
7. 设树T有17条边，有12片树叶，2个3度结点，求4度结点数。
& 设A二{1,2},试构成集合P(A)xAo
9.设*运算是有理数集Q上的二元运算，对于任意的a,bwQ, a*b=a+b-axb,问运算*是 否可交
换、可结合的？
11＞将下列命题符号化
(1) 他即聪明又用功。(PAQ) (2) 仅当你走我才留下。(QTP)
(3) 所有老的国家选手都是运动员。((VX)(R(X)TQ(X))) (4) 某些教练是年老的，但是健壮的。((3X)(P(X)AQ(X) AR(X)))
12＞设A是一个非空集合，*是A上的二元运算，对于任意a,beA,有a*b=b,判定*运 算是否
可结合的、可交换？
三、证明题
1. 设＜G,*＞是一个独界点，并且对于G中的每一个元素x都有x*x=e,其中e是幺元， 证
明＜G,*＞是一个阿贝尔群。
2. 设G是具有n个结点的简单无向图，如果G屮每对结点的度数Z和均大于等于n-1, 那
么G是连通的。
3. 试用推理规则证明：A—B, (―IBVC) A—iC, ―i(—AAD)=＞ —I D
4. 若集合A上的关系R和S是自反、对称和传递的，试证明RcS也是自反、对称和传 递
的。
5. 证明任何图中，度数为奇数的结点必定是偶数个。 6. 试证明：A T(B/\\C),(ET-!F)T「CBT(AA-IS)=>BTE
7. 若R是集合A上的相容关系，试证明L也是A上的相容关系。
&证明任意一棵无向树至少有两片树叶(退化树除外)
《离散数学》综合复习资料参考答案
一、判断题
题目 答案 题目 答案 二、基本题
1> 解：原式O
O(PA-IQ) V-I (PA->Q)«T
1 V 11 X 2 X 12 3 X 4 V 5 V 6 V 7 V 8 X 9 X 10 V 13 V 所以公式为重言式
2、 解：P(A)={0,{1},{{1}}, {1,{1}}}
P(A)-{0}= {0,{1},{{1}}, {1,{1}}}-{0}={{1},{{1}}, {141}}}
3、 解：设树根的度数为X,因为有17条边，所以结点数=17+1=18,由握手定理得:
12*1+4*4+1*3+1*X=2*17 解得 x=3
所以树根度数为3。
4、 解：1) 「PTQ 2) QV R 或(QA-IRWQAR)
5、 解：原式u>((P—Q.)A (Q.— P)) ―> (—Pv―Q) ―I―((―PVQ.)A (—Q.vP)) v (―i Pv―Q.) O (HPVCDA HQvPjJvf-! PviQ) «(-iPvQv-i PV-IQ)A (-IQVPV-I PV-IQ) oT 人 ToT
所以公式为重言式
6、 解：幺元为：e, a的逆元为b, b的逆元为3。
7、 解：设有x个4度结点，因为有17条边，所以结点数=17+1=18,由握手定理得:
12*l+2*3+x*4=2*17解得：x=4,所以有4个4度结点。 8、 解：P(A) = {0,{1},{2},{1,2}}
P(A)XA={<0/1>,<0,2>Z<{1},1>,<{1},2>,<{2},1>,<{2}/2>,<{1,2},1>,<{1,2}/2>}
9、 解：因为 a*b= a+b-axb=b+a-bxa=b*a
所以运算是可交换的。
a*(b*c)=a+(b*c)-ax(b*c)=a+(b+c-bxc)-ax(b+c-bxc)=a+b+c-bxc-axb-axc+axbxc (a*b)*c=(a+b-axb)+c-(a+b-axb) xc=a+b+c-axb-axc-bxc+axbx c
所以 a*(b*c)= (a*b)*c
10、 解：强分图由｛v\"｛v2｝,｛v3｝,｛v4｝导出的子图
单侧分图由｛vl,v2,v3｝,｛v2,v3,v4｝导出的子图 弱分图由｛vl,v2,v3,v4｝#出的子图
11、 (1) (PAQ)
(2) (QTP)
(3) ((VX)(R(X)TQ(X))) (4) ((3X)(P(X)AQ(X) AR(X))) 12＞ 解：a*(b*c)=a*c=c
(a*b)*c=b*c=c
所以a*(b*c)= (a*b)*c,即*运算是可结合的。
av＞b时,a*b=boa=b*a,所以不可交换
13、解：强分图由｛vl,v2,v3,v4｝和｛v5｝导出的子图
由｛vl,v2,v3,v4,v5｝^出的子图是单侧分图，也是弱分图 三、证明题
1、 设＜G,*＞是一个独界点，并且对于G中的每一个元素x都有x*x=e,其中e是幺元， 证明
＜G/＞是一个阿贝尔群。
证明：＜G,*＞是独异点，*运算封闭，且满足结合律，且有幺元， 只须证vG,*＞中每个元素都有逆元，并且*运算满足交换律。
因为对于G中的每一个元素x都有x*x=e,所以x的逆元就是x,故vG,*＞是群。 对于Vx,yw
G,则 x*ye G,
所以(x*y)*(x*y)=e,而(x*y)*(y*x)=x*(y*y)*x=x*e*x=x*x=e
故(x*y)*(x*y)= (x*y)*(y*x),所以 x*y=y*x,即*运算满足交换律。 所以vG,*＞是一个阿贝尔群。
2、 设G是具有n个结点的简单无向图，如果G中每对结点的度数之和均大于等于n-1, 那么
G是连通的。
证明：假设G不连通，则G至少有两个连通分支G1,G2, 设G1屮有nl个结点，G2屮有n2个结点，则nl+n2＜=no
从 G1 和 G2 中各任取一点 u 和 v,则 deg(u)＜=nl-l, deg(v)＜=n2-l,
则deg(u)+deg(v)＜=nl-l+n2-l＜=n-2,与G中每对结点的度数之和均大于等于n-1矛盾, 所以G是连通的。
P(附加前提)
3、试用推理规则证明：ATB, (^BVC) A^C, HI AAD)^ D
证明(1)D
T(2)E
⑵AAD)
(3) AviD
(8) (―i BA―C) v(i CAC) T(7)E
(9) (―i BA―C) T(8)E
⑸ATB
T(4)(5)l
(7) (iBvC) AiC (10)-IB
T(6)(10)l
所以 A —B, (—BvC) A—C, -1(-1 AAD)=> ―i D
4、 若集合A上的关系R和S是自反、对称和传递的，试证明RcS也是自反、对称和传的。
证明：1)自反性
对X/awA, R’S 具有自反性，故 2) 对称性 若 a,be A,有 又因为R,S具有对称性，故 3) 传递性 若 a,b,ce A, 有 则因为R,S具有传递性，所以va,c>wR且 递 5、 证明任何图屮，度数为奇数的结点必定是偶数个。 证明：设V1,V2分别是G中奇数度数和偶数度数的结点集，则由握手定理， ^deg（v） + ^deg（v） = ^deg（v） = 2\\E\\ v^Vl v^V2 由于工dcgW）是偶数之和，必为偶数，而2|E|是偶数, M2 故得^deg（v）是偶数，所以|V1|是偶数。 Ml 6、试证明：AT（B人CUET-^TrCBTg人一6）=>BTE 证明:(1)B P（附加前提） (2) BT(AA「S) P (3) AA-.S T(l)(2)l (4)A T(3)l (5) AT(BAC) P (6) BAC T(4)(5)l (7)C T(6)l (8) (ET-IF)T「C P （9）「（ET「F） T(7)(8)l (10) ^(-IEV-IF) T(9)E (11)EAF T(10)E (12)E T(ll)l (13) BTE CP 7、若R是集合A上的相容关系，试证明2也是A上的相容关系。 证明：（本题答案不唯 一）即证明L具有自反性、对称性 因为R相容关系，所以R具有自反性、对称性 1） 自反性 对X/awA, R具有自反性，故 若 a’bwA,有 又因为R有对称性，故 8、证明任意一棵无向树至少有两片树叶（退化树除外） 证明：设T有v个结点e条边，则e二v・l 1) 若无树叶，即对任意vi有d(vi)>=2 则 Ed(vi)=2e>=2v, 即e>v与树定义孑盾 2) 若有一片树叶， 则 Zd(vi)=2e>=2(v-l)+l=2v-l 与2e=2v-2矛盾。 因篇幅问题不能全部显示，请点此查看更多更全内容