2009年4月离散数学试题(附答案)

第一篇：2009年4月离散数学试题(附答案)

全国2009年4月自学考试离散数学试题（附答案）

课程代码：02324

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。/S 1．下列为两个命题变元P，Q的小项是（）A．P∧Q∧ P B． P∨Q C． P∧Q

D． P∨P∨Q 2．下列语句中是真命题的是（）A．我正在说谎

B．严禁吸烟

C．如果1+2=3，那么雪是黑的

D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A． P∧ Q B． P∨ Q C．（PQ）

D．（ P∨ Q）

4．命题公式（P∧（P→Q））→Q是（）A．矛盾式 B．蕴含式 C．重言式

D．等价式

5．命题公式（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111 C．全体指派

D．无

6．在公式（x）F（x，y）→（ y）G（x，y）中变元x是（）A．自由变元

B．约束变元

C．既是自由变元，又是约束变元

D．既不是自由变元，又不是约束变元

7．集合A={1，2，„，10}上的关系R={|x+y=10，x∈A，y∈A}，则R的性质是（A．自反的 B．对称的

C．传递的、对称的

D．反自反的、传递的

8．若R和S是集合A上的两个关系，则下述结论正确的是（）A．若R和S是自反的，则R∩S是自反的 B．若R和S是对称的，则RS是对称的 C．若R和S是反对称的，则RS是反对称的 D．若R和S是传递的，则R∪S是传递的

全国2009年4月自学考试离散数学试题）

9．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是．．t（R）中元素的是（）A．<1，1> C．<1，3>

B．<1，2> D．<1，4> 10．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（）A．1∈A C．{{4，5}}A

B．{1，2，3}A D．∈A 11．在自然数集N上，下列运算是可结合的是（）A．ab=a-2b C．ab=-a-b

B．ab=min{a，b} D．ab=|a-b| 12．在代数系统中，整环和域的关系是（）A．整环一定是域 C．域一定是整环

B．域不一定是整环 D．域一定不是整环

13．下列所示的哈斯图所对应的偏序集中能构成格的是（）

A． B．

C． D．

14．设G为有n个结点的简单图，则有（）A．Δ(G)＜n C．Δ(G)＞n

B．Δ(G)≤n D．Δ(G)≥n

15．具有4个结点的非同构的无向树的数目是（）A．2 C．4

二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。

B．3 D．5 16．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的辖域为________，x的辖域为________。17．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。

18．设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n，那么复合函数（ff）（n）

全国2009年4月自学考试离散数学试题

2=________（gf）（n）=________。

19．设复合函数gf是从A到C的函数，如果gf是满射，那么________必是满射，如果gf是入射，那么________必是入射。

20．设A={1，2}，B={2，3}，则A-A=________，A-B=________。

21．设S是非空有限集，代数系统

中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是________，零元是________。

+>中，2的阶是________。22．在是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是________。24．在下图中，结点v2的度数是________。

0125．设图D=，V={v1，v2，v3，v4}，若D的邻接矩阵A=11101001001-1，则deg（v1）=________，01从v2到v4长度为2的路有________条。

三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）

+B，A的幂集P（A）26．已知A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，A○。

27．构造命题公式（（P∧Q）→P）∨R的真值表。

28．下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，A4及可达矩阵P。

29．求下列公式的主合取范式和主析取范式：P∨（ P→（Q∨（ Q→R）））

30．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画的哈斯图，并求A中的最大元、最小元、极大元、极小元。

四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）31．在整数集Z上定义：abab2,a,bZ，证明：是一个群。32．R是集合A上自反和传递的关系，试证明：RR=R。

全国2009年4月自学考试离散数学试题

33．证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。

五、应用题（本大题共2小题，第34小题6分，第35小题9分，共15分）34．构造下面推理的证明。

如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。

35．今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：

（1）当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。

（2）当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。

全国2009年4月自学考试离散数学试题

第二篇：离散数学试题+答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（）A.汉密尔顿回路

B.欧拉回路 C.汉密尔顿通路

D.初级回路

2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（）A.10

B.12

C.16

D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是（）A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是（）A.<{1},·>

B.〈{-1},·〉

C.〈{i},·〉

D.〈{-i},·〉

5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有（）A.〈Z，+，/〉

B.〈Z，/〉 C.〈Z，-，/〉

D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是（）A.〈Q，*〉Q是全体有理数集，*是数的乘法运算

B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算

7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性

8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是（）A.R∪IA

B.R

C.R∪{〈c,a〉}

D.R∩IA 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取（）A.｛〈c,a〉，〈a,c〉｝

B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}

D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是（）A.∈

B.

C.{}

D.{}∈

11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x

www.xiexiebang.com 专注于收集各类历年试卷和答案

D.(x)(y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于（）A.(x)A(x)→B

B.(x)A(x)→B C.A(x)→B

D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x（）A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元

14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（）A.P∨Q

B.P∧┐Q

C.P→┐Q

D.P∨┐Q 15.以下命题公式中，为永假式的是（）A.p→(p∨q∨r)

B.(p→┐p)→┐p C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉最小上界是______。

20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。

21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。

22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。

25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。

三、计算题(共30分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证

是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

www.xiexiebang.com 专注于收集各类历年试卷和答案

(1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。

30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。

四、证明题(共20分)32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。

33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。

证明：〈F, 〉是群。

34.(6分)在个体域D={a1,a2,„，an}中证明等价式：

(x)(A(x)→B(x))(x)A(x)→(x)B(x)

五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

参考答案

一、单项选择题(本大题共15小题，每小题1分，共15分)

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空题 16.0 17.1

0 18.单位元

19.x∩y

x∪y 20.入射

满射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

www.xiexiebang.com 专注于收集各类历年试卷和答案

24.可满足式

永假式(或矛盾式)25.陈述句

真值

三、计算题

1100101026.M=

1011001122M=21110111

121011M2ij18,ij6 M2i1i1j144

G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，x∈P(A),xn=

当n是奇数时，x∈P(A),xn=x

于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=(｛a｝-1)n｛b｝n｛a｝n=

当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝= 28.(1)偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无；

极大元：2，5，极小元：1，3

下界：4，下确界4；

上界：无，上确界：无

29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

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

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

www.xiexiebang.com 专注于收集各类历年试卷和答案

30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai为ei上的权，则

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)

(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

xy

d(vi)=2(x+y-1)。

i又树叶的度为1，任一分支点的度大于等于2

且度最大的顶点必是分支点，于是

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1

从而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元

由此上知〈F，〉是群

34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))

www.xiexiebang.com 专注于收集各类历年试卷和答案

(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an)))

(┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an))

┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an))

┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)

五、应用题

35.令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t

结论：p→t

证①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,„，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

第三篇：离散数学试题与答案

《离散数学》试题及答案

一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1.命题公式(PQ)Q为()

(A)矛盾式(B)可满足式(C)重言式(D)合取范式

2．设P表示“天下大雨”，Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）。

(A)． PQ；(B)．PQ；(C)．PQ；(D)．PQ．

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(B){1,2, 3}A

(C){{4,5}}A(D)A

4.设A＝{1,2},B={a,b,c},C={c,d}, 则A×(BC)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.设G如右图：那么G不是().(A)哈密顿图；(B)完全图；

(C)欧拉图；(D)平面图.二、填空题：本大题共5小题，每小题4分，共20

6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝－

8.在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9.写出一个不含“”的逻辑联结词的完备集.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为 MR＝100100

三、证明题（共30分）

11.（10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)

12.（10分）构造证明：(P(QS))∧(R∨P)∧QRS

（0,1）13.（10分）证明与[0,1)，[0,1)与[0,1]等势。

四、解答题(共35分)

14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个33方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.）

15.（8分）求命题公式(PQ)(PQ)的真值表.16.（10分）设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}

毕节学院《离散数学》课程试卷

求R1R2的集合表达式.17.（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

三个条件：(1)若A去，则C和D中要去1个人；(2)B和C不能都去；

(3)若C去，则D留下。

一、单项选择题(每小题3分，共15分)

1.B2.C3.C4.A5.B

二、填空题(每小题4分，共20分)

6.{,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.老乡

9.{,}或{,} 或 {}或 {}

10.见

f(0)0111························································································ 10分 ,n1,A ·f()n1nn

f(x)x,x[0,1)A

14.85 1 2 7 6

填对每个格得1分。

15.表中最后一列的数中，每对1个数得2分.11016.MR1,(2分)001

MR201(4分)0100

010101(6分)0000110 MR1R2001

R1R2{1,}(10分)

17.解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。······························································································ 2分因此(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F

(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T ··································································································································· 8分

毕节学院《离散数学》课程试卷

故有三种派法：B∧D，A∧C，A∧D。······································································· 10分

毕节学院《离散数学》课程试卷

第四篇：离散数学试题

中央电大离散数学试题

月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，{2}，{1，2}}，则下列表述正确的是()．

A．2AB．{1}A

C．1AD．2  A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为

()．

A．6B．4C．3D．

53．设无向图G的邻接矩阵为

0111110011100001100111010

则G的边数为()．

A．1B．7C．6D．14 4．设集合A={a}，则A的幂集为()．

A．{{a}}B．{a，{a}}

C．{，{a}}D．{，a}

5．下列公式中()为永真式．

A．AB  ABB．AB  (AB)

C．AB  ABD．AB  (AB)

二、填空题（每小题3分，本题共15分）

6．命题公式PP的真值是

7．若无向树T有5个结点，则T的边数为．

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i

9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素，就可使新得到的关系为对称的．

10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天上课．”翻译成命题公式．

12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

四、判断说明题（每小题7分，本题共14分）

判断下列各题正误，并说明理由．

13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．

14．设G是一个有4个结点10条边的连通图，则G为平面图．

五．计算题（每小题12分，本题共36分）

15．试求出（P∨Q）→（R∨Q）的析取范式．

16．设A={{1}, 1, 2}，B={ 1, {2}}，试计算

（1）（A∩B）（2）（A∪B）（3）A （A∩B）．

17．图G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，对应边的权值依次为1、2、3、1、4及5，试

（1）画出G的图形；

（2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

六、证明题（本题共8分）

18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

中央电大2010年7月离散数学

试题解答

(供参考)

一、单项选择题（每小题3分，本题共15分）

1．B2．D3．B4．C5．B

二、填空题（每小题3分，本题共15分）

6．假（或F，或0）

7．48．t-

19． <2, 1>

10．z，y

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：今天上课，（2分）则命题公式为：P．（6分）

12．设 P：他去操场锻炼，Q：他有时间，（2分）则命题公式为：P Q．（6分）

四、判断说明题（每小题7分，本题共14分）

13．错误．（3分）因为A中元素2没有B中元素与之对应，故f不是A到B的函数．（7分）

14．错误．（3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”（7分）

五．计算题（每小题12分，本题共36分）

15．（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）（4分）

(┐P∧┐Q)∨（R∨Q）（8分）

(┐P∧┐Q)∨R∨Q（析取范式）（12分）

16．（1）（A∩B）={1}（4分）

（2）（A∪B）={1, 2, {1}, {2}}（8分）

（3）A（A∩B）={{1}, 1, 2}（12分）

17．（1）G的图形表示如图一所示：ad1

5b c（3分）图一

（2）邻接矩阵：

01101111（6分）1101

1110

（3）最小的生成树如图二中的粗线所示：

a 3d5

b图二1c

权为：1+1+3=5

六、证明题（本题共8分）

18．证明：设xA，因为R自反，所以x R x，即< x, x>R；

又因为S自反，所以x R x，即< x, x >S．即< x, x>R∩S故R∩S自反．

10分）12分）（4分）（6分）（8分）（（

第五篇：全国2008年4月自考离散数学试题

全国2008年4月自考离散数学试题

课程代码：02324

一、单项选择题(本大题共15小题，每小题1分，共15分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）

A.P∧QB.P→Q C.P→QD.P→Q

2.下列命题联结词集合中，是最小联结词组的是（）

A.{，}B.{，∨，∧} C.{，∧}D.{∧，→}

3.下列命题为假命题的是（）

A.如果2是偶数，那么一个公式的析取范式惟一

B.如果2是偶数，那么一个公式的析取范式不惟一

C.如果2是奇数，那么一个公式的析取范式惟一

D.如果2是奇数，那么一个公式的析取范式不惟一

4.谓词公式 x(P(x)∨yR(y))→Q(x))中变元x是（）

A.自由变元B.约束变元

C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元

5.若个体域为整数减，下列公式中值为真的是（）

A.xy(x+y=0)B.y x(x+y=0)C.x y(x+y=0)D.xy(x+y=0)

6.下列命题中不正确的是（）

A.x∈{x}-{{x}}B.{x}{x}-{{x}}

C.A={x}∪x,则x∈A且xAD.A-B=A=B

7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（A.PQB.PQ C.QPD.Q=P

8.下列表达式中不成立的是（）

A.A∪(BC)=(A∪B)(A∪C)B.A∩(BC)=(A∩B)(A∩C)C.(AB)×C=(A×C)(B×C)D.(A-B)×C=(A×C)-(B×C)9.半群、群及独异点的关系是（）

A.{群}{独异点}{半群}B.{独异点}{半群}{群} C.{独异点}{群}{半群}D.{半群}{群}{独异点} 10.下列集合对所给的二元运算封闭的是（）

A.正整数集上的减法运算

B.在正实数的集R+上规定为ab=ab-a-b a,b∈R+ C.正整数集Z+上的二元运算为xy=min(x,y)x,y∈Z+ D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法

11.设集合A={1，2，3}，下列关系R中不是等价关系的是（）A.R={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}）

C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函数中为双射的是（）

A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)= C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15

13.设集合A={a,b, c}上的关系如下，具有传递性的是（）

A.R={,,,}B.R={,} C.R={,,,}D.R={}

14.含有5个结点，3条边的不同构的简单图有（）

A.2个B.3个

C.4个D.5个

15.设D的结点数大于1，D=是强连通图，当且仅当（）

A.D中至少有一条通路B.D中至少有一条回路

C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路

二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。

16.设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。

17.设A={1,2,3,4,5}，RA×A，R={<1,2>，<3,4>,<2,2>}，则R的自反闭包r(R)=__________。

对称闭包t(R)=__________。

18.设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。

19.对于公式 x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________ ,当论域为{0,1,2}时，其真值为_____________。

20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数 ,。

21.3个结点可构成_________个不同构的简单无向图，可构成________个不同构的简单有向图。

22.无向图G=如左所示，则G的最大度

Δ(G)=_____________，G的最小度δ(G)=_____________。

23.设图G,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_ ________, deg+(v4)=____________。

24.格L是分配格，当且仅当L既不含有与_______同构的子格，也不含有与______同格的子格。

25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>}, S={<4,2>,<2,5>,<3,1>,<1,3>}，则。

三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）

26.设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，画出R的关系图，并求出A中各元素的等价类。

27.构造命题公式（P∨Q）（P∧Q）的真值表。

28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））

29.设A={a, b, c, d, e}，R为A上的关系，R={，，, , ,, }∪IA，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。

30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。

四、证明题（本大题共3小题，第31、32题各6分，第33题8分，共20分）

31.设（L，≤）是格，试证明： a, b, c ∈L, 有a∧（b∨c）≥（a∧b）∨（a∧c）；

a∨（b∧c）≤（a∨b）∧（a∨c）。

32.设R是A上的自反和传递关系，如下定义A上的关系T，使得 x, y∈A，∈T ∈R∧(y, x)∈R。

证明T是A上的等价关系。

33.设有G=, V的结点数|V|=n，称该图为n阶图，若从结点vi到vj存在路，证明从vi到vj必存在长度小于等于n-1的一条路。

五、应用题（本大题共2小题，第34题7分，第35题8分，共15分）

34.构造下面推理的证明。

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

35.今要将6人分成3组（每组2个人）去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。

（1）能否使得每组的2个人都能相互合作？

（2）你能给出几种不同的分组方案？

《离散数学》试题及答案3

一、填空题设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A(B)＝ __________________________.2.设有限集合A, |A| = n, 则 |(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4.已知命题公式G＝(PQ)∧R，则G的主析取范式是_______________________________

__________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AB＝_________________________;AB＝_________________________;A－B＝ _____________________.7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________.8.设命题公式G＝(P(QR))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9.设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1•R2 = ________________________,R2•R1 =____________________________,R12 =________________________.10.设有限集A, B，|A| = m, |B| = n, 则| |(AB)| = _____________________________.11 设A,B,R是三个集合，其中R是实数集，A = {x |-1≤x≤1, xR}, B = {x | 0≤x < 2, xR},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ ,.13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________.14.设一阶逻辑公式G = xP(x)xQ(x)，则G的前束范式是__________________________ _____.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

16.设谓词的定义域为{a, b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.17.设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则RS＝_____________________________________________________, R2＝______________________________________________________.二、选择题设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是()。

(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = {2,3,4,5},则元素6为B的()。

(A)下界(B)上界(C)最小上界(D)以上答案都不对下列语句中，()是命题。

(A)请把门关上(B)地球外的星球上也有人

(C)x + 5 > 6(D)下午有会吗？设I是如下一个解释：D＝{a,b}, 则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x), H＝xP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是()。

(A)GH(B)HG(C)G＝H(D)以上都不是.9 设A, B为集合，当()时A－B＝B.(A)A＝B(B)AB(C)BA(D)A＝B＝.设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有()。

(A)自反性(B)传递性(C)对称性(D)以上答案都不对下列关于集合的表示中正确的为()。

(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c} 12 命题xG(x)取真值1的充分必要条件是().(A)对任意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图，有5个顶点，6个面，则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个顶点的完全图，则从G中删去()条边可以得到树.(A)6(B)5(C)10(D)4.15.设图G的相邻矩阵为，则G的顶点数与边数分别为().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、计算证明题

1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；

(3)写出A的最大元，最小元，极大元，极小元。

2.设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y)| x, yA 且 x  y}, 求

(1)画出R的关系图；

(2)写出R的关系矩阵.3.设R是实数集合，,,是R上的三个映射，(x)= x+3, (x)= 2x, (x)＝ x/4,试求复合映射•，•, •, •，••.4.设I是如下一个解释：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011

试求(1)P(a, f(a))∧P(b, f(b));(2)xy P(y, x).5.设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出A的最大元，最小元，极大元，极小元；

(3)写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。

7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；

(2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：

(1)G =(P∧Q)∨(P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(P∧R))

13.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.(1)试写出R和S的关系矩阵；

(2)计算R•S, R∪S, R－1, S－1•R－1.四、证明题

1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。

2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。

4.(本题10分)A, B为两个任意集合，求证：

A－(A∩B)=(A∪B)－B.参考答案

一、填空题

1.{3};{{3},{1,3},{2,3},{1,2,3}}.2..3.1= {(a,1),(b,1)}, 2= {(a,2),(b,2)},3= {(a,1),(b,2)}, 4= {(a,2),(b,1)};3, 4.4.(P∧Q∧R).5.12, 3.6.{4}, {1, 2, 3, 4}, {1, 2}.7.自反性；对称性；传递性.8.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x |-1≤x < 0, xR};{x | 1 < x < 2, xR};{x | 0≤x≤1, x12.12;6.13.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.14.x(P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)};{(1, 1),(1, 2),(1, 3)}.二、选择题

1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D

三、计算证明题

1.(1)

(2)B无上界，也无最小上界。下界1, 3;最大下界是3.(3)A无最大元，最小元是1，极大元8, 12, 90+;极小元是1.2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)

(2)

3.(1)•＝((x))＝(x)+3＝2x+3＝2x+3.(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)•＝((x))＝(x)+3＝x/4+3,(4)•＝((x))＝(x)/4＝2x/4 = x/2，(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.4.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x))

R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = 1.5.(1)

(2)无最大元，最小元1，极大元8, 12;极小元是1.(3)B无上界，无最小上界。下界1, 2;最大下界2.6.G = (P→Q)∨(Q∧(P→R))= (P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)

=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)= (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z))

9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}，t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；

(2)关系图:

11.G＝(P∧Q)∨(P∧Q∧R)

＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7)

H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)

＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7)

G,H的主析取范式相同，所以G = H.13.(1)

P∧Q∧R)7

(2)R•S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1•R－1＝{(b, a),(d, c)}.四证明题

1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S(1)P∨RP

(2)R→PQ(1)(3)P→QP

(4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP

(7)Q→SQ(5)(6)(8)Q∨SQ(7)

2.证明：(A-B)-C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)

3.证明：{A∨B, C→B, C→D}蕴涵A→D(1)AD(附加)(2)A∨BP(3)BQ(1)(2)(4)C→BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)

所以 {A∨B, C→B, C→D}蕴涵A→D.4.证明：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B)

＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B

而(A∪B)－B =(A∪B)∩~B

=(A∩~B)∪(B∩~B)=(A∩~B)∪

= A－B

所以：A－(A∩B)=(A∪B)－B.8

1.离散数学试题及答案2 离散数学试题

一.多重选择填空题

(本题包括16个空格，每个空格3分，共48分。每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1．命题公式(P∧(P→Q))→Q是_____式。

(1)重言(2)矛盾(3)可满足(4)非永真的可满足 2．给定解释I=(D,)=(整数集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x

(1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整数，<30}，Ｂ={x|x是质数，x<20}，C={1,3,5}，则① =_____;② =_____;③ =_____;④ =_____。(1){1,2,3,5}(2)(3){0}(4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19} 5．设A、B、C是集合，下列四个命题中，_____在任何情况下都是正确的。(1)若A B且B∈C，则A∈C(2)若A B且B∈C，则A C(3)若A∈B且B C，则A C(4)若A∈B且B C，则A∈C 6．设集合Ａ={a,b,c,d,e,f,g}，Ａ的一个划分 ={{a,b},{c,d,e},{f,g}}，则所对应的等价关系有_____个二元组。

(1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除关系。S的子集Ｂ＝{2,4,6｝，则在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上确界是_____；Ｂ的下确界是_____。

(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．设有有限布尔代数(B,+,*,’,0,1)，则 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,„,n}，n∈N，定义为模n加法，即x y=(x+y)mod n，则代数系统(G，)_____。

(1)是半群但不是群(2)是无限群(3)是循环群(4)是变换群(5)是交换群

10．n个结点、m条边的无向连通图是树当且仅当m=_____。(1)n+1(2)n(3)n-1(4)2n-1 二请给出命题公式的主析取范式。(10分)三假设下列陈述都是正确的：(1)学生会的每个成员都是学生并且是班干部；

(2)有些成员是女生。问是否有成员是女班干部？请将上述陈述和你的结论符号化，并给出你的结论的形式证明。(10分)四设R和S是集合Ｘ上的等价关系,则S∩R必是等价关系。(10分)

参考答案

一、1.1、3 2.4 3.4 4.1；4；2；2 5.4 6.4 7.1；7；4；7 8.2、4、6 9.3、4 10.3

二、分析：求给定命题公式的主析取范式与主合取范式，通常有两种方法——列表法和等值演算法。(1)列表法

列出给定公式的真值表，其真值为真的赋值所对应的极小项的析取，即为此公式的主析取范式。(2)等值演算法在等值演算中，首先将公式中的蕴涵联结词和等价联结词化去，使整个公式化归为析取范式，然后删去其中所有的永假合取项，再将析取式中重复出现的合取项合并和合并合取项中相同的命题变元，最后对合取项添加没有出现的命题变元，就是合取 ,经过化简整理，即可得到主析取范式。解：（1）列表法设

000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根据真值表中真值为1的赋值所对应的极小项的析取，即为的主析取范式。由表可知

（2）等值演算

三、解：有成员是女班干部。

将命题符号化，个体域为全总个体域。

：x是学生会的成员。：x是学生：x是班干部：x是女性前提：，结论：证明： ① P ② ES①，e为额外变元 ③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨

离散数学试题及答案1

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

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F

(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧ D)∨(C∧D)T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为：

(()∧())，()(()∧())下面给出证明：

(1)()P

(2)(c)T(1)，ES(3)(()∧())P

(4)(c)∧(c)T(3)，US(5)(c)T(4)，I

(6)(c)∧(c)T(2)(5)，I

11(7)(()∧())T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。

四、（15分）设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∪R－1＝{<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>，<5，5>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，Rn对称。

因R对称，则有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2对称。若对称，则x yz(x z∧zRy)z(z x∧yRz)y x，所以对称。因此，对任意正整数n，对称。

对任意的x、y∈A，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f－1：B→A是双射。

证明因为f：A→B是双射，则f－1是B到A的函数。下证f－1是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f－1(y)＝x，所以f－1是满射。

对任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f－1是单射。

综上可得，f－1：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3＝b2*b∈S，„，bn∈S，„。

因为S是有限集，所以必存在j＞i，使得＝。令p＝j－i，则＝ *。所以对q≥i，有＝ *。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于 ∈S，有＝ * ＝ *(*)＝„＝ *。

令a＝，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤(n－2)。

证明设G有r个面，则2m＝ ≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤(n－2)。

（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G*＝是连通平面图G＝的对偶图，则G* G，于是|F|＝|V*| 12 ＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。

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

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R 附加前提

(2)PR P

(3)P T(1)(2)，I(4)P∨Q P

(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)S∨R T(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E(3)x(P(x)∧Q(x))T(2)，E(4)P(a)∧Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会 13 打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如 Ai(Ai为Ai或)的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、„、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈，两者必有一个成立，取Ai为包含元素a的Ai或，则a∈ Ai，即有a∈ si，于是U si。又显然有 siU，所以U＝ si。

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和分别出现在sp和sq中，于是sp∩sq＝。

综上可知，{s1，s2，„，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。

证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fog是A到C的函数；

(2)对任意的x∈A，有fog(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fog。所以Dfog＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fog＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fog是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fog。又因fog是A到C的函数，则可写为fog(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a－1*b∈H}，则R是G中的一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以∈R。

若∈R，则a－1*b∈H。因为H是G的子群，故(a－1*b)－1＝b－1*a∈H。所以∈R。