2023年7月19日发(作者：)

题型

一、填空题

1、设集合A有n个元素，那么A的幂集P(A)的元素个数为____________。

2、谓词公式xF(x)Q(x,y)中的前束范式为______________。

3、设集合A＝{a,b,{a,b}}，B＝{{a,b}},则B-A=_____________。

4、设集合A＝{0,1}，B＝{1,2},则A×B=_____________________________________。

5．已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是 。

二、单项选择题

1、下列各命题中真值为真的命题有（ ）。

A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数

C. 2+2≠4当且仅当3是奇数 D. 2+2=4仅当3不是奇数

2、设个体域D={a,b}，与公式xA(x)等价的公式是( )。

A.

A(a)A(b) B.

A(a)A(b) C.

A(a)A(b) D.

A(b)A(a)

3、令F(x):x是人，G(x):x是犯错误，则命题“没有不犯错误的人”可符号化为（ ）。

A.x(F(x)G(x)) B.x(F(x)G(x))

C.x(F(x)G(x)) D.x(F(x)G(x))

4、下列命题公式不是永真式的是( )。

A.

(pq)p B .

p(qp) C.

p(qp) D.

(pq)p

5、设X={1,2,3},Y={a,b,c},f={<1,b>,<2,a>,<3,a>},则以下命题正确的是( )。

A．f是从X到Y的二元关系，但不是从X到Y的函数

B．f是从X到Y的函数，但不是满射的，也不是单射的

C．f是从X到Y的满射，但不是单射 D．f是从X到Y的双射

6、设集合A={a, b, c}，A上的二元关系R={, , }，则R是( )。

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

7、设集合A={1,2,3,4}，A上的等价关系R={ <3,2>, <2,3>}IA，则对应于R的划分是（ ）。

A. {{1},{2,3},{4}} B. {{1,3},{2,4}} C. {{1,3},{2},{4}} D.

{{1},{2},{3},{4}}

8、图G1如图1所示，以下说法正确的是( )。

A. a是割点 B. {b,c}是点割集

C. {b,d}是点割集 D. c是割点

a

b

c

图1 G1

d

9、设集合S={1,-1}，下面定义的哪种运算关于集合S是封闭的( )。

A. 普通的减法运算 B. 普通的加法运算

C. 普通的乘法运算 D. 以上均不是

10、集合A={2,3,6,12,24,36}上的偏序关系R的哈斯图G2如图2所

示，则集合B={2,3,6}的最小元为（ ）。

A. 2 B. 3 C. 2和3 D. 不存在

24

12

6

2

3

36

图2 G2

三、推理及证明题

1、已知A，B，C是三个集合，证明：A-(BC)=(A-B)-C.

2、构造下面推理的证明。

前提：A，A→B，A→C，B→(D→C)

结论：D

四、综合应用题

1、利用等值演算法求命题公式（PQ）R的主合取范式并给出其成真赋值和成假赋值。

2、设集合Ａ={a，b，c}上的二元关系R={a，b，b，a，b，c}，求R的自反闭包r(R)，对称闭包s(R)及传递闭包t(R)。

3、设有向图D如图G3所示,回答下列问题：

（1）求图D的邻接矩阵；

（2）求图D中长度为2的通路数；

（3）求图D中长度为2的回路数；

（4）求图D的可达矩阵。

4、如图4-1和图4-2所示的两个图G4，G5：

（1）试判断它们是否为欧拉图？并说明理由；

（2）若是欧拉图，请写出一条欧拉回路；

（3）若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图。

c

a

b

b

d

e

a

e

f

j

g

i

d

c

h

图4-1 G4 图4-2 G5

5、设R为实数集合，在R上定义二元运算*，x,yR，有

x*yxyxy

（1）验证二元运算*是否满足结合律；

（2）求二元运算*的单位元；

（3）对实数x，求其逆元。

离散数学期末考试复习题

一、填空题

1、谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是 。

2、将以下命题进行命题符号化为______________________。

(1) 李平不但聪明又用功。

(2) 李平虽然聪明，但不用功。

(3) 李平不但聪明，而且用功。

(4) 李平不是不聪明，而是不用功。

3、将以下命题进行命题符号化为______________________。

(1) 人不犯我，我不犯人；人若犯我，我必犯人。

(2) 不经一事，不长一智。

(　pq)的成真赋值为_______________________。 4、 命题公式　5、命题公式(pq)(pq)的成真赋值为 ___________________。

6、将命题“没有一个运动员不是强壮的”谓词符号化为___________________。

7、给定简单命题函数：

A(x)：x身体好， B(x)：x学习好， C(x)：x工作好，

复合命题函数 A(x)→(B(x)∧C(x))表示的含义是：________________。

8、将下列命题符号化：________________。

(1)偶数均能被2整除. (2)存在着偶素数. (3)没有不吃饭的人.(4)素数不全是奇数.

9、公式xP(x)xQ(x)的前束范式为_____________________________。

10、谓词公式(xF(x，y)yG(x，y))的前束范式为 。

11、在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。

12、若集合A＝{a,b},B＝{0,1,2},则A×B为______________________；B×A为______________________。

13、设集合A = {1, 2}，则P(A)为________________； P(A)×A为_______________________。

14、设集合A={0, 1}, B={1, 2}, C={0, 1, 2} ，则A, B和C的笛卡尔积A×B×C为：________________________。

15、请用谓词表达式（或枚举方式）描述实数集上子集A上的小于等于关系__________________；正整数集合的子集B上的整除关系____________________；集合C的幂集上的包含关系_________________；集合D={1,2,3,4,5,6,7}上的模3同余关系__________________________。

16．设R是定义在集合A{1,2,3,4}上的二元关系R{1,1,1,2,2,3,1,4}，则R的对称闭包s(R)_______________。

17、命题“所有的人都是要死的”的否定的含义是___________。

18、设集合A中有m个元素，集合B中有n个元素，则集合A和集合B的笛卡尔积A×B中含有___________个元素，定义在集合A和集合B上不同的二元关系有___________个，从集合A到集合B不同的函数有___________个。

19．无向连通图是欧拉图的充分必要条件是____________________。

20．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则 G的边数是 ．

21．设给定图G(如下图所示)，则图G的点割集是 ．

b

a





c

f





d

e



22．设无向图G＝是哈密尔顿图，则V的任意非空子集V1，都有 ．．

23．设有向图D为欧拉图，则图D中每个结点的入度 ．

24．设完全图Kn有n个结点(n≥2)，m条边，当 时，Kn中存在欧拉回路．

25．集合A={a , b , c }上总共可定义的二元运算的个数为______。

26．设A{1,1}，则关于普通加法、减法、乘法中___ ____运算是封闭的。

27．设Zn{0,1,2,...,n1}，在代数系统Zn,,中，,分别表示模n的加法和乘法，则Zn对运算的单位元是______，

Zn对的单位元是_______。

28．设G={1 , 2 , 3 , 4 , 5, 6}，G关于模7乘法构成代数系统，群G的幺元是_________，元素3与______互为逆元。

二、单项选择题

1、下列句子中有（ ）个是命题。

(1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。A. 1 B . 2 C. 3 D. 4

2、下列公式中，哪个是永真式（ ）

A.

q(pq) B.

(pq)p C.

p(pq) D.

(pq)q

3、 设F(x):

x是有理数，G(x)：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为( )。

A.

x(F(x)G(x)) B.

x(F(x)G(x))

C.

x(F(x)G(x)) D.

x(F(x)G(x))

4、 设个体域是整数集，则下列命题的真值为真的是( )。

A．yx(xy1) B．xy(xy0)

C．xy(xyy2) D．yx(xyx2)

5、下列命题中为假命题的是( )（其中P（A）为A的幂集）

A．{}P() B.

P({}) C.

P(){} D.P()P({})

6、 集合A{1,2,L,10}上的关系R{x,y|xy10,x,yA}，则R的性质为( )。

A、自反的 B、传递的、对称的

C、对称的 D、反自反的、传递的

7、设R,Z,N分别表示实数、整数和自然数集，

设函数f1:N{0,1,2}，f(x)xmod3，（x除以3所得的余数），

f2:RR,f(x)2x，f3:ZN,f(x)|x|，f4:NNN，f(x)x,x1

则上述函数中满射的个数为（ ）。

A．1 B. 2 C. 3 D. 4

8、设R和S定义在P上，P是所有人的集合。Rx,y|x,yPx是y的父亲，Sx,y|x,yPx是y的母亲 ，则对于x,yS1R表示( )

A.x是y的丈夫 B.x是y的妻子 C. x是y的孙子 D.x是y的祖母

9、设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（ ）．

A. f◦g B. g◦f C. f◦f D. g◦g

10．设图G的邻接矩阵为

则G的边数为( )．

A．5 B．6 C．3 D．4

11．图G如右图所示，以下说法正确的是 ( ) ．

A．{(a, d)}是割边

B．{(a, d)}是边割集

C．{(d, e)}是边割集

D．{(a, d) ,(a, c)}是边割集

12．无向图G存在欧拉通路，当且仅当( )．

A．G中所有结点的度数全为偶数

B．G中仅有有两个奇数度结点

C．G连通且所有结点的度数全为偶数

D．G连通且仅有两个奇数度结点

13．设S={a,b}，则S上总共可定义的二元运算的个数是（ ）

A.4 B.8 C.16 D.32

14．设集合A{1,2,3,...,10}，下面定义的哪种运算关于集合A是不封闭的（ ）。

A．x*ymax{x,y} B．x*ymin{x,y}

C．x*yGCD(x,y) 即x,y的最大公约数

D．x*yLCM{x,y} 即x,y的最小公倍数

15．在自然数集N上，下列哪种运算是可结合的？（ ）

A.a*b=a-b B.a*b=max{a,b} C.a*b=a+2b D.a*b=|a-b|

+16．设是正整数集Z上的二元运算，其中abmaxa,b（即取a与b中的最大者），那么在Z中（ ）

A．不适合交换律；B．不适合结合律；C．存在单位元；D．每个元都有逆元。

三、计算题

1、 求命题公式(pq)(pr)的主析取范式，主合取范式及其成真成假赋值。

+ 2、 求命题公式((pq)r)p的主析取范式，主合取范式及其成真成假赋值。

3、 求命题公式(PQ)R主析取范式，主合取范式及其成真成假赋值。

4、 求命题公式p  (q  r)主析取范式，主合取范式及其成真成假赋值。

5、给定集合A={a,b,c,d}，给出A上的所有等价关系。

6、给定集合A={a,b,c}，给出A上的所有等价关系。

7、设A={a,b,c,d}。下列哪个是A的划分,请说明原因？若是划分，则求其诱导的等价关系？

（1）B={{a},{b,c},{d}};

（2）C={{a,b},{c},{a,d}};

（3）D={{a},{b,c}}

8、设A,R为偏序集，其中A{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求A中的极大元最大元、最小元、极大元、极小元。

9、设集合A{1,2,3,4,6,9,12,18,36}，R为A上的整除关系，则R为偏序关系。

1) 求该关系的哈斯图；

2) 令B{2,3,6}，求B的最大元、最小元、极大元、极小元、上界，上确界，，下界和下确界。

10、 设集合A{a,b,c,d}，R为A上的二元关系，且R{(a,b),(b,c),(c,a),(d,d)}，

1) 求R的关系矩阵；

2) 求R的性质；

3) 求R的自反闭包，对称闭包以及传递闭包t(R)；

11、 给定解释I如下：

(1) D1={2,3}； (2) D1中特定元素a=2；

(3) 函数f(x)为f(2)=3,f(3)=2；

(4)谓词F(x)为F(2)=0;F(3)=1;G(x,y)为G(i,j)=1,i,j=2,3;

L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;

在解释I下，求下列各式的真值。

1)x(F(x)G(x,a))

2)x(F(f(x))G(x,f(x)));

3)xyL(x,y)

12、求出下列公式的前束范式

1)

xF(x)xG(x)

2)xF(x)xG(x)

3)xF(x)xG(x)

4)xF(x)yG(x,y)

5)x(F(x)yG(x,y,z))zH(x,y,z)

13、求1到1000之间不能被5、6、8整除的数的个数。

14、设A＝{a,b,c,d},R＝{,,,},试给出R和r(R),s(R),t(R)的关系图。

15、设图GV，E，其中Va1, a2, a3, a4, a5,Ea1, a2，a2, a4，a3, a1， a4, a5，a5, a2

（1）试给出G的图形表示；

（2）求G的邻接矩阵，关联矩阵；

（3）判断图G是强连通图、单侧连通图还是弱连通图？

16、设有向图D如右图所示，求图D中长度为3的通路数，

并指出其中的回路数．

v1

v2

v3

17、在实数集合R上定义二元运算X*YXY2X2Y6

v4

（1） 验证*是否满足交换律和结合律。

（2） 求*的单位元。

（3） 对任何实数X，求其逆元。

18、设代数系统A,*，其中A{a,b,c,d}，*运算定义如下表，请指出*运算是否是可交换的；是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。

*abcdaabcdbbcdaccdabddabc

19、设V=为代数系统，其中A={0,1,2,3,4}，a,bA,a*b(ab)mod5。

（1）列出*的运算表

（2）*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。

20、设Z为整数集合，在Z上定义二元运算*，，x,yZ，有

x*yxy2，

（1）二元运算*满足结合律吗？

（2）二元运算*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。

（3）Z与二元运算*是否构成群，为什么。

22、学生会下设6个委员会, 第一委员会={张, 李, 王}, 第二委员会={李, 赵, 刘}, 第三委员会={张, 刘, 王}, 第四委员会={赵, 刘, 孙}, 第五委员会={张, 王}, 第六委员会={李, 刘, 王}. 每个月每个委员会都要开一次会, 为了确保每个人都能参加他所在的委员会会议, 这6个会议至少要安排在几个不同时间段?

23、某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会，每个地方只能去一人. 已知a只想去上海，b只想去广州，c, d, e都表示想去广州或香港. 问该课题组在满足个人要求的条件下，给出一种派遣方案？

24、有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈?

25、画出下面平面图的对偶图

四、推理及证明。

1、如果我上街,我一定去新华书店.我没上街,所以我没去新华书店.

2、若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。

3、如果今天是星期一,则要进行英语或离散数学的考试.如果英语老师有会,则不考英语.今天是星期一,英语老师有会,所以进行离散数学的考试.

4、构造下面推理的证明

前提：q→p，q  s，s  t, t  r

结论：p  q  s  r

5、判断下列推理是否正确。先将命题符号化，再写出前提和结论，然后进行判断。

a) 如果今天是1号，则明天是5号，今天是1号，所以明天是5号。

b) 如果今天是1号，则明天是5号，明天是5号，所以今天是1号。

c) 如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。

d) 如果今天是1号，则明天是5号，明天不是5号，所以今天不是1号。

6、构造下面推理的证明

前提：P→Q，¬(Q∨R)

结论：¬P

7、构造下面推理的证明

前提：(P∧Q)→R，¬R∨S，¬S，P

结论：¬Q

8、构造下面推理的证明

前提：AB∧C, ¬B∨D , (E¬P)¬D, BA∧¬E

结论：BE

9、给定集合A，证明P(A)上的包含关系为偏序关系。

10、给定有限集合A，证明A上的小于等于关系为偏序关系。

11、设A,R为偏序集，其中A{1,2,3,4,5,6,7,8,9}，R是A上的整除关系，试证明R为偏序关系。

12、令I是整数集合，I上关系R定义为：R={|x-y可被m整除}，求证R是自反、对称和传递的。

13、已知A、B、C是三个集合，证明以下集合恒等式。

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

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

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

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

14、若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

15、设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中 的奇数度顶点个数相等．

16、设连通图G有k个奇数度的结点，证明在图G中至少要添加k条边才能使其成为2欧拉图．

17、设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图.

18、证明K5 和 K3,3不是平面图.

五、判断题

1、下列命题公式的类型，若为可满足式，给出成真赋值

1)

(pq)q;

2)

((pq)p)q;

3)

(pq)q;

4)

xF(x)(xyG(x,y)xF(x));

5)

(F(x,y)R(x,y))R(x,y);

6)

xF(x)xF(x);

7)

xF(x)F(y);

8)

xF(x)F(y);

9)

p(qr)

10)

(pq)(pr)

11)

(pq)(qp);

2、如何判断一个二元关系是否具有自反性、反自反性、对称性、反对称性以及传递性（给出一种方法即可）。

3、设集合A={1,2,3},A上关系R1，R2,R3，R4，....判断其各有哪些性质(用二进制码依次对是否具有自反、反自反、对称、反对称、传递性质进行标示)：

R1={<1,1>, <1,2>, <2,1>};

R2={<1,2>, <2,3>, <1,3>};

R3={<1,1>, <3,3>};

R4={<1,1>, <2,2>, <3,3>, <1,2>, <1,3>, <2,1>};

R5={<1,2>, <2,1>,<2,3>, <1,3>};

R6={<1,1>, <2,2>, <3,3>, <1,2>, <1,3>};

......

4、判断以下f、g、h是否为从A到B的函数，若是，再判断是否是单射、满射或双射；若不是，请说明理由。

1) A={1,2,3,4,5}，B={6,7,8,9,10}，f={<1,8>, <3,9>, <4,10>, <2,6>, <5,9>}。

2) A={1,2,3,4,5}，B={6,7,8,9,10}，g={<1,8>, <3,10>, <2,6>, <4,9>}。

3) A={1,2,3,4,5}，B={6,7,8,9,10}，h={<1,7>, <2,6>, <3,8>, <4,5>, <1,9>,

<5,10>}。

4) A=B=R(实数集)， f(x)=x2-x。

5) A=B=R(实数集)， f(x)=x3。

6) A=B=R(实数集)， f(x)=x。

5．给定两个图G1，G2（如下图所示）：

（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．

（2）若是欧拉图，请写出一条欧拉回路．