离散数学作业题截图

第一篇：离散数学作业题截图

离散数学作业题2003版

华南理工大学网络教育学院 2014–2015学第一学期 《 离散数学 》作业 (解答必须手写体上传，否则酌情扣分)

1.设命题公式为  Q (P  Q)  P。

(1)求此命题公式的真值表; (2)求此命题公式的析取范式; (3)判断该命题公式的类型。

2.用直接证法证明

前提：P  Q，P  R，Q  S 结论：S  R

3.在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 4.用直接证法证明：

前提：(x)(C(x)→ W(x)∧R(x))，(x)(C(x)∧Q(x)) 结论：(x)(Q(x)∧R(x))。

5.设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。

(1) 给出关系R; (2) 给出COV A

(3) 画出关系R的哈斯图;

(4) 给出关系R的极大、极小元、最大、最小元。

6.求带权图G的最小生成树，并计算它的权值。

《 离散数学作业 》 第 1 页 (共 2 页)

7.给定权为1，9，4，7，3;构造一颗最优二叉树。

8.给定权为2，6，3，9，4;构造一颗最优二叉树。

9、给定权为2，6，5，9，4，1;构造一颗最优二叉树。

10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，d:10%,e:10%,f:5%。试给出传输这6个字母的最佳前缀码?问传输1000个字符需要多少位二进制位?

《 离散数学作业 》 第 2 页 (共 2 页)

第二篇： 离散数学课件作业

第一部分 集合论

第一章 集合的基本概念和运算 1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是

[ ] A.2 ∈A; B.1 ∈ A; C.5 ∈A; D.{2}  A。

1-2 A,B 为任意集合，则他们的共同子集是

[ ] A.A; B.B; C.A∪B; D.

Ø 。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ?

(1) N  Q，Q ∈S，则 N  S

[

]

(2)-1 ∈Z，Z ∈S， 则 -1 ∈S

[

]

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，

E = {x│x ∈R 并且 x2 - 7x + 12 = 0}，F = { 4，Ø ，3，3}， 试问哪两个集合之间可用等号表示 ?

1-5 用列元法表示下列集合

(1)A = { x│x ∈N 且 x2 ≤ 9 } (2)A = { x│x ∈N 且 3-x 〈 3 }

第二章 二元关系

2-1 给定 X =(3, 2，1)，R 是 X 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈X 且 x < y } 求：(1)domR =?; (2)ranR =?; (3)R 的性质。

2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试求： (1)R 的列元表达式; (2)给出 dom(R 。R)。

2-3 判断下列映射 f 是否是 A 到 B 的函数;并对其中的 f：A→B 指出他的性质，即是否单射、满射和双射，并说明为什么。

(1)A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。 (2)A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，3〉}。 (3)A = B = R， f = x 。 (4)A = B = N， f = x2 。 (5)A = B = N， f = x + 1 。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱(x-y)能被3整除}，则自然映射 g：A→A/R使 g(1) =

[

] A.{1,2｝;

B.{1,3｝;

C.{1,4｝;

D.{1｝。

2-5 设 A ={1，2，3}，则商集A/IA =

[

] A.{3｝;

B.{2｝;

C.{1｝;

D.{{1｝，{2｝，{3｝｝ 。

2-6.设f(x)=x+1，g(x)=x-1 都是从实数集合R到R的函数，则f。g=

[

]

A.x+1;

B.x-1;

C.x;

D.x2。

第三章 结构代数(群论初步) 3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ?

(1)S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。 (2)S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ;

二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。 (3)S3 = {0，1}，二元运算 * 是普通乘法。

3-2 在自然数集合上，下列那种运算是可结合的

[

]

A.x*y = max(x,y) ;

B.x*y = 2x+y ; C.x*y = x2+y2 ;

D.x*y =︱x-y︱..

3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z 都有 x 。y = x + y ，

试问〈Z，。〉能否构成群，为什麽 ?

第二部分 图论方法 第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ?

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为

[ ]

第五章 树

5-1 握手定理的应用(指无向树)

(1)在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个?

(2)一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片?

5-2 一棵树中有 i 个顶点的度数为 i(i=2，…k)，其余顶点都是树叶(即一度顶点)，问树叶多少片?设有x片,则 x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树

T。试问：(1) T 的权 W(T)? (2)树高几层 ?

5-4 以下给出的符号串集合中，那些是前缀码?将结果填入[ ]内. B1 = {0，10，110，1111} [ ] B2 = {1，01，001，000} [ ] B3 = {a，b，c，aa，ac，aba，abb，abc} [ ] B4 = {1，11，101，001，0011} [ ]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [ ]

5-6(是非判断题)二元正则树有奇数个顶点。 [ ]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.

求传输他们的最佳前缀码。

1、最优二元树 T; 2.每个字母的码字;

第三部分 逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

(1)2月 17 号新学期开始。 [ ] (2)离散数学很重要。 [ ] (3)离散数学难学吗 ? [ ] (4)C 语言具有高级语言的简洁性和汇编语言的灵活性。 [ ] (5)x + 5 大于 2 。 [ ] (6)今天没有下雨，也没有太阳，是阴天。 [ ]

6-2 将下列命题符号化. (1)2 是偶素数。

(2)小李不是不聪明，而是不好学。 (3)明天考试英语或考数学。(兼容或) (4)你明天不去上海，就去北京。(排斥或)

6-3 分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型. (1)﹃(p→q)∧ q; (2)((p→q)∧ p)→q; (3)(p→q)∧ q。

以下两题(6-4;6-5)为选择题,将正确者填入[ ]内. 6-4 令 p：经一堑;q：长一智。命题’’只有经一堑，才能长一智’’符号化为

[

] A. p→q;

B.

q→p;

C.

p∧q;

D.

﹁q→﹁p

6-5 p：天气好;q：我去游玩.命题 ”如果天气好，则我去游玩” 符号化为

[

]

A. p→q;

B.

q→p;

C.

p∧q;

D.

﹁q→p

6-6 证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。

第七章 谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化 (1)这台机器不能用。

(2)如果 2 > 3，则 2 > 5。

7-2 填空补缺题：设域为整数集合Z，命题xy彐z(x-y=z)的真值为 (

)

7-3 在谓词逻辑中将下列命题符号化 (1)有的马比所有的牛跑得慢。 (2)人固有一死。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 ,

量词 ”所有”，- 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

2010年2月20号。

第三篇：离散数学

离散数学试题(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页