广东工业大学离散数学试卷和答案-2015B

《离散数学》题库与答案一、选择或填空（数理逻辑部分）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”互为逆否命题的是_________。

离散数学试题(B卷答案1〕一、证明题〔10分〕1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R证明:左端(P∧Q∧R)∨((Q∨P)∧R)((P∧Q)∧R))∨((Q∨P)∧R)((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R((P∨Q)∨(P∨Q))∧RT∧R(置换)R2)x(A(x)B(x))xA(x)xB(x)证明：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取X式和主合取X式〔10分〕。

证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R))〔P∧(Q∨R)〕∨(P∧Q∧R)(P∧Q)∨(P∧R))∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R)m0∨m1∨m2∨m7M3∨M4∨M5∨M6三、推理证明题〔10分〕1〕C∨D，(C∨D)E，E(A∧B)，(A∧B)(R∨S)R∨S证明：(1)(C∨D)EP(2)E(A∧B)P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)P(5)(C∨D)(R∨S)T(3)(4)，I(6)C∨DP(7)R∨ST(5)，I2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。

一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 22n.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 .4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是(P∧⌝Q∧R)5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝{4} ; A⋃B＝{1,2,3,4};A－B＝{1,2} .7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0)9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则R1∙R2 ={(1,3),(2,2),(3,1)} , R2∙R1 = {(2,4),(3,3),(4,2)} _R12 ={(2,2),(3,3).10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = .11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} ,A∩B ={x | 0≤x≤1, x∈R} , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} .14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是∃x(⌝P(x)∨Q(x)) .15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。

离散数学考试题(后附详细答案)一、命题符号化（共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分，共20分）1. 在集合论中，下列哪个选项不是集合的运算？A. 并集B. 交集C. 差集D. 乘法2. 命题逻辑中，下列哪个命题是真命题？A. (P ∧ ¬P) → QB. (P ∨ Q) ∧ ¬(P ∧ Q)C. P → (Q → P)D. (P → Q) ∧ (Q → R) → (P → R)3. 函数f: A → B，如果f是单射，那么下列哪个选项是正确的？A. A中不同的元素在B中可能有相同的像B. B中每个元素都有原像C. A中不同的元素在B中有不同的像D. B中不同的元素在A中有不同的原像4. 在图论中，下列哪个选项不是图的基本术语？A. 顶点B. 边C. 邻接D. 矩阵5. 组合数学中，从n个不同元素中取出k个元素的组合数记作C(n, k)，下列哪个选项是错误的？A. C(n, k) = C(n, n-k)B. C(n, 0) = 1C. C(n, 1) = nD. C(n, k) = C(k, n)6. 关系R是A×B上的二元关系，下列哪个选项不是关系R的性质？A. 自反性B. 对称性C. 传递性D. 可数性7. 在命题逻辑中，下列哪个命题等价于P ∨ (Q ∧ R)？A. (P ∨ Q) ∧ (P ∨ R)B. (P ∧ Q) ∨ (P ∧ R)C. (P ∨ Q) ∨ RD. (P ∨ Q) ∧ R8. 集合{1, 2, 3}的幂集含有多少个元素？A. 3B. 6C. 8D. 99. 在图论中，下列哪个选项不是树的性质？A. 无环B. 至少有两个顶点C. 任意两个顶点都由唯一路径连接D. 至少有一个环10. 在集合论中，下列哪个选项是正确的？A. 空集是任何集合的子集B. 任何集合都是其自身的超集C. 空集是任何非空集合的真子集D. 空集是其自身的并集二、简答题（每题10分，共30分）11. 简述命题逻辑中的德摩根定律，并给出一个例子。

离散数学考试题目及答案1. 试述命题逻辑中的等价关系和蕴含关系。

答案：命题逻辑中的等价关系是指两个命题在所有可能的真值赋值下都具有相同的真值。

若命题P和Q等价，则记作P⇔Q。

蕴含关系是指如果命题P为真，则命题Q也为真，但Q为真时P不一定为真。

若命题P蕴含Q，则记作P→Q。

2. 证明：若集合A和B的交集非空，则它们的并集包含A和B。

答案：设x属于A∩B，即x同时属于A和B。

根据并集的定义，若元素属于A或B，则它属于A∪B。

因此，x属于A∪B。

由于x是任意属于A∩B的元素，所以A∩B≠∅意味着A∪B至少包含A∩B中的所有元素，即A∪B包含A和B。

3. 给定一个有向图G，如何判断G中是否存在环？答案：判断有向图G中是否存在环，可以采用深度优先搜索（DFS）算法。

在DFS过程中，记录每个顶点的访问状态，如果遇到一个已访问过的顶点，且该顶点不是当前路径的直接前驱，则表示存在环。

4. 描述有限自动机的组成部分及其功能。

答案：有限自动机由以下几部分组成：输入字母表、状态集合、转移函数、初始状态和接受状态集合。

输入字母表定义了自动机可以接收的符号集合；状态集合包含了自动机所有可能的状态；转移函数定义了在给定输入符号和当前状态的情况下，自动机如何转移到下一个状态；初始状态是自动机开始工作时的状态；接受状态集合包含了所有使自动机接受输入字符串的状态。

5. 什么是图的连通分量？如何确定一个无向图的连通分量？答案：图的连通分量是指图中最大的连通子图。

在一个无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的。

确定无向图的连通分量可以通过深度优先搜索（DFS）或广度优先搜索（BFS）算法。

从任一顶点开始搜索，搜索过程中访问的所有顶点构成一个连通分量。

重复此过程，直到所有顶点都被访问过，即可确定图中所有连通分量。

离散数学考试题目及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={3,4,5}，则A∩B的元素个数为：A. 0B. 1C. 2D. 3答案：B2. 函数f: X→Y是一个双射，当且仅当：A. f是单射且满射B. f是单射C. f是满射D. f是双射答案：A3. 命题p: "x是偶数"，命题q: "x是3的倍数"，下列逻辑运算中，表示"x是6的倍数"的是：A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案：A4. 有向图G中，若存在从顶点u到顶点v的有向路径，则称顶点u可达顶点v。

若G中任意两个顶点都相互可达，则称G为：A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案：A5. 在二进制数系统中，下列哪个数的值最大？A. 1010B. 1100C. 1110D. 1101答案：C6. 布尔代数中，逻辑或运算符表示为：A. ∧B. ∨C. ¬D. →答案：B7. 有限自动机中，状态q0是初始状态，状态q1是接受状态。

若存在从q0到q1的ε-转移，则该自动机：A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案：C8. 命题逻辑中，若命题p和q都为真，则p∧q的真值是：A. 真B. 假C. 可能为真，也可能为假D. 无法确定答案：A9. 集合{1,2,3}的子集个数为：A. 4B. 6C. 7D. 8答案：D10. 若关系R在集合A上是自反的，则对于A中的任意元素a，有：A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案：A二、填空题（每题3分，共15分）1. 集合A={1,2,3}的幂集包含__个元素。

答案：82. 若函数f: X→Y是满射，则对于Y中的任意元素y，至少存在X中的一个元素x，使得f(x)=__。

离散数学习题答案习题一1、利用逻辑联结词把下列命题翻译成符号逻辑形式（1）他既是本片的编剧，又是导演--- P ∧ Q（2）银行利率一降低，股价随之上扬--- P → Q（3）尽管银行利率降低，股价却没有上扬--- P ∧ Q（4）占据空间的、有质量而且不断变化的对象称为物质--- M (S∧P∧T) （5）他今天不是乘火车去，就是随旅行团去了九寨沟--- P ▽ Q（6）小身体单薄，但是极少生病，并且头脑好使--- P ∧ Q ∧ R（7）不识庐山真面目，只缘身在此山中--- P → Q （解释：因为身在此山中，所以不识庐山真面目）（8）两个三角形相似，当且仅当他们的对应角相等或者对应边成比例--- S (E∨T) （9）如果一个整数能被6整除，那么它就能被2和3整除。

如果一个整数能被3整除，那么它的各位数字之和也能被3整除解：设 P –一个整数能被6整除Q –一个整数能被2整除 R –一个整数能被3整除S –一个整数各位数字之和能被3整除翻译为：（P →（Q ∧ R））∧（R → S）2、判别下面各语句是否命题，如果是命题，说出它的真值（1）BASIC语言是最完美的程序设计语言--- Y，T/F（2）这件事大概是小王干的--- N（3）x2 = 64 --- N（4）可导的实函数都是连续函数--- Y，T/F（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利 --- N（6）客观规律是不以人们意志为转移的--- Y，T（7）到2020年，中国的国民生产总值将赶上和超过美国--- Y，N/A（8）凡事都有例外--- Y，F3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式（1）（P ∨（～P ∧ Q））→ Q解：P Q ～P ∧ Q P ∨（～P ∧ Q）（P ∨（～P ∧ Q））→ Q 可满足式0 0 0 0 10 1 1 1 11 0 0 1 01 1 0 1 14、利用真值表方法验证下列各式为永真式（1）~（8）略5、证明下列各等价式（3）P→（Q∨ R）（P → Q）∨（P → R）证明：左式～P∨Q∨ R⇔～P∨Q∨～P∨ R⇔（～P∨Q）∨（～P∨ R）⇔（P → Q）∨（P → R）右式（4）（P∧ Q）∨（R∧ Q）∨（R∧ P）（P∨ Q）∧（R∨ Q）∧（R∨ P）证明：左式(（P∨R）∧ Q）∨（R∧ P）⇔(（P∨R）∨R) ) ∧(（P∨R）∨P) ) ∧（Q∨R）∧（Q∨P）（P∨ Q）∧（R∨ Q）∧（R∨ P）右式6、如果P∨ Q Q∨R,能否断定 P R ？如果P∧ Q Q∧R，能否断定 P R？如果～P ～R，能否断定 P R？解：（1）如果P∨ Q Q∨R，不能判断P R，因为如果 Q = P∨ R, 那么P∨ Q P∨P∨ R Q∨R，但P可以不等价于R.（2）如果P∧ Q Q∧R，不能判断P R，因为如果 Q = P∧ R, 那么P∧ Q P∧P∧ R Q∧R，但P可以不等价于R.（3）如果～P ～R，那么有P R，因为～P ～R，则～P <-> ～R为永真式，及有P <-> R为永真式，所以P R.8、把下列各式用↑等价表示出来（1）(P∧Q) ∨～P解：原式 ((P↑Q) ↑ (P↑Q)) ∨(P↑P)(((P↑Q) ↑ (P↑Q)) ↑((P↑Q) ↑ (P↑Q))) ↑((P↑P) ↑(P↑P))9、证明：{ ～→}是最小功能完备集合证明: 因为{～, ∨}是最小功能完备集合,所以,如果{ ～→}能表示出∨,则其是功能完备集合。