华中科技大学2013——2014年《离散数学》试卷A卷

离散数学试题（A卷答案）一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。

则根据题意应有：A→C⊕D，⌝(B ∧C)，C→⌝D必须同时成立。

因此(A→C⊕D)∧⌝(B∧C)∧(C→⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧(⌝B∨⌝C)∧(⌝C∨⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧((⌝B∧⌝C)∨(⌝B∧⌝D)∨⌝C∨(⌝C∧⌝D))⇔(⌝A∧⌝B∧⌝C)∨(⌝A∧⌝B∧⌝D)∨(⌝A∧⌝C)∨(⌝A∧⌝C∧⌝D)∨(C∧⌝ D∧⌝B∧⌝C)∨(C∧⌝ D∧⌝B∧⌝D)∨(C∧⌝ D∧⌝C)∨(C∧⌝ D∧⌝C∧⌝D)∨(⌝C∧D∧⌝B∧⌝C)∨(⌝C∧D∧⌝B∧⌝D)∨(⌝C∧D∧⌝C)∨(⌝C∧D∧⌝C∧⌝D)⇔F∨F∨(⌝A∧⌝C)∨F∨F∨(C∧⌝ D∧⌝B)∨F∨F∨(⌝C∧D∧⌝B)∨F∨(⌝C∧D)∨F⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D∧⌝B)∨(⌝C∧D)⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D)⇔T故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。

S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：∀x(S(x)∧W(x))，∃x Y(x)∃x(S(x)∧Y(x))下面给出证明：(1)∃x Y(x) P(2)Y(c) T(1)，ES(3)∀x(S(x)∧W(x)) P(4)S( c)∧W( c) T(3)，US(5)S( c) T(4)，I(6)S( c)∧Y(c) T(2)(5)，I(7)∃x(S(x)∧Y(x)) T(6) ，EG三、（10分）设A、B和C是三个集合，则A⊂B⇒⌝(B⊂A)。

《离散数学》考试试卷（试卷库20卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库20卷）试题总分： 100 分考试时限：120 分钟、选择题（每题2分，共20分）1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，则“人总是要死的”谓词公式表示为( )（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧（C ）))()((x Mortal x M x →?（D ）))()((x Mortal x M x ∧?2. 判断下列命题哪个正确？( )（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集）（D ）若A 为非空集，则A ≠A∪A 成立3. 集合},2{N n x x A n∈==对( )运算封闭（A ）乘法（B ）减法（C ）加法（D ）y x -4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则N b a ∈?,有=∨b a ( )（A ）a（B ）b（C ）min(a ，b)（D ） max(a ，b)5. 有向图D=，则41v v 到长度为2的通路有( )条（A ）0 （B ）1 （C ）2 （D ）36. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点（A ）10 （B ）4 （C ）8 （D ）127. 下面哪一种图不一定是树？（）（A ）无回路的连通图（B ）有n 个结点n-1条边的连通图（C ）每对结点间都有通路的图（D ）连通但删去一条边则不连通的图 8. 设P ：我将去镇上,Q ：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）（A ）P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代数系统中,其中*是加法运算,（）不是群。

大学期末考试试卷（A 卷）2013-2014学年第二学期 考试科目： 离散数学 考试类型：（闭卷）考试 考试时间： 120 分钟学号 姓名 年级专业(在下划线上填空. 在圆括号内填✓或✗. 笔字符✐表示用铅笔作图或在图上答题)一. 逻辑24分1. (8分)公式(p ∧q ) →(p ∨r )是重言式( ); {∨, ↔}是联结词完备集( ); ∀x ∃y (F (x ,y )∨G (x ,y ))是闭式( ); ∀xF (x ) → ∀yG (x , y )是前束范式()..2. (4分) (p →q ) ∨ (q →r )的成真赋值是______________________________________. 论域是人, F (x ): x 量小; G (x ): x 是君子, “量小非君子”符号化为______________________.3.(4分)用等值演算法证明(p → q ) ∧ (p → r ) ⇔ p → q ∧r .4. (4分)求(p ∨q ) ∨r 的主析取范式.5. (4分)前提: p→q, ⌝(q∧r), r, 结论: ⌝p. 构造推理的证明.序号公式依据(只填序号)①二. 关系24分1. (6分)设R={〈0,2〉,〈1,3〉,〈2,2〉,〈3,4〉}, 则R是函数( ), R是单射(), R是反对称的().2. (4分)设R= {〈a, a〉, 〈a, c〉, 〈d, e〉}, 则|r(R)|= ________ , dom R={________________}.3. (6分)设R= {〈a, a〉, 〈b, c〉, 〈d, e〉}, S= {〈a, b〉, 〈b, c〉, 〈c, b〉}. 画出R的关系图并求R S.3. (4分)写出集合A的划分{{1}, {2, 3}, {4}}}导出的等价关系R, 并写出A.4. (4分) 画出{2, 3, 12, 18}上的整除关系的哈斯图 , 并写出偏序集的极小元.三. 组合计数16分1. (2分) x1 + x2 + x3 = 13 (x1, x2, x3≥ 0)有________个整数解.2. (4分)有多少个十进制三位数的数字恰有一个8和一个9?3. (4分)把3只蓝球, 2只红球, 2只黄球排成一列, 黄球不相邻, 有多少种方法?4. (6分)运用二项式定理和微积分技巧证明11112111n n k n k k n ++=⎛⎫-=⎪-+⎝⎭∑.四. 图论36分1.(6分)图1的各图中, 割边最多的是________; 点色数最大的是________; 支配数最小的是________ (填相应字母).2.(8分)图2中的两个实心点之间有____条简单通路. 该图有____条简单回路, 它有____个点割集; 要使它成为哈密顿图, 至少要加有____条边.3.(4分)森林里有5棵树, 18片树叶, 其余顶点是2度或3度的. 森林里有几个3度分枝点?4.(4分)证明数列2, 3, 3, 5, 5, 6, 6不可简单图化.5. (4分)证明K 5不是平面图.图1图27. (6分)(a)画一个5阶自对偶图. (b)画一个6阶3正则的平面图.。

--北京工商大学离散数学试卷(A)答案及评分标准题号 一 二三 四 五 六 七总分得分一、（30分）设A ={1,2,3,4}，给定A 上二元关系R 如下：R ={<1,1>, <1,2>, <2,3>, <3,3>, <4,4>}请回答以下各问题：1.写出R 的关系矩阵. （3分）2.画出R 的关系图. （3分）3.求包含R 的最小的等价关系，并写出由其确定的划分. （6分）4.分别用关系矩阵表示出R 的自反闭包r (R )、对称闭包s (R ). （6分）5.求传递闭包t (R ).（写出计算步骤）（6分）6.求R 2的关系矩阵. （3分）7.集合A 上最多可以确定多少个不同的二元关系？说明理由。

（3分）[解] (1)⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010001000011R M 。

……（3分）（2） ……（3分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R 的最小等价关系为: {<1, 2>, <1, 3>, <2, 1>,<2, 3>, <3, 1> <3, 2>}∪I A , ……（3分） 对应的划分为{{1, 2, 3},{4}}. ……（6分） 法二：包含R 的最小的等价关系就是tsr (R ), 计算过程如下：⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=100001000110001110000100001000011000010001000011)(E M M R R r,100001100111001110000110001100011000010001100011][)()()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+=T R r R r R sr M M M ,3,10001110111011110000110011100111000011001110011)]([)()()]([2≥=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⨯⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⨯=k M M M M k R sr R sr R sr R sr 从而,10000111011101111000011101110111100001110111011110000111011101111000011001110011432)]([)]([)]([)()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=R sr R sr R sr R sr R tsr M M M M M即}2,3,1,3,3,2,1,2,3,1,2,1{)(><><><><><><⋃=A I R tsr =包含R 的最小的等价关系， ……（3分） 故其对应的划分为{{1, 2, 3},{4}}. ……（6分） 法三：由于4=A ，包含R 的最小的等价关系就是4131211)()()()()()(----⋃⋃⋃⋃⋃⋃⋃⋃==R R R R R R R R I R rts R tsr A ,计算过程如下：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃100001100101001110000110000100011000010001000011][1TR R R R M M M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃10000111011101111000011001010011)][(22)(21T R R R R M M M412131)()(33)(10000111011101111000011001010011)][(---⋃⋃⋃==⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=R R R R T R R R R M M M M M 考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。

离散数学第三版华中科技大学答案1、若a < b ，则下列各式正确的是（A） [单选题] *A、2a<2(正确答案)B、-3a<-3bC、a-2>b-2D、a+3<b+12、若a-b>0，则( B ) [单选题] *A、a<bB、a>b(正确答案)C、a=bD、a<b或a=b3、若a=x4+2x2+1，b=x4+x2+1，则下列各式正确的是（） [单选题] *A、a>bB、a<bC、a ≥ b(正确答案)D、a ≤ b4、下列命题正确的是（） [单选题] *A、若a<b, 则ac<bcB、若a<b, 则ac2<bc2C、若a<b, 则-2a>-2b(正确答案)D、若a<b, 则a-1>b-15、若2-3x>8, 则x的取值范围是（） [单选题] *A、（2，+∞）B、（-∞，2）C、（－2，+∞）D、（-∞，－2）(正确答案)6、若a<0，则下列不等式不正确的是（） [单选题] *A、4-a>3-aB、4+a>3+aC、4a>3a(正确答案)D、3a>4a7、若a>b, b<0,则下列不等式正确的是( B ) [单选题] *A、ab>0(正确答案)B、a-b>0C、a ÷b>0D、a ÷b<08、a2+c2 与 2ac 的大小关系是（） [单选题] *A、a2+c2≥2ac(正确答案)B、a2+c2≤2acC、a2+c2＞2acD、a2+c2＜2ac9、若a<b ,c<0, 则下列各式正确的是（） [单选题] *A、a+c>c>c>b+c B、ac<bc C、ac<0D、ac2<bc2(正确答案)10、下列各式正确的是（） [单选题] *A、a2>0B、|a|>0C、4-a<4D、a2-2a+3>0(正确答案)11、若|x|<1，则 x 的取值范围是（） [单选题] *A、(-∞ ,1)B、(-∞ ,-1)C、(-∞ ,-1)∪(1,+∞ )D、(-1,1)(正确答案)12、不等式|2x-1|< 3 的解集是（） [单选题] *A、（－2，2）B、（－1，2）(正确答案)C、（－∞，－1）∪（2，+∞）D、（－∞，2）13、不等式|2x-3|>5 的解集是（） [单选题] *A、{ x|x<-1或x>4}(正确答案)B、{ x|x<-1}C、{ x|x>4}D、{ x|-1<x<4}14、若|x|>3 ，则x的取值范围是（） [单选题] *A、{x|-3<x<3}B、{x|x<-3或x>3}(正确答案)C、{x|x>3}D、{x|x<-3}15、不等式|x+2|<5在正整数集中的解集是（） [单选题] *A、{1,2}(正确答案)B、{1,2,3}C、{0,1,2,3}D、{-7,5}16、不等式|x+1|>2 的解集是（） [单选题] *A、{x|x>1}B、{x|x<-3}C、{x|x<-3或x>1}(正确答案)D、{x|－3<x<1}17、不等式 |x-2|<3 的解集是（） [单选题] *A、{x|x<-1或x>5}B、{x|x<-1}C、{x|x>5}D、{x|-1<x<5}(正确答案)18、若不等式|x-m| < 2的解集为{x|2 < x < 6}，则m= （） [单选题] *A、2B、4(正确答案)C、6D、819、若不等式|x-3| > a的解集是{x|x < 2或x > 4}，则a= （） [单选题] *A、3B、2C、1(正确答案)D、020、若不等式|x|<m的解集是(-5,5)，则m= （） [单选题] *A、5(正确答案)B、3C、-3D、-521、集合{x|-1<x≤5}用区间可表示为（） [单选题] *A、（﹣1，5）C、（﹣1，4 ）D、[﹣1，5 ]22、集合{x|x<2}可用区间表示为（） [单选题] *A、（﹣∞，2）(正确答案)B、（﹣∞，2 ]C、[ 2，＋∞）D、（2，＋∞）23、集合A=（﹣1，4），集合B = [ 0，5 ]，则A∪B =（） [单选题] *A、RB、（﹣1，5 ](正确答案)C、[ ﹣1，5 ]D、（﹣1，5）25、设集合A=（﹣∞，﹣1），全集为R，则集合A的补集是（） [单选题] *A、（﹣∞，﹣1）B、（﹣∞，﹣1 ]C、[﹣1，＋∞）(正确答案)D、（﹣1，＋∞）26、集合R用区间表示为（） [单选题] *A、（﹣∞，0）B、（0，＋∞）D、R27、3属于以下哪个区间（） [单选题] *A、（2，4）(正确答案)B、（1，2）C、（0，2）D、（0，1）28、表示正确的区间是（） [单选题] *A、（＋∞，﹣∞）B、（3，﹣3）C、（1，0）D、（3，4）(正确答案)29、长张高速的某路段最低限速60km/h，最高限速120km/h，则汽车在该路段的正常行驶速度（单位:km/h）的取值范围可用区间表示为（） [单选题] *A、[ 60，120](正确答案)B、[ 120，＋∞）C、（﹣∞，60 ]D、（60，120]30、区间（﹣7，2 ]可用集合表示为（） [单选题] *A、{x | -7<x<2}B、{x | -7≤x≤2}C、{x | -7<x≤2}(正确答案)D、{x|-7≤x<2}32、已知二次方程x^2-5x+6=0的两根分别为2和3，则不等式x^2-5x+6<0的解集为（） [单选题] *A、（﹣3，﹣2）B、（﹣3，2）C、（2，3）(正确答案)D、（﹣2，3）31、下列不等式为一元二次不等式的是（） [单选题] *A、3x＋4<0B、1/x+1>0C、√x+1<0D、x^2-x+1<0(正确答案)33、已知二次方程x^2-x-2=0的两根分别为2和－1，则不等式x^2-x-c=0的解集为（－1，2），则c的值为（） [单选题] *A、1B、﹣1C、2(正确答案)D、﹣235、若不等式的解集为[－3，a]，则a的值为（） [单选题] *A、9B、﹣9C、－3D、3(正确答案)36、要使√(x^2-2x+1)有意义，则x的取值范围（） [单选题] *A、空集B、R(正确答案)C、{ 0 }D、137、方程的判别式，要使，此时x的取值范围为（） [单选题] *A、空集(正确答案)B、RC、{ 0 }D、238、若不等式的解集为（－2，5），则c的值为（） [单选题] *A、3B、4C、5(正确答案)D、639、以下说法正确的是（） [单选题] *A、x^2<4的解集为{x|x<±2}B、当a=时，不等式ax^2+bx+c>0不是一元二次不等式(正确答案)C、x+3>0的解集为空集D、不等式（x+1）（x+2）<0的解集为（1，2）40、长方形长为x厘米，宽为x-4厘米（x>4），要使此长方形面积大于50平方厘米，可用不等式表示为（） [单选题] *A、x（x-4）>50(正确答案)B、x（x-4）<50C、x（x-4）≥50D、x（x-4）≤5041、不等式的解集是（） [单选题] *A、R(正确答案)B、∅C、（-2，+∞）D、(-∞,-2)∪(2,+∞)42、不等式的解集是（） [单选题] *A、∅B、[5,+∞)C、{5}D、R(正确答案)43、如果a>b，那么下列各式正确的是（） [单选题] *A、3a>3(正确答案)B、-3a>-3bC、a-3≤b-3D、a-2>b-144、若a>b，则下列不等式一定成立的是( B ) [单选题] *A、 3a<3(正确答案)B、-3a<-3bC、 a^2>b^2D、a-b<045、不等式的解集是（） [单选题] *A、{ x|x≥2}B、{x|x≤-2}C、{x|x≥2或x≤-2}(正确答案)D、{x|-2≤x≤2}46、由不等式|x|<3的正整数解组成的集合是（） [单选题] *A、（-3,3）B、{-2，-1，0，1，2}C、{1，2}(正确答案)D、{1,2,3}47、下列各式正确的是（） [单选题] *A、4/7> 5/9(正确答案)B、4/7< 5/9C、4/7 = 5/9D、2/3>5/648、不等式|3x-1|<1的解集为（） [单选题] *A、RB、{x|x<0或x>2/3}C、 {x|x>2/3}D、{x|0<x<2/3}(正确答案)49、不等式x^2-9>0的解集是（） [单选题] *A、{x|x>3}B、{x|x<-3}C、{x|-3<x<3}D、{x|x<-3或x>3}(正确答案)50、不等式|2x－1|>1的解集是（） [单选题] *A、{x|x<0}B、{x|x>1}C、{x|0<x<1}D、{x|x<0或x>1}(正确答案)51、集合{x|-1<x≤5}用区间可表示为（） [单选题] *A、（-1,5）B、[-1,5]C、(-1,5](正确答案)D、(-1,4)52、如果a>b，b>c，则（） [单选题] *A、a>c(正确答案)B、a<cC、b<cD、b>a53、不等式|2x-3|>5的解集为（） [单选题] *A、 (-1,4)B、(-∞,1)∪(4,+∞)(正确答案)C、(-∞,-1)D、(4,+∞)54、不等式(x+1)(x-3)>0的解集为（） [单选题] *A、{x|x>3}B、{x|x<-1}C、{x|-1<x<3}D、{x|x>3或x<-1}(正确答案)55、不等式2/(x-1)≥0的解集为（） [单选题] *A、{x|x>1}(正确答案)B、{x|x≥1}C、{x|-1<x<1}D、{x|x>1或x<-1}56、如下图所示，数轴上阴影部分表示的区间是（） [单选题] *A、（-4，2）B、 [2,-4)C、 [-4,2](正确答案)D、（-4,2]57、不等式|3x+1|>10的解集为（） [单选题] *A、(-3,11/3)B、(-∞,-3)∪(11/3,+∞)C、(-11/3,3)D、(-∞,-11/3)∪(3,+∞)(正确答案)58、不等式| x－3|≤ 6的解集是（） [单选题] *A、{ x| －1≤x≤ 2 }B、{ x| 4≤x≤ 9 }C、{ x| －3≤x≤ 9 }(正确答案)D、{ x| －3≤x≤ 2 }59、不等式x^2-4x+4≥0的解集是（） [单选题] *A、[2,+∞)B、(-∞,2]C、∅D、R(正确答案)60、不等式|x+2|>3的解集为（） [单选题] *A、[-5,1]C、(-5,1)D、(-∞,-5)∪(1,+∞)(正确答案)61、若√(x^2-x-6)有意义，则x的取值范围是（） [单选题] *A、（-∞，-1]∪[3，+∞）B、（-∞，-2]∪[3，+∞）(正确答案)C、[-2,3]D、(-1,3)62、不等式x(x＋1)<0的解集是（） [单选题] *A、{x|x<－1}B、{x|x>0}C、{x|－1<x<0}(正确答案)D、{x|x<－1或x>0}63、不等式x^2+x-6≥0的解集是（） [单选题] *A、[-3,2]B、(-∞,-3)∪(2,+∞)C、[-2,3]D、(-∞,3]∪[2,+∞）(正确答案)64、若方程x^2-4x-5=0的两个根分别为-1和5，则不等式x^2-4x-5<0的解集为（） [单选题] *A、(-1,5)(正确答案)C、[-1,5]D、(-∞,-1]∪[5,+∞)65、不等式x^2-9<0的解集为（） [单选题] *A、（3，+∞）B、(-∞,3)C、(-3,3)(正确答案)D、(-∞,-3)∪(3,+∞)66、若5x+3<18 ，则（） [单选题] *A、x<-5B、x>-5C、x<3(正确答案)D、x>567、不等式（3-x）(x+5)<0的解集为（） [单选题] *A、(-5,3)B、(3,5)C、(-∞,-5)D、(-∞,-3) U(5,+∞)(正确答案)68、不等式x^2≤0的解集为（） [单选题] *A、∅B、RC、{x|x=1}D、[－1，1](正确答案)69、不等式（x＋1）（x－2）≥0的解集是（） [单选题] *A、{x|x≤－1或x≥2}(正确答案)B、{x|x≤－1或x>2}C、{x|－1≤x≤2}D、{x|－1≤x<2}70、不等式|x+1|<5在正整数集中的解集是（） [单选题] *A、{1,2}B、{-6,5}C、{0,1,2}D、{1,2,3}(正确答案)。

.1 / 11大学2013—2014学年度第二学期期末考试《离散数学》试卷A第一局部选择题〔共20分〕一、单项选择题〔本大题共10小题，每题只有一个正确答案，答对一题得2分共20分〕 1、对任意集合A 、B 、和C ，以下论断中正确的选项是： 【】A. 假设A ∈B ，B ⊆C ，那么A ∈CB. 假设A ∈B ，B ⊆C ，那么A ⊆CC. 假设A ⊆B ，B ∈C ，那么A ∈CD. 假设A ⊆B ，B ∈C ，那么A ⊆C2、设A={a,{a}},以下式子中正确的有： 【】A. {a}∈ρ(A)B. a ∈ρ(A)C. {a}Íρ(A)D. 以上都不是3、P ：我将去镇上。

Q ：我有时间。

命题“我将去镇上，当且仅当我有时间〞符号化为：【】A. P →QB. Q →PC. P ↔QD. Q ∨¬P4、命题公式：〔P ∧〔P →Q 〕〕→Q 是 【】A ．矛盾式B. 可满足式 C. 重言式 D. 不能确定5、谓词公式)())()((x Q y yR x P x →∃∨∀中，量词x ∀的辖域是： 【】A. ))()((y yR x P x ∃∨∀B. )(x PC. )(),(x Q x PD.)()(y yR x P ∃∨6、在如下各图中，哪一个是欧拉图？ 【】7、设|V|>1，G= < V , E >是强连通图，当且仅当： 【】A ．G 中至少有一条通路B ．G 中至少有一条回路C ．G 中有通过每个结点至少一次的通路D ．G 中有通过每个结点至少一次的回路8、设}}2,1{},1{,{Φ=S ，那么 ρ(S) 有多少个元素？ 【】A ．3；B ．6；C ．7；D ．8 ；9、集合A={1，2，3，4，5，6，7，8，9，10}上的关系R={<x, y> | x + y = 10}，那么R 的性质为：【】A ．自反的；B ．对称的；C ．传递的、对称的；D ．反自反的、传递的10、集合A 上的等价关系R ，其等价类集合{[ a]R | a ∈ A}称为： 【】A ．A 与R 的并集，记作A ∪RB ．A 与R 的交集，记作A ∩RC ．A 与R 的商集，记作A/RD ．A 与R 的差集，记作A - R二、填空题(本大题共10小题，每题2分,共20分)11、集合A={φ,{φ}}，那么A 的幂集为。

《离散数学》试卷（A 卷）一、 选择题（共5 小题，每题 3 分，共15 分）1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕⋃)(为(C )。

A 、{1,2}B 、{2,3}C 、{1,4,5}D 、{1,2,3}2、下列语句中哪个是真命题 ( A )A 、如果1+2=3，则4+5=9；B 、1+2=3当且仅当4+5≠9。

C 、如果1+2=3，则4+5≠9；D 、1+2=3仅当4+5≠9。

3、个体域为整数集合时，下列公式（ C ）不是命题。

A 、)*(y y x y x =∀∀B 、)4*(=∃∀y x y xC 、)*(x y x x =∃D 、)2*(=∃∃y x y x4、全域关系A E 不具有下列哪个性质（ B ）。

A 、自反性B 、反自反性C 、对称性D 、传递性5、函数612)(,:+-=→x x f R R f 是（ D ）。

A 、单射函数B 、满射函数C 、既不单射也不满射D 、双射函数二、填充题（共 5 小题，每题 3 分，共15 分）1、设|A|=4，|P(B)|=32，|P(A ⋃B)|=128，则|A ⋂B|=ˍˍ2ˍˍˍ.2、公式)(Q P Q ⌝∨∧的主合取式为 。

3、对于公式))()((x Q x P x ∨∃，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为ˍˍˍ1ˍˍˍ。

4、设A ＝{1,2,3,4}，则A 上共有ˍˍˍ15ˍˍˍˍ个等价关系。

5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。

三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分）1、“这个语句是真的”是真命题。

（ F ）2、“刚和小强是同桌。

”是复合命题。

（ F ）3、))(()(r q q p p ∧⌝∧→⌝∨是矛盾式。

（ T ）4、)(T S R T R S R ⋂⋅⊆⋅⋃⋅。

实用文档离散数学试题（A卷答案）PQPQR))的主析取范式( ∨)?(?∧10一、（分）求(??PQPQR PQPQR)) ∧?∨∧))(∨∧?(∨?())??(?解：((?)?PQPQR))∧∨?)∨(?(∧PQPPQQPQR) ∨)∧∨()∧(∨∨∨??(∨PQPQR)∨)∧(?(∨∨PQRRPQR) ∧(∨∨(∨∧?∨?())PQRPQRPQR) ∨∨∨??()∨∧∨∧)((∨?∧MM01?∨∨∨∨∨mmmmmm736542二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。

试判断王教授是哪里人？PQR：王教授是杭州人。

：王教授是苏州人；设设解：王教授是上海人；则根据题意应有：PQ∧甲：?QP?乙：∧QR∧?丙：?王教授只可能是其中一个城市的人或者3个城市都不是。

所以，丙至少说Q?对了一半。

因此，可得甲或乙必有一人全错了。

又因为，若甲全错了，则有P，因此，乙全对。

同理，乙全错则甲全对。

所以丙必是一对一错。

故王教∧授的话符号化为：实用文档PQQRQRQPQR))(??∧∧)∨(?)∧∧)))((?∨∧(()∧((∧?PQQRPQQRQPQR) ??∧∧∧∧?∧∧?(?)∧∨∧∧?()∨(?PQRPQR) ?)∨?(?(∧∧∧?∧PQR???∧∧?T因此，王教授是上海人。

tsrRR的且具有自反性、对称性和传递性的最是包含10分）证明)(三、（小关系。

RAtsrR)(4.19上的二元关系，则由定理知，证明设是包是非空集合R的且具有自反性、对称性和传递性的关系。

含R的且具有自反性、对称性和传递性的任意关系，则由闭包的若是包含'R rRsrRs()＝)?。

由定理4.15和由定理4.16得定义知，进而有(()?'''RRR tsrRt()＝?。

离散数学试题（Ａ卷及答案)一、证明题（１0分)1)(⌝Ｐ∧(⌝Ｑ∧R））∨(Q∧R)∨(Ｐ∧Ｒ）⇔Ｒ证明：左端⇔(⌝Ｐ∧⌝Q∧R）∨（(Q∨P)∧Ｒ)⇔(（⌝P∧⌝Q）∧R))∨(（Q∨P)∧Ｒ）⇔(⌝（Ｐ∨Ｑ)∧R）∨(（Q∨P)∧R）⇔（⌝(Ｐ∨Ｑ)∨(Q∨P））∧R⇔（⌝(Ｐ∨Q)∨（Ｐ∨Q））∧R⇔T∧R（置换）⇔R2)∃x（A(ｘ)→B（x))⇔∀ｘＡ（x）→∃xB(x)证明：∃x(A（x)→B(x)）⇔∃x(⌝A(x)∨B(x））⇔∃x⌝A（ｘ）∨∃xB（x)⇔⌝∀xA （ｘ）∨∃xB(x)⇔∀xA(ｘ）→∃ｘB(ｘ）二、求命题公式(P∨（Q∧R))→(Ｐ∧Ｑ∧Ｒ)的主析取范式和主合取范式(10分)证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(Ｐ∨（Q∧Ｒ)）∨（Ｐ∧Q∧R)）⇔（⌝P∧(⌝Ｑ∨⌝Ｒ)）∨(P∧Q∧R)⇔（⌝P∧⌝Q）∨（⌝P∧⌝R）)∨（P∧Q∧R）⇔（⌝Ｐ∧⌝Q∧R）∨(⌝P∧⌝Q∧⌝R）∨（⌝P∧Q∧⌝R))∨(⌝P ∧⌝Q∧⌝Ｒ))∨(P∧Q∧R）⇔m0∨m１∨ｍ2∨m7⇔M3∨M4∨M5∨Ｍ６三、推理证明题（１0分)1）Ｃ∨D, (C∨D)→⌝E, ⌝E→(Ａ∧⌝Ｂ）, （A∧⌝B)→（R∨S)⇒Ｒ∨S证明：(1) （C∨D）→⌝E ﻩﻩ(2）⌝Ｅ→（A∧⌝B) ﻩ(3）（C∨Ｄ)→(Ａ∧⌝Ｂ）(4）（Ａ∧⌝Ｂ)→（R∨S）（5) (Ｃ∨D)→(R∨Ｓ) ﻩ(6) C∨Ｄ（７） R∨S2）∀ｘ(P(ｘ)→Q(y)∧Ｒ(x）),∃xP(ｘ)⇒Q（y）∧∃ｘ（P(x)∧Ｒ（x))证明(１)∃xＰ(ｘ)(2)P（ａ)(3)∀ｘ（P(x)→Ｑ(y)∧R（x))(４)P（ａ）→Q(y）∧Ｒ(a）(5)Ｑ(ｙ)∧Ｒ(a）(６)Q（y)(7)R(a）(８)P(ａ）(9)P（a)∧R（a)（10)∃ｘ(Ｐ（x）∧R(x）)(１1)Ｑ（y）∧∃ｘ(P(ｘ)∧Ｒ(x）)四、设m是一个取定的正整数,证明:在任取ｍ＋1个整数中，至少有两个整数，它们的差是ｍ的整数倍证明设1a,2a,…,1+m a为任取的m+1个整数，用ｍ去除它们所得余数只能是０,１，…，m－1,由抽屉原理可知,1a,2a,…,1+m a这m+1个整数中至少存在两个数sa和t a，它们被m除所得余数相同,因此s a和t a的差是m的整数倍。