19春华南理工《离散数学》随堂练习答案

离散数学课后习题及答案离散数学是计算机科学与数学的重要基础课程之一，它涵盖了很多重要的概念和理论。

为了更好地掌握离散数学的知识，课后习题是必不可少的一部分。

本文将介绍一些常见的离散数学课后习题，并提供相应的答案，希望对读者有所帮助。

一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}2. 设A={1,2,3}，B={2,3,4}，C={3,4,5}，求(A∪B)∩C的结果。

答案：(A∪B)∩C={3,4}二、逻辑与命题1. 判断下列命题的真假：a) 若2+2=5，则地球是平的。

b) 若今天下雨，则我会带伞。

c) 若x>0，则x^2>0。

答案：a)假，b)真，c)真。

2. 用真值表验证下列命题的等价性：a) p∧(q∨r) ≡ (p∧q)∨(p∧r)b) p→q ≡ ¬p∨q答案：a)等价，b)等价。

三、关系与函数1. 给定关系R={(1,2),(2,3),(3,4)}，求R的逆关系R^-1。

答案：R^-1={(2,1),(3,2),(4,3)}2. 设函数f(x)=x^2，g(x)=2x+1，求复合函数f(g(x))的表达式。

答案：f(g(x))=(2x+1)^2=4x^2+4x+1四、图论1. 给定图G，其邻接矩阵为：0 1 11 0 11 1 0求图G的度数序列。

答案：度数序列为(2,2,2)2. 判断下列图是否为连通图：a) G1的邻接矩阵为：0 1 11 0 01 0 0b) G2的邻接矩阵为：0 1 01 0 10 1 0答案：a)不是连通图，b)是连通图。

五、组合数学1. 从10个不同的球中，任选3个，求共有多少种选法。

答案：C(10,3)=120种选法。

2. 求下列排列的循环节：a) (123)(45)(67)b) (12)(34)(56)(78)答案：a)循环节为(123)(45)(67)，b)循环节为(12)(34)(56)(78)。

华南理工大学网络教育学院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））。

华理离散数学试题及答案一、单项选择题（每题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. 什么是图的生成树？请简述其特点。

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

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

《离散数学》练习题一答案一、单项选择题（每小题2分，共8分） 1—5 . D C B C C 6—10 ． A B D C A11—15 C B C D A 16—20 C C B D C 21—25 C C B D C 26—30. D C B A D 31. C二、填空题（每空1分，共11分）1． nn 2． P 、Q 的真值同时为1 3.4. 奇5. 126. Q P ⌝∧7. 9 8．Q P ⌝→ 9．P ,Q 的真值都为010.D B C A ⊆⊆ , 11. 0 12. c b =13. 14 14. c 15. P Q ↔ 或 Q P ↔ 16. b 17. 假 18. 219. 17 20. 0 21. 有余(补)分配格 22. 假 23. 2 24. 17 25. 0 26. 有余(补)分配格 27. ()()Q P Q P ⌝∧∨∧⌝28.{}d d a b b a a c a d c b a b b a , , , , , , , , , , , , , , ,, ，29.⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=100000010000101000110100101010111101R M30. 7 31.1968339=三、解答题（共81分）3.(10分)设G 是平面图，有n 个顶点，m 条边，f 个面，k 个连通分支，证明：1+=+-k f m n 。

证明：对于图G 的每个连通分支都是连通平面图，因此由欧拉公式，有2111=+-f m n 2222=+-f m n… …2=+-k k k f m n其中i i i f m n , , 分别是第i 个连通分支中的顶点数、边数和面数，则1 , , 212121-+=+++=+++=+++k f f f f m m m m n n n n k k k将上述k 个等式相加，有k k f m n 21=-++-，即1+=+-k f m n4.(8分)化简下列布尔表达式。

19春华南理工《离散数学》随堂练习答案第一章命题逻辑·第一节命题与联结词当前页有10题，你已做10题，已提交10题，其中答对10题。

1.(单选题) 在下面句子中，是命题的是( )A．明年“五一”是晴天。

B．这朵花多好看呀！。

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

C．这朵花多好看呀！ D．计算机机房有空位吗？参考答案：B3.(单选题) 在下面句子中( )是命题A．如果天气好，那么我去散步。

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

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

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

”可符号化为：( )参考答案：A7.(单选题) 设：P ：刘平聪明。

Q：刘平用功。

在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：( )8.(单选题) 设：P：他聪明；Q：他用功。

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

”在命题逻辑中可符号化为( )参考答案：D9.(单选题) 设：P：我们划船。

Q：我们跑步。

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

”可符号化为：( )参考答案：B10.(单选题) 设：P：王强身体很好；Q：王强成绩很好。

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

”在命题逻辑中可符号化为( ) 参考答案：D11.(单选题) 设：P：你努力；Q：你失败。

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

”在命题逻辑中可符号化为( )参考答案：C12.(单选题) 设：p：派小王去开会。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（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. 关于图论的基本概念，以下哪个说法是正确的？A. 无向图中的边无方向性，有向图中的边有方向性。

B. 有向图中的边无方向性，无向图中的边有方向性。

C. 无向图和有向图都是由顶点和边组成的。

D. 无向图和有向图都只由边组成。

答案：A2. “若顶点集合为V，边集合为E，那么图G可以表示为G(V, E)”是关于图的哪个基本概念的描述？A. 图的顶点B. 图的边C. 图的邻接D. 图的表示方法答案：D3. 以下哪个命题是正确的？A. 若集合A和B互相包含，则A和B相等。

B. 若集合A和B相交为空集，则A和B相等。

C. 若集合A和B相等，则A和B互相包含。

D. 若集合A和B相等，则A和B相交为空集。

答案：C二、填空题1. 有一个集合A = {1, 2, 3, 4}，则集合A的幂集的元素个数为__________。

答案：162. 设A = {a, b, c}，B = {c, d, e}，则集合A和B的笛卡尔积为__________。

答案：{(a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e)}3. 若p为真命题，q、r为假命题，则合取范式(p ∨ q ∨ r)的值为__________。

答案：真三、计算题1. 计算集合A = {1, 2, 3, 4}和集合B = {3, 4, 5, 6}的交集、并集和差集。

答案：交集：{3, 4}并集：{1, 2, 3, 4, 5, 6}差集：{1, 2}2. 计算下列命题的真值：(~p ∨ q) ∧ (p ∨ ~q)，其中p为真命题，q为假命题。

答案：真四、证明题证明：对于任意集合A和B，如果A和B互相包含，则A和B相等。

证明过程：假设A和B互相包含，即A包含于B且B包含于A。

设x为集合A中的任意元素，则x也必然存在于集合B中，即x属于B。

同理，对于集合B中的任意元素y，y也属于集合A。

《离散数学》课后习题答案《离散数学》简介1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。

教学方式以课堂讲授为主，课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。

《离散数学》学科内容随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。

离散数学的应用遍及现代科学技术的诸多领域。

离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。

1-1，1-2（1） 解：a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) P→┓Q（4） 解：a)设Q:我将去参加舞会。

R:我有时间。

P:天下雨。

Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。

b)设R:我在看电视。

Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c) 设Q:一个数是奇数。

R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5) 解：a) 设P：王强身体很好。

Q：王强成绩很好。

P∧Qb) 设P：小李看书。

Q：小李听音乐。

P∧Qc) 设P：气候很好。

Q：气候很热。

P∨Qd) 设P： a和b是偶数。

Q：a+b是偶数。

P→Qe) 设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

PQf) 设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a) P:天气炎热。

Q:正在下雨。

P∧Qb) P:天气炎热。

R:湿度较低。

P∧Rc) R:天正在下雨。

S:湿度很高。

R∨Sd) A:刘英上山。

B:李进上山。

A∧Be) M:老王是革新者。

N:小李是革新者。

M∨Nf) L:你看电影。

M:我看电影。

┓L→┓Mg) P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh) P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。

《离散数学》练习题和参考答案《离散数学》练习题和参考答案一、选择或填空（数理逻辑部分）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、判断下列语句是不是命题。

若是，给出命题的真值。

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

(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）P↔（4）QP→⌝P⌝⌝（2）QQ→P⌝→（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=09、设全体域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是负数”的否定是（）。