离散数学填空题及答案

编 号 1 题目 谓词公式 x(P(x) yR(y))Q(x)中量词 x 的辖域是（） 。 答：P(x) yR(y) 答案 题 分 型 值 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 大纲 难 度 3 2 令 R(x):x 是实数，Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符 号化表示为（） 。 答：x(R(x)Q(x)) 答：m=n-1 答：所有边一次且恰好一次 答：2n-2 答：简单无回路 答：偶数 3 3 一棵无向树的顶点数 n 与边数 m 关系是()。 3 4 一个图的欧拉回路是一条通过图中()的回路。 3 5 有 n 个结点的树，其结点度数之和是()。 3 6 设 T 是一棵树，则 T 是一个连通且()图。 3 7 任一有向图中，度数为奇数的结点有()个。 3 8答：{0，1，2，3，4，6}  设 A {x | (x N)且(x  5)},B {x | x E 且x  7}（N：自然数集，E+ 正偶数） 则A B （） 。 12 9 设 P，Q 的真值为 0，R，S 的真值为 1，则 答：1填 2 空 3 。(P  (Q  (R P)))  (R  S)的真值= （） 10 公式(P  R) (S  R) P的主合取范式为（） 。 11 设 A={1， 2， 3， 4}， A 上关系为｛,,,｝ 则 R2 = ()。 答：{, , , } 12 设 A={a，b，c，d}，其上偏序关系 R 的哈斯图为 则 R= （） 。 13 树是不包含树是不包含（）的（）图的。 答：环;无向 答：{,,,,}  IA 答：(P S  R)(P S  R) 题 填 2 空 题 填 2； 空 题 填 2 空 题 4 3 4 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 题 填 2 空 3 14 设 A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ()。 答：R={,,}3 15 设 f，g 是自然数集 N 上的函数x N,f (x)  x 1,g(x)  2x，则 答：2(x+1)3 f g(x) （ ） 。 16 设 A={a，b，c}，A 上二元关系 R={ , ,, }, 则 s（R）= （） 。 17 P， Q 真值为 0 ； R， S 真值为 1。 则wff (P (R  S))  ((P Q)(R  S)) 答：1 答： { a ,a , a ,b , a ,c , c,c , b,a , c,a } 5 3 的真值为（） 。 18 。wff ((P Q) R)  R的主合取范式为（）答：(P  Q  R) (P Q  R) (P Q  R) 题 填 2 空 题 4 19 设 P（x） 填 2 ：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数 y。 答：(P  Q  R) (P Q  R) (P Q  R) 空 则谓词wffx(P(x)  y(O(y)  N(y,x)))的自然语言是（） 。题 20 谓 词wff xy(z(P(x,z)  P(y,z))  uQ(x, y,u))的 前 束 范 式 为 （） 。 21 若 P，Q，为二命题，P  Q真值为 0 当且仅当（） 。 22 将量词辖域中出现的（） 和指导变元交换为另一变元符号，公式其余 的部分不变，这种方法称为换名规则。 23 设 G 为 9 阶无向图，每个结点度数不是5 就是 6，则 G 中至少有 （） 答：6 个 5 度结点。 填 2 空 题 答：约束变元 答：P 真值为 1，Q 的真值为 0填 2 空 题 填 2 空 题 答：填 2 空 题 3 4 xyzu(P(x,z) P(y,z)Q(x, y,u)) 3 3 3 24答：2填 2 空 题 3 有向图 （） 条。 中从 v1到 v2长度为 2 的通路有 25 设[L,,]是 代 数 系 统 ， 则[L,,]满 足 幂 等 律 ， 即 对aL有 （） 。 26 任何(n,m) 图 G = (V,E) , 边与顶点数的关系是（） 。 27 当 n 为（）时,非平凡无向完全图Kn是欧拉图。 28 已知一棵无向树 T 有三个 3 顶点,一个 2 度顶点,其余的都是 1 度顶点,则 T 中 有（）个 1 度顶点。 29 集合 A={,{}}的幂集 P(A) =（） 。 30 设|A|=3，则 A 上有（）个二元关系。 答：a a  a 且 a  a  a 填 2 空 题 4 答： d(v)  2m vV 填 2 空 题 填 2 空 题 填 2 空 题 3 答：奇数3 答：53 答：{,{},{{}},{,{}}} 填 21 空 题 填 2 空 题 3 答：293 31 Q：我将去上海， R：我有时间，公式(Q  R) (R  Q)的自然语言为 （） 。 32 公式(Q  P)(P Q)的主合取范式是（） 。 答：我将去上海当且仅当我有空填 2 空 题 ：填 2 空 题 填 2 空 题 3 答3 (P Q)(P  Q)(P Q) (P  Q) 33 若 S {S 1 ,S 2 , , S m } 是 集 合A的 一 个 分 划 ， 则 它 应 满 足 （） 。 34 代数系统中，|A|1，如果e和分别为的幺元和零元，则e和的 关系为（） 。 35答：乘法 n 设A {x | x  2 , n N}，定义 A 上的二元运算为普通乘法、 除法和加法， 则代数系统中运算*关于（）运算具有封闭性。 36 设是由元素aG生成的循环群，且|G|=n，则 G = ()。 37 一个图是平面图的充要条件是 ()。 答：G {a,a , a 2n1 (2) 答：(1)S i  S j  (i  j)  S i1 m 3 i  A 答：e 填 2 空 题 填 2 空 题 3 3 ，an e} 填 2 空 题 4 答：它不包含与 K3, 3或 K5在 2 度结点内同构的子图填 2 空 题 38 某人有三个儿子，组成集合 A={S1,S2,S3}， 在 A 上的兄弟关系具有 答：反自反性、对称性、传递性填 2 空 （）性质。 题 39答：双射填 2 cf: B  A 若f : A  B是函数，则当 f 是A  B的（） ，是 f 空 3 3 3 的逆函数。 40 设 P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占 据空间的，有质量的而且不断运动的叫做物质”的符号化为（） 。 41 设 A，B 是两命题公式，A  B当且仅当（） 。 42 对 谓 词 公 式 yP(x, y)zQ(x,z)xR(x, y) 的 自 由 变 元 代 入 得 ()。 43 对集合 X 和 Y，设