离散数学a卷魏霞

第一篇：离散数学a卷魏霞

离散数学考试试题（A卷及答案）

一、(10分)判断下列公式的类型(永真式、永假式、可满足式)? 1)((PQ)∧Q)((Q∨R)∧Q) 2)((QP)∨P)∧(P∨R) 3)((P∨Q)R)((P∧Q)∨R) 解：1)永真式;2)永假式;3)可满足式。

二、(8分)个体域为{1，2}，求xy(x+y=4)的真值。

解：xy(x+y=4)x((x+1=4)∨(x+2=4))

((1+1=4)∨(1+2=4))∧((2+1=4)∨(2+1=4)) (0∨0)∧(0∨1) 1∧10

三、(8分)已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少?A到B的函数数是多少?

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

四、(10分)已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|=20，|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|=55，|A|+|B|+|C|=70/0.5=140。

由容斥原理，得

|A∪B∪C|=|A|+|B|+|C|―|A∩B|―|A∩C|―|B∩C|+|A∩B∩C| 所以

|A∩B∩C|=75-|A∪B∪C|=75-(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|-2|A∩B∩C|)+|A∩B∩C|=75-140+55+20=10 没有乘坐过其中任何一种的儿童共10人。

六、(12分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

1 x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七(10分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。

证明：1)先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。

2)再证h是单射。

、∈A×C，若h()=h()，则=，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。 综合1)和2)，h是双射。

八、(12分)是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。

证明：1)a,b∈G，ab=a*u-1*b∈G，运算是封闭的。

2)a,b,c∈G，(ab)c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a(bc)，运算是可结合的。 3)a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。

4)a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。 所以也是个群。

九、(10分)已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

解：D的邻接距阵A和可达距阵P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0

1 0 1 0 0

0 0 1 0 0

P=

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

十、(10分)求叶的权分别为

2、

4、

6、

8、

10、

12、14的最优二叉树及其权。

解：最优二叉树为

权=148

离散数学考试试题(B卷及答案)

一、(10分)求命题公式(P∧Q)(PR)的主合取范式。

解：(P∧Q)(PR)((P∧Q)(PR))∧((PR)(P∧Q))((P∧Q)∨(P∧R))∧((P∨R)∨(P∨Q)) (P∧Q)∨(P∧R) (P∨R)∧(Q∨P)∧(Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M1∧M3∧M4∧M5

二、(8分)叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F(x)：x是一个人。G(x)：x要死的。A：苏格拉底。 命题符号化为x(F(x)G(x))，F(a)G(a) 证明：

(1)x(F(x)G(x)) P (2)F(a)G(a) T(1),US (3)F(a) P (4)G(a) T(2)(3),I

三、(8分)已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) 证明：∵x A∩(B∪C) x A∧x(B∪C)

 x A∧(xB∨xC)

( x A∧xB)∨(x A∧xC)  x(A∩B)∨x A∩C  x(A∩B)∪(A∩C)

∴A∩(B∪C)=(A∩B)∪(A∩C)

四、(10分)已知R和S是非空集合A上的等价关系，试证：1)R∩S是A上的等价关系;2)对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2)因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分) 设A={a，b，c，d}，R是A上的二元关系，且R={，，，}，求r(R)、s(R)和t(R)。

解 r(R)=R∪IA={，，，，，，，} s(R)=R∪R={，，，，，} R={，，，} R={，，，} R={，，，}=R

t(R)=R={，，，，，，，，} i1i

4232-

1六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()=。证明h是双射。

证明：1)先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()==，所以h是满射。

2)再证h是单射。

、∈A×C，若h()=h()，则= ，所以f(a1)=f(a2)，g(c1)=g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1=a2，c1=c2，所以=，所以h是单射。

综合1)和2)，h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。

证明： a,b∈H有b∈H，所以a*b∈H。 a∈H，则e=a*a∈H

4 -1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*(b)∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。

八、(10分)设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G=,A={a,b,c},*的运算表为：(写过程，7分)

(1)G是否为阿贝尔群?

(2)找出G的单位元;(3)找出G的幂等元(4)求b的逆元和c的逆元 解：(1)(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群

(2)因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a (3)因为a*a=a 所以G的幂等元是a (4)因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为

2、

4、

6、

8、

10、

12、14的最优二叉树及其权。

解：最优二叉树为

权=148 5

第二篇：离散数学考试试题(A、B卷及答案)test7

离散数学考试试题(A卷及答案)

一、(10分)证明(A∨B)(P∨Q)，P，(BA)∨PA。

证明：(1)(A∨B)(P∨Q)

P (2)(P∨Q)(A∨B)

T(1)，E (3)P

P (4)A∨B

T(2)(3)，I (5)(BA)∨P

P (6)BA

T(3)(5)，I (7)A∨B

T(6)，E (8)(A∨B)∧(A∨B)

T(4)(7)，I (9)A∧(B∨B)

T(8)，E (10)A

T(9)，E

二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：

(1)甲和乙只有一人参加; (2)丙参加，丁必参加; (3)乙或丁至多参加一人; (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。

解

符号化命题，设A：甲参加了比赛;B：乙参加了比赛;C：丙参加了比赛;D：丁参加了比赛。 依题意有，

(1)甲和乙只有一人参加，符号化为AB(A∧B)∨(A∧B); (2)丙参加，丁必参加，符号化为CD; (3)乙或丁至多参加一人，符号化为(B∧D); (4)丁不参加，甲也不会参加，符号化为DA。 所以原命题为：(AB)∧(CD)∧((B∧D))∧(DA) ((A∧B)∨(A∧B))∧(C∨D)∧(B∨D)∧(D∨A) ((A∧B∧C)∨(A∧B∧C)∨(A∧B∧D)∨(A∧B∧D))∧((B∧D)∨(B∧A)∨(D∧A)) (A∧B∧C∧D)∨(A∧B∧D)∨(A∧B∧C∧D)T

但依据题意条件，有且仅有两人参加竞赛，故A∧B∧C∧D为F。所以只有：(A∧B∧C∧D)∨(A∧B∧D)T，即甲、丁参加了围棋比赛。

三、(10分)指出下列推理中，在哪些步骤上有错误?为什么?给出正确的推理形式。 (1)x(P(x)Q(x))

P

1 (2)P(y)Q(y)

T(1)，US (3)xP(x)

P (4)P(y)

T(3)，ES (5)Q(y)

T(2)(4)，I (6)xQ(x)

T(5)，EG 解

(4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。

正确的推理过程为：

(1)xP(x)

P (2)P(c)

T(1)，ES

(3)x(P(x)Q(x))

P (4)P(c)Q(c)

T(3)，US (5)Q(c)

T(2)(4)，I (6)xQ(x)

T(5)，EG

四、(10分)设A={a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。

解

设R={，，，}，则 因为R，R不自反; 因为∈R，R不反自反;

因为∈R，R，R不对称; 因为∈R，∈R，R不反对称;

因为∈R，∈R，但R，R不传递。

五、(15分)设函数g：A→B，f：B→C，

(1)若fg是满射，则f是满射。 (2)若fg是单射，则g是单射。

证明

因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。

(1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)=z，即f(g(x))=z。由g：A→B可知g(x)∈B，于是有y=g(x)∈B，使得f(y)=z。因此，f是满射。

(2)对任意的x

1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、(15分)设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得TR且R，证明T是一个等价关系。

证明

因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。

若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。

2 若∈T，∈T，即∈R且∈R，∈R且∈R，因R传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。

所以，T是A上的等价关系。

七、(15分)若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b1∈H。 -证明

必要性：对任意的a、b∈H，由是的子群，必有b1∈H，从而a*b1∈H。

-

-充分性：由H非空，必存在a∈H。于是e=a*a1∈H。

-任取a∈H，由e、a∈H得a1=e*a1∈H。

-

-对于任意的a、b∈H，有a*b=a*(b1)1∈H，即a*b∈H。

-

-又因为H是G非空子集，所以*在H上满足结合律。 综上可知，是的子群。

八、(15分)(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗?

证明

(1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

uwv

3 离散数学考试试题(B卷及答案)

一、(15分)设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。

(1)写出F在全功能联结词组{}中的命题公式。 (2)写出F的主析取范式与主合取范式。

解

(1)设A：开关A关闭;B：开关B关闭;C：开关C关闭;F=(A∧C)∨(B∧C)。 在全功能联结词组{}中：

A(A∧A)AA A∧C( A∧C)( AC)(AC)(AC)

A∨B(A∧B)(( AA)∧(BB))( AA)(BB) 所以

F((AC)(AC))∨((BC)(BC)) (((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC))) (2)F(A∧C)∨(B∧C)

(A∧(B∨B)∧C)∨((A∨A)∧B∧C) (A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C) m3∨m5∨m7

主析取范式 M0∧M1∧M2∧M4∧M6

主合取范式

二、(10分)判断下列公式是否是永真式? (1)(xA(x)xB(x))x(A(x)B(x))。 (2)(xA(x)xB(x))x(A(x)B(x)))。 解

(1)(xA(x)xB(x))x(A(x)B(x)) (xA(x)∨xB(x))x(A(x)B(x)) (xA(x)∨xB(x))∨x(A(x)∨B(x)) (xA(x)∧xB(x))∨xA(x)∨xB(x) (xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(x)∨xB(x)) x(A(x)∨A(x))∨xB(x) T

所以，(xA(x)xB(x))x(A(x)B(x))为永真式。

(2)设论域为{1，2}，令A(1)=T;A(2)=F;B(1)=F;B(2)=T。

则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真;而由于A(1)B(1)为假，所以x(A(x)B(x))也为假，因此公式(xA(x)xB(x))x(A(x)B(x))为假。该公式不是永真式。

三、(15分)设X为集合，A=P(X)-{}-{X}且A≠，若|X|=n，问 (1)偏序集是否有最大元?

4 (2)偏序集是否有最小元?

(3)偏序集中极大元和极小元的一般形式是什么?并说明理由。 解

偏序集不存在最大元和最小元，因为n>2。

考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|=n，则第n-1层是X的n-1元子集，第n层是X。偏序集与偏序集相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X;而极大元恰好是比X少一个元素，即X-{x}，x∈X。

四、(10分)设A={1，2，3，4，5}，R是A上的二元关系，且R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解

r(R)=R∪IA={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)=R∪R1={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} -R2={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}=R2

t(R)=Ri={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，i1<5，5>}。

五、(10分)设函数g：A→B，f：B→C，

(1)若fg是满射，则f是满射。 (2)若fg是单射，则g是单射。

证明

因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。

(1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)=z，即f(g(x))=z。由g：A→B可知g(x)∈B，于是有y=g(x)∈B，使得f(y)=z。因此，f是满射。

(2)对任意的x

1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、(10分)有幺元且满足消去律的有限半群一定是群。

证明

设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。

考虑a，a2，…，ak，…。因为G只有有限个元素，所以存在k>l，使得ak=al。令m=k-l，有al*e=al*am，其中e是幺元。由消去率得am=e。

于是，当m=1时，a=e，而e是可逆的;当m>1时，a*am-1=am-1*a=e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。

七、(20分)有向图G如图所示，试求： (1)求G的邻接矩阵A。

5 (2)求出A

2、A3和A4，v1到v4长度为

1、

2、3和4的路有多少?

(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。

解

(1)求G的邻接矩阵为：

00A00101011

101100(2)由于

00A200111022010

1 A302111020111203220

4 A4120301012313 2322所以v1到v4长度为

1、

2、3和4的路的个数分别为

1、

1、

2、3。 (3)由于

00TAA000002131212TAA

21011102132110 2121再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。

00(4)因为B4AA2A3A40000以求可达矩阵为P00111111。

11111110100110+

101010001110



2010

+

1110



01102120312204+

2120320101231323220

000741



747

，所

747



43400(5)因为PPT0011101111∧1111111100001110=01110111000111，所以{v1}，{v2，v3，v4}构成G的强分图。

111111 6

第三篇：离散数学

离散数学试题(A卷答案)

一、(10分)

(1)证明(PQ)∧(QR)(PR) (2)求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 解：(1)因为((PQ)∧(QR))(PR) ((P∨Q)∧(Q∨R))∨(P∨R) (P∧Q)∨(Q∧R)∨P∨R (P∧Q)∨((Q∨P∨R)∧(R∨P∨R)) (P∧Q)∨(Q∨P∨R) (P∨Q∨P∨R)∧(Q∨Q∨P∨R) T 所以，(PQ)∧(QR)(PR)。

(2)(P∨Q)R(P∨Q)∨R(P∧Q)∨R (P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M2∧M4∧M6 m0∨m1∨m3∨m5

所以，其相应的成真赋值为000、00

1、0

11、10

1、111：成假赋值为：0

10、100、110。

二、(10分)分别找出使公式x(P(x)y(Q(y)∧R(x，y)))为真的解释和为假的解释。

解：设论域为{1，2}。

若P(1)=P(2)=T，Q(1)=Q(2)=F，R(1，1)=R(1，2)=R(2，1)=R(2，2)=F，则 x(P(x)y(Q(y)∧R(x，y))) x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2)))) (P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) (T((F∧F)∨(F∧F)))∧(T((F∧F)∨(F∧F))) (TF)∧(TF) F 若P(1)=P(2)=T，Q(1)=Q(2)=T，R(1，1)=R(1，2)=R(2，1)=R(2，2)=T，则 x(P(x)y(Q(y)∧R(x，y))) x(P(x)((Q(1)∧R(x，1))∨(Q(2)∧R(x，2)))) (P(1)((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)((Q(1)∧R(2，1))∨(Q(2)∧R(2，2)))) (T((T∧T)∨(T∧T)))∧(T((T∧T)∨(T∧T))) (TT)∧(TT) T

三、(10分)

在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢做汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

解

论域：所有人的集合。A(x)：x喜欢步行;B(x)：x喜欢坐汽车;C(x)：x喜欢骑自行车;则推理化形式为：

x(A(x)B(x))，x(B(x)∨C(x))，xC(x)xA(x) 下面给出证明： (1)xC(x)

P (2)xC(x)

T(1)，E (3)C(c)

T(2)，ES (4)x(B(x)∨C(x))

P (5)B(c)∨C(c)

T(4)，US (6)B(c)

T(3)(5)，I (7)x(A(x)B(x))

P (8)A(c)B(c)

T(7)，US (9)A(c)

T(6)(8)，I (10)xA(x)

T(9) ，EG

四、(10分)

下列论断是否正确?为什么? (1)若A∪B=A∪C，则B=C。 (2)若A∩B=A∩C，则B=C。 (3)若AB=AC，则B=C。

解 (1)不一定。例如，令A={1}，B={1，2}，C={2}，则A∪B=A∪C，但B=C不成立。 (2)不一定。例如，令A={1}，B={1，2}，C={1，3}，则A∩B=A∩C，但B=C不成立。 (3)成立。因为若AB=AC，对任意的x∈B，当x∈A时，有x∈A∩BxABxAC=(A∪C)-(A∩C)x∈A∩Cx∈C，所以BC;当xA时，有xA∩B，而x∈Bx∈A∪B，所以x∈A∪B-A∩B=ABx∈AC，但x A，于是x∈C，所以BC。

同理可证，C B。

因此，当AB=AC时，必有B=C。

五、(10分)若R是集合A上的自反和传递关系，则对任意的正整数n，R=R。

证明 当n=1时，结论显然成立。设n=k时，Rk=R。当n=k+1时，Rk+1=Rk*R=R*R。下面由R是自反和传递的推导出R*R=R即可。

由传递性得R*RR。另一方面，对任意的∈R，由R自反得∈R，再由关系的复合得∈R*R，从而RR*R。因此，R=R*R。

由数学归纳法知，对任意的正整数n，Rn=R。

n

六、(15分)设函数f：R×RR×R，f定义为：f()=。

(1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。

(4)求复合函数f-1f和ff。

证明 (1)对任意的x，y，x1，y1∈R，若f()=f()，则=，x+y=x1+y1，x-y=x1-y1，从而x=x1，y=y1，故f是单射。

(2)对任意的∈R×R，令x=uw2uw2-

1，y=

uw2，则f()=<

uw2+

uw2，

uw2->=，所以f是满射。

uw2-1(3)f()=<-1，

uw2>。

xyxy2xy(xy)2(4)ff()=f(f())=f()=<-1-1

，>= ff()=f(f())=f()==<2x，2y>。

七、(15分)设X={1，2，3，4}，R是X上的二元关系，R={<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R的关系图。 (2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为：

10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的;由于对角线上存在非0元，R不是反自反的;由于矩阵不对称，R不是对称的;

经过计算可得 102M(R)111011101100M(R)，所以R是传递的。 00

八、(10分)若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b-1∈H。

3 证明 必要性：对任意的a、b∈H，由是的子群，必有b-1∈H，从而a*b-1∈H。 充分性：由H非空，必存在a∈H。于是e=a*a∈H。 任取a∈H，由e、a∈H得a-1=e*a-1∈H。

对于任意的a、b∈H，有a*b=a*(b)∈H，即a*b∈H。 又因为H是G非空子集，所以*在H上满足结合律。 综上可知，是的子群。

九、(10分)给定二部图G=，且|V1∪V2|=m，|E|=n，证明n≤m/4。

证明 设|V1|=m1，则|V2|=m-m1，于是n≤m1(m-m1)=m1m-m22

2-

1-1

-1

m12。因为(m2m1)20，即4mm1m1，所以n≤m2/4。

4 离散数学试题(B卷答案)

一、(20分)用公式法判断下列公式的类型： (1)(P∨Q)(PQ) (2)(PQ)(P∧(Q∨R)) 解：(1)因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q) m1∨m2∨m3 M0

所以，公式(P∨Q)(PQ)为可满足式。

(2)因为(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R))

(P∨Q)∨(P∧Q∧R))

(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R)

(P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

所以，公式(PQ)(P∧(Q∨R))为可满足式。

二、(15分)在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。

Q(x)：x是勤奋的;x是科学家;C(x)：解：论域：所有人的集合。H(x)：x是身体健康的;S(x)：x是事业获得成功的人;F(x)：x是事业半途而废的人;则推理化形式为：

x(S(x)Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧H(x))

x(C(x)∨F(x)) 下面给出证明：

(1)x(S(x)∧H(x))

P (2)S(a)∧H(a)

T(1)，ES (3)x(S(x)Q(x))

P (4)S(a)Q(a)

T(1)，US (5)S(a)

T(2)，I (6)Q(a)

T(4)(5)，I (7)H(a)

T(2)，I (8)Q(a)∧H(a)

T(6)(7)，I

5 (9)x(Q(x)∧H(x)C(x))

P (10)Q(a)∧H(a)C(a)

T(9)，Us (11)C(a)

T(8)(10)，I (12)xC(x)

T(11)，EG (13)x(C(x)∨F(x))

T(12)，I

三、(10分)设A={，1，{1}}，B={0，{0}}，求P(A)、P(B)-{0}、P(B)B。 解

P(A)={，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)-{0}={，{0}，{{0}}，{0，{0}}-{0}={，{0}，{{0}}，{0，{0}} P(B)B={，{0}，{{0}}，{0，{0}}{0，{0}}={，0，{{0}}，{0，{0}}

四、(15分)设R和S是集合A上的任意关系，判断下列命题是否成立? (1)若R和S是自反的，则R*S也是自反的。 (2)若R和S是反自反的，则R*S也是反自反的。 (3)若R和S是对称的，则R*S也是对称的。 (4)若R和S是传递的，则R*S也是传递的。 (5)若R和S是自反的，则R∩S是自反的。 (6)若R和S是传递的，则R∪S是传递的。

解

(1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。

(2)不成立。例如，令A={1，2}，R={<1，2>}，S={<2，1>}，则R和S是反自反的，但R*S={<1，1>}不是反自反的。

(3)不成立。例如，令A={1，2，3}，R={<1，2>，<2，1>，<3，3>}，S={<2，3>，<3，2>}，则R和S是对称的，但R*S={<1，3>，<3，2>}不是对称的。

(4)不成立。例如，令A={1，2，3}，R={<1，2>，<2，3>，<1，3>}，S={<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S={<1，3>，<1，1>，<2，1>}不是传递的。

(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。

五、(15分)令X={x1，x2，…，xm}，Y={y1，y2，…，yn}。问 (1)有多少个不同的由X到Y的函数?

(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射? (3)当n、m满足什么条件时，存在双射，且有多少个不同的双射?

解

(1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共n个。

(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有Cnm!=n(n-1)(n―m―1)个。

(3)显然当|m|=|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，

6 mm故不同的双射有m!个。

六、(5分)集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个? 解

X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。

七、(10分)若是群，则对于任意的a、b∈G，必有惟一的x∈G使得a*x=b。

证明 设e是群的幺元。令x=a-1*b，则a*x=a*(a-1*b)=(a*a-1)*b=e*b=b。所以，x=a-1*b是a*x=b的解。

若x∈G也是a*x=b的解，则x=e*x=(a*a)*x=a*(a*x)=a*b=x。所以，x=a*b是a*x

-

1-1

-1

-1=b的惟一解。

八、(10分)给定连通简单平面图G=，且|V|=6，|E|=12。证明：对任意f∈F，d(f)=3。 证明

由偶拉公式得|V|-|E|+|F|=2，所以|F|=2-|V|+|E|=8，于是d(f)=2|E|=24。若存在f∈

fFF，使得d(f)>3，则3|F|<2|E|=24，于是|F|<8，与|F|=8矛盾。故对任意f∈F，d(f)=3。

第四篇：离散数学自学

学习体会

专业：计算机 姓名：范文芳 学号： 成绩： 院校：

离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。

学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础;其二是在离散数学的学习过程中，培训自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。但是由于离散数学的离散性、知识的分散性和处理问题的特殊性，使部分学生在刚刚接触离散数学时，对其中的一些概念和处理问题的方法往往感到困惑，特别是在做证明题时感到无从下手，找不到正确的解题思路。因此，对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。

一、认知离散数学

离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论

基础。

1.定义和定理多

离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法;集合的五种运算的定义;关系的定义和关系的四个性质;函数(映射)和几种特殊函数(映射)的定义;图、完全图、简单图、子图、补图的定义;图中简单路、基本路的定义以及两个图同构的定义;树与最小生成树的定义。掌握和理解这些概念对于学好离散数学是至关重要的。 2. 方法性强

在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的。如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。反之，则事倍功半。在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。在平时的讲课和复习中，老师会总结各类解题思路和方法。作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。 3. 抽象性强

离散数学的特点是知识点集中，对抽象思维能力的要求较高。由于这些定义的抽象性，使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材，都会在每一章中首先列出若干个定义和定理，接着就是这些定义和定理的直接应用，如果没有较好的抽象思维能力，学习离散数学确实具有一定的困难。因此，在离散数学的学习中，要注重抽象思维能力、逻辑推理能力的培养和训练，这种能力的培养对今后从事各种工作都是极其重要的。

在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课

中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。 4. 内在联系性

离散数学的三大体系虽然来自于不同的学科，但是这三大体系前后贯通，形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如：集合论、函数、关系和图论，其解题思路和证明方法均有相同或相似之处。

二、认知解题规范

一般来说，离散数学的考试要求分为：了解、理解和掌握。了解是能正确判别有关概念和方法;理解是能正确表达有关概念和方法的含义;掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度，试题类型一般可分为：判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算;计算题主要考核学生的基本运用技能和速度，要求写出完整的计算过程和步骤;证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出严格的推理和论证过程。

学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。

通过离散数学的学习和训练，能使同学们学会在离散数学中处理问题的一般性的规律和方法，一旦掌握了离散数学中这种处理问题的思想方法，学习和掌握离散数学的知识就不再是一件难事了。复习离散数学的整个过程可大致分为三个

阶段。

第一阶段，大量进行知识储备的阶段。

离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。由于这些定义非常抽象，初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。对于跨专业自学的朋友来说更是如此。这是离散数学学习中的第一个困难。因此，对于第一遍复习，我们提出一个最为重要的要求，即准确、全面、完整地记忆所有的定义和定理。具体做法可以是：在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记，直到能够全部正确地默写出来为止。无须强求一定要理解，记住并能准确复述 各定义定理是此阶段的最高要求。也不需做太多的题(甚至不做课后习题也是可以的，把例题看懂就行)，重心要放在对定义和定理的记忆上。请牢记，这是为未来的向广度和深度扩张作必要的准备。

这一过程视各人情况不同耗时约在一到两个月内。 第二阶段，深入学习，并大量做课后习题的阶段。

这是最漫长的一个阶段，耗时也很难估计，一般来说，若能熟练解出某一章75%以上的课后习题，可以考虑结束该章。

解离散数学的题，方法非常重要，如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。例如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化，等价命题的相互转化(包括化为主合取范式与主析取范式)，以给出的若干命题为前提进行推理和证明。相应的对策也马上就可以提出来。以推理题为例，主要是利用P、T规则，加上蕴涵和等价公式表，由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法。由此可见，在平常复习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。

“熟读唐诗三百首，不会做诗也会吟。”要是拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了。这一情况具有普遍性，对许多院校的考试都适用。

第三阶段，进行真题模拟训练，提高整体水平和综合能力的阶段。

这一阶段从第二阶段结束一直持续到考试。

除了我们使用的课本外，应尽可能地弄到报考院校的专业课历年试题。因为每个单位对该科目的侧重点毕竟有不同，从历年试题中可以获取许多有用的信息。这些历年试题此时就有了巨大的作用。

第五篇：离散数学期末试卷

北京工业大学经管学院期末试卷

《离散数学》(A)

学号姓名：成绩

一、单项选择题(每题2分，共18分)

1.令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( D ) .

A.P→Q

C.P∧Q B.P∨Q D.P∧Q

p→q，蕴涵式，表示假设、条件、“如果，就”。

“→”与此题无关

2. 关于命题变元P和Q的极大项M1表示(C)。 书P15-P20，此题换作p、q更容易理解

A.┐P∧QB.┐P∨Qp∨┐q ---- 01---- 1 ----- M

1C.P∨┐QD.P∧┐Q

3.设R(x)：x是实数;S(x,y)：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：( D )

4.在论域D={a,b}中与公式(x)A(x)等价的不含存在量词的公式是( B )

A.A(a)A(b)

C. A(a)A(b)

5.下列命题公式为重言式的是( C )

A.Q→(P∧Q)

C.(P∧Q)→PB.P→(P∧Q) D.(P∨Q)→QB. A(a)A(b) D. A(b)A(a)

牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况

6. 设A={1，2，3｝，B={a,b｝，下列二元关系R为A到B的函数的是(A)

A. R={<1,a>,<2,a>,<3,a>｝

B. R={<1,a>,<2,b>｝

C. R={<1,a>,<1,b>,<2,a>,<3,a>｝

D. R={<1,b>,<2,a>,<3,b>,<1,a>｝

-第 1页

7.偏序关系具有性质( D )背

A.自反、对称、传递

B.自反、反对称

C.反自反、对称、传递

D.自反、反对称、传递

8.设R为实数集合，映射:RR,(x)x22x1,则 是(D).(A) 单射而非满射(C) 双射(B) 满射而非单射(D) 既不是单射也不是满射.

书P96.设函数f：A→B

(1)若ranf=B，则f是满射的【即值域为B的全集，在本题中为R，该二次函数有最高点，不满足】

(2)若对于任何的x1,x2∈A , x1≠x2,都有f(x1)≠f(x2)，则称f是单射的【即x,y真正一一对应，甚至不存在一个y对应多个x。显然，本题为二次函数，不满足】

(3)若f既是满射的，又是单射的，则称f是双射的【本题中两个都不满足，既不是单射也不是满射】

二、填空题(每空2分，共22分)

1.设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，,∈S,*=, 则*运算的幺元是_____<1,0>_____。∈S, 若a≠0， 则的逆元是______<1/a,-b>______。书P123定义

2.在个体域D中，公式xG(x)的真值为假当且仅当__某个G(x)的真值为假__，公式xG(x)的真值为假，当且仅当__所有G(x)的真值都为假__。

3.给定个体域为整数域，若F(x)：表示x是偶数，G(x)：表示x是奇数;那么，(x)F(x)(x)G(x)是一个(x)(F(x)G(x))是一个

4.设Aa,b,c　,A上的二元关系Ra,b,b,c,则r(R)

{,,,,,} ;

。

书P8

9、P85.自反闭包：r(R) = R U R0

={,} U {,,,} ={,,,,,}对称闭包：s(R) = R U R-1 = {,} U {,} = {,,,}-第 2页

传递闭包：t(R) = RUR2 UR3U……

5. 设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有___8___个.

书P96，B上A的概念：

设A、B为集合，所有从A到B的函数构成集合BA ，读作“B上A”

如果|A| = m，|B| = n，m、n不全是0，则|BA| = nm

即，若题中给出集合A有m个元素，B有n个元素，可直接用nm 计算出A到B的函数个数。本题中为23 = 8

6.设,,a,bG，则(a-1)-1，(ab)-1b-1 * a-1。

书P139公式

7. 设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},

g={<1,2>,<2,3>,<3,3>}，则fg=__{<1,3>,<2,1>,<3,1>}___，gf=__{<1,3>,<2,3>,<3,2>}__。 书P82-8

3合成：FG = {|xGz∧zFy}

需要说明的是，这里的合成FG是左复合，即G先作用，然后将F复合到G上。之前的答案“有误”，因为采用了右复合。这两种合成定义所计算的合成结果是不相等的，但两个定义都是合理的，只要在体系内部采用同样的定义就可以了。总之，在咱们的离散里牢记左复合。

三、计算题(每题9分，共36分)

1. 设集合A={1, 2, 3,4,5}，A上的关系R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,

3>,<3,5>,<4,4>,<5,5>}

(1) 画出R的关系图;

(2)问R具有关系的哪几种性质(自反、对称、传递、反对称).自反性、传递性

书P87表格，根据关系图可直接判断性质……

(3) 给出R的传递闭包。

R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}

-第 3页

R2 = RR = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}R3 = R2R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}……

所以，t(R) = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}

2. 集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆

元。 *abcde

abaccc

babcde

cccccc

dedcba

edecdb

幺元：b

零元：c

逆元：a-1 =a,b-1 =b, d-1 =d,e-1 =e

书P123定义

3.求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式及成真赋值。

A = P→((┐P∨Q)∧ (Q∧P))

= P→((┐P∨Q)∧ (Q∧P))

= P→((┐P ∧Q∧P)∨(Q∧Q∧P))

= P→(Q∧P)

= ┐P∨(Q∧P)

= (┐P∧(Q∨┐Q))∨(Q∧P)

= (cP∧Q)∨(┐P∧┐Q)∨(P∧Q)

= (┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)

= m0∨m1∨m

3成真赋值为00，01，1

14.求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数?-第 4页

完全平方数的个数：1000=1000000，所以有1000个(即1到1000)

完全立方数的个数：1003 =1000000，所以有100个(即1到100)

既是完全平方数又是完全立方数的重复部分：106 =1000000，所以有10个(即16到106) 所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10) = 998910

2四、证明题(每题8分，共24分)

1.若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止?(给出相应推理的证明过程)

2.给出关系不满足对称性的条件并证明。

∃∈R∧∉R

⇔∃∈R∧∉R

⇔┐∀(∈R∧∈R)

3.如果关系R和S为X上的等价关系，证明：R∩S也是X上的等价关系。

(1)自反

设x∈X【推∈R∩S】

∵R和S为X上的等价关系

∴R和S均为X上的自反关系

∵x∈X

∴∈R, ∈S

∴∈R∩S

∴R∩S在X上是自反的

(2)对称

设∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的对称关系

∴∈R,∈S

∴∈R∩S

-第 5页

∵此时∈R∩S

∴R∩S在X上是对称的【∈R∩S时，必有∈R∩S】

(3)传递

设∈R∩S，∈R∩S【推∈R∩S】

∵∈R∩S

∴∈R,∈S

∵∈R∩S

∴∈R,∈S

∵R和S为X上的等价关系

∴R和S均为X上的传递关系

∴∈R,∈S

∴∈R∩S

∵此时∈R∩S，∈R∩S

∴R∩S在X上是传递的【∈R∩S，∈R∩S时，必有∈R∩S】

综上所述，R∩S在X上是自反、对称、传递的

∴R∩S为X上的等价关系

书P90

等价关系：自反、对称、传递

偏序关系：自反、反对称、传递

因此要证明某关系在非空集合上是等价关系或偏序关系，一般需分为三个性质分别证明，同时，题目条件中若给出等价关系或偏序关系，也可分为三部分选择使用。这类题条件较多(自己设的、题目推的)，一定要思路清晰，否则容易写乱自己绕不出来„„

这道题三部分每个部分所设的条件都是该性质定义里的“若”，想要推出定义里的“则”，即用定义证明。这就是思路很重要的一部分。

-第 6页