离散数学期末复习题库

数理逻辑

一、选择题。

1、下列选项中是原子命题的是（)

A、霍金去世了。B、霍金是物理学家，也是科普作家。

B、霍金的《时间简史》你看过吗?D、我看过《时间简史》，但没有看

懂。

2、下列命题中，（）不是真命题。。

A、海水是咸的当且仅当雪是白色的

B、如果1+1=2,那么7+8>16

C、若太阳从西边落下，则2是奇数

D、夏天冷当且仅当冬天热

3、下列句子不是命题的是)

A.雪是黑色的。B.江西师大是一座工厂。

C.好大的雪啊!D.若7+8>16,则三角形有4条边。

4、下列句子是命题的是（)

A.我正在说谎。B.X<Oo

C.好大的雪啊!D.如果x大于3,则X?大于9。

5、下列句子是命题的是（)

A.我正在说谎。B.X<Oo

C.好大的雪啊!D.如果x大于3,则x?大于9。

6、下列联结词中不是完备的是()

A、-\V,A}B、{-1,v}C、V,A}D、{-I,A}

7、下列选项中哪一个是复合命题?()

A、我不去看电影。B、如果x>3,那么/>9。

C、我正在说谎。D、把大象放进冰箱需要多少步?

8、公式（Pf」Q）\，R的成假解释是（P,Q,R）=（）

B、(T,T,T)B、(T,T,F)C、(T,F,T)D、(T,F,F)

9、下列选项中是合式公式的是（)

A、a+Z?+c=3B、P〈Q+RC>R^Q-^PD、R八Q—P

10、下列公式不是永真公式的是()

C、PTPB、PnPC、PvdD、

11、下列公式()为重言式.

A.―iPA—iQ<->PvQB.(Qf(PvQ))^(-.QA(PVQ))

C.(P->(「Q.P))c(「Pf(P—Q))D.(-.PV(PAQ))—Q

12、设A(x)：x是人，B(x)：x是工人，则命题“有人是工人”可符号化

为().

A.(3x)(A(x)AB(x))B.(Vx)(A(x)AB(x))

C.-|(Vx)(A(x)-*B(x))D.-|(3X)(A(x)AnB(x))

13、下列是真命题的有()

A、⑷。{⑷}；B、{{0}}e{(D,{(D}}；

C、OG({O),O)；D、{<b)€{{<D))e

14、设个体域A={a,b},公式VxP(x)A3AS(X)在A中消去两次后应为()。

A、P(x)八S(x)B、P(a)/\PS)/\(S(a)vSS))

C、P(a)八5(。)D、P(a)AP(b)AS(a)vS(b)

15、若P：他聪明；Q：他用功；则“他既聪明，又用功”，可符号化为()

A.PVQB.PAQC.P-1QD.PVnQ

16、令p：经一堑；q：长一智。

命题“只有经一堑，才能长一智”符号化为()

A.p—q；B.q—p；C.pAQ；D."«q——«p

17、设全体域D是正整数集合，下列命题的真值为真的是()

A.Vx3y(xy=y)B.3xVy(x+y=y)

C.3xVy(x+y=x)D.Vx3y(y=2x)

二、填空题

1、李敖和霍金都是作家，并且都于今年去世了。

设W(e)表示“e为作家”，D(e)表示“e于今年去世了”，a表示“李敖”；b

表示“霍金”，将语句符号化为;

2、朝鲜是中国的邻国，越南也是中国的邻国，但朝鲜不是越南的邻国。

设L(e”g)表示“弓是j的邻国”，a表示“中国”，b表示“朝鲜”；c表示“越

南”，将语句符号化为;

3、设P：我去旅游，Q：我有时间，将语句“我去旅游，仅当我有时间翻译

符号化为：o

4、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”

的符号化表示为o

谓词公式Vx(P(x)v3yR(y))fQ(x)中量词Wx的辖域是。

5、设C(x)表示x是运动员，G(x)表示x是强壮的。命题“没有一个运动员不

是强壮的”可符号化为;

6、设P：我生病，Q：我去学校，将语句“只有在我生病时，我才不去学校

命题符号化为：。

7、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的

符号化表示为。

8、谓词公式Vx(P(x)vRR(y))->Q(x)中量词Vx的辖域是

9、设P,Q的真值为0,贝!)(2人。)八(「夕\/「。)的真值=

10、设一阶逻辑公式G=X/xP(x)——>3xQ{x},则G的前束范式是

三、大题

求公式T。-Q）v（「尸人（Q-「R））的主析取范式和主合取范式。

求公式（P玲Q）AR的主析取范式和主合取范式，并指出公式的类型。

求公式（「Pf0）八（RvP）的主析取范式和主合取范式。

求命题公式（（〃v/f/）一〃主析取范式和主合取范式.

求公式（（PfQ）rP）的主析取范式和主合取范式.

四、推理题

1、如果今天是星期三，那么我有一次英语或数学测试；如果数学老师有事，

那么没有数学测试；今天星期三且数学老师有事，所以我们有一次英语测试。

2、论证：如果你上课认真听讲了，你必学好了离散数学。如果你今天考试没过，

你一定没有学好离散。你认真复习并且上课认真听了。所以你今天离散考试能

过。

3、今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看

书。故我在看书时，说明今天下雨。

4、如果今天天气好，那么我下午会去踢足球。如果今天天气不好，那么我下午

会去看电影。如果我下午去看电影，我就会邀请山姆和我一起去。山姆下午没

有去看电影。

结论：今天天气好。

5、今天我走路或者骑自行车上班。如果我骑自行车上班，则我不用伞。

如果今天下雨，并且我不用伞，则我会被雨淋湿，

今天下雨，且我没有被雨淋湿，说明我今天走路上班。

6、前提：p\/q,p―>—।厂,s—》t,-iS—>r,-if.

结论：q

7、前提：pT（q7r）,sT「q,p,s

结论：r

集合论

一、选择题

1、下列集合中元素个数最多的是（）

A、｛锐角三角形，直角三角形，钝角三角形｝

B、｛三国演义，西游记，水浒传，红楼梦｝

C、｛正弦,余弦,正切,余切,正割,余割｝

D、｛鼠，牛，虎，兔，龙，蛇，马，羊，猴，鸡，狗，猪｝

2、下列集合运算中不满足交换律的是（）

A、集合的并B、集合的交C、集合的差D、集合的对称差

3、如果二元关系a.R?都有传递性，那么（）也一定有传递性

A、KUR?B、与n&C、D、飞㊉&

4、下列关于集合的说法错误的是（）

A、集合的元素个数可以为无穷多个

B、集合可以没有元素

C、集合可以为自身的元素

D、集合可以为自身的子集

5、假设集合A=｛北京，上海，天津，重庆｝,8=｛天津，重庆，广州，深圳｝,

C=｛北京，上海，广州，深圳｝,则集合C=（）

A、A\JBB、C、A-BD、4㊉8

6、下列哪个性质没有闭包？（）

A、自反性B、传递性C、对称性D、反对称性

7、集合A=｛1,2,…,10｝上的关系R=｛<x,y>|x+y=10,x,yeA）,则R的性质为

（）o

A.自反的B.对称的C.传递的，对称的D.传递的

8、若集合A二{a,b},B={a,b,{a,b}},则（）.

A.AuB,且AwBB.AGB,但A(ZB

C.AuB,但AeBD.AaB,且A《B

9、函数/(x)=2x+3,g(x)=x2-\,则复合函数/og(x)=()

A.2x~+1B.(2x+3)2—1C.x~+2x+2D.x~—2x—4

10、A,B为两个集合，如果AGB,则下面那个是错误的。()

A、ADB#0B、〜BG〜A

C、(B-A)UA=BD、(B-A)UA=A

11、GW㊉),其中S={L2,3},㊉为集合对称差运算，

则方程{1,2馋工={1.3}的解为()o

A、{2,3}；B、{1,2,3}；

C、{1,3}；D、①。

12、下列函数是双射的为()

A.f:IfE,f(x)=2x；B.f:N-/N,f(n)=<n,

n+l>；

C.f:R-1,f(x)=[x]；D.f:I-N,f(x)=|x|o

(注：I一整数集，E—偶数集，N一自然数集，R—实数集)

13、设集合A={0,{1},{3}},则下式为真的是()

A.leAB.{3R

C.{I}o4D.0eA

14、X={a,b,c,d},Y={1,2,3,4},f从X到Y的映射，其中

f(a)=1,f(b)=4,f(c)=3,f(d)=2,ROf>()

A.双射B.满射不是单射

C.单射不是满射D.不是单射也不是满射

15、集合A={1,2,・・・,10}上的关系R={<x,y>|x+y=10,x,ywA},则R的性质为

()o

A、自反的B、对称的C、传递的，对称的D、传递的

-010-

16、设集合A={a,b,c}上的二兀关系R的关系矩阵胚=][0，

010

那么R=()o

A.{<ab>t<bta>t<6,及,<a,c»

B.{<a,b>y<bfa>,<bfb>,<cfb>}

C.{<5,b>,<a,a>t<btb>,<c,a>}

D.{<&必―,<c,a>}

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

A.leAB.{1,2,3}c4

C.{{4,5}0D.0EA

18、X={a,b,c,d,e},Y={1,2,3,4},f从X到Y的映射，其中

f(a)=1,f(b)=4,f(c)=2,f(d)=3,f(e)=4,则f是()

A.双射B.满射不是单射

C.单射不是满射D.不是单射也不是满射

19、设R是集合A={1,2,3,4)上的二元关系，R={<2,1>,<2,3>,<1,3>},则

下列()不成立。

A、R是自反关系B、R是反自反关系

C、R是反对称关系D、R是传递关系

010'

20、设集合A={a,b,c}上的二元关系R的关系矩阵四=110,

100

那么R=(),

A.{<a,力,<b,a>,<bfb>t<&c>}

B.{<a力,<bfa>,<6,力,<c,b>}

C.{<5,b>,<a,a>t<btb>,<c,a>}

D.{<a,必―,<c,a>}

21、设A={a,{a}},下列命题错误的是()。

A.{a}£P(A)B.{a}Gp(A)

C.{{a}}eP(A)D.{{a}}「P(A)

22.若A-B=①，则下列哪个结论不可能正确？()

A.A二①B.B=①C.AED.B5

23.集合A={1,2,—,10}上的关系R={<x,y>|x+y=10,x,y€A},

则R的性质为()o

A.自反的B.对称的C.传递的，对称的D.传递的

24、S={a,b,c},S上的等价关系至多有（）

A.3个；B.4个;C.5个；D.6个

二、填空题

1、一元关系N={(1,2),(2,3),(1,3),(1,1)},/?2={(1,2),(2,1),(1,3),(3,1)},则

KoR、=,R、o&=

3、右边哈斯图中偏序集A=

4、二元关系R[={(1,1),(2,1),(2,3),(3,1)},

&={(L2),(2,1),(3,3)},则N。&=,;

5•设A={{1},{2},1,2},B={1,2,{1,2}},则(1)A-B=,

(2)AxB=o

6.设S={1,2,3,4},A上的关系区={<1,2),〈2,1〉，〈2,3〉，〈3,4〉}

则(1)RoR=(2)R*4=o

7、集合4:{2,{6}}的幕集2、o

8、设集合A={1,2,3,4},A上的关系R={(1,4),(2,3),(3,2)},

则R2=.RJ=

9、设集合A、B为两个集合，A={l,2,4},B={l,3}JMAn8=tAxB

10、设集合A、B为两个集合，A={1,2,4},B={3,4},则An8=__________t

4U8=iA—B=

11、设A={l,2},B={a,b,c},C={c,d},则4X(8cC)=

12、设集合/4={1,2,3,4},A上的关系

6

/?,={(1,4),(2,3),(3,2)},

则

&={(2,1),(4,3),(3,2)},KOR2=

13、设A={1,2,3},则A上既不是对称的又不是反对称的关系

R=;A上既是对称的又是反对称的关系

R=o

14、设集合A、B为两个集合，A={a,b,c},B={c,d}/IJA-8=t

B-A=rA㊉4=r

15、设4={1,2,3},二元关系A={(1,1),(1,2),(2,1)},%={(U),(2,2),(3,3)},

叫=则与。&=

{(1,2),(2,3),(1,3)},,R2OR=,

&。Ri=_______

16.设集合A={1,2,3,4},A上的关系l={(1,4),(2,3),(3,2)},

&={(2,1),(4,3),(3,2)},则&。6=.

17.设集合A、B为两个集合，4={1,2,3,4},3={3,4},则人。8

二,A\JB-tA—B=

18.设A={0},8={a,b,c},C={Gd},则AX(8cC)二

三、大题

-i11r

1、设集合八={々ec,d}上的二元关系R的关系矩阵为;；；；

0101

写出自反闭包r(/?),对称闭包s(H)和传递闭包KR)的关系矩阵。

1000

2、设集合A={〃/c,d}上的二元关系R的关系矩阵为:1::

0011

写出自反闭包NR),对称闭包s(R)和传递闭包f(R)的关系矩阵。

3、设A={1,2,3,4,5},A上二元关系丁二代工尸山工小丁是素数},

(1)画出的T的关系图，写出T的关系矩阵；

(2)求出T的自反闭包、对称闭包和传递闭包的关系矩阵。

4、设A={1,2,3,4,5},R={(1,2),(2,3),(3,4)(4,3)(2,5)(5,5)}。求R

的自反闭包r(R),对称闭包s(R),传递闭包t(R)。

5,设4=匕，b,c,d},R={(a,b),(b,c),(c,d))<,求R的自反闭包r(R),对

称闭包s(R),传递闭包t(R)。

6、设集合A={〃也c,4}上的二元关系R的关系矩阵为

"1000、

1011

MR=

K0000

I。001人求

-111O-

7.设集合八={々力心力上的二元关系R的关系矩阵为:1::

0011

求r(R),s(R),«R)。

-01r

8.设集合A={a也c}上的二元关系R的关系矩阵为11()

101

求r(R),s(R)J(R)。

9、设A={1,2,3,4},R={(1,2),(2,3),(3,4)}。求R的自反闭包r(R),对称

闭包s(R),传递闭包t(R)。

10.（6分）集合A={1,2,3,4}上的偏序关系图为如下，请画出其哈斯图。

（2）写出其极大、极小，最大、最小元。

图论

一、选择题

1、如果一个无向图中每个顶点的度数都是3,那么它可能有（）个顶点

A、19B、91C、29D、92

2、下列说法正确的是（）

A、树至少应该含有一条边

B、至少含有两个顶点的树至少应该有两片树叶

C、树的分枝点一定比树叶少

D、带权连通图的最小生成树是唯一的

3、下列说法错误的是（）

A、无向图中度数为奇数的顶点有偶数个

B、连通且无圈的无向图就是树

C、顶点度数集完全相同的两个无向图必然同构

D、欧拉图中所有顶点度数均为偶数

4、已知一颗树有七个2度顶点，五个3度顶点，三个4度顶点，则有多少个1

度顶点？（）

B、12B、13C、14D、15

5、无向连通图有28个顶点，它最少有多少条边？（)

A、26B、27C、28D、29

6、下列说法错误的是（）

C、两个无向图同构，则顶点度数序列一定相同

B、带权连通图的最小生成树可以不唯一

C、有向图去掉各边方向所得无向图连通，则有向图单侧连通

D、强连通的有向图必然单侧连通

7、无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有（）

个4度结点.

A.3B.2C.1D.0

8、若连通图G=<KE>,其中=则要删去弓中（）条边,

才能确定G的一棵生成树。

A.n+m-1B.n-m+1C.m-n+lD.m-n-l

9、给定无向图G如右图所示，下面给出的结点集子集中,

不是点割集的为（).

A.{6,MB.{M

C.{a,c}D.{&e}

10、设G是连通平面图,有0个结点，e条边,r个面，则r=（）.

A.e—v+2B.r+e-2

C.e-v—2D.e+P+2

11、设G为9阶无向图，每个结点度数不是5就是6,则G中至少有（)

个5度结点。

A、4B、5C、6D、7

12、下图中，（A）是欧拉图。

[A][B][C][D]

13、设G是一个哈密尔顿图，则G一定是（）。

A.欧拉图B.树C.平面图D.连通图

14、一棵树有2个2度顶点,1个3度顶点,3个4度顶点，则其1度顶点为（）o

A.9B.8C.7D.5

二、填空题

1、右图（是/不是）欧拉图,

（是/不是）哈密尔顿图。

2、下图（是/不是）欧拉图，（是/不是）哈密尔顿图

3.右图不是欧拉图，是哈密尔顿图。（填“是”

是“）

6.在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树

中应该有6片树叶。

三、大题

1、无向图G=(V,E),其中V={a,b,c,d,e,f,g},

E={{a,b},{a,c},{a,d},{b,e},{c,d}>{c,f},{d,e}>{d,f},{e,g},{f,g}}

对应边的权值依次为4,3,1,5,2,7,6,8,9,10.(如上图)

(1)写出G的邻接矩阵；

(2)求出G权最小的生成树及其权值：

(3)求出从顶点a到顶点g的最短路径及其长度。

2、无向图G=(V,E),其中V={a,b,c,d,e,f},

E={{a,b},{a,c},{b,d},{c,d},{c,e},{c,f},{d,f},{e,f}}

对应边的权值依次为1,3,5,2,6,4,7,8(如上图)

(1)写出G的邻接矩阵；

(2)求出G权最小的生成树及其权值；

(3)求出从顶点a到顶点f的最短路径及其长度。

3、无向图G=(V,E),其中V={a,b,c,d,e,f},E={{a,b},{a,c},{b,c},{b,d},{b,e},

{c,d},{c,e},{d,e},{d,f},{e,f}},对应边的权值依次为2,4,5,7,3,2,1,6,4,3

(1)画出G的图形；

(2)写出G的邻接矩阵；

(3)求出G权最小的生成树及其权值；

(4)求出从顶点a到顶点f的最短路径及其长度。

4、求下面带权图的最小生成树。

5、图作＜匕£)，其中V={a,b,c,d、e,f}fZF{(a,m,(a,c),

(a,e),(b,d),(b,e),(Ge),(d,e),(d/),(e,/)},

对应边的权值依次为5,2,1,2,6,1,9,3及8.

(1)画出G的图形；

(2)写出G的邻接矩阵；

(3)求出G权最小的生成树及其权值.

6.无向图(G,E),G={a,b,c,d,e),

E={{a,0},{a,c},{4d},g,c},{b,e},{c,e},m,e}},其权值分别为1,4,5,2,6,3,7.

(1)画出无向图。

(2)求最小生成树及其权值。

(3)求出从。到e最短路径及其长度。(10分)

7、无向图G=(V,E),其中V={a,b,c,d,e,f},

E={{a,b},{a,c},{b,c},{b,d},{b,e),{c,d},{c,e},{d,e},{d,f}»{e,f}},

对应边的权值依次为1,4,2,7,8,2,5,2,4,1

(1)画出G的图形；(2)写出G的邻接矩阵；

(3)求出G权最小的生成树及其权值；

(4)求出从顶点a到顶点f的最短路径及其长度。

7.无向图年(V,E),其中V={a,b,c,d,e}.

E={{a,b},{a,c},{b,c},{b,d},{c,d},{c,e},{d,e}},

对应边的权值依次为2,5,2,6,3,7,3

(1)画出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的生成树及

其权值；

(4)求出从顶点a到顶点e的最短路径及其长度。

8.图0<匕£>,其中片{a,b,c,d,e,f、,层{(a,b),(a,c),

(a,e),(b,d),(b,e)t(c,e),(d,e)t(d,/),(e,/)),

对应边的权值依次为5,2,1,2,6,1,9,3及8.(1)画出G的图形；(2)

写出G的邻接矩阵；(3)求出G权最小的生成树及其权值.

9.求下面带权图的最小生成树。

代数结构

一、填空题

1、定义二元运算*:〃冲=。+8+3。那么下列说法错误的是()

A、(N,*)是半群B、(Z,*)是半群C、(N,*)是群D、(Z,*)是群

2、下列关于群环域说法错误的是()

A、每一个群都是半群B、每一个域都是环

C、含幺半群就是群D、可换除环就是域

3、下列说法正确的是()

A、实数集R在普通乘法下构成群

B、实数集R在普通加法下构成群

C、自然数集N在普通乘法下构成群

D、自然数集N在普通加法下构成群

4、下列哪个选项是群()

A、无理数集合O'定义普通加法

B、4={0,1,2,3}定义乘法区:。勤=刈除以4的余数

C、Z,={0,1,2,3,4}定义乘法③：。③匕=刈除以5的余数

D、〃阶矩阵定义矩阵乘法

5、下列说法正确的是()

A、自然数集N按普通数的乘法构成群

B、〃阶矩阵按矩阵乘法构成群

C、整数环按整数的加法成群，按整数的乘法成半群

㊉01@01

D、在集合4二{0,1}上定义㊉：001,③：000,贝11(4,㊉,⑼为域

110101

6、在自然数集N上，下列哪种运算是可结合的？()

A.a*b=a-bB.a*b=max{a,b}C.a*b=a+2bD.a*b=|a-b|

7、下面那个代数系统表示的范围最大？()

A、群B、半群

C、阿贝尔群D、独异点

8、下列各代数系统中不含有零元素的是()

A.<Q,*)Q是全体有理数集，*是数的乘法运算

B.〈Mn(R),*〉，Mn(R