北京大学1997年研究生入学考试离散数学试题

第一篇：北京大学1997年研究生入学考试离散数学试题

北京大学1997年研究生入学考试 离散数学试题（共50分）(7分)

在一阶逻辑自然推理系统F中，构造下面推理的证明。个体域是人的集合。

“每位科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。”

2(8分)

在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：

甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后，笑曰：你们3人中有一人全说对了，有一人全说错了，还有一人对错各半。

试用逻辑演算法判断王教授是哪里人？

3(3分)

设根树T有17条边，12片树叶，4个4度内点，1个3度内点。求T的树根的度数。

4(7分)

设无向图G是n(n≥3)个顶点的极大平面图，证明G的对偶图G*的边连通度l(G)≥2，并且G*是3-正则图(Δ(G)=d(G)=k的无向图G称作k-正则图)。

5(4分)

设R={| x,yÎnÙx+3y=12}，求R2。

6(6分)

设A为集合，B=P(A)-{Æ}-{A}，且B≠Æ。

求偏序集的极大元，极小元，最大元和最小元。

7(4分)

设A={1,2,3}，fÎAA，且f(1)=f(2)=1，f(3)=2，定义G：A→P(A)，G(x)=f-1(x)。说明G有什么性质(单射、满射和双射)，计算值域ranG。

8(4分)

设I是格L的非空子集，如果

(1)“a,bÎI，有aÚbÎI，(2)”aÎI，“xÎL，有x≤aÞxÎI。

则称I是格L的理想。

证明：格L的理想是一个子格。

9(7分)

设G为n阶群，aÎG。令

H={xax-1|xÎG}，N(a)={x|xÎGÙax=xa}。

证明：

① |H|=[G:N(a)]；

② 设C={x|xÎGÙ”yÎG(xy=yx)}是群G的中心，且|C|=m，则|H|∣n/m。

第二篇：西安交通大学1999年研究生入学考试离散数学试题

西安交通大学1999年研究生入学考试 离散数学试题(30分)

请判断下列各题的正确性。

⑴ 2∩2=2ABA∩B。

⑵ AB=A当且仅当B=Æ。

⑶(A´C)(B´D)=(AB)´(CD)。

⑷ 设|A|=5，则A上恰有31个不同的等价关系。

⑸ 设R非空集合A上的关系，R是A上可传递的，当且仅当R○RÍR。

⑹ 若R1，R2均为非空集合A上的等价关系，那么R1○ R2也为A上的等价关系。

⑺ 设

为半序集，ƹSÍP，若S有上界，则S必有上确界。

⑻ 设N为自然数集合，I为整数集合，´是算术乘法，则与同构。

⑼ 设是群，则G中至少有一个二阶元素。

⑽ 设为整环，|R|=n，则是域。

⑾ 设为域，为的子环，则为整环。

⑿ 设为格，|L|=n，则为有界格。

⒀ 存在7个结点的自补图。

⒁ 下图为平面图。

图1 题1(14)

⒂ 下图为哈密尔顿图。

图2 题1(15)图

2(8分)

设(G,*)为循环群，生成元为a，设(A,*)和(B,*)均为(G,*)的子群，而a和a分别为(A,*)和(B,*)的生成元。

① 证明(A∩B,*)是(G,*)的子群。

② 请问：(A∩B)是否为循环群。如果是，请给出其生成元。

3(10分)

设(A,Å,Ä)是环，A={f |f是A到A的函数}。定义A上的运算à和*如下，设f,gÎA, 对于任意的xÎA。

(fàg)(x)=f(x)Åg(x)；

(f*g)(x)=f(x)Äg(x)；

证明：(A,à,*)是环。

4(6分)

设A=和B=是两个格，f是A到B的同态函数。证明A的同态象是B的子格。(注：A的同态象即：f(L1)={f(x)|xÎL1})。

5(8分)

设G=（V,E）是简单的无向平面图，证明G中至少有一个结点的度数小于等于5。

6(10分)

设G是连通的无向图，且有2k>0个奇结点，证明：G中存在各边不重复的k条简单路P1，P2，…，Pk，使得 A

A

A

A

i

j

E(G)=E(P1)∪E(P2)∪…∪E(Pk)。

7(8分)

设个体域为整数集合，将下述语句分别表示成仅含有N(e)、P(e)、Q(e)、E(e1,e2)、L(e1,e2)、D(e1,e2)所组成的谓词公式：其中各谓词定义如下：

N(e)： e是自然数，P(e)： e是素数，Q(e)： e是偶数，E(e1,e2)：e1=e2，L(e1,e2)：e1

② 并非所有的素数都不是偶数。

8(8分)

判断下列逻辑关系是否成立。若成立，请用指派分析法给出证明。否则，请给出相应的指派。

① $x(ØA(x)→B(x))→“xC(x)Þ”x(B(x)→C(x))；

② $x(A(x)→“yB(x,y))ÞØ”y$xB(x,y)→“xA(x)。

9(12分)

构造形式推理过程：

① ØR(ØPÚS), Q→ØS╞ P→(Q→R)；

② $x(A(x)→”yB(y))，“x(B(x)→$yC(y))╞ ”xA(x)→$yC(y)。

第三篇：离散数学试题

中央电大离散数学试题

月

一、单项选择题（每小题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分）（（

第四篇：08离散数学试题

离散数学试题

一、填空（共36分）

1、命题公式PQ的真值为假，当且仅当。

2、设F(x)：x是整数，G(x):x是自然数，则命题“并不是每个整数都是自然数”符号化为。

3、设10阶平面图G有5个面，则G中有条边。

4．设A={1，2，3，4，5，6，7}，R是A上的模4同余关系，则关系R＝。

5．六阶循环群的所有生成元为，所有子群为。

6．设集合Sa,b,c，S上所有互不相同的等价关系的数目为。

7．R是非空集合上的偏序关系，当且仅当R具有

8．仅用联结词来表示PQ为。

二、解答题（共24分）。

1． 求等价于下面公式的前束合取范式与前束析取范式。（10分）xPxyzQx,y(z)R(y,x)

2． 整数集合Z上的二元运算*定义为x*y判断Z,*是不xy2，是群？如果是，求出它的单位元以及每个元素的逆元。（8分）

3． 设A,B,C是三个集合，函数f:AB，函数g:BC。若函数

gf:AC是双射，则f和g一定都是双射函数吗？若是，请给出证明；若否，请举例说明。（6分）

三、证明题（共40分）

1．（10分）构造下面推理的证明（个体域取学生的集合）：

每个一年级学生至少有一个高年级学生作他的辅导员。凡理科学生的辅导员皆是理科学生。小王是理科一年级学生。因此，至少有一个理科高年级学生。

2．（8分）证明在至少含有3个节点的简单连通平面图中，至少有一个节点的度数小于等于5。

3．4． 证明命题的等价关系：证明在无向完全图Kn

顿图。（6分）

5． 设G为群，PQPQPQ（8分）n3中任意删去3条边后，所得到的图是哈密f:GG，xG有fxx1。证明当且仅当G是

交换群，f是G的自同构。（8分）

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

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

取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中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。