021046[离散数学(2)] 天津大学机考题库答案

《离散数学》题库与答案一、选择或填空（数理逻辑部分）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）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。

）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。

A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。

答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。

答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。

答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。

答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。

离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。

离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。

而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。

本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。

第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。

命题变量用字母表示，代表一个命题。

命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。

括号用于改变命题联结词的优先级。

习题2：列举命题逻辑的基本定律。

答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。

1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。

集合的基本运算包括并、交、差和补等。

习题2：列举集合的基本定律。

答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。

第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。

答：命题逻辑的推理规则是用来推导命题的逻辑规则。

常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。

习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。

答：假言推理规则可以用来证明该命题。

根据假言推理规则，如果A成立，则B成立。

又根据假言推理规则，如果B不成立，则A不成立。

2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。

与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。

第一章测试1.下列语句（）是命题。

A:我只知道一件事情，就是我什么也不知道。

B:你正在说谎。

C:岂有此理？D:请打开门！答案:B2.设命题公式A为¬ (p∧¬q)∨(p→r)。

则在p、q、r的下列真值指派（）下，A的真值为假。

A:0、1、1B:1、0、0C:1、1、0D:0、0、1答案:B3.下列字符串（）是命题公式。

A:p→rB:(p→r)C:¬ (p∧¬q)∨(p→r)D:(¬ (p∧¬q))答案:B4.下列公式（）是公式¬(p∧¬q)∨(p→r)的合取范式。

A:(¬p∨q)∧rB:(¬p∨q)∧(¬p∨r)C:¬p∨q∨¬p∨rD:q∧(¬p∨r)答案:C5.公式¬(p∧¬q)∧(p→r)不能逻辑蕴含（）。

A:¬p∧qB:¬pC:¬p∨rD:(¬p∨q)∧r答案:D6.公式¬ (p∧¬q)∧(p→r)等价于（）。

A:¬p∨(q∧r)B:¬p∨(¬q∧r)C:(¬p∧q)→(p→r)D:(p∧¬q)→(p→r)答案:A第二章测试1.设P(u)：u是运动员，Q(u)：u是大学生。

则命题“存在运动员是大学生”被翻译为（）。

A:∃x(P(x)∧Q(x))B:∃x(P(x)→Q(x))C:∃x(P(x)∨Q(x))D:∃xQ(x)答案:A2.设P和Q是谓词，则下列字符串（）是一元命题函数。

A:∃x(P(u, x)∨Q(u))B:P(u, v)∧Q(u)C:∃xQ(x)D:P(u, u)→Q(v)答案:A3.下列字符串（）是谓词公式。

A:¬P(u, u)→Q(v)B:∃xP(x, x)C:P(u, v)∧Q(u)D:∃x∀xP(x, x)答案:B4.对于公式¬∃x(¬P(u, x)→∀yQ(y))，∃x的作用域是（）。

第2次作业一、单项选择题(本大题共40分，共20小题，每小题2分)1.假设A={a, b, c, d},考虑子集S= {{a, b}, {b, c}, {d}},则下列选项正确的是()oA.S是A的覆盖B.S是A的划分C.s既不是划分也不是覆盖D.以上选项都不正确2.设h是群G上的一个同态，|G|二12,山(G)|二3,则|K| (K是h的核)二_________________ ()A.1B.2C.D.3.L23 ), 设G是连通(n,m)的平面图，有r个面，且每个面的次数至少为L( 则A.m>3n-6B.Hl <c.m+n-r=2D.m+r-n二24.如果小王和小张都不去，则小李去。

设P：小王去。

Q：小张去。

R：小李去。

则命题符号化为_________ oA.-I QA-i PVRB.(Q->P)ARC.(n PAn QLRD.(PAQ)-R5.没有不犯错误的人。

M(x)： x为人。

F (x) : x犯错误。

则命题可表示为()OA.(Vx) (M(x) F (x)B.(3x) (M(x) AF(x)C.(Vx) (M(x)AF(x))D.(3x) (M(x)-F(x)6.(1)燕子北冋，春天来了。

设P:燕了北回。

Q：春天來了。

则(1)可以表示为___________ oP->QQ-PC.UQD.P VQ7.命题公式(P->QA-i P)的类型是___________ 。

A.重言式B.矛盾式C.可满足式D.永真式6.一阶逻辑公式Vx(F(x, y)AG(y, z) )—VzF(z, y)是()前束范式封闭公式C.永真式D.永假式7.谓词公式(3x)P(x, y) A (Vx) (Q(x, z)-> Gx) (Vy)R(x, y, z)中的量词Vx 的辖域是()。

A.(Vx)(Q(x,z)->(3 x)( Vy)R(x,y ,z)B.Q(x, z)-> (Vy)R(x, y, z)C.Q (x, z) —(3x) (Vy) R (x, y, z)D.Q(x, z)8.关于半群的性质，下面说法不正确的是()A.若〈S,*>S且*在8上是封闭的，那么匸是一个半群，B<B, *>也是一个半群。

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

b)我今天进城，除非下雨。

c)仅当你走，我将留下。

2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。

（4分）4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。

离散数学（2）-1复习题一、判断题1、任何两个重言式的合取或析取，仍然是一个重言式。

（T）2、一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。

（T）3、在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。

（ T ）4、任何一个谓词公式，均和一个前束范式等价。

（T）5、(P→Q)(P→R) P →(Q R)。

（T）6、(P Q)→R(P→R)(Q→R)。

（F）7、(x)（P(x)→Q(x)）(x)P(x)→(x)Q(x)。

（F）8、(x)(P(x)→Q(x)) (x)P(x)→(x)Q(x)。

（ T）9、(x) (y) P (x, y) (x)(x)P(x,y)。

（T）10、公式()()()()"??是永假式。

（T）x P x y P y11、()()谯。

（T）P Q P Q P Q刿?。

（T）12、P P P二、选择题1、下列语句中为命题的是（D）。

A．这朵花是谁的？ B．这朵花真美丽啊！C．这朵花是你的吗？ D．这朵花是他的。

2、设P: 我有时间，Q: 我去书店买书，将命题“只要我有时间，我就去书店买书”符号化为( D )。

A．P∨Q B．⌝P→⌝QC．P∧Q D．P→Q3、设A和B都是命题，则A B→的真值为假当且仅当（D）。

A．A为假，B为真 B．A为假，B也假C．A为真，B也真 D．A为真，B为假4、命题公式()P Q R ⌝∧→的成真赋值为（ B ）。

A ．000，001，110B ．001，011，101，110，111C ．全体赋值D ．无5、与命题公式()P Q P →→等值的公式是（ D ）。

A. ()P Q R ∨→B. ()P Q R →∨C ．()P Q R →→D ．()P Q R ∧→6、下列命题联结词集合中哪个不是完备集？（ A ）。

A ．},{↔⌝B ．},{→⌝C ．{}↑D ．{}↓7、下列各式中，哪些是析取范式（ A ）？A ．P Q ⌝∧B ．()P Q R ⌝∧∨C ．(())P Q R ∧⌝⌝∨D ．()P Q R ⌝∧∨⌝8、设谓词():P x x 是运动员，():Q x x 是强壮的，命题“没有一个运动员不是强壮的”可符号化为（ C ）。

大学离散数学试卷二及答案一、单项选择题 （2分×10=20分）1、下列语句是命题的有[ B ]。

A. 122>+y x ；B. 2010年的国庆节是晴天；C. 青年学生多么朝气蓬勃呀！D. 学生不准吸烟!2、在命题逻辑中，任何命题公式的主合取范式都 [ C ]。

A. 不一定存在;B. 不存在；C. 存在且唯一;D. 存在但不唯一.3、设S={1,2,3,4}，R={<1,1>,<3,3>,<4,4>}，则R 满足的性质是 [ C ]A. 自反、对称、传递的 ;B. 自反、对称、反对称的;C. 对称、反对称、传递的;D. 只有对称性.4. 与命题p ∧(p ∨q)等值的公式是 [ A ]。

A. p ；B. q ；C. p ∨q ；D. p ∧q.5. 设M={a,b,c}，M 上的等价关系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}确定的集合M 的划分是[ D ]。

A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c }}6. 设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“每个人都喜欢某种花”的逻辑符号化为[ C ]。

A. )),()(()((y x H y F y x M x →∃∧∀；B. )),()(()((y x H y F y x M x →∃→∀；C. )),()(()((y x H y F y x M x ∧∃→∀；D. )),()(()((y x H y F y x M x ∧∀→∃.7. 下列图中，不是哈密顿图的为[ A ]。

A B C D8. 下列四组数据中，能作为某个4阶无向简单图的度序列的为[ D ]。

A. 1,2,3,4 ；B. 2,2,2,3；C. 1,1,2,3；D. 1,1,1,3.9. 一棵无向树T 有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T 中有[ C ]片树叶。

离散考试试题及答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念不是布尔代数的基本运算？A. 与B. 或C. 非D. 模答案：D2. 集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A3. 命题逻辑中，下列哪个符号表示“蕴含”关系？A. ∧B. ∨C. →D. ↔答案：C4. 关系R在集合A上是自反的，意味着什么？A. 对于所有a∈A，(a, a)∈RB. 对于所有a∈A，(a, a)∉RC. 对于所有a∈A，(a, b)∈RD. 对于所有a∈A，(a, b)∉R答案：A二、填空题（每题5分，共20分）1. 一个集合的基数是集合中元素的________。

答案：数量2. 在有向图中，如果存在一条从顶点u到顶点v的路径，则称顶点v 是顶点u的________。

答案：可达的3. 一个图是连通的，当且仅当图中任意两个顶点都是________。

答案：连通的4. 在命题逻辑中，一个命题的否定是________。

答案：它的对立命题三、简答题（每题10分，共30分）1. 请解释什么是图的哈密顿回路。

答案：哈密顿回路是一个图中的闭合回路，它恰好访问图中的每个顶点一次。

2. 描述一下什么是二元关系，并给出一个例子。

答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。

例如，小于关系是数字集合上的一个二元关系。

3. 什么是图的生成树？答案：图的生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树，即它是连通的且没有环。

四、计算题（每题15分，共30分）1. 给定一个集合A={1,2,3,4,5}，计算它的幂集。

答案：幂集P(A)={∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5},{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}, A}。

自考离散数学考试题及答案一、选择题（每题2分，共10分）1. 在集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ∩答案：A2. 有限自动机中的一个状态不包括以下哪个元素？A. 初始状态B. 终止状态C. 转移函数D. 输入符号答案：C3. 在命题逻辑中，德摩根定律描述了哪些命题的等价性？A. (¬P ∧ ¬Q) ↔¬(P ∨ Q)B. (P ∨ Q) ↔¬(¬P ∧ ¬Q)C. (P ∧ Q) ↔¬(P ∨ Q)D. (¬P ∨ ¬Q) ↔¬(P ∧ Q)答案：A4. 以下哪个算法是用于解决图的最短路径问题？A. 欧几里得算法B. 迪杰斯特拉算法C. 快速排序算法D. 弗洛伊德算法答案：B5. 布尔代数中，一个表达式可以有的最大项数是多少？A. nB. 2^nC. n^2D. 2n答案：B二、填空题（每题3分，共15分）6. 在关系数据库中，确保实体完整性的约束称为________。

答案：主键7. 一个有向图中，如果存在从顶点A到顶点B的路径，则称顶点A可以________顶点B。

答案：到达8. 在命题逻辑中，如果命题P和命题Q都为真，则命题P → Q的真值是________。

答案：真9. 一个命题函数的真值表中，如果某一行的P和Q都为假，那么这一行的结果是________。

答案：真10. 在图论中，一个完全图是指图中任意两个顶点都________。

答案：相连三、解答题（共75分）11. （15分）证明：在任何非空集合中，至少存在一个元素不包含于该集合的任何子集中。

答案：略12. （20分）给定一个有向图，描述如何使用拓扑排序算法来对图中的顶点进行排序。

答案：略13. （20分）解释什么是正规表达式，并给出一个例子来说明如何使用它来匹配字符串。

答案：略14. （20分）证明：在任何无向图中，边数最多的生成子图最多有3n/2条边，其中n是顶点的数量。