离散数学(52)

计算机离散数学-试题及答案1、下列语句中，不是命题的有（）A、 5能被2整除B、太阳系以外的星球上有生物C、现在开会吗？D、小李在宿舍里答案： C2、下列命题中真值为T的有（）A、若2+2=4,则3+3¹6;B、若2+2=4,则3+3=6;C、 2+2=4,当且仅当3+3¹6;D、 2+2¹4,当且仅当3+3=6;答案： B3、用P表示：天下大雨；Q表示：他乘公共汽车上班。

将“如果天下大雨，他就乘公共汽车上班。

”符号化正确的是（）A、 P®QB、Q®PC、PÙQD、PÚQ答案： A4、集合{a,b,c}的幂集的元素个数为（）A、 6B、 9C、 7D、 8答案： D5、对于集合S={,{1},{1,2}},下列表达式正确的是A、{1,2}ÎSB、2ÎSC、1ÎSD、{2}ÎS答案： A6、与谓词公式~P®Q等价的公式是A、~PÚQB、P~ÚQC、~P~ÚQD、PÚQ答案： D7、集合A={a,b}与集合B={1,2}的笛卡儿乘积为A、 {(a,1(b,2)}B、 {(a,2)(b,1)}C、 {(a,1),(b,1),(a,2),(b,2)}D、 {(a,b),(b,a),(a,a),(b,b)}答案： D8、无向图的关联矩阵中“关联”指的是A、顶点与顶点的关联B、边与边的关联C、边与顶点的关联D、都不是答案： C9、与公式A等价的公式是（）A、公式A的前束范式B、公式A的斯柯林范式C、公式A的前束范式和斯柯林范式D、都不是答案： A10、I为整数集，下列系统中不是代数系统的有（）A、 (I,÷ )B、 (I, +)C、 (I,× )D、都不是答案： A11、设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A、 10B、 12C、 16D、 14答案： D12、在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A、 b∧(a∨c)B、 (a∧b)∨(a’∧b)C、 (a∨b)∧(a∨b∨c)∧(b∨c)D、 (b∨c)∧(a∨c)答案： A13、设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A、 <{1},·>B、〈{-1},·〉C、〈{i},·〉D、〈{-i},·〉答案： A14、设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A、〈Z，+，/〉B、〈Z，/〉C、〈Z，-，/〉D、〈P(A)，∩〉答案： D15、下列各代数系统中不含有零元素的是( )A、〈Q，*〉Q是全体有理数集，*是数的乘法运算B、〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C、〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈ZD、〈Z，+〉，Z是整数集，+是数的加法运算答案： D16、设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A、 R∪IAB、 RC、 R∪{〈c,a〉}D、 R∩IA答案： C17、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A、｛〈c,a〉，〈a,c〉｝B、 {〈c,b〉，〈b,a〉}C、 {〈c,a〉，〈b,a〉}D、 {〈a,c〉，〈c,b〉}答案： D18、下列式子正确的是( )A、Ø∈ØB、Ø⊆ØC、{Ø}⊆ØD、{Ø}∈Ø答案： B19、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为A、 P∨QB、 P∧┐QC、 P→┐QD、 P∨┐Q答案： B20、以下命题公式中，为永假式的是( )A、 p→(p∨q∨r)B、 (p→┐p)→┐pC、┐(q→q)∧pD、┐(q∨┐p)→(p∧┐p)答案： C21、设R1，R2是集合A＝{1，2，3，4}上的两个关系，其中R1＝{(1，1)，(2，2)，(2，3)，(4，4)}，R2＝{(1，1)，(2，2)，(2，3)，(3，2)，(4，4)}，则R2是R1的( )闭包．A、自反B、反对称C、对称D、以上都不是答案： C22、与P®Q等价的公式有( )A、PÚQB、~PÚ Q--C、~(PÙ~Q)D、~PÙQ答案： C23、A={a,b,c,d},B={1,2,3,4},下列关系中A到B的关系不正确的是( )A、 {(d,1),(c,3)}B、 {(a,1),(b,3),(c,3)}C、 {(1,a),(2,b)}D、 {(a,4),(b,3),(c,2),(d,1)}答案： C24、整数集I上的关系“”是( )A、自反的B、对称的C、非对称的D、非传递的答案： C25、集合A={a,{a},{b,c}}的子集不正确有（）A、ÆB、 {b}C、 {a,{a},{b,c}}D、 {a}答案： B26、下列句子中，（）是命题。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（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)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 （命题必须满足是陈述句，不能是疑问句或者祈使句。

总复习题1. 设︱A ︱=5, ︱P(B)︱=512, ︱P(A ∩B)︱=8, 则︱A ⊕B ︱＝ , ︱A ∪B ︱＝ 。

2. 设p :选小王当班长，q ：选小李当班长，则选小王或小李中的一人当班长可符号化为____。

3. 命题公式根据赋值可分为________________、________________和______________三类。

4. 含N 个个命题变项的命题公式有______________组赋值，有_____________个真值。

5. ()A A B ∨∧=______________，()A A B ∧∨=__________________。

6. 设{|3,,14}A x x k k N k ==∈≤≤，则用列举法表示A =________________________。

7. 集合A ={1，2}的幂集P (A )与A 的笛卡尔积()P A A ⨯=________________________________________________________________________________________________________。

8. 某无向图G 中，共有边15条，该图中共有5度顶点2个，4度顶点3个，剩下的均为2度顶点，则该图中共有顶点 个。

9. 一个结点为n 的无向完全图，其边的数目为 。

10．已知<Z 6, ⊕>是一个群，则这个群的幺元是 ，这个群当中，逆元和自身相等的元素有 。

11. 已知关系R 1＝{<a,a>,<a,c>,<b,d>,<c,b>},R 2={<c,a>,<b,c><a,d><d,b>}，写出下列关系 R 2◦R 1= ,R 13= 。

12、设Φ是一个空集，则下列之一哪一个不成立（①、Φ∈Φ②、Φ⊆Φ③、Φ∈{Φ}④、Φ⊆{Φ}13、如果命题公式G=P ∧Q ，则下列之一哪一个成立（①、G=⌝(P →Q) ②、G=⌝(P →⌝Q)③、G=⌝(⌝P →Q)④、G=⌝(⌝P →⌝Q)14、设X 、Y 是两个集合，|X|＝n ，|Y|＝m ，则从X 到Y 可产生（①、mn②、nm③、n m ⨯④、2m n⨯15、若复合映射τσ⋅是满射，则 ( )。

离散数学组合数学与离散概率离散数学是数学的一个分支，研究离散对象之间的关系。

而组合数学是离散数学的一个重要分支，研究的是集合论、图论、数字理论及其他离散结构的组合与计数问题。

离散概率是在离散场景下进行概率推理和计算的数学方法。

一、组合数学组合数学是数学中研究离散结构与计数方法的一个分支，它主要包括排列组合、二项式定理、递归等内容。

1. 排列组合排列组合是组合数学中最基础的概念之一，指的是从给定的元素中按照一定规则选取若干元素进行排列或组合。

在排列中，元素的顺序是重要的。

比如从元素{A, B, C}中选取两个元素进行排列，一共有6种可能的结果{AB, AC, BA, BC, CA, CB}。

而在组合中，元素的顺序不重要。

以同样的集合{A, B, C}为例，选取两个元素的组合只有三种{AB, AC, BC}。

排列组合的计算公式为：排列公式：P(n, k) = n! / (n - k)!组合公式：C(n, k) = n! / (k! * (n - k)!)其中，n为元素的总数，k为选取的元素个数。

2. 二项式定理二项式定理是组合数学中的一个重要定理，它描述了多项式的幂展开式中每一项的系数。

二项式定理的表达式为：(x + y)^n = C(n, 0) * x^n * y^0 + C(n, 1) * x^(n-1) * y^1 + ... + C(n, n) * x^0 * y^n其中，C(n, k)表示从n个元素中选取k个元素的组合数。

3. 递归递归是组合数学中常用的一种计算方法，它通过将大问题分解为相同或类似的小问题来求解。

在组合数学中，递归常用于计算排列组合的问题。

比如计算阶乘n!时，可以使用递归的方法进行计算。

二、离散概率离散概率是在离散场景下进行概率推理和计算的数学方法，它与连续概率不同，连续概率是在连续场景下进行概率计算的方法。

离散概率常用于描述离散随机变量的分布与概率。

其中，离散随机变量指的是取值为有限个或可数无穷个的随机变量。

§5.2 图的连通性习题5.21．证明或否定：（1）简单图G 中有从点u 到点v 的两条不同的通路，则G 中有基本回路。

（2）简单图G 中有从点u 到点v 的两条不同的基本通路，则G 中有基本回路。

解：（1）简单图G 中有从点u 到点v 的两条不同的通道，则G 中有回路。

（2）简单图G 中有从点u 到点v 的两条不同的路，则G 中有回路。

解 （1）不一定：如下图，点1与点3之间有两条通道：（1、2、3）和（1、2、1、2、3），但图中没有回路。

（2）一定：设两条路分别为),,,,,(211v x x x u L m =和),,,,,(212v y y y u L n =。

若对m i ≤≤1，n j ≤≤1有j i y x ≠，则),,,,,,,,,,(12121u y y y y v x x x u n n m -是一条回路。

否则假设l k y x =且是离u 最近的一对（即对k i ≤≤1，l j ≤≤1，不存在j i y x =），则),,,,,,,,,(12121v y y y x x x u l k -是一条回路。

2．设G 是简单图，)(G δ≥2，证明G 中存在长度大于或等于1)(+G δ的基本回路。

证：以图G 中一点v 1出发，与之相邻的点设为v 2，由于)(G δ≥2，则v 2至少还有一个邻接点，设为v 3，若v 3与v 1邻接，则形成长度为1)(+G δ的基本回路，则若v 3不与v 1邻接，则至少还有一个邻接点，设为v 4，若v 4与v 1或v 2邻接，则形成长度为大于或等于1)(+G δ的基本回路，若v 4与v 1和v 2都不邻接，至少还有一个邻接点，设为v 5，…，依次类推，一定可以到达最后一个顶点v i ，由于)(G δ≥2，则除了v i -1外，一定会与前面的某个顶点邻接，就会形成长度为大于或等于1)(+G δ的基本回路。

3．证明：若连通图G 不是完全图，则G 中存在三个点w v u ，，，使E v u ∈)(，，E w v ∈)(，，E w u ∉)(，。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等众多领域都有着广泛的应用。

下面就为大家整理一下离散数学的一些重要知识点。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象所组成的整体。

比如，一个班级里所有学生就可以构成一个集合。

集合的表示方法有列举法和描述法。

列举法就是将集合中的元素一一列举出来，如{1, 2, 3, 4, 5}；描述法是用元素所满足的条件来描述集合，如{x ｜ x 是小于 10 的正整数}。

集合之间的关系包括子集、真子集、相等。

如果集合 A 中的所有元素都属于集合 B，那么 A 就是 B 的子集；如果 A 是 B 的子集，且 B中存在元素不属于 A，那么 A 就是 B 的真子集；如果 A 和 B 包含的元素完全相同，那么 A 和 B 相等。

集合的运算有并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所得到的集合；补集是在某个给定的全集 U 中，集合 A 的补集是由不属于 A 的元素组成的集合。

二、关系关系是集合中元素之间的某种联系。

比如，在一个班级中，同学之间的“朋友关系”就是一种关系。

关系可以用矩阵和图来表示。

矩阵表示中，若元素之间存在关系则对应位置为 1，否则为 0；图表示中，用节点表示元素，有关系的元素之间用边连接。

关系的性质包括自反性、对称性、反对称性和传递性。

自反性是指每个元素都与自身有关系；对称性是指如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是指如果 a 与 b 有关系且 b 与 a 有关系，那么 a ＝b；传递性是指如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

三、函数函数是一种特殊的关系，它对于定义域中的每个元素，都有唯一的对应值在值域中。

函数的类型有单射、满射和双射。

离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（⌝P⇄Q）∧(P⇄R∨S)b)我今天进城，除非下雨。

设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：⌝Q→P或⌝P→Qc)仅当你走，我将留下。

设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P2.用谓词逻辑把下列命题符号化a)有些实数不是有理数设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：∃x(R(x) ∧⌝Q(x)) 或⌝∀x(R(x) →Q(x))b)对于所有非零实数x，总存在y使得xy=1。

设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为：∀x(R(x) ∧⌝E(x,0) →∃y(R(y) ∧E(f(x,y),1))))c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)⇄∀a(A(a)→∃b(B(b) ∧ E(f(a),b) ∧∀c(S(c) ∧ E(f(a),c) →E(a,b))))二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R))↔(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）(P→(Q→R))↔(R→(Q→P))⇔（⌝P∨⌝Q∨R）↔(P∨⌝Q∨⌝R)⇔(（⌝P∨⌝Q∨R）→(P∨⌝Q∨⌝R)) ∧ ((P∨⌝Q∨⌝R) →（⌝P∨⌝Q∨R）).⇔(（P∧Q∧⌝R）∨ (P∨⌝Q∨⌝R)) ∧ ((⌝P∧Q∧R) ∨（⌝P∨⌝Q∨R）)⇔(P∨⌝Q∨⌝R) ∧(⌝P∨⌝Q∨R) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（⌝P∧⌝Q∧⌝R)∨（⌝P∧⌝Q∧R)∨（⌝P∧Q∧⌝R)∨（P∧⌝Q∧⌝R)∨（P∧⌝Q∧R)∨（P∧Q∧R)2.设个体域为{1,2,3}，求下列命题的真值（4分）a)∀x∃y(x+y=4)b)∃y∀x (x+y=4)a) T b) F3.求∀x(F(x)→G(x))→(∃xF(x)→∃xG(x))的前束范式。

02.2020年2⽉份-专升本-第⼆学期-离散数学期末考试练习20200219-离散数学期末考试练习Round 1⼀、单选题1.((A∪B)∩B)?(A∪B)的简化结果为（）答案：D、?2.合集A={1,2,?,10}上的关系R={(x,y)|x+y=10,x∈A,y∈A},则R的性质为（）答案：B、对称的3.函数的复合满⾜（）答案：B、结合率4.R为实数集，运算*定义为：a,b∈R,a?b=a?|b|,则代数系统(R2?)是（）答案：A、半群5.任何⼀个有限群在同构的意义下可以看作是（）答案：B、置换群6.设Z是整数集，+，?分别是普通加法和乘法，则(Z,+,?)是（）答案：C、整数7.若图G1与G2同构，则它们相对应的邻接矩阵A(G1)与A(G2)()答案：A、相同或者其中⼀个通过⾏与列变换能转换成另⼀个8.设A?B=?,则有（）答案：C、A?B9.设A={a,b,c,d,e},B={0,1}，那么可定义()种不同A到B的函数答案：D、3210.具有如下定义的代数系统(G,*)，哪个不构成群？（）答案：D、G=Q，*是普通乘法11、+，?为⼀般的加法和乘法，则下述代数系统中哪⼀个是整环？（）答案：A、S={x|x=a+b√3,a,b∈Q}12、下⾯四个格所对应的哈斯图，哪个是分配格？（）答案：D、13、下列哪种说法与其他三个不相等（）答案：D、B?A14.在代数系统中，整环和域的关系为（）答案：C、域⼀定是整环15、下⾯哪些集合关于指定的运算构成环？（）答案：C、{a+b√2|a,b∈Z},关于数的加法和乘法16、下⾯哪个偏序集构成有界格（）答案：D、(P(A),?),A=(a,b,c)17、设G=(n,m)是Euler图，则n,m有关系（）答案：D、n,m的奇偶性即可以相同也可以相反18、对意集合A、B、C，下述论断正确的是（）答案：A、若A∈B,B?C,则A∈C19、设P={x|(x+1)2≤4},Q={x|x2+16≥5x}，则下列选项正确的是（）答案：C、Q?P20、设A={a,b,c}上的关系如下，有传递性的有（）答案：D、ρ4={}21、图的构成要素是（）答案：C、结点与边22、哈密尔顿回路是（）答案：C、既是基本回路也是简单回路23、设G=(n,m)为⽆向简单图，可构成邻接矩阵的数⽬为（）答案：A、n!24、下列公式中，（）是可满⾜式。