离散数学填空题与答案_1.pdf
编 题目 答案 号 1谓词公式 x(P(x)yR(y)Q(x)中量词 x 的辖域是（）。答：P(x)yR(y)2 令 R(x):x 是实数，Q(x):x 是有理数。则命题“并非每个实数都是有理数”的 答：x(R(x)Q(x)符号化表示为（）。3 一棵无向树的顶点数 n 与边数 m 关系是()。答：m=n-1 4一个图的欧拉回路是一条通过图中()的回路。答：所有边一次且恰好一次 5有 n 个结点的树，其结点度数之和是()。答：2n-2 6设 T 是一棵树，则 T 是一个连通且()图。答：简单无回路 7任一有向图中，度数为奇数的结点有()个。答：偶数 8 x|(x N)且(x 5),B x|x E 且 x 7+答：0，1，2，3，4，6 设 A（N：自然数集，E 正偶数）则 A B（）。9设 P，Q 的真值为 0，R，S 的真值为 1，则答：1 题 分 大纲 难 型 值 度 填 2 3.1 3 空 题 填 2 3.1 3 空 题 填 2 7.1 3 空 题 填 2 6.4 3 空 题 填 2 6.4 3 空 题 填 2 6.2 3 空 题 填 2 6.1 3 空 题 填 2 1 2 空 题 填 2 2.1 3 空 (P(Q (R P)(R S)的真值=（）。题 10 公式(P R)(S R)P 的主合取范式为（）。答：(PSR)(PSR)填 2 2.3 4 空 题 11 设 A=1，2，3，4，A 上关系为 ,则 R2 =答：,填 2 4.1；4.2 3 空 ()。题 12设 A=a，b，c，d，其上偏序关系 R 的哈斯图为 答：,IA 填 2 4.4 4 空 题 则 R=（）。13 树是不包含树是不包含（）的（）图的。答：环;无向 填 2 8.1 3 空 题 14 设 A=1，2，3，则 A 上既不是对称的又不是反对称的关系 R=()。答：R=,填 2 4.3 3 空 题 15 设 f，g 是自然数集 N 上的函数 x N,f(x)x 1,g(x)答：2(x+1)填 2 5.2 3 2x，则 空 f g(x)（）。题 16 设 A=a，b，c，A 上二元关系 R=,答：填 2 4.4 5 则 s（R）=（a,a ,a,b ,a,c ,c,c ,b,a ,c,a 空 ）。题 17 P，Q 真值为 0；R，S 真值为 1。则wff(P (R S)(P Q)(R S)答：1 填 2 2.2 3 空 的真值为（）。题 18 wff(P Q)R)R 的主合取范式为（）。答：(P Q R)(P Q R)(P Q R)填 2 2.3 4 空 题 19 设 P（x）：x 是素数，E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整 答：(P Q R)(P Q R)(P Q R)填 2 3.1 3 空 数 y。则 谓 词wff x(P(x)y(O(y)N(y,x)的自然语言是 题 （）。20 谓 词 答：填 2 3.2 4 wff x y(z(P(x,z)P(y,z)uQ(x,y,u)的 前 束 范 式 为 空 x y z u(P(x,z)P(y,z)Q(x,y,u)题 （）。21 若 P，Q，为二命题，P Q 真值为 0 当且仅当（）。答：P 真值为 1，Q 的真值为 0 填 2 2.1 3 空 题 22 将量词辖域中出现的（）和指导变元交换为另一变元符号，公式其余 答：约束变元 填 2 3.1 3 空 的部分不变，这种方法称为换名规则。题 23设 G 为 9 阶无向图，每个结点度数不是 5 就是 6，则 G 中至少有（）答：6填26.13 个 5 度结点。空 题 24 答：2 有向图 中从 v1到 v2长度为 2 的通路有 （）条。25 设 L,是代数系统，则L,满足幂等律，即对 a L 有 答：a a a 且 a a a （）。26任何(n,m)图 G=(V,E),边与顶点数的关系是（）。答：d(v)2m v V 27当 n 为（）时,非平凡无向完全图 Kn是欧拉图。答：奇数 28 已知一棵无向树 T 有三个 3 顶点,一个 2 度顶点,其余的都是 1 度顶点,则 T 中 答：5 有（）个 1 度顶点。29 集合 A=,的幂集 P(A)=（）。答：,30设|A|=3，则 A 上有（）个二元关系。答：29 填 2 6.33 空 题 填 2 8.24 空 题 填 2 6.4 3 空 题 填 2 6.2 3 空 题 填 2 7.1 3 空 题 填 2 1 3 空 题 填 2 4.1 3 空 题 31 32 33 34 35 36 37 38 39 Q：我将去上海，R：我有时间，公式(Q R)(R Q)的自然语言为 答：我将去上海当且仅当我有空 填 2 空 （）。题 公式(QP)(P Q)的主合取范式是（）。答 ：填 2 空 (PQ)(P Q)(PQ)(P Q)题 若S S1,S2,Sm 是集合 A的一个分划，则它应满足（）。m 填 2 答：(1)Si Sj(i j)(2)Si A 空 i 1 题 代数系统 中，|A|1，如果e 和 分别为 的幺元和零元，则e 和 的 答：e 填 2 空 关系为（）。题 设 A x|x 2n,n N ，定义 A上的二元运算为普通乘法、除法和加法，答：乘法 填 2 空 则代数系统 中运算*关于（）运算具有封闭性。题 设 是由元素a G 生成的循环群，且|G|=n，则 G=()。2,a n 1 n e 填 2 答：G a,a，a 空 题 一个图是平面图的充要条件是()。答：它不包含与 K 3,3或 K 5在 2 度结点内同构的子图 填 2 空 题 某人有三个儿子，组成集合 A=S1,S2,S3，在 A 上的兄弟关系具有 答：反自反性、对称性、传递性 填 2 空（）性质。题 若 f:A B 是函数，则当 f 是A B 的（），f c:BA 是 f 答：双射 填 2 空 的逆函数。题 2.1 3 2.3 3 4.4 3 8.1 3 8.1 3 8.3 4 6.4 3 4.1 3 5.2 3 40 设 P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占 答：据空间的，有质量的而且不断运动的叫做物质”的符号化为（）。41 设 A，B 是两命题公式，A B 当且仅当（）。答：42 对谓词公式 yP(x,y)zQ(x,z)xR(x,y)的 自 由 变 元 代 入 得 答：()。S P Q 填 2 2.1 3 R 空 题 A B T 填 2 2.1；2.2 3 空 题 yP(u,y)填 2 3.1；3.2 3 zQ(u,z)xR(x,w)空 题 43 对集合 X 和 Y，设|X|=m，|Y|=n，则从 X到 Y的函数有()个。答：nm 填 2 5.1 3 空 题 44 若关系 R 是等价关系 ,则 R 满足()性质。答：自反性、对称性、传递性 填 2 4.4 3 空 题 45 关系 R 的传递闭包 t(R)=()。答：Ri R 填 2 4.3 4 空 i 1 题 46 代数系统 A,是群，则它满足 ()。答：运算*在 A 上封闭，*在 A 上可结合，*填 2 8.2；8.3 3 在 A 上存在幺元，A 中每个元素都有逆元；空 题 47 设 A,和 B,是两代数系统，f 是 A,到 B,答 ：填 2 8.2；8.3 3 ,A,f(a b)f(a)f(b),f(a b)f(a)f(b)空 a,b 的同态映射，则 f 具有()性质。题 48 若连通平面图 G V,E 共有 r 个面，其中V v,E 答：v e r 2 填 2 6.4 3 e，则它满足的 空 Euler 公式为()。题 49 50 51 52 树 T 的边数 e 与点数 v 有关系()。答：e v 1 填 2 7.1；7.2 3 空 题 n 个命题变元有 ()个互不等价的极小项。答：2n 填 2 2.2；2.3 3 空 题 n (n)填 2 2.2；2.3 3 答：Ai 按 De-Morgan 定理，A1A2 An Ai=(空 )。i 1 i 1 题 公式 P(Q R)的主析取范式为(答 ：填 2 2.3 4)。(P Q R)(P QR)(PQR)(PQR)空 (P Q R)(P QR)(PQR)0,1,2,3,4,5,7 题 53 54 55 设 P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比 y 重，则命题“大象比老鼠 重”的符号化为()。1 0 1 设 X a,b,c，X上的关系 R 的关系矩阵是 M R 1 1 0，则 1 1 1 MRR()。在 具 有 n个 结 点 的 有 向 图 中，任 何 基 本 通 路 的 长 度 都 不 超 过 ()。答：x y(P(x)Q(y)R(x,y)1 11 答：1 11 1 11 答：n-1 填 2 3.1 3 空 题 填 2 6.3 4 空 题 填 2 6.13 空 题 56 任何图的点连通度(G)，边连通度(G)，最小点度(G)的关系为答：(G)(G)(G)()。填 2 6.1；6.2 3 空 题 57 结点数 n（n 3）的简单连通平面图的边数为 m，则 m 与 n 的关系为 答：m 3n 6 ()。58 群 G 的非空子集 H 是 G 的子群当且仅当若 x,y H 则()。答：x y 1 H 59 代数系统 A,是环，若对运算“”还满足 ()则 答：含幺元，可交换，无零因子 A,是整环。60 给定命题公式 A、B，若（），则称 A 和 B 是逻辑相等的。答：对于 A，B 中原子变元P1,P2,Pn任意一组 真值指派，A 和 B 的真值相同。61 设 A a,b,c 考虑下列子集 S1 a,b,b,c，答：S1,S2,S3,S4,S5；S3，S4，S5 S2 a,a,b,a,c，S3 a,b,c，S4 a,b,c S5 a,b,c，S6 a,a,c 则 A 的覆盖有（），A 的划分有（）。62 若 G V,E 为哈密顿图，则对于结点集 V 的每个非空子集 S，均有 答：P(G-S)（）S成立，63 某班有学生 50 人,有 26 人在第一次考试中得优,有 21 人在第二次考试中得优,答：14 有 17 人两次考试都没有得优,那么两次考试都得优的学生人数是 （）。填 2 6.44 空 题 填 2 8.34 空 题 填 2 8.2；8.3 5 空 题 填 2 2.1 3 空 题 填 2 4.4 4 空 题 填 2 6.4 4 空 题 填 2 1 3 空 题 64 给命题变元 p、s 和 r 指派真值 1,q 指派真值0,公式 p(s r)q)s)的真值为（）。65 设 p：我生病，q：我去上课，命题“我虽然生病但我还是去上课”符号化为：（）。66 公式 xA(x)xB(x)的前束范式为（）。67 若1,2,3,4上的二元关系 R=,则 R 的自反闭包 r(R)=（）。68 有向图 D 如下，则 D 的邻接矩阵 A(D)=（）。69 5 阶的群有（）个不同的子群。70一棵高度为 5 的二元树结点数最多为（）。答：1 答：pq 答：x(A(x)B(x)或 x(A(x)B(x)答：r(R)=,0 1 01 0 0 11 答：0 0 01 0 1 00 答：2 答：63 填 2 2.1；2.2 3 空 题 填 2 2.1；2.2 3 空 题 填 2 3.24 空 题 填 2 4.1；4.2 4 空 题 填 2 6.33 空 题 填 2 8.34 空 题 填 2 7.1；7.2 3 空 题 71 一个连通平面图 G 有 10 条边，G 中度为 1 的顶点有 2 个，其余是度为 6 的顶 答：5，7 填 2 6.1；6.2 3 点，则 G 中共有（空 ）个顶点，（）个面。题 72 集 合 X=0,1,2,3，R 是 X 上 的 二 元 关 系 ，0 1 1 0 填 2 6.2；6.3 3 0 1 0 1 空 R=,，则 R 的关系矩阵 M R是 答：0 0 1 题 （）。1 0 1 0 0 73 无向图 G 中有 n 个结点 m 条边，且 G 中每个结点的度数不是 k 就是 k+1,则 G 答：(k+1)n-2m 填 2 6.1；6.2 3 空 中度数为 k 的结点的个数是（）。题 74 设 Z+=x x Z x0，*表示求两个数的最小公倍数的运算，则*运算的幺 答：1 填 2 8.1；8.2 3 空 元是（）。题 75 群总共有（）个不同的子群。答：2 填 2 8.1；8.2 4 空 题 76 在个体域 D=a,b 中，与公式 xA(x)等价又不含量词的公式是（）。答：A(a)A(b)填 2 3.1；3.2 3 空 题 77 具有 4 个结点的有向完全图的边数为（）条。答：24 填 2 6.1 3 空 题 78 若 p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为（）。答：p q 填 2 2.1 3 空 题 79 若集合 A=1,2,3 上的二元关系 R1和 R2的关系图如下所示，答：r(R)=,填 2 4.1；4.2 3 空 题 则 R1oR2=（）。80 树是平面图，它有（）个面。答：1 填 2 6.1；7.13 空 题 81 哈密尔顿回路要求经过图中（）一次且仅一次。82 有向图 D 如下：D 的邻接矩阵 A=(aij)3 3,则 a11=（）,a32=（83 在一棵根树中，仅有一个结点的入度为（），称为树根，其余结点的 入度均为（）。84 合式公式 Q(P (P Q)与 QP 的关系是 _ 的。（等价或蕴含选一）85 设 R 为非空集合 A 上的二元关系，如果 R 满足（），则称 R 为 上的一个偏序关系。答：每个顶点 填 2 6.4 3 空 题 ）。答：1，0 填 2 6.3 3 空 题 答：0，1 填 2 7.2 3 空 题 答：等价 填 2 2.2；2.3 3 空 题 A 答：自反、反对称、传递 填 2 4.3 3 空 题 86 设 R 为 A 上的关系，则 R 的自反闭包 r(R)=（），对称闭包 s(R)=答：R Ix ,R R c 填 2 4.3 4 空 （）。题 87 一棵高度为 3 的二叉树结点数最多为（）。答：7 填 2 7.1；7.2 3 空 题 88 设 Z 是整数集，在 Z 上定义二元运算 *为 a*b=a+b+a?b，其中+和?是数的加法 答：a,0 填 2 8.1；8.2 3 和乘法，则代数系统 的幺元是（），零元是（）。89设 T 是有 n 个结点的完全二叉树，则 T 叶子数为（）。答：(n+1)/2 90设 A=a,b,c,则 A A 中的元素有()。答：9 91 图 G 与其对偶图 G*的结点数目（）相等。答：不一定 92 设 S 1,2,3，定义 S S上的等价关系 答：4 R a,b ,c,d|a,b S S,c,dS S,a d b c 则 由 R 产生的S S 上一个划分共有（）个分块。93 设 G，是一个群，则对任意的 a,b G 均有(a b)1=（）。答：b 1*a 1 94 0 1 0 1 答：2，2 设图 D=，V=v，v，v，v A=1 0 1 1 ，则 1 23 4，若 D 的邻接矩阵 1 1 0 0 1 0 0 1 deg-（v1）=（），从 v2到 v4 长度为 2 的路有（）条。95 设 A=1，2，B=2，3，则 A-A=（），A-B=（）。答：，1 空 题 填 2 7.1；7.2 3 空 题 填 2 1；4.1 3 空 题 填 2 6.44 空 题 填 2 4.3；4.4 3 空 题 填 2 8.3 5 空 题 填 2 6.3 4 空 题 填 2 13 空 题 96 两个重言式的析取是（）式，一个重言式与一个矛盾式的析取是 答：重言式，重言式 （）式。97 一个无向树中有 6 条边，则它有（）个结点。答：5 98 谓词公式(x)(y)（P(x,y)R(y)Q(y)，则其约束变元是（），答：（P(x,y)R(y)中的 x,y;Q(y)中的 y 自由变元是（）。99 一个结点为 n 的无向完全图，其边的数目为（）,并且它是 答：n(n-1)/2,n（）度正则图。100 设 R 为非空集合 A 上的等价关系，其等价类记为 xR。x,y A，若 x,y 答：xR=yR,R，则 xR与 yR的关系是（），而若 x,y R，则 x Ry R=（）。填 2 2.1；2.2 3 空 题 填 2 7.13 空 题 填 2 2.1；2.2 3 空 题 填 2 6.1；7.1 3 空 题 填 2 4.44 空 题
