离散数学复习题.doc

一、选择题1若P：他聪明；Q：他用功；则“他虽聪明，但不用功”可符号化为（ ）A. B. C. D. 2P、Q为命题变元，则的对偶式为（ ）A . B . C . D . 3谓词公式的否定式为（ ）A .B .C .D .4A = 1, 2, 3，R = | 为A上的一个二元关系，则下列命题中（ ）为真。A . R不是自反的B . R不是对称的C . R不是传递的D . R不是反自反的5若A为集合，则IA是A上的（ ）。A . 全序关系B . 偏序关系C . 半序关系 D . 拟序关系6A = 1, 2, 3，在下列A上的二元关系中，（ ）不是可传递的。A . B ., , C .D . IA7二部图K2, 3是（ ）A. 欧拉图B. 哈密顿图C. 非平面图D. 平面图85阶无向完全图的边数为（ ）A. 5B. 10C. 15D. 209下列命题中不正确的是（ ）。A. B. C. D. 10在A = a, b, c上可以定义（ ）个不同的二元关系。A . 9B. 18C . 81D . 51212设G是简单连通平面图，G有11个顶点，5个面，则G有（ ）条边。A . 10B. 12C . 14D . 1613一个连通无向图，如果它的所有顶点的度数是偶数，则它具有（ ）。A. 哈密顿回路B. 欧拉回路C. 基本路径D. 基本回路14设A = a, b, c，A上的二元关系R =, , ，则关系R的对称闭包为（ ）A. B. RC. D. 15以下命题公式中，为永假式的是（ ）A. B. C. D. 16若A，B，C为集合，则A (B C) =（ ）A. B. C. D. 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时，与公式等价的是（ ）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的关系矩阵是（ ）A.B. C. D. 21命题公式在（ ）个真值指派下为T。A . 1B . 2C . 3D . 422设G是n个结点m条边的连通平面图，则当n3时必有（）成立。A.m B.n = 2mC. m 3n 6 D. n 1 = m23. 在简单无向图G = 中，如果V中的每个结点都与其余的所有结点邻接，则该图称为（）A. 正则图B. 完全图C. 连通图D. 强连通图24. 在下列关于图论的命题中，为真的命题是（）A.一个强连通的有向图一定是欧拉图B.一个无向图所有顶点的度都是偶数，则它一定有欧拉回路C.一定能构造一个欧拉图，使得结点数和边数的奇偶性相反D.无向欧拉图中一定存在有一条边是割边25. 给定n个结点的一个图，它还是一个树的下列说法中，（）是不对的。A.无回路的连通图B.无回路但若增加一条新边就会变成回路C.连通且m = n 1，其中m是边数，n是结点数D.所有结点的度数226连通图G是一棵树，当且仅当G中（）A 有些边不是割边B 每条边都是割边C 无割边集D 每条边都不是割边27下列命题公式为重言式的是（）A. Q(PQ)B. P(PQ)C. (PQ)PD. (PQ)Q28下列4个推理定律中，不正确的是（）A. A(AB)B. (AB)ABC. (AB)ABD. (AB)BA29谓词公式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上恒等关系，要使Ixa,b，b,c，c,a，b,aR为X上的等价关系，R应取( )A.c,a，a,c B.c,b，b,aC.c,a，b,a D.a,c，c,b36.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x1.5C.再过5000年，地球上就没水了。D.我正在说谎46.下列是命题公式p(qr)的成真指派的是( )A.110，111，100 B.110，101，011 C.所有指派 D.无47下列是两个命题变元p，q的极小项是（ ）AppqBpqCpqDppq48下列语句中是命题的只有（ ）A1+1=10Bx+y=10Csinx+siny0Dx mod 3=249下列各图不是欧拉图的是（ ）二、填空题1设个体域为整数集合，命题的真值为_2的主析取范式中，含有_个极小项。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 ()的边连通度为_。12命题“设G为任意的n阶简单的哈密尔图，则，均有d(u)+d(v)n”的真值为_。13设A=2,3,4，B=4,5,6，R是从A到B的关系，且xRy x与y互质，那么R = _。14设全集E1，2，3，4，5，A1，5，B1，2，3，4，C2，5，则(AB)C_ ，(A)(C)_。15公式P(QR)在联结词全功能集，中等值形式之一为_。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,yP(A),则x,y最大下界是_，最小上界是_。21.设R为非空集合A上的等价关系，其等价类记为xR。x,yA，若x,yR，则xR与yR的关系是_，而若x,yR，则xRyR=_。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.若H1H2Hn是_，则称H1,H2,Hn是相容的，若H1H2Hn是_，则称H1,H2,Hn是不相容的。25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。26.有向图D如下：D的邻接矩阵A=(aij)33,则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时消去公式中的量词。3、求下列公式的主析取范式和主合取范式（结果要求用编码形式表示）：（1） （2）4、设A = a, b, c, d, e，定义A中的关系R1 = , , , , , , , , ，R2 = , , , , , ，判断R1，R2是否具有自反性、对称性和传递性，然后求它们的自反闭包、对称闭包和传递闭包。5、设集合A = a, b, c，（1）写出A的幂集P(A)。（2）画出偏序关系的哈斯图，指出该偏序关系的极大元和极小元。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 = , ,，并求G的邻接矩阵和G中长度为1，2，3，4的路的数目。8、判断下列公式的类型：（1） （2）9、设S为X上的关系，证明若S是自反的和传递的，则SS = S，其逆为真吗？10设X = 1, 2, 3, 4，R = , , , 。求R的自反闭包、对称闭包、传递闭包。11、求下列公式的主析取范式和主合取范式 (1) (2) 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，5IA;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。15.求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。16.设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。17.求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。28.一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。29证明A(BC),(CD)E, F(DE) |- A(BF)成立。四、应用题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之间架设电