华南理工网络教育学院-离散数学试题A

华南理工大学网络教育学院2019–2020学年度第一学期《离散数学》作业1、用推理规则证明Q，⌝P → R，P → S，⌝ S⇒Q∧R证（1）P → S P（2）⌝ S P（3）⌝P（1）（2）拒取式（4）⌝P → R P（5）R （3）（4）假言推理（6）Q P（7）Q∧R（5）（6）合取2、用推理规则证明⌝（P∧⌝Q），⌝Q∨R，⌝ R⇒⌝P证（1）⌝Q∨R P（2）⌝ R P（3）⌝Q（1）（2）析取三段论（4）⌝（P∧⌝Q）P（5）⌝P ∨ Q （4）等价转换（6）⌝P （3）（5）析取三段论3．设命题公式为⌝Q∧（P→Q）→⌝P。

（1）求此命题公式的真值表；解（1）真值表如下P Q ⌝Q P→Q ⌝Q∧（P→Q）⌝P⌝Q∧（P→Q）→⌝P0 0 1 1 1 1 10 1 0 1 0 1 11 0 1 0 0 0 11 1 0 1 0 0 1（2）求此命题公式的析取范式；解：⌝Q∧（P→Q）→⌝P⇔⌝（⌝Q∧（⌝P∨Q））∨⌝P⇔（Q∨⌝（⌝P∨Q））∨⌝P⇔⌝（⌝P∨Q）∨（Q∨⌝P）⇔1（析取范式）⇔（⌝P∧⌝Q）∨（⌝P∧Q）∨（P∧⌝Q）∨（P∧Q）（主析取范式）（3）判断该命题公式的类型。

解：该公式为重言式4．在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。

每个人或者喜欢坐汽车或者喜欢骑自行车。

有的人不喜欢骑自行车。

因而有的人不喜欢步行。

令F(x)：x喜欢步行。

G(x)：x喜欢坐汽车。

H(x)：x喜欢骑自行车。

解：前提是：∀x（F（x）→⌝ G（x）），∀x（G（x）∨H（x）），∃ x⌝ H（x）。

结论：∃ x ⌝F（x）。

证(1)∃ x ⌝H（x）P(2)⌝H（c）ES(1)(3)∀x（G（x）∨H（x））P(4) G（c）∨H（c）US(3)(5) G（c）T(2，4)I(6)∀x（F（x）→⌝ G（x））P(7)F（c）→⌝ G（c）US(6)(8)⌝ F（c）T(5,7)I(9)（∃x）⌝ F（x）EG(8)5．用直接证法证明：前提：（∀x）（C（x）→W（x）∧R（x）），（∃x）（C（x）∧Q（x））结论：（∃x）（Q（x）∧R（x））。

第一章命题逻辑1.1命题与联结词一、单项选择题1、A .明年“五一”是晴天 B .这朵花多好看呀!C.这个男孩真勇敢啊! D .明天下午有会吗?在上面句子中，是命题的是2. A . 1 + 101 = 110 •中国人民是伟大的。

C.这朵花多好看呀! 计算机机房有空位吗? 在上面句子中，是命题的是3. A .如果天气好，那么我去散步。

B •天气多好呀!C.x=3。

•明天下午有会吗?在上面句子中（）是命题下面的命题不是简单命题的是4.A. 3是素数或4是素数）.2018年元旦下大雪C. 刘宏与魏新是同学•圆的面积等于半径的平方与之积5. 下面的表述与众不一致的一个是A. P :广州是一个大城市（）.P:广州是一个不大的城市C.6 .设，P:他聪明；Q:他用功。

在命题逻辑中，命题：“他既聪明又用功。

”可符号化为：（）A. P Q B . P QC. P Q D . P Q7.设：P :刘平聪明。

Q刘平用功。

在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：（）A. P Q B . P QC. P Q D . P Q&设：P:他聪明；Q:他用功。

则命题“他虽聪明但不用功。

”在命题逻辑中可符号化为()A. P Q B . P QC. P Q D . P Q9 .设：P:我们划船。

Q：我们跑步。

在命题逻辑中，命题：“我们不能既划船又跑步。

”可符号化为：（）A. P Q B . (P QC. P Q D . P Q10 .设: P：王强身体很好；Q:王强成绩很好。

命题“王强身体很好化为（)A. P Q B . P QC. P Q D . P QP :广州是一个很不小的城市D. P:广州不是一个大城市11 .设：P：你努力；Q你失败。

则命题“除非你努力，否则你将失败，成绩也很好。

”在命题逻辑中可符号在命题逻辑中可符号化为（）A. Q P B . P QC. P Q D . Q P12 .设：p：派小王去开会。

第六章特殊图论6.1 二部图（含补充的欧拉图与哈密尔顿图）一、单项选择题1 •下列说法不对的是（）A.欧拉图可以一笔画成，图要一笔画成则一定要是欧拉图B.欧拉路经过每条边一次且仅有一次，经过的节点可多次C.汉密尔顿路经过每个节点一次且仅一次，经过的边可多次D.当且仅当简单图的闭包是汉密顿图时，这个简单图是汉密顿图2.下列说法不对的是（）A.无向图为欧拉路则其奇数度节点可以是一个B.—个图是欧拉图当且仅当它连通且均为偶数度节点C.当一个图每一对节点的度数之和都大于或等于节点数减一，就有汉密尔顿路D.若一个图G V,E , S V, S ，G含有汉密尔顿路，则W G S S3.下列为欧拉图的是（）4．在下列关于图论的命题中，为真的命题是( )A.完全二部图Kn, m (n 1, m 1)是欧拉图B.欧拉图一定是哈密尔顿图C.无向完全图Kn (n 3)都是欧拉图D.无向完全图Kn ( n 3)都是哈密尔顿图5.在下列关于图论的命题中，为假的命题是( )A.完全二部图Kn, m (n , m 为非零正偶数)是欧拉图B.哈密尔顿图一定是欧拉图C.有向完全图Kn (n 2)都是欧拉图D.无向完全图Kn ( n 3且为奇数)都是欧拉图6.在下列关于图论的命题中，为假的命题是( )A. n =m 且大于1 时，完全二部图Kn, m 是哈密尔顿图B.强连通的有向图都是哈密尔顿图C.完全二部图Kn, m （n , m 为非零正偶数）的欧拉回路含mn条边D.无向完全图K2n（n 2）至少加n条边才能成为欧拉图6.2平面图一、单项选择题1 •下列说法不对的是（）A.—个有限平面图的次数之和等于边数的两倍B.平面图G的节点数为v,面数为r，边数为e,则有v-e+r=2C. G是一个V个节点，e条边的连通简单平面图，则V 3 e 3v 6D. —个图是平面图，当且仅当他不含有与K3,3或K5在2度节点内同构子图2.下列各图为平面图的是（）3•设G为任意的连通的平面图，且G有n个顶点，m条边，r个面，则平面图的欧拉公式为（）A. n - m + r = 2 B . m - n + r = 2C.n + m - r =2 D . r + n + m = 26.3树与有向树一、单项选择题1•下列不能作为一棵树的度数列的一组数是（）A. 1,1,2,2,3,3,4,4 B . 1,1,1,1,2,2,3,3C. 1,1,1,2,2,2,2,3 D . 1,1,1,1,2,2,2,3,32.在下列关于图论的命题中，为假的命题是（）A. 6阶连通无向图至少有6棵生成树B. n阶m条边的无向连通图，对应它的生成树，至少有m-n+1条基本回路C.高为h的正则二叉树至少有h+1片树叶D.波兰符号法的运算规则是每个运算符与它前面紧邻的两个数进行运算3•下列四个图中与其余三个图不同构的图是（）A ．15B ．14C ．17D ．11（Kruskal 算法） 求一棵最小生成树并计算它的权值为1） 2） （3） （4） 出 图 G 的一棵生成树为（ )A ． { (1, 2), (1, 3),( 2, 4) ,( 3, 5) }B ．{ (1, 2), (1, 3),( 2, 3) ,(2, 4) }C ．{ (1, 2), (1, 3),( 3, 5) ,( 4, 5) }D ． { (1, 2), ( 3, 4),( 3, 5) ,( 4, 5) }5． 如 图所 示带权 图, 用避 圈法 (Krus k al 算法） 求一棵最小生成树并计算它的权值为（ ）4．给定无孤立点无向图 G 的边集：{ (1 , 2), (1, 3) , (2, 3), ( 2, 4) , (2, 5), ( 3, 4), (3, 5) },找 6．如图所示带权图,用避圈法A. 15 B . 16 C . 17 D . 197 •求带权图G 的最小生成树，并计算它的权值为 （） A. 10 B . 15 C .7 D . 98给定权为 2, 6， 3，8，4;则该二叉树的权为（）A. 51 B . 63 C .48 D .7218•给定权为 1，9, 4，7, 3; 构造一颗最优二叉树，则该二叉树的权为 （）A. 31 B . 45 C .51 D .569.给定权为 2, 6， 5, 9, 4, 1 ;构造一颗最优二叉树，则该二叉树的权为 （）A. 48 B . 51 C .55 D .6410•给定权为 3，4, 5, 6, 7, 8, 9;构造一棵最优二叉树，则该二叉树的权为（）A. 96 B . 85 C .120 D .116答案：6.1、单项选择题- 1、A 2、A 3 、（4） 4、D 5、B 6、B6.2、单项选择题- 1、B 2、(3) 3、A6.3、单项选择题 1、A 2、D 3、( 3) 4、A 5、D 6、A 7、C 8、A 8、C 9、D 10、D。

华理离散数学试题及答案一、单项选择题（每题2分，共10分）1. 在离散数学中，以下哪个概念是用来描述两个集合之间元素的对应关系的？A. 函数B. 映射C. 序列D. 集合答案：A2. 命题逻辑中，以下哪个符号表示逻辑“与”？A. ∧B. ∨C. →D. ¬答案：A3. 集合{1, 2, 3}和{3, 4, 5}的交集是什么？A. {1, 2}B. {3, 4}C. {3}D. {1, 2, 3, 4, 5}答案：C4. 以下哪个图是无向图？A. 有向图B. 无向图C. 完全图D. 部分图答案：B5. 在图论中，一个图的度是指什么？A. 顶点的数量B. 边的数量C. 顶点的度数D. 图的连通性答案：C二、填空题（每题2分，共10分）1. 在集合论中，空集用符号____表示。

答案：∅2. 如果A和B是两个集合，那么A和B的并集用符号____表示。

答案：A∪B3. 逻辑运算中的否定运算符用符号____表示。

答案：¬4. 在图论中，如果一个图的任意两个顶点都可以通过路径相连，则称这个图为____图。

答案：连通5. 一个有n个顶点的完全图，其边的数量为____。

答案：\(\frac{n(n-1)}{2}\)三、简答题（每题5分，共20分）1. 请解释什么是二元关系，并给出一个例子。

答案：二元关系是集合A和集合B之间的一种对应关系，它由有序对(a, b)组成，其中a属于A，b属于B。

例如，如果A是人名集合，B是年龄集合，那么“小于”就是一个二元关系。

2. 什么是归纳推理？请给出一个简单的例子。

答案：归纳推理是一种从特殊到一般的推理方法，它通过观察一系列具体实例来推断出一个普遍的结论。

例如，观察到太阳每天从东方升起，我们归纳出“太阳每天都会从东方升起”。

3. 什么是图的生成树？请简述其特点。

答案：图的生成树是包含图中所有顶点的子图，并且是一个树。

它的特点是没有环，并且任意两个顶点之间有且仅有一条路径。

华南理工网络教育学院离散数学试题A一、选择题1、在下列命题中，不是命题的是（）A.这是一个苹果B.今天是星期一C.苏州在南京的南边D.明天会下雨吗？E.所有猫都是动物2、下列命题中，真命题是（）A.如果a>b，那么ac>bcB.如果a>b，c>d，那么a+c>b+dC.如果a>b>0，c>d>0，那么ac>bdD.如果a>b>0，那么对任意实数c，ac>bc3、下列命题中，假命题是（）A.如果一个命题的逆命题是真命题，那么这个命题是假命题B.如果一个命题的否命题是假命题，那么这个命题是真命题C.如果一个命题的逆否命题是假命题，那么这个命题是假命题D.如果一个命题的否命题是真命题，那么这个命题是真命题二、填空题1、填空题中的空档里，请按照数学表达式的正确格式填写答案。

设A和B是两个集合，用符号表示它们之间的关系，相交关系为 A ∩B，全集为 U，则 A的补集表示为 A'。

2、如果一个命题的逆命题是真命题，那么这个命题是____________。

3、如果一个命题的否命题是假命题，那么这个命题____________。

4、如果一个命题的逆否命题是假命题，那么这个命题是____________。

5、在下列各小题中，选择一个适当的答案填入空格内。

（1）如果a>b>0，那么对任意实数c，ac________bc；（2）如果a>b>0，c>d>0，那么ac________bd；（3）如果a>b>0，那么对任意实数c，ac________bc；（4）如果a>b>0，那么对任意实数c，ac________bc。

答案：（1）> （2）> （3）> （4）<解析：根据不等式的性质进行判断。

6、下列各小题中，选择一个适当的答案填入空格内。

（1）如果a<b<0，那么对任意实数c，ac________bc；（2）如果a<b<0，c<d<0，那么ac________bd；（3）如果a<b<0，那么对任意实数c，ac________bc；（4）如果a<b<0，那么对任意实数c，ac________bc。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1)设：p：派小王去开会。

q：派小李去开会.则命题：“派小王或小李中的一人去开会" 可符号化为：（p q) (p q）。

（2）设A,B都是命题公式，A B，则A B的真值是T。

（3）设:p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p q .（4）设A , B 代表任意的命题公式，则蕴涵等值式为A B A B。

（5）设，p：径一事;q：长一智。

在命题逻辑中,命题:“不径一事，不长一智。

" 可符号化为： p q 。

（6）设A , B 代表任意的命题公式，则德摩根律为（A B）Û A B）。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。

”可符号化为: （p q）（p q） .（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题:“他既聪明又用功。

" 可符号化为：P Q .（9）对于命题公式A,B,当且仅当 A B 是重言式时，称“A蕴含B”，并记为A B。

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:“我们不能既划船又跑步.”可符号化为：（P Q) 。

（11）设P，Q是命题公式,德·摩根律为：（P Q）P Q) 。

（12）设P:你努力.Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：P Q .（13）设p：小王是100米赛跑冠军。

q:小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军.”可符号化为：p q。

（14）设A，C为两个命题公式，当且仅当A C为一重言式时,称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A B A B。

（）2.命题公式p q r是析取范式。

( √ )3.陈述句“x + y > 5”是命题。

华南理工大学网络教育学院2010– 2011学年度第二学期期末考试《离散数学》教学中心：专业层次：学号：姓名：座号：注意事项：1. 本试卷共八大题，满分100分，考试时间120分钟，闭卷；2. 考前请将以上各项信息填写清楚；3. 所有答案直接做在试卷上,做在草稿纸上无效；一．填空：(20分)1．设P：他诚实；Q：他好学。

在命题逻辑中，命题：“他既诚实又好学。

”可符号化为：。

2．设M(x)：x是人；P(x)：x会用C++语言编写程序。

在谓词逻辑中，命题：“有人会用C++语言编写程序，但不是所有人都会用C++语言编写程序。

”可符号化为：。

3．设A和C是两个命题公式，当且仅当为一重言式时，称C是A的有效结论。

4．设集合A={1, 2, 3 }，B={ a, b }，则A×B＝___________________________________________________。

5．设R为定义在集合X上的二元关系，如果对于每个x, y X，______ ____ ____________ ，则称集合X上的关系R是对称的。

6．设关系R和S为，R={<1，2>，<3，4>，<2，2>}，S={<4，2>，<2，5>，<3，1>，<1，3>}，则R◦S =______ ___ __ ________________。

7．含有__ ___ __ ___的半群称为独异点。

8．集合A的幂集P(A)关于集合的并运算“∪”的么元为_____________。

9．给定图G，若存在一条回路，经过图中的___________________恰好一次，称这条回路为哈密顿回路。

10．一棵有m条边的树含有______________________结点。

二．判断下列命题的对错。

正确的在括号内填√,错误的在括号内填×。

(10分)1.“请注意听讲！”是命题。

离散数学考试题目及答案一、单项选择题（每题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)=__。

《离散数学》期末考试考点及模拟题答案一、考试题型及分值各种题型所占的比例：填空题10%,判断题10%,选择题20%,其它题型60%新出试卷按照如下各种题型所占的比例：填空题20%，判断题15%，选择题30%，其它题型35%二、考点1.命题逻辑熟练掌握命题及其表示；掌握常用联结词（「、八、V、f、）的使用；熟练掌握命题公式的符号化；熟练掌握使用真值表判别命题等价的方法；掌握使用等价公式判别命题等价的方法；掌握重言式与蕴含式的概念及其判别方法;了解其他联结词的使用；了解对偶的概念；掌握求命题范式的方法；熟练掌握命题演算推理的基本理论.2.谓词逻辑熟练掌握谓词的概念及其表示；熟练掌握量词的使用；掌握使用谓词公式翻译命题的方法；掌握变元的约束；掌握谓词演算中等价式与蕴含式的判别;了解前束范式的求法；熟练掌握谓词演算推理的基本理论.3.集合与关系熟练掌握集合的概念和表示法；掌握集合的基本运算；掌握序偶与笛卡尔积的概念；熟练掌握关系及其表示；掌握关系的基本性质；了解复合关系和逆关系的概念；掌握关系的闭包运算；了解集合的划分和覆盖；掌握等价关系与等价类的概念;了解相容关系的概念；掌握各种序关系的概念.4.函数熟练掌握函数的概念；掌握逆函数和复合函数的概念；了解基数的概念；了解可数集与不可数集；了解基数的比较.5.代数结构掌握代数系统的概念；掌握n元运算及其性质；掌握半群、群与子群的概念;了解阿贝尔群和循环群的概念；了解陪集与拉格朗日定理;了解同构与同态的概念；了解环与域的概念.6.图论掌握图的基本概念；掌握路与回路的概念；熟练掌握图的矩阵表示；掌握欧拉图和哈密顿图的概念；掌握平面图的概念；了解对偶图与着色；熟练掌握树与生成树的概念;了解根树及其应用.（一）参考教材与网上资料复习（二）随堂练习或作业题在在新出试卷里有较大比例提高三、模拟试卷附后（请参考学习资料，找到或者做出解答）一、考试对象计算机学科中计算机科学与技术、软件工程等专业本科生二、考试的性质、目的离散数学是随着计算机科学的发展而逐渐形成的一门学科，是近代数学的一个分支在计算机科学中，它主要应用于数据结构、操作系统、编译原理、数据库理论、形式语言与自动机、程序理论、编码理论、人工智能、数字系统逻辑设计等方面它是计算机科学各专业重要的专业基础课.本课程教学的目标是:①使学生掌握离散数学的基本理论和基本知识，为学习有关课程以及今后工作打好基础.②培养和提高学生的抽象思维与逻辑推理能力.四、考试方式及时间：考试方式：闭卷考试时间：120分钟五、课程综合评定办法1期末闭卷考试：占总成绩60%.2、平时成绩（作业、考勤情况等）：占总成绩40%3、试题难易程度：基础试题：中等难度试题：较难试题：难度较大的试题 =4： 3： 2： 1六、考试教材《离散数学》左孝凌、李为^、刘永才编著，上海科学技术文献出版社附：模拟试卷华南理工大学网络教育学院2012 - 2013学年度第一学期期末考试《离散数学》试卷(模拟卷)教学中心：专业层次：学号：姓名：座号：注意事项：1.本试卷共五大题，满分100分，考试时间120分钟，闭卷;2.考前请将以上各项信息填写清楚；3.所有答案直接做在试卷上,做在草稿纸上无效；4.考试结束，试卷、草稿纸一并交回.一.判断题(每题2分，共10分)1、设A, B都是合式公式，则A A B F「B也是合式公式.(J)2. P f Q o「P v Q ,(v)3、对谓词公式(V x) (P (y) V Q (x,y)) △R (x,y)中的自由变元进行代入后得到公lllllll !lllll式(V x) (P (z) V Q (x,z)) △R (x,y) . (x)4.对任意集合 A、B、C,有(A—B) —C = (A—C) - (B—C). (j)5. 一个结点到另一个结点可达或相互可达. (X )二.单项选择题(每题2分，共20分)1.设：。

2020-2021《离散数学》期末课程考试试卷A2专业: 考试日期： 所需时间：120分钟 总分：100分 闭卷 一、选择题（每小题3分，总共30分）1、设P ：我们划船，Q ：我们跑步。

命题“我们不能既划船又跑步”符号化为（ ）A 、Q P ⌝∧⌝B 、Q P ⌝∨⌝C 、)(Q P ↔⌝D 、)(Q P ⌝↔ 2、下列语句中哪个是真命题？（ ）A 、我正在说谎。

B 、严禁吸烟C 、如果1+2=3，那么雪是黑的。

D 、如果1+2=5，那么雪是黑的。

3、命题公式Q Q P P →→∧))((是（ ）A 、矛盾式B 、蕴含式C 、重言式D 、等值式4、谓词公式)())()((x Q y yR x P x →∃∨∀中变元x 是（ ） A 、自由变量 B 、约束变量 C 、既不是自由变量也不是约束变量 D 、既是自由变量也是约束变量5、若个体域为整数域，下列公式中哪个值为真？（ ）A 、)0(=+∃∀y x y xB 、)0(=+∀∃y x x yC 、)0(=+∀∀y x y xD 、)0(=+∃⌝∃y x y x6、设个体域A={a,b},公式)()(x xS x xP ∃∧∀在A 中消去量词应为（ ） A 、)()(x S x P ∧ B 、))()(()()(b S a S b P a P ∨∧∧ C 、)()(b S a P ∧ D 、)()()()(b S a S b P a P ∨∧∧8、设A={{1，2，3}，{4，5}，{6，7，8}}，下列正确的是（ ） A 、1∈A B 、{1，2，3}⊆A C 、{{4，5}}⊂A D 、Φ∈A 9、幂集P （P （P （Φ）））为（ ）A 、{{Φ}，{Φ，{Φ}}}B 、{Φ，{Φ}，{Φ，{Φ}}}C 、{Φ，{Φ}，{Φ，{Φ}}，{{Φ}}}D 、{Φ，{Φ，{Φ}}}10、任意一个具有多个等幂元的半群，它（ ）A 、不能构成群B 、不一定能构成群C 、能构成群D 、不能构成交换群 二、填空题（每小题2分，总共16分）1、对于前提：S Q ⌝→，S ∨R ，R ⌝，Q P ↔⌝，其有效结论为2、谓词公式)()()(y yR x xQ x xP ∃∨∀→∀的前束范式为3、设集合A={x|x <3,x ∈Z},B={x|x=2k,k ∈Z} C={1,2,3,4,5},则 A ⊕（C-B ）=4、某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，其中只有3人同时参加3种球队，则仅仅参加两种球队的队员为 人 。

3 2 1 ,考试作弊将带来严重后果！ 华南理工大学期末考试 《Discrete Mathematics 》 ： 1. 考前请将密封线内填写清楚； 所有答案请直接答在答题纸上； ．考试形式：闭卷； 本试卷共4 大题，满分100分， 考试时间120分钟。

． Choose an answer to the following question. (10 x 2’ = 20’) ) B) x > 1.5 D) Help me. is true for all possible assignments of truth values to p q except for which assignment?( ) ）p false, q true B ）p true, q false ）p false, q false D ）p true, q true “No Computer Major is taking any courses ” where C(x) is the statement x is a Computer ) A ） B ） C ） D ） (4) Function f is defined as x x x f Z Z f 2)(,:-=→, so f is ( ) A ）onto B ） both onto and one-to-one C ）one-to-one D ） neither onto nor one-to-one (5) Supposed a binary relation R (Figure 1) on the set A = { 1, 2, 3 }, R is ( ) A) irreflexive, symmetric, non-transitive B) reflexive, antisymmetric, transitive C) irreflexive, antisymmetric, transitive Figure 1. D) reflexive, antisymmetric, non-transitive (6) Which of these arguments is true?( ) A) (P(S), subset of ) is a poset and also total ordered B) (Z +,|) is totally orderedC) The divisibility relation(可整除) “ | ” is a partial ordering on the set of positive integers.(Z+,|) is a poset.D) (N, >=) is well-ordered(7) (A⋃B)-C= ( )A) (A – C) ⋃ B B) (A-C)⋃(B-C)C) A – (B⋃C) D) (A-C)∩(B-C)(8) Which statement is correct?（）A) There are 2n 1s and n (n-2) 0s in the adjacency matrix for C n.B) C n is always bipartite .C) Q n has n2n edges and 2n vertices.D) K n has n (n+1)/2 edges and n vertices.(9) How many planar graphs in the following graphs? ( )A) 4 B) 3 C) 2 D) 1(10) Which statement is wrong? ( )A. If a directed graph is strongly connected, it must be an Euler graph.B. A graph with cut edge cannot be an Euler graph.C. If a graph is an Euler graph, it must be a strongly connected graph.D. A graph with cut vertex cannot be a Hamilton graph.2．Fill in the blanks. (10 x 2’ = 20’)(1) If p→q is true, the truth value of p∧q →q is(2) Let C(x): x is a computer. D(x): x is a peripheral equipment. P(x, y): x can communicate with y. Express the sentence “some computers can’t communicate with some peripheral equipment” as a logical expression as______________.(3) Let l be “Lois works late”, let j be “John works late”, and let e be “they willeat at home ”. Express the statement “If Lois or John do not work late, then they will eat at home ”__________________(4)A={ l ，m ，n }，B={ a ，b ，c }，C={ x ，y ，z }. R ：A→B ，S ：B→C ，and R={ <l ，b>，<m ，a >，<n ，c> }, S={< a ，y>，<b ，x> ，<c ，y>，<c ，z>}， SоR =______________.(5) A = { ∅, {∅}}, )(A ρ i s t h e p o w e r s e t o f A . )(A ρ=______________.(6) R is the real number domain. For x R ∀∈, ()2f x x =+, ()2g x x =- and ()3h x x =. Hence, ()h g f = _______________.(7) R is “ more than or equal to ” relation on Z ×Z ，then R -1=________.(8) R is the relation “brother or sister ”, xRy represents “x is the brother or sister of y ”, ① irreflexive ② reflexive ③ symmetric ④antisymmetric ⑤ transitive. R has the properties _____.(9) The complete bipartite graph K m, n has ____ cut edges.(10) The sum of the weights of the minimum spanning tree forthe graph in the right hand side is _____.3. Computation and Analysis. (6 x 6’ = 36’)(1) Prove the equivalence of predicate:()()(()())()()()()x y P x Q y x P x y Q y ∀∀→⇔∃→∀(2) Given the premises ⌝A ∨B, ⌝C →⌝B, C →D, how to get the conclusion A →D?(3) Suppose A = {a , b, c, d}, a relation on A is R = {<a, b>, <b, a>, <b, c>, <c, d>}. Please use the zero-one matrix to find the transitive closure of R.0100101000010000R M ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦(4)Can the following graph be drawn in one stroke ? Why ?(5) Find out whether G and H are isomorphic. No matter what the judgment is, please give your explanation and argument.(6) Use the ordered rooted tree to represent the expression ((3*x-5*(y↑2))↑5)/(a*((b↑3)-4*c))4.Application of Discrete Mathematics. (4 x 6’ = 30’)(1)Use inference to obtain conclusion from the premises.All the people who like walking do not like driving. Every person likes driving or riding. Some people don’t like riding. Therefore, some people don’t like walking.(2)Suppose R is a reflexive and transitive relation on A. T is also a relation on A, such that:<a，b>∈T <a，b>∈R and <b，a>∈RProve that T is an equivalence relation.(3) 6 people are supposed to accomplish 3 tasks in groups (2 people in one group). The people in the same group should cooperate with each other to accomplish the task. We now know each person could cooperate with at least other 3 people. Is that possible that all the tasks could be accomplished?(4) The roads represented by this graph are all unpaved. The lengths of the roads between pairs of towns are represented by edge weights. Which roads should be paved so that there is path of paved roads between each pair of town so that a minimum road length is paved?。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1）设：p：派小王去开会。

q：派小李去开会。

则命题：“派小王或小李中的一人去开会”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。

（2）设A，B都是命题公式，A⇒B，则A→B的真值是T。

（3）设：p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p∧q。

（4）设A , B 代表任意的命题公式，则蕴涵等值式为A → B⇔⌝A∨B。

（5）设，p：径一事；q：长一智。

在命题逻辑中，命题：“不径一事，不长一智。

”可符号化为：⌝ p→⌝q 。

（6）设A , B 代表任意的命题公式，则德∙摩根律为⌝（A ∧ B）⇔⌝A ∨⌝B）。

（7）设，p：选小王当班长；q：选小李当班长。

则命题：“选小王或小李中的一人当班长。

”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。

（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题：“他既聪明又用功。

”可符号化为：P∧Q 。

（9）对于命题公式A，B，当且仅当 A → B 是重言式时，称“A蕴含B”，并记为A⇒B。

（10）设：P：我们划船。

Q：我们跑步。

在命题逻辑中，命题：“我们不能既划船又跑步。

”可符号化为：⌝ (P∧Q) 。

（11）设P , Q是命题公式，德·摩根律为：⌝（P∨Q）⇔⌝P∧⌝Q）。

（12）设P：你努力。

Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：⌝P→Q。

（13）设p：小王是100米赛跑冠军。

q：小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军。

”可符号化为：p∨q。

（14）设A，C为两个命题公式，当且仅当A→C为一重言式时，称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A→B⇔⌝A∧B。

（⨯）2.命题公式⌝p∧q∧⌝r是析取范式。

（√）3.陈述句“x + y > 5”是命题。

第一章命题逻辑1.1 命题与联结词一、单项选择题1、 A．明年“五一”是晴天。

B．这朵花多好看呀！。

C．这个男孩真勇敢啊！ D．明天下午有会吗？在上面句子中，是命题的是( )2. A．1＋101＝110 B．中国人民是伟大的。

C．这朵花多好看呀！ D．计算机机房有空位吗？在上面句子中，是命题的是( )3. A．如果天气好，那么我去散步。

B．天气多好呀！C．x=3。

D．明天下午有会吗？在上面句子中( )是命题4．下面的命题不是简单命题的是( )A．3是素数或4是素数 B．2018年元旦下大雪C．刘宏与魏新是同学 D．圆的面积等于半径的平方与π之积5．下面的表述与众不一致的一个是( )A．P：广州是一个大城市 B．⌝P：广州是一个不大的城市C．⌝P：广州是一个很不小的城市 D．⌝P：广州不是一个大城市6．设，P：他聪明；Q：他用功。

在命题逻辑中，命题：“他既聪明又用功。

”可符号化为：( )A．P ∧Q B．P→QC．P∨⌝Q D．P∧⌝Q7．设：P ：刘平聪明。

Q：刘平用功。

在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：( )A．P ∧Q B．⌝P∨QC．P∨⌝Q D．P∧⌝Q8．设：P：他聪明；Q：他用功。

则命题“他虽聪明但不用功。

”在命题逻辑中可符号化为( )A．P ∧Q B．P→QC．P∨⌝Q D．P∧⌝Q9．设：P：我们划船。

Q：我们跑步。

在命题逻辑中，命题：“我们不能既划船又跑步。

”可符号化为：( )A．P→Q B．⌝（P ∧Q）C．P∨Q D．P∧⌝Q10．设：P：王强身体很好；Q：王强成绩很好。

命题“王强身体很好，成绩也很好。

”在命题逻辑中可符号化为( )A．P ∨Q B．P→QC．P∧⌝Q D．P∧Q11．设：P：你努力；Q：你失败。

则命题“除非你努力，否则你将失败。

”在命题逻辑中可符号化为( )A ．Q →PB ．P → QC ．⌝ P →QD ．Q ∨⌝P12．设：p ：派小王去开会。

《离散数学》考试试卷（试卷库14卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分考试时限：120 分钟⼀、选择题（每题2分，共20分）1. 下述命题公式中，是重⾔式的为( )（A ）)()(q p q p ∨→∧（B ）q p ∨))()((p q q p →∨→?（C ）q q p ∧→?)(（D ）q q p →?∧)(2. 对任意集合A,B,C,下列结论正确的是（）（A ）若A ?B,B ∈C,则A ?C ；（B ）若A ∈B,BC,则A ?C ；（C ）若A ?B,B ∈C,则A ∈C ；（D ）若A ∈B,B ?C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系, ,则由R 产⽣的S S ?上⼀个划分共有( )个分块。

（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是⼀棵树当且仅当G 中( )（A ）有些边是割边（B ）每条边都是割边（C ）所有边都不是割边（D ）图中存在⼀条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平⾯图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下⾯命题公式中真值为1的是（）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=中,结点总度数与边数的关系是（）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公⽤⼀个电源,则⾄少需有五插头的接线板数（）（A ）７（B ）８（C ）９（D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（）（A ）11 （B ）14 （C ）17（D ）15⼆、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。

2020-2021《离散数学》期末课程考试试卷A一、填空题（每空3分，共15分）1．命题公式)(r q p p ∨∨→的类型是 。

2．设p ：我将去镇上。

q ：我有时间。

则命题“我将去镇上，仅当我有时间。

”的符号化形式为 。

3．化简下面集合表达式：)())((C B A C A B -= 。

4．已知一有向图的D 的度序列为（2,3,2,3），出度序列为（1,2,1,1），则D 的入度序列为 。

5．5个顶点的非同构的无向树共有 棵。

二、选择题（单项选择题，每题3分，共30分）1．设命题公式)(p q p ⌝→∧，记作A ，则使A 的真值指派为1的p ，q 的取值是（ ）。

A 、00B 、 01C 、10D 、112．设p ：你努力。

q ：你将失败。

则命题“除非你努力，否则你将失败。

”符号化为（ ）。

A 、p →q B 、q →p C 、┐p →q D 、┐q →p 3．下列公式中不与)(q p ↔⌝等值的是（ ）。

A 、)()(q p q p ∨⌝∧⌝∨B 、)()(q p q p ∧⌝∨⌝∧C 、q p ↔⌝D 、q p ⌝↔4．下面公式正确的是（ ）。

A 、)()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ B 、)()())()((x xB x xA x B x A x ∃∨∃⇔∨∃C 、)())((x xB A x B A x ∃→⇔→∀D 、)()(x A x x xA ⌝∃⇔⌝∃5．下列命题错误的是（ ）。

A 、}},,{,,,{},{c b a c b a b a ⊆ B 、}},{,,,{},{b a c b a b a ∈ C 、}}},{{,,{},{b a b a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6．设R={<x,y>|x,y ∈R ，x-y+2>0且x-y-2<0}，则R 具有的性质是（ ）。

离散数学试题A卷及答案一、单项选择题（每题2分，共10分）1. 在集合{1,2,3}中，子集的个数是多少？A. 3B. 7C. 8D. 9答案：C2. 以下哪个命题是真命题？A. ∃x∈R, x^2 = -1B. ∀x∈R, x^2 ≥ 0C. ∀x∈R, x^2 = 1D. ∃x∈R, x^2 = 2答案：B3. 函数f: N → N定义为f(x) = 2x，该函数是：A. 单射B. 满射C. 双射D. 非函数答案：A4. 以下哪个逻辑表达式等价于p∧(q∨¬p)？A. p∧qB. p∨qC. ¬p∨qD. p∧¬p答案：A5. 以下哪个图是二分图？A. 完全图K5B. 完全二分图K3,3C. 环图C5D. 星形图K1,4答案：B二、填空题（每题3分，共15分）1. 若A={1,2,3}，B={2,3,4}，则A∩B=______。

答案：{2,3}2. 命题“若x>0，则x^2>0”的逆否命题是：若x^2≤0，则______。

答案：x≤03. 在一个有向图中，若存在从顶点u到顶点v的有向路径，则称v可到达u，若图中每个顶点都可到达其他所有顶点，则称该有向图是______。

答案：强连通的4. 一个集合的幂集包含该集合的所有______。

答案：子集5. 在逻辑中，合取（AND）操作符用符号______表示。

答案：∧三、解答题（每题10分，共20分）1. 证明：若A⊆B且B⊆C，则A⊆C。

证明：设x∈A，则由A⊆B，可得x∈B。

又由B⊆C，可得x∈C。

因此，A⊆C。

2. 给定一个图G，包含顶点集V={v1, v2, v3, v4}和边集E={(v1,v2), (v2, v3), (v3, v4), (v4, v1), (v1, v3), (v2, v4)}，请判断该图是否是欧拉图，并说明理由。

答案：该图是欧拉图。

因为该图是连通的，且每个顶点的度都是偶数。

结束语：本试题涵盖了离散数学中的基本概念和原理，通过这些题目的练习，可以加深对离散数学知识的理解。

华南理工大学网络教育学院2014–2015学年度第一学期《离散数学》作业（解答必须手写体上传，否则酌情扣分）1．设命题公式为?Q?（P?Q）??P。

（1）求此命题公式的真值表；（2）求此命题公式的析取范式；（3）判断该命题公式的类型。

解：（1）真值表如下：P Q ?Q P ?Q ?Q?（P?Q）?P ?Q?（P?Q）??P0 0 1 1 1 1 10 1 0 1 0 1 11 0 1 0 0 0 11 1 0 1 0 0 1（2）?Q?（P ?Q）??P??(?Q?(?P? Q)) ?? P?( Q?? (?P? Q)) ?? P ?? ( ?P? Q) ? (Q??P) ?1（析取范式）?(?P?? Q) ? (?P? Q) ? (P?? Q) ?（P? Q）（主析取范式）（3）该公式为重言式2．用直接证法证明前提：P?Q，P?R，Q?S结论：S?R解：（1）?S P(2)Q ?S P(3) ? Q (1)(2)(4)P? Q P(5)P (3)(4)(6) P ? R P(7)R (5)(6)(8)?S? R （1）（7）即SVR得证3．在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。

每个人或者喜欢坐汽车或者喜欢骑自行车。

有的人不喜欢骑自行车。

因而有的人不喜欢步行。

令F(x)：x喜欢步行。

G(x)：x喜欢坐汽车。

H(x)：x喜欢骑自行车。

解：前题：?x (F (x) →?G(x)), ?x (G (x) ?H (x))? x ?H (x)结论:? x ?F (x)证：（1）? x ?F (x) p(2) ?H (x) ES(1)(3) ?x (G (x) ?H (x)) P(4)G (c) vH (c) US(3)(5)G (c) T(2,4)I(6)?x (F (x) →?G(x)), p(7)F (c) →?G(c) US(6)(8) ?F (c) T(5,7)I(9)( ? x) ?F (x) EG(8)4．用直接证法证明：前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x））结论：（?x）（Q（x）∧R（x））。

华科离散数学试题与答案试卷离散数学试题与答案试卷一一、填空 20% (每小题2分)，+A,{x|(x,N)且(x,5)},B,{x|x,E且x,7}1(设 (N:自然数集，E 正偶A,B,数) 则。

2(A，B，C表示三个集合，文图中阴影部分的集合表达式为。

A B C 3(设P，Q 的真值为0，R，S的真值为1，则，(P,(Q,(R,，P))),(R,，S)的真值= 。

(P,R),(S,R),，P4(公式的主合取范式为。

，xP(x),,xP(x)5(若解释I的论域D仅包含一个元素，则在I下真值为。

6(设A={1，2，3，4}，A上关系图为2则 R = 。

7(设A={a，b，c，d}，其上偏序关系R的哈斯图为则 R= 。

8(图的补图为。

9(设A={a，b，c，d} ，A上二元运算如下:* a b c da abc db bcd ac cd a bd d a b c 那么代数系统<A，*>的幺元是，有逆元的元素为，它们的逆元分别为。

10(下图所示的偏序集中，是格的为。

二、选择 20%(每小题 2分)1、下列是真命题的有( ){a},{{a}}{{,}},{,,{,}}A( ; B(;,,{{,},,}{,},{{,}}C( ; D( 。

2、下列集合中相等的有( ),,,, A({4，3};B({，3，4};C({4，，3，3};D( {3，4}。

3、设A={1，2，3}，则A上的二元关系有( )个。

2，23，33 2 32 A( 2;B( 3;C( ; D( 。

4、设R，S是集合A上的关系，则下列说法正确的是( )R,S A(若R，S 是自反的，则是自反的;R,S B(若R，S 是反自反的，则是反自反的;R,S C(若R，S 是对称的，则是对称的;R,S D(若R，S 是传递的，则是传递的。

5、设A={1，2，3，4}，P(A)(A的幂集)上规定二元系如下R,{,s,t,|s,t,p(A),(|s|,|t|}则P(A)/ R=( )A(A ;B(P(A) ;C({{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}};,D({{}，{2}，{2，3}，{{2，3，4}}，{A}},,6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为( )7、下列函数是双射的为( ),,，A(f : IE , f (x) = 2x ; B(f : NNN, f (n) = <n , n+1> ;,,C(f : RI , f (x) = [x] ; D(f :IN, f (x) = | x | 。