离散数学自学考试复习题.doc

离散数学 复习题 设A和B都是命题，则A→B的真值为假当且仅当 。A. A为假，B为真 B. A为假，B为假C. A为真，B为真 D. A为真，B为假 下列公式中为重言式的是 。A. P→(P∨Q∨R) B. ┐(Q→P)∧PC. (P→Q)→(Q→┐P) D. (P∧┐P)←→Q 设A＝{a，{a}}，P(A)表示A的幂集，下面各式中错误的是 。A. {a}∈P(A) B. {a}P(A) C. {{a}}∈P(A) D. {{a}}P(A) 设A＝{1,2,3,4,5,6}上的关系为R＝{x,y|xy}，则R-1具有 。A. 对称性 B. 自反性C. 反自反性、反对称性、传递性 D. 以上都不对 设R是非空集合A上的二元关系，则R的对称闭包S(R)＝ 。A. R∪IA B. R∪RC C. R-IA D. R∩RC 映射的复合运算满足 。A. 交换律 B. 结合律 C. 幂等律 D. 分配律 设R、I分别是实数集合和整数集合，-、×、/ 分别是普通的减法、乘法和除法运算，则 是半群。A. I，- B. R，- C. R，× D. R，/ 在一个格A，≤中，对任意的a，b，c∈A，都有 。A. a∨(b∧c)≤(a∨b)∧(a∨c) B. a∧(b∨c)≤(a∧b)∨(a∧c)C. a∨(b∧c)＝(a∨b)∧(a∨c) D. A、B、C都正确 无向简单图G中结点间的连通关系是 。A. 偏序关系 B. 等价关系C. 既是偏序关系又是等价关系 D. A、B、C都错误 10.设G是一个有v个结点e条边的连通简单平面图，若v≥3，则 。A. v≤3e-6 B. e≤3v-6C. v≤3e+6 D. e≤3v+6 11．设P和Q是命题，P，(P∨QQ。 ( ) 12．设A和B是集合，A-B＝A当且仅当B＝Φ。 ( ) 13．一个不是自反的关系，一定是反自反的。 ( ) 14．若A和B是任意两个集合，则A×B＝B×A。 ( ) 15．关系f＝{m,n|m,n∈N,m+n＜10}是函数，其中N是自然数集合。 ( ) 16．集合B是集合A的真子集，则K[B]＜K[A]。 ( ) 17．整环一定是域。 ( ) 18．任何两个具有2n个元素的有限布尔代数都是同构的。 ( ) 19．已知无向连通图G中有n个结点，m条边，G中无回路，则m＝n-1。( ) 20.如果两个图的结点数相同、边数相等、度数相同的结点数目也相等，那么这两个图是同构的。 ( ) 21.设命题P表示“我今天将去公园”，命题Q表示“天下雨”，则命题“我今天去公园，除非下雨”可以符号化为 (1) 。 22.命题“只有教师才有教师资格证(T(x)，C(x))”可符号为： (2) 。 23.设P(A)是集合A的幂集，如果|A|＝n，则|P(A)|＝ (3) ，|A×P(A)|＝ (4) 。 24.设A＝{a,b,c}，P(A)为A的幂集，{P(A)，}是偏序集。则P(A)的子集＝{Φ，{a}，{b}，{a,b}，{b,c}}的极大元是 (5) ，最大元是 (6) ，上界是 (7) ，下确界是 (8) 。 25.设f和g是从整数集到整数集合的函数，其定义为f(x)＝2x+3和g(x)＝3x+2，则gf(x)＝ (9) ，fg(x)＝ (10) 。 26.设A，*是一个代数系统，并设R是A上的一个等价关系，如果a1，a2和b1，b2∈R时， (11) ，则称R为A上的同余关系。 27.设A，≤是一个格，由它诱导的代数系统为A，∨，∧，如果对于任意的a,b,c∈A，当b≤a时，有 (12) ，则称A，≤为模格。 28.一个图是平面图，当且仅当它不包含与 (13) 或 (14) 在2度结点内同构的子图。 29.无向图G具有一条欧拉路，当且仅当G是 (15) ，且有 （16） 奇数度结点。 30.无向图G如右图所示，则G的点连通度 (17) ，边连通度为 (18) ，它的生成树有 (19) 条树枝和 (20) 条弦。 31.求(A→(B∧C))∧(﹁A←→(﹁B∧﹁C))的主析取范式和主合取范式。 32.将下列推理形式化，并推证其结论所有牛都有角，有些动物是牛，所