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是奇数C. 2+2≠4当且仅当3是奇数2、设个体域D={a,b}，与公式A.

A(a)A(b)）。B. 2+2=4当且仅当3不是奇数D. 2+2=4仅当3不是奇数xA(x)等价的公式是( )。D.

A(b)A(a)B.

A(a)A(b)C.

A(a)A(b)3、令F(x):x是人，G(x):x是犯错误，则命题“没有不犯错误的人”可符号化为（A.x(F(x)C.x(F(x)G(x))G(x))）。B.D.x(F(x)x(F(x)G(x))G(x))4、下列命题公式不是永真式的是A.

(pq)p(

p))。C.

p(qp)B .

p(qD.

(pq)p5、设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.反对称的IA，则对应于R的划分是)。7、设集合A={1,2,3,4}，A上的等价关系R={ <3,2>, <2,3>}（）。B. {{1,3},{2,4}} A. {{1},{2,3},{4}}

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

C. {{1,3},{2},{4}} D. 8、图G1如图1所示，以下说法正确的是(

A. a是割点C. {b,d}是点割集B. {b,c}是点割集D. c是割点)。a

b

c

图1 G1d

9、设集合S={1,-1}，下面定义的哪种运算关于集合A. 普通的减法运算C. 普通的乘法运算B. 普通的加法运算D. 以上均不是S是封闭的( )。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

36

3

图2 G2三、推理及证明题1、已知A，B，C是三个集合，证明：A-(B2、构造下面推理的证明。前提：A，A→Ｂ，A→Ｃ，B→(D→结论：D

C)C)=(A-B)-C.四、综合应用题1、利用等值演算法求命题公式（PQ）赋值。r(R)，对称闭包s(R)及传递闭包t(R)。3、设有向图D如图G3所示,回答下列问题：（1）求图D的邻接矩阵；（2）求图D中长度为2的通路数；（3）求图D中长度为2的回路数；（4）求图D的可达矩阵。R的主合取范式并给出其成真赋值和成假2、设集合Ａ={a，b，c}上的二元关系R={a，b，b，a，b，c}，求R的自反闭包4、如图4-1和图4-2所示的两个图G4，G5：（1）试判断它们是否为欧拉图？并说明理由；（2）若是欧拉图，请写出一条欧拉回路；（3）若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图。a

e

j

c

d

i

h

g

f

b

a

c

b

d

e

图4-1 G4图4-2 G5x,yxyR，有5、设R为实数集合，在R上定义二元运算*，x*yxy（1）验证二元运算*是否满足结合律；（2）求二元运算*的单位元；（3）对实数x，求其逆元。离散数学期末考试复习题一、填空题1、谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。2、将以下命题进行命题符号化为______________________。(1) 李平不但聪明又用功。(2) 李平虽然聪明，但不用功。(3) 李平不但聪明，而且用功。(4) 李平不是不聪明，而是不用功。3、将以下命题进行命题符号化为______________________。(1) 人不犯我，我不犯人；人若犯我，我必犯人。(2) 不经一事，不长一智。4、命题公式　(　pq)的成真赋值为_______________________。5、命题公式(pq)(pq)的成真赋值为___________________。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的点割集是ab．fced．．22．设无向图G＝是哈密尔顿图，则V的任意非空子集V1，都有23．设有向图D为欧拉图，则图D中每个结点的入度．，m条边，当时，Kn中存在欧拉回路．24．设完全图Kn有n个结点(n≥2)25．集合A={a , b , c }上总共可定义的二元运算的个数为______。26．设A{1,1}，则关于普通加法、减法、乘法中___ ____运算是封闭的。27．设Zn{0,1,2,...,n1}，在代数系统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、下列公式中，哪个是永真式（）(pq) B.

(pq)p C.

p(pq) D.

(pq)qA.

q3、设F(x):

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

x(F(x)G(x)) D.

x(F(x)G(x))C.

4、设个体域是整数集，则下列命题的真值为真的是A．yx(xy1) B．xy(xy0)( )。2C．xy(xyy2) D．yx(xyx)5、下列命题中为假命题的是( )（其中P（A）为A的幂集）P({}) C.

P(){} D.P()P({})A．{}P() B.

6、集合A{1,2,,10}上的关系R{x,y|xy10,x,yA}，则R的性质为( )。A、自反的 B、传递的、对称的C、对称的 D、反自反的、传递的7、设R,Z,N分别表示实数、整数和自然数集，设函数f1:N{0,1,2}，f(x)xmod3，（x除以3所得的余数），f2:RR,f(x)2，f3:ZxN,f(x)|x|，f4:NNN，f(x)x,x1则上述函数中满射的个数为（）。A．1 B. 2 C. 3 D. 4

8、设R和S定义在P上，P是所有人的集合。RSx,y|x,yPx是y的母亲x,y|x,yS1Px是y的父亲，，则对于x,yR表示( )

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?g10．设图G的邻接矩阵为则G的边数为( )．A．5 B．6 C．3

11．图G如右图所示，以下说法正确的是A．{(a, d)}是割边B．{(a, d)}是边割集C．{(d, e)}是边割集D．{(a, d) ,(a, c)}是边割集(

D．4

) ．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．x*ymax{x,y}B．x*ymin{x,y}C．x*yGCD(x,y)）A是不封闭的（）。即x,y的最大公约数）D.a*b=|a-b|

D．x*yLCM{x,y}即x,y的最小公倍数15．在自然数集N上，下列哪种运算是可结合的？（A.a*b=a-bB.a*b=max{a,b} C.a*b=a+2b

16．设是正整数集Z上的二元运算，其中ab++maxa,b（即取a与b中的最大者），那么在Z中（）A．不适合交换律；B．不适合结合律；C．存在单位元；D．每个元都有逆元。三、计算题1、求命题公式(pq)(pr)的主析取范式，主合取范式及其成真成假赋值。2、求命题公式((p3、求命题公式(Pq)Q)r)p的主析取范式，主合取范式及其成真成假赋值。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)xyL(x,y)12、求出下列公式的前束范式xG(x)1)

xF(x)xG(x)2)xF(x)3)xF(x)xG(x)yG(x,y)yG(x,y,z))zH(x,y,z)xF(x)4)5)x(F(x)13、求1到1000之间不能被5、6、8整除的数的个数。14、设A＝{a,b,c,d},R＝{,,,},试给出R和r(R),s(R),t(R)的关系图。15、设图GV，E，其中Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a4,a5，a5,a2（1）试给出G的图形表示；（2）求G的邻接矩阵，关联矩阵；（3）判断图G是强连通图、单侧连通图还是弱连通图？16、设有向图D如右图所示，求图D中长度为3的通路数，并指出其中的回路数．v1v2v317、在实数集合R上定义二元运算X*YXY2X2Y6v4（1）验证*是否满足交换律和结合律。（2）求*的单位元。（3）对任何实数X，求其逆元。18、设代数系统A,*，其中A{a,b,c,d}，*运算定义如下表，请指出*运算是否是可交换的；是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。*abcdaabcdbbcdaccdabddabc19、设V=为代数系统，其中A={0,1,2,3,4}，a,bA,a*b(ab)mod5。（1）列出*的运算表（2）*是否有零元和幺元？若有幺元，请求出所有可逆元素的逆元。20、设Z为整数集合，在Z上定义二元运算*，，x,yZ，有x*yxy2，（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、构造下面推理的证明前提：AB∧C, ?B∨D , (E?P)?D, BA∧?E

结论：BE

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中至少要添加k2条边才能使其成为欧拉图．17、设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图.

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

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

(pq)q;q)p)q;xF(x));2)

((p3)

(p4)

5)

6)

7)

8)

9)

10)

p(pq)xF(x)(F(x,y)xF(x)xF(x)q;(xyG(x,y)R(x,y))xF(x);F(y);F(y);r)(pr)R(x,y);xF(x)(qq)q)(qp); 11)

(p2、如何判断一个二元关系是否具有自反性、反自反性、对称性、反对称性以及传递性（给出一种方法即可）。3、设集合A={1,2,3},A上关系R1，R2,R3，R4，....判断其各有哪些性质(用二进制码依次对是否具有自反、反自反、对称、反对称、传递性质进行标示)：1={<1,1>, <1,2>, <2,1>}; RR2={<1,2>, <2,3>, <1,3>};

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

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

5={<1,2>, <2,1>,<2,3>, <1,3>}; RR6={<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>}。24) A=B=R(实数集)， f(x)=x-x。35) A=B=R(实数集)， f(x)=x。6) A=B=R(实数集)， f(x)=x。5．给定两个图G1，G2（如下图所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出一条欧拉回路．