离散数学复习题

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

B. P～Q

C. P～Q

D. P～Q

2．P、Q为命题变元，则PQ的对偶式为（ ） A . PQ

B . QP

C . P～Q

D . Q～P

3．谓词公式xyP(x,y)的否定式为（ ） A .xy～P(x,y)

B .xy～P(x,y)

C .xy～P(x,y)

D .xy～P(x,y)

4．A = {1, 2, 3}，R = {| x,yAxy}为A上的一个二元关系，则下列命题中（ ）为真。 A . R不是自反的 B . R不是对称的 C . R不是传递的 D . R不是反自反的 5．若A为集合，则IA是A上的（ ）。 A . 全序关系

B . 偏序关系

C . 半序关系

D . 拟序关系

6．A = {1, 2, 3}，在下列A上的二元关系中，（ ）不是可传递的。 A . {<1, 2>}

B .{<1, 2>, <2, 1>, <1, 1>} C .AA

D . IA

7．二部图K2, 3是（ ） A. 欧拉图

B. 哈密顿图

C. 非平面图

D. 平面图

8．5阶无向完全图的边数为（ ） A. 5

B. 10

C. 15

D. 20

D. 

9．下列命题中不正确的是（ ）。 A. 

B. 

C. 

10．在A = {a, b, c}上可以定义（ ）个不同的二元关系。 A . 9

B. 18

C . 81

D . 512

12．设G是简单连通平面图，G有11个顶点，5个面，则G有（ ）条边。 A . 10

B. 12

C . 14

D . 16

13．一个连通无向图，如果它的所有顶点的度数是偶数，则它具有（ ）。 A. 哈密顿回路

B. 欧拉回路 C. 基本路径 D. 基本回路

C. Rc,a

14．设A = {a, b, c}，A上的二元关系R ={, , }，则关系R的对称闭包为（ ） A. RIA

B. R

D. RIA

15．以下命题公式中，为永假式的是（ ） A. P(PQR) C. ～(QP)P

B. (P～P)～P

D. ～(P～P)(P～P)

16．若A，B，C为集合，则A – (B – C) =（ ） A. (A－B)C

B. (AC)－B

C. A－(BC)

D. (A－B)(AC)

18．设A = { a, b, c }，则下列是集合A的划分的是（ ）

A. { {b, c}, {c} } B. { {a, b}, { a, c} } C. { {a, b}, c } D. { {a, b}, { c} } 19．在个体域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)

20．设集合X = {0, 1, 2, 3}，R是X上的二元关系，R = {(0, 0), (0, 2), (1, 2), (1,3), (2,0), (2, 1), (3, 3) }，则R的关系

矩阵是（ ）

10100100001110A.11001101B. 0011D. 00110001 01 1 00111100 C. 100001011110000101021．命题公式(PQ)(QP)在（ ）个真值指派下为T。

A . 1

B . 2

C . 3

D . 4

22．设G是n个结点m条边的连通平面图，则当n≥3时必有（ ）成立。 A. m ≤

n(n1)2 B. n = 2m C. m ≤ 3n – 6 D. n –1 = m

23. 在简单无向图G = 中，如果V中的每个结点都与其余的所有结点邻接，则该图称为（A. 正则图

B. 完全图

C. 连通图

D. 强连通图

24. 在下列关于图论的命题中，为真的命题是（ ） A.一个强连通的有向图一定是欧拉图

B.一个无向图所有顶点的度都是偶数，则它一定有欧拉回路 C.一定能构造一个欧拉图，使得结点数和边数的奇偶性相反 D.无向欧拉图中一定存在有一条边是割边

25. 给定n个结点的一个图，它还是一个树的下列说法中，（ ）是不对的。 A.无回路的连通图

B.无回路但若增加一条新边就会变成回路 C.连通且m = n –1，其中m是边数，n是结点数 D.所有结点的度数≥2

26．连通图G是一棵树，当且仅当G中（ ） A 有些边不是割边

B 每条边都是割边

C 无割边集

D 每条边都不是割边

27．下列命题公式为重言式的是（ ） A. Q→(P∧Q)

B. P→(P∧Q)

C. (P∧Q)→P

D. (P∨Q)→Q

28．下列4个推理定律中，不正确的是（ ） A. A(A∧B) B. (A∨B)∧～AB C. (A→B)∧AB

D. (A→B)∧～B～A

29．谓词公式x(P(x)∨yR(y))→Q(x)中量词x的辖域是( ) A. x(P(x)∨yR(y)) B. P(x) C. (P(x) ∨yR(y)) D. P(x), Q(x)

30．设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（ ） A. P(x)∧S(x)

B. P(a)∧P(b)∧(S(a)∨S(b)) C P(a)∧S(b)

D. P(a)∧P(b)∧S(a)∨S(b)

31．设D=为有向图, V={a, b, c, d, e, f }, E={, , , , },是（ ）A.强连通图

B.单向连通图 C.弱连通图

D.不连通图

32．在有n个结点的连通图中，其边数（ ）

A.最多有n – 1条 B.至少有n – 1条 C.最多有n条 D.至少有n条

） 33.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 34.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性

35.设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〉}

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

D.(x)(y)(A(x,y)→A(f(x,a),a))

37.设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

38.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x( ) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 39.下列不是平面图的是( )

40.设A={a,b,c}，则下列是集合A的划分的是( )

A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},c} D.{{a},{b,c}} 41.下列命题中，不正确的是( ) A.{φ}∈{φ,{φ}} B.{φ}∈{φ,{{φ}}} C.{φ}{φ,{φ}} D.φ{φ,{ φ}}

42.设个体域是正整数集，则下列公式中真值为真的公式是( ) A.(x)(y)(x·y=0) B.(x)(y)(x·y=1) C.( x)(y)(x·y=2) D.(x)(y)(z)(x-y=z)

43.令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为( )

A.(x)(F(x)∧(y)(G(y)∧H(x,y))) B.(x)(xF(x)→(G(y)→H(x,y))) C.(x)(F(x)→(y)(G(y)∧H(x,y))) D.(x)(F(x)→(y)(G(y)→H(x,y))

44.在个体域D={a,b}中，与公式(x)A(x)等价又不含量词的公式是( )

A.A(a)∧A(b) B.A(a)→A(b) C.A(a)∨A(b) D.A(b)→A(a) 45.下列句子是命题的是( ) A.水开了吗? B.x>1.5

C.再过5000年，地球上就没水了。 D.我正在说谎

46.下列是命题公式p∧(q∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 47．下列是两个命题变元p，q的极小项是（ ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 48．下列语句中是命题的只有（ ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 49．下列各图不是欧拉图的是（ ）

二、填空题

1．设个体域为整数集合，命题xy(xy0)的真值为_________ 2．PQ的主析取范式中，含有_________个极小项。 4．集合A = {,}，则幂集P(A) = _______________。

5．图G = （|V| = n, |E| = m）是树的充要条件是G连通，且n =__________。 6．无向图为欧拉图的充要条件是G连通，且G中无__________顶点。

7．数组2，3，3，4能构成无向简单的度数序列，此命题的真值为____________。

8．一个无向简单图G如果同构于图的补图，则称为自补图。5阶非同构的自补图有__________个。 9．在一颗根树中，仅有一个节点的入度为________，称为树根，其余节点的入度均为_________。 11．完全二部图Kr,s (rs)的边连通度为___________。

12．命题“设G为任意的n阶简单的哈密尔图，则u,vV(G)，均有d(u)+d(v)≥n”的真值为___________。 13．设A={2,3,4}，B={4,5,6}，R是从A到B的关系，且xRy <=> x与y互质，那么R = ____________________。 14．设全集E＝{1，2，3，4，5}，A＝{1，5}，B＝{1，2，3，4}，C＝{2，5}，则(A∩B)∪～C＝_______________ ，ρ(A)∩ρ(C)＝_____________________。

15．公式P→(Q→R)在联结词全功能集{～，∧}中等值形式之一为____________________。

16．一个连通平面图G有10条边，G中度为1的点有2个，其余是度为6的顶点，则G中共有_________个顶点，________个面。

17．设A = {2, 3, 6, 12}，≤是A上整除关系，则偏序集的最大元是_________，极小元是_________。 18．一个顶点数为n的无向完全图，其边的数目为 ；并且它是 度正则图。

19.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。 20.设A为集合，P(A)为A的幂集，则〈P(A)，〉是偏序集，若x,y∈P(A),则x,y最大下界是______，最小上界是______。

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.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。 26.有向图D如下：D的邻接矩阵A=(aij)3×3,则a11=____,a32=____。

28.设命题P为“明天上午8点下雨”，Q为“明天上午8点下雪”，R为“我去学校”，则“如果明天上午8点不下雨且不下雪则我去学校”可表示为公式________；而“只有当明天上午8点不下雪并且不下雨时我才去学校”可表示为公式________。

三、计算与证明

1、设A= {a, b, c, d, e}，给定A上的划分＝{{a, b}, {c}, {d, e}}，求由确定的等价关系，并画出它的关系图。 2、在个体域为D={a, b, c}时消去公式x(F(x)yG(y))中的量词。 3、求下列公式的主析取范式和主合取范式（结果要求用编码形式表示）： （1）(PQ)(PQ)) （2）((PQ)Q)((QR)Q)

4、设A = {a, b, c, d, e}，定义A中的关系R1 = {, , , , , , , , }，R2 = {, , , , , }，判断R1，R2是否具有自反性、对称性和传递性，然后求它们的自反闭包、对称闭包和传递闭包。 5、设集合A = {a, b, c}， （1）写出A的幂集P(A)。

（2）画出偏序关系< P(A) – {},>的哈斯图，指出该偏序关系的极大元和极小元。 6、设为偏序集，其中A={1，2，3，4，6，9，24，54}，R是A上的整除关系。 （1）画出的哈斯图； （2）求R关于A的极大元；

（3）求B={4, 6, 9}的最小上界和最大下界。

7、试画出有向图G = ，其中V = {v1, v2, v3, v4}，E = {< v1, v2>, < v2, v4>,< v2, v3>,< v3, v4>,< v4, v1>,< v4, v2>,< v4, v4>}，并求G的邻接矩阵和G中长度为1，2，3，4的路的数目。 8、判断下列公式的类型：

（1）(PQ)(PQ)) （2）((PQ)Q)((QR)Q) 9、设S为X上的关系，证明若S是自反的和传递的，则SS = S，其逆为真吗？

10设X = {1, 2, 3, 4}，R = {<1, 2>, <2, 1>, <2, 3>, <3, 4>}。求R的自反闭包、对称闭包、传递闭包。 11、求下列公式的主析取范式和主合取范式

(1) ～((P～Q)R) (2) (P(QR))(PQR) 12、证明一个自补图一定有4k或4k + 1个顶点。

13、若平面图G与其对偶图G*同构，则称G是自对偶图。设G含n个顶点m条边，证明若G是自对偶图，则m = 2(n – 1)。

14.设A={1,2,3,4,5},A上偏序关系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA; (1)作出偏序关系R的哈斯图

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

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

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

28.一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。 29证明A→(B→C),(C∧D)→E, ┓F→(D∧┓E) |- A→(B→F)成立。

四、应用题

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

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

3.某发电厂a要向b,c,d,e四个地点送电，已知发电厂可以和b,c,d直接架接电线，地点e可以和b与d直接架设电线，其他由于地理原因无法直接架设电线，在a,b,c,d和e之间架设电线时不能有回路存在，否则会造成浪费。请找出所有电线架设方案，使从a可向b，c，d，e供电。

4.对下面推理进行符号化，并作证明。会操作计算机的人都认识26个英文字母。文盲都不认识26个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。(个体域：所有人的集合)

5．设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。