《离散数学题库及复习资料.docx》由会员分享，可在线阅读，更多相关《离散数学题库及复习资料.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学题库与答案离散数学题库与答案一、选择或填空一、选择或填空（数理逻辑部分）（数理逻辑部分）1、下列哪些公式为永真蕴含式？(A)PQ)=(PPQ=PQ(3)P=PQ(4)Q=QP(2)(1)答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？()Q)PR)(2)P(QQ)(3)(PQ)(Q(1)(PQ)(4)P(P答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?()QQ=PQ=P(3)PQ(2)P(1)P=PPQ)=(PP(PQ)=P(6)(PQ)=Q(5)(4)P答：（2）是第三章的
2、化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式x(A(x)B(y，x)z C(y，z)D(x)中，自由变元是()，约束变元是()。答：x,y,x,z（考察定义在公式x A 和x A 中，称x 为指导变元，A为量词的辖域。在x A 和x A 的辖域中，x 的所有出现都称为约束出现，即称 x 为约束变元，A 中不是约束出现的其他变项则称为自由变元。于是 A(x)、B(y，x)和z C(y，z)中 y 为自由变元，x 和 z 为约束变元，在 D(x)中 x 为自由变元）5、判断下列语句是不是命题。若是，给出命题的真值。()(1)北京是
3、中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗？(4)若 7+818，则三角形有 4 条边。(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。）6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或 或变且”）7、设 P：我生病，Q：我去学校，则下列命题可符号化为()。(1)只有在生病时，我才不去学校(2)若我生病，则我不去学
4、校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校（注意“只有才”和“除非就”两者PQ 答：（1）QP（4）QP（3）QP都是一个形式的）（2）8、设个体域为整数集，则下列公式的意义是()。(1)xy(x+y=0)(2)yx(x+y=0)答：（1）对任一整数 x 存在整数 y 满足 x+y=0（2）存在整数 y 对任一整数 x 满足 x+y=09 9、设全体域 D 是正整数集合，确定下列命题的真值：(1)xy(xy=y)()(2)xy(x+y=y)()(3)xy(x+y=x)()(4)xy(y=2x)()答：（1）F(反证法：假若存在，则（x-1）*y=0 对所有的 x 都
5、成立，显然这个与前提条件相矛盾)（2）F（同理）（3）F（同理）（4）T（对任一整数 x 存在整数 y 满足条件 y=2x 很明显是正确的）10、设谓词 P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式x(P(x)Q(x)在哪个个体域中为真?()(1)自然数(2)实数(3)复数(4)(1)-(3)均成立答：（1）（在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了）11、命题“2 是偶数或-3 是负数”的否定是（）。答：2 不是偶数且-3 不是负数。12、永真式的否定是（）(1)永真式(2)永假式(3)可满足式(4)(1)-(3)均有可能答：（2）
6、（这个记住就行了）EMBED Equation.3Q)化简为（），公式P(Q)P13、公式(Q)可化简为（）。(P(PQP（考查分配率和蕴含等值式知识的掌握）P，Q答：Q(x)中 量 词 x 的 辖 域 是14、谓 词 公 式 x(P(x)yR(y)（）。答：P(x)yR(y)（一对括号就是一个辖域）15、令 R(x):x 是实数，Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。Q(x)x(R(x)答：（集合论部分）（集合论部分）16、设 A=a,a，下列命题错误的是（）。P(A)(4)P(A)(3)aP(A)(2)a(1)aP(A)a答：(2)（a是 P（A）的一
7、个元素）之间写上正确的符号。17、在 0（）(4)(3)(1)=(2)答：(4)（空集没有任何元素，且是任何集合的子集）18、若集合 S 的基数|S|=5，则 S 的幂集的基数|P(S)|=（）。答：32（2 的 5 次方 考查幂集的定义，即幂集是集合 S 的全体子集构成的集合）+16 且2xR,Q=x|5EMBED Equation.34 且 x219、设 P=x|(x+1)R,则下列命题哪个正确（）xQ(4)P=QP(3)PP(2)Q(1)Q答：（3）（Q 是集合 R，P 只是 R 中的一部分，所以 P 是 Q 的真子集）20、下列各集合中，哪几个分别相等()。(1)A1=a,b(2)A2
8、=b,a(3)A3=a,b,a(4)A4=a,b,c(5)A5=x|(x-a)(x-b)(x-c)=0(6)A6=x|x2-(a+b)x+ab=0答：A1=A2=A3=A6，A4=A5（集合具有无序性、确定性和互异性）21、若 A-B=，则下列哪个结论不可能正确？()AB(4)B(1)A=(2)B=(3)A答：（4）（差集的定义）22、判断下列命题哪个为真?()(1)A-B=B-A=A=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若 A 的一个元素属于 B，则 A=B答：（1）（考查空集和差集的相关知识）23、判断下列命题哪几个为正确？(),(3)(1),(2)(5)a,b
9、a,b,a,b(4)答：（2），（4）24、判断下列命题哪几个正确？()A(4)若 A 为非空集，则 A(1)所有空集都不相等(2)成立。答：（2）C，则 B()C。AB=AAB=AC，25、设答：=（等于）26、判断下列命题哪几个正确？()(1)若 ABAC，则 BC(2)a,b=b,aP(A)P(B)（P(S)表示 S 的幂集）(3)P(AB)AA 成立。(4)若 A 为非空集，则 A答：（2）27、，是三个集合，则下列哪几个推理正确：C=AB(3)AB，B，BC(2)AC=AB，B(1)ABC=AC答：（1）（3）的反例 C 为0，1，0 B 为0，1，A 为 1 很明显结论不对）（二元
10、关系部分）（二元关系部分）28、设1,2,3,4,5,6，B=1,2,3，从到 B 的关系 x,y|x=y2求(1)R(2)R-1=,（考查二元关系的定1答：（1）R=,(2)R=|R）1为 R 的逆关系，即 R1义，R29、举出集合 A 上的既是等价关系又是偏序关系的一个例子。()答：A 上的恒等关系30、集合 A 上的等价关系的三个性质是什么？()答：自反性、对称性和传递性31、集合 A 上的偏序关系的三个性质是什么？()答：自反性、反对称性和传递性(题 29，30，31 全是考查定义)32、设 S=,，上的关系 1,2，2,1，2,3，3,4 R(2)R-1。求(1)RGR=1,1，1,
11、3，2,2，2,4 （考 查 F 答：R=|t(FG)）R-1=2,1，1,2，3,2，4,3 33、设1，2，3，4，5，6，是 A 上的整除关系，求 R=()R=,34、设1,2,3,4,5,6，B=1,2,3，从到 B 的关系 x,y|x=2y，求(1)R(2)R-1。=,(361答：（1）R=,(2)R35、设1,2,3,4,5,6，B=1,2,3，从到 B 的关系 x,y|x=y2，求 R 和 R-1的关系矩阵。000000010000000001的关系矩阵=1R000000001000000001答：R 的关系矩阵=A，则 R36、集合 A=1,2,10上的关系 R=|x+y=10
12、,x,y的性质为（）。(1)自反的(2)对称的(3)传递的，对称的(4)传递的答：（2）（考查自反 对称 传递的定义）（代数系统部分）（代数系统部分）37、设 A=2,4,6，A 上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是()，零元是()。答：2，6（单位元和零元的定义，单位元：e。x=x零元：。x=）38、设 A=3,6,9，A 上的二元运算*定义为：a*b=mina,b，则在独异点中，单位元是()，零元是()；答：9，3（半群与群部分）（半群与群部分）39、设G,*是一个群，则x=b，则 x=()；(1)若 a,b,xG，ab，则 x=()。x=a(2)若 a,b,
13、xG，ab（2）b（考查群的性质，即群满足消去律）1答：（1）a40、设 a 是 12 阶群的生成元，则 a2是()阶元素，a3是()阶元素。答：6,441、代数系统是一个群，则 G 的等幂元是()。答：单位元（由 a2=a,用归纳法可证 an=a*a(n-1)=a*a=a，所以等幂元一定是幂等元，反之若 an=a 对一切 N 成立，则对 n=2 也成立，所以幂等元一定是等幂元，并且在群中，除幺元即单位元 e 外不可能有任何别的幂等元）42、设 a 是 10 阶群的生成元，则 a4是()阶元素，a3是()阶元素答：5，10（若一个群 G 的每一个元都是 G 的某一个固定元 a 的乘方，我们就把
14、 G 叫做循环群；我们也说，G 是由元 a 生成的，并且用符号G=表示，且称 a 为一个生成元。并且一元素的阶整除群的阶）43、群的等幂元是()，有()个。答：单位元，1（在群中，除幺元即单位元 e 外不可能有任何别的幂等元）44、素数阶群一定是()群,它的生成元是()。答：循环群，任一非单位元（证明如下：任一元素的阶整除群的阶。现在群的阶是素数 p，所以元素的阶要么是 1 要么是 p。G 中只有一个单位元，其它元素的阶都不等于 1，所以都是 p。任取一个非单位元，它的阶等于 p，所以它生成的 G 的循环子群的阶也是 p，从而等于整个群 G。所以 G 等于它的任一非单位元生成的循环群）45、设
15、G,*是一个群，a,b,cG，则a，则 c=()。a=ba=b，则 c=()；(2)若 c(1)若 c(2)b（群的性质）1a答：（1）b的子群的充分必要条件是()。是G,46、是群 或 a，b答：1，则 T 中至少存在()片树叶。答：268、任何连通无向图 G 至少有()棵生成树，当且仅当 G 是()，G 的生成树只有一棵。答：1，树69、设 G 是有 n 个结点 m 条边的连通平面图，且有 k 个面，则 k 等于:(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。答：（1）70、设 T 是一棵树，则 T 是一个连通且()图。答：无简单回路71、设无向图 G 有 16 条边且
16、每个顶点的度数都是 2，则图 G 有()个顶点。(1)10(2)4(3)8(4)16答：（4）72、设无向图 G 有 18 条边且每个顶点的度数都是 3，则图 G 有()个顶点。(1)10(2)4(3)8(4)12答：(4)73、设 图G=，V=a，b，c，d，e，E=,则 G 是有向图还是无向图？答：有向图74、任一有向图中，度数为奇数的结点有()个。答：偶数75、具有 6 个顶点，12 条边的连通简单平面图中，每个面都是由()条边围成？(1)2(2)4(3)3(4)5答：（3）76、在有 n 个顶点的连通图中，其边数（）。(1)最多有 n-1 条(2)至少有 n-1 条(3)最多有 n 条
17、(4)至少有 n 条答：（2）77、一棵树有 2 个 2 度顶点，1 个 3 度顶点，3 个 4 度顶点，则其 1度顶点为（）。(1)5(2)7(3)8(4)9答：（4）78、若一棵完全二元（叉）树有 2n-1 个顶点，则它（）片树叶。(1)n(2)2n(3)n-1(4)2答：（1）79、下列哪一种图不一定是树（）。(1)无简单回路的连通图(2)有 n 个顶点 n-1 条边的连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图答：（3）80、连通图 G 是一棵树当且仅当 G 中（）。(1)有些边是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉路径答：（2）
18、（数理逻辑部分）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式：二、求下列各公式的主析取范式和主合取范式：R1、(PQ)RQ)P(R解：(PQ)R)（析取范式）(QR)P(R)QP)P(R)EMBED Equation.3Q)(QP(EMBEDEquation.3P(R)QP(R)Q(PR)QP(R)QR)（主Q(PR)EMBED Equation.3QP(R)QP(析取范式）EMBEDEquation.3EMBEDEquation.3QP(R)(PQ)EMBED Equation.3(PEMBED Equation.3R)QP(R)R)QEMBED Equation.3(PEMBE
19、D Equation.3R)Q(PEMBED Equation.3R)（原公式否定的主析取范式）QEMBEDQP(R)EMBED Equation.3Q(PR)Q(PR(PQ)Equation.3R)R)（主合取范QP(R)EMBED Equation.3QP(式）EMBED Equation.3PR)(QR)2、(PEMBED Equation.3P（析取范式）R)(QR)解：(PEMBED Equation.3(PR)EMBED Equation.3Q)(Q(PEMBED Equation.3R)(REMBED Equation.3Q)(QP(R)QP)EMBEDEquation.3(PR
20、)Q(PR)QP(R)Q(PR)QEMBEDP(EMBED Equation.3R)QP(R)QP(EMBED Equation.3EMBED Equation.3QP(R)Equation.3QR)EMBEDEquation.3(PR)Q(PP(EMBED Equation.3R)QP(R)QP(R)QEMBEDEMBED Equation.3QP(R)EMBED Equation.3QEquation.3R)(主析取范式)EMBED Equation.3P）R)(QR)（(PEMBEDQ(PEMBED Equation.3R)EMBED Equation.3Q(PEquation.3R）（
21、原公式否定的主析取范式）P(R)QP(EMBEDEquation.3PR)(QR)(PR)（主合取范式）EMBED Equation.3QP)(RPQ)3、(P)(RPQ)解：(P)（合取范式）(RQ)(PEMBED Equation.3(Q(PEMBED Equation.3R)(RQ(PR)Q)EMBED(PR)Q(PEMBED Equation.3R)Q(PR)Q(PR)Equation.3QEMBED Equation.3(PEMBED Equation.3R)Q(PR)Q(PR)（主合取范式）QP)(RPQ)(EMBEDEquation.3EMBEDEquation.3Q(PEMBE
22、DQP(R)EMBED Equation.3QP(R)QP(R)Equation.3R)EMBED Equation.3R)（原公式否EMBED Equation.3QP(定的主合取范式）P)(RPQ)(EMBEDEquation.3EMBEDEquation.3Q(PR)QP(EMBEDEquation.3(PEMBEDEquation.3R)Q(PR)R)Q(PR)Q（主析取范式）EMBED Equation.3R)4、Q(PEMBED Equation.3R)解：Q(PEMBED Equation.3R（主合取范式）PEMBED Equation.3QEMBED Equation.3R)
23、）（Q(PEMBEDP(EMBED Equation.3R)EMBED Equation.3QP(R)QP(EMBED Equation.3R)QP(R)Equation.3QEMBEDEquation.3Q(PR)EMBEDEquation.3Q(PR）（原公式否定的主合取范式）Q(PR)EMBED Equation.3R)Q(PEMBED Equation.3(PEMBED Equation.3R)Q(PR)Q(PEMBEDEquation.3EMBEDEquation.3Q(PR)QEMBED Equation.3R)QP(R)EMBED Equation.3QP(R)EMBED Equ
24、ation.3QP(EMBED Equation.3R）（主析取范式）(QP)5、P(P(QP)解：P(PP)Q(PEMBED Equation.3PPEMBED Equation.3PT(主合取范式)EMBED Equation.3(PQ)P(EMBED Equation.3Q)P(Q)（主析取范式）(PQ)P)(R(PQ)6、P)(RQ)PEMBED Equation.3(P)(R(PQ)解：P)（析取范式）(REMBED Equation.3Q)(PEMBEDEquation.3(REMBEDEquation.3Q(PR)Q)Q(PR)EMBED Equation.3Q(PR)EMBED Equation.3Q(PR)Q(PR)EMBED Equation.3Q(PEMBED Equation.3R)EMBED Equation.3Q(PR)EMBED Equation.3Q(PR)（主析取范式）Q(PEMBED Equation.3R)EMBEDEquation.3Q(PP)(R(PQ)(R)EMBED Equation.3QP(R)QP(R)P(EMBED Equation.3R)EMBED Equation.3QP(