下载文档原格式
离散数学是计算机科学中的一门核心课程，它涉及到数学中的许多概念和方法。
以下是一些离散数学的经典教材：
1.《离散数学》（作者：Kozen）
这是一本非常经典的离散数学教材，涵盖了离散数学中的许多基本概念和方法，包括集合论、图论、数理逻辑、组合数学等。
这本书的内容非常丰富，而且语言通俗易懂，是学习离散数学的好教材。
2.《离散数学及其应用》（作者：Rosen）
这是一本非常经典的离散数学教材，涵盖了离散数学中的许多基本概念和方法，包括集合论、图论、数理逻辑、组合数学等。
这本书的内容非常详细，而且有很多例子和练习题，可以帮助读者更好地掌握离散数学的知识。
3.《离散数学教程》（作者：Kleitman）
这是一本非常经典的离散数学教材，涵盖了离散数学中的许多基本概念和方法，包括集合论、图论、数理逻辑、组合数学等。
这本书的内容非常详细，而且有很多例子和练习题，可以帮助读者更好地掌握离散数学的知识。
4.《离散数学精讲》（作者：Sipser）
这是一本非常经典的离散数学教材，涵盖了离散数学中的许多基本概念和方法，包括集合论、图论、数理逻辑、组合数学等。
这本书的内容非常详细，而且有很多例子和练习题，可以帮助读者更好地掌握离散数学的知识。
以上是一些离散数学的经典教材，每本书都有其独特的风格和特点，读者可以根据自己的需求和兴趣选择适合自己的教材。
02324离散数学知识点
离散数学是研究离散对象和离散结构的数学分支，其知识点包括但不限于集合论、图论、逻辑学、组合数学等。
以下是其中一些重要的知识点：
1. 集合论：集合论是离散数学的基石，它研究集合、集合之间的关系和集合的性质。
2. 图论：图论是离散数学的重要组成部分，它研究图（由节点和边构成的结构）的性质和分类。
3. 逻辑学：逻辑学是离散数学的另一个重要组成部分，它研究推理的规则和形式。
在离散数学中，逻辑通常用于描述和证明一些结构或系统的性质。
4. 组合数学：组合数学是离散数学的一个分支，它研究计数、排列和组合问题。
5. 离散概率论：离散概率论是离散数学的另一个分支，它研究离散随机事件的数学模型。
6. 离散概率分布：离散概率分布是描述离散随机事件发生概率的数学模型。
7. 离散随机变量：离散随机变量是能够取到可数无穷多个值的随机变量。
8. 离散概率空间：离散概率空间是一个集合，它包含一个可数无穷多的元素，每个元素都有一个与之相关的概率值。
9. 离散随机过程：离散随机过程是离散随机事件在时间或空间上的序列。
这些知识点都是离散数学的重要组成部分，它们在计算机科学、数学、物理学等领域都有广泛的应用。
命题逻辑▪令狐采学▪(论域)定义：论域是一个数学系统，记为D。
它由三部分组成：•(1)一个非空对象集合S，每个对象也称为个体；•(2) 一个关于D的函数集合F；•(3)一个关于D的关系集合R。
▪（逻辑连接词）定义•设n>0,称为{0,1}n到{0,1}的函数为n元函数，真值函数也称为联结词。
•若n =0，则称为0元函数。
▪（命题合式公式）定义：•(1).常元0和1是合式公式；•(2).命题变元是合式公式；•(3).若Q,R是合式公式，则(Q)、(Q R) 、(Q R) 、(Q R) 、(Q R) 、(Q R)是合式公式；•(4).只有有限次应用(1)—(3)构成的公式是合式公式。
▪（生成公式）定义1.5 设S是联结词的集合。
由S生成的公式定义如下：•⑴若c是S中的0元联结词，则c是由S生成的公式。
•⑵原子公式是由S生成的公式。
•⑶若n≥1，F是S中的n元联结词，A1,…,An是由S生成的公式，则FA1…An是由S生成的公式。
▪（复杂度）公式A的复杂度表示为FC(A)•常元复杂度为0。
•命题变元复杂度为0，如果P是命题变元，则FC (P)=0。
•如果公式A=B，则FC (A)=FC(B)+1。
•如果公式A=B1 B2，或A=B1 B2，或A=B1B2，或A=B1 B2，或A=B1 B2，或则FC (A)=max{FC(B1), FC(B2)}+1。
▪命题合式公式语义•论域：研究对象的集合。
•解释：用论域的对象对应变元。
•结构：论域和解释称为结构。
•语义：符号指称的对象。
公式所指称对象。
合式公式的语义是其对应的逻辑真值。
▪（合式公式语义）设S是联结词的集合是{，，，，，}。
由S生成的合式公式Q在真值赋值v下的真值指派v(Q)定义如下：•⑴v(0)=0, v(1)=1。
•⑵若Q是命题变元p，则v(A)= pv。
•⑶若Q1,Q2是合式公式▪若Q= Q1，则v(Q)= v(Q1)▪若Q=Q1 Q2，则v(Q)=v(Q1)v(Q2)▪若Q=Q1∨Q2，则v(Q)=v(Q1)∨v(Q2)▪若Q=Q1Q2，则v(Q)=v(Q1)v(Q2)▪若Q=Q1 Q2，则v(Q)=v(Q1) v(Q2)▪若Q=Q1Q2，则v(Q)=v(Q1)v(Q2)▪（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下：•⑴若Q是S中的0元联结词c，则v(Q)=c。
离散数学概念离散数学是一门研究离散结构的学科，其中的离散结构可以表示为离散对象或离散事件。
它是计算机科学的基础学科之一，在算法设计和系统分析中有着广泛的应用和深远的影响。
离散数学中的概念包括集合、关系、函数、图论、计数等。
1.集合集合是离散数学中最基础、最重要的概念之一。
集合是指具有某种共同特征的事物的总体，用括号{}括起来表示。
例如，一个集合A包含了元素a、b、c，则A={a,b,c}。
集合的基本运算包括：并集、交集、补集和差集。
并集指的是包含两个集合中所有元素的一个新集合，交集指的是两个集合中共有的元素构成的一个集合，补集则是指一个集合相对于另一个集合的所有不包含的元素构成的集合，差集则是指一个集合中除去另一个集合中共有的元素后所剩余的元素所构成的集合。
2.关系关系是指任意两个元素之间的一种有序的二元关系，用箭头表示，例如(x,y)表示x与y之间有一种特定关系。
关系可以是等于（=）、大于（>）、小于（<）等。
根据关系的定义，关系可以分为反对称、对称、传递等几种类型。
其中反对称关系是指如果(x,y) 且(y,x)，则x=y；对称关系是指如果(x,y) ，则(y,x)；而传递关系则是指如果(x,y)且(y,z)，则(x,z)。
3.函数函数是指一个集合中的每一个元素都对应于另一个集合中的唯一元素的一种映射关系。
函数通常用f(x)来表示，其中f为函数名称，x为变量名称。
例如，用f(x)=x^2表示一个函数，当x为2时，f(x)的值为4。
函数的性质包括：单调性、奇偶性、周期性等。
其中单调性是指函数在定义域内的增减情况；奇偶性则是指函数与自身的中心对称关系；周期性则是指函数图像的重复性。
4.图论图论是离散数学中最为重要和实用的一部分，它用数学语言对各种问题进行分析和解决，例如网络连接问题、旅行商问题等。
图由点和边组成，点表示对象，边表示对象之间的关系。
常用的图有有向图和无向图，有向图是指图中的边有一个方向，无向图则是指图中的边没有方向。
离散数学群的概念嘿，朋友！咱们今天来聊聊离散数学里那个有点神秘又挺有趣的“群”的概念。
你知道吗？群就像是一个小小的魔法世界。
在这个世界里，元素们有着自己独特的规则和玩法。
比如说，一群小伙伴一起玩游戏，规定了某些特定的动作和顺序，这就有点像群的规则啦。
群中的元素之间也有类似的“默契”。
群得满足几个条件呢。
首先，得有个封闭性。
这啥意思？就好比你在一个封闭的房间里，不管怎么折腾，都跑不出去，在群里，元素之间运算的结果还得在这个群里才行。
你想想，如果每次运算结果都跑群外面去了，那不乱套啦？还有结合律得成立。
这就像搭积木，先搭左边再搭右边，或者先搭右边再搭左边，最后搭出来的样子应该是一样的。
要是不一样，那不就抓狂啦？另外，得有个单位元。
这就好比玩游戏里的起点，从这出发，不管怎么折腾，跟其他元素运算，都能保持自己的“身份”。
逆元也不能少。
这就像有去有回，去了还能原路返回。
要是只能去不能回，那不就被困住啦？群这个概念在生活中也有不少影子呢。
比如说，时钟上的数字，12 个数字构成了一个群。
为啥？因为时针转一圈又回到原来的位置，这就是封闭性呀。
再比如，我们常见的正多边形的旋转对称，这也是群。
你说，这离散数学里的群是不是挺有意思？它就像一个隐藏在数学世界里的神秘组织，有着自己独特的规矩和秩序。
咱们学了群的概念，就能更好地理解很多数学问题，就像有了一把神奇的钥匙，能打开更多知识的大门。
总之，离散数学中的群概念，虽然有点抽象，但只要咱们多琢磨，多联系实际，就能发现它的魅力和用处。
别觉得它难，只要用心，咱们都能玩转这个小世界！。
什么叫离散数学
什么叫“离散”？离散，就是和连续相反的。
随便拿⼀堆东西，如⼤到宇宙，⼩到粒⼦团，若其整体中的元素是独⽴的，分开的，则叫“离散”。
计算机是不能处理连续信息的，这是由计算机的本质：0和1，决定的。
正因为这样，如果要借助计算机来处理连续的东西，其中有⼀个必须的步骤：离散化。
“离散数学”是什么？它是⼀门研究离散物质的规律的学科，是数学的⼀个分⽀。
近代数学，尤其是计算数学，在解决实际问题的时候，对于连续问题往往只能推论出“是否有解”，进⼀步可能会求出“解的形式”。
⽽实际的需求，却⾮要得到⼀个结果不可。
因此，在数学建模时，我们通常会⽤⼀个离散的模型去逼近这个连续的问题，最终⽤计算机进⾏⼤量运算来得到⼀个近似值。
不要以为我上⾯说的距离我们很远，⽐如我们常⽤的求根号（你敢说实际中不需要求根号？），就是通过迭代法取近似值。
离散数学
作业要求：
（1）禁止用附件提交作业。
附件提交的作业计0分。
（2）作业按题号顺序作答，乱序、不写题号等视情况扣分。
（3）选择题直接提交答案，不要抄题。
（4）卷面整洁，文字、符号以及图等要清晰可辨。
一、单选题（每题2分，共15小题）
1.集合}}}{{},{,{c b a A =，则下列不属于A 的子集的是（ ）
A.}}{{a
B.}}{{b
C.}}}{{{c
D.}}{,{b a
2.设全集{1,2,...,9,10}U =的子集为A={偶数}，B={奇数}，则下列选项正确的是（ ）
A.A
B =∅ B.A
B =∅ C.A B U =
D. 以上答案都不对
3.已知集合}4,3,2,1{=A ， },,{c b a B =， }8,6,4,2,1{=C ,定义A 到B 的关系c)}(4,b),(3,a),(2,a),{(1,1=ρ，B 到C 的关系(c,1)}(b,6),{(a,4),2=ρ，则下列属于21ρρ的是（ ）
A.)8,1(
B.)4,1(
C.)6,2(
D.)1,3(
4.集合}3,2,1{=A 上的关系)}3,1(),1,2(),2,1{(=R ，则R 具有（ ）
A.对称性
B.自反性
C.可传递性
D.以上说法都不对
5.集合{1,2,3}A =上的下列关系，是由A 到A 的函数的是（ ）
A.{(1,3),(2,3),(3,1)}f =
B.{(1,2),(3,1)}g =
C.{(1,1),(2,1),(3,2),(1,3)}h =
D.{(1,3),(2,1),(2,2)}I =
6.集合},,{},3,2,1{c b a B A ==，则A 到B 的映射中，是单射的是（ ）
A.}b)b)(3,a)(2,(1,{
B.}b)b)(3,a)(1,(1,{
C.}c)b)(3,a)(2,(1,{
D.}b)b)(3,b)(2,(1,{
7. 下面各集合都是N 的子集，（ ）集合在普通加法运算下是封闭的。
A.}16|{整除的幂可以被x x
B.}5|{互质与x x
C.}30|{的因子是x x
D.}30|{<x x
8.设集合A={1，2，3，4，5}上偏序关系图为，
则子集B={2，3，4}的最大下界为（ ）
A.1
B.4
C.5
D.无
9.设,L <≤>是格，则对任意12,l l L ∈，有（ ）
A.12212()()l l l l l ∨=⇔≤
B.12212()()l l l l l ∧=⇔≤
C.12112()()l l l l l ∨=⇔≤
D. 以上答案都不对
10. 设图G 的相邻矩阵为⎥⎥
⎥
⎥⎥
⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢⎣⎡0110110101110110010111110，则G 的顶点数与边数分别为（
） A.5,4
B.6,5
C.10,4
D.8,5
11. 无向简单图>=<E V G ,，},,,,{54321v v v v v V =，则||E 的最大值是（
）
A.8
B.10
C.12
D.16
12.在如下各图中是欧拉图的是（ ）
13. Q P ,是真命题，R 是假命题，则（ ）
A.R Q P ∧→为真
B.Q P R ∨→为真
C.R P Q ∨→为假
D.P Q R ∧→为假
14.设是乌鸦x :P(x )，一样黑y x ,:y),Q(x ，则命题“天下乌鸦一般黑”可符号化为（
）
A.),()(y x Q x xP →∃
B.),()()(y x Q y P x P →∨
C.),())()()(((y x Q y P x P y x →∧∀∀
D.)),()()((y x Q x P x ⌝∧∃⌝
15.谓词公式)())()((x Q y yS x F x →∃∨∀中变元是（ ）。
A. 自由变元
B. 约束变元
C. 既是自由变元也是约束变元
D. 以上答案都不对
二、简答题（每题5分，共6小题）
1.写出集合{,,{}}a a ∅的幂集.
2.设(4,5)}(3,3),(2,4),{(1,2),1=ρ，(5,4)}(4,2),(2,4),{(1,3),2=ρ，试求关系12ρρ的
定义域和值域。
3. 说明什么是等价关系。
4. 请解释什么是群.
5.给定如图所示的图,G V E =<>，求出从A 到E 的所有初级路。
6.用二叉树表示算术表达式()a b c d *+-。
三、证明题（每题10分，共4小题）
1.已知C B g B A f →→:,:，f 是单射，g 是单射，证明gf 是单射。
2.设（L,≤）是一个格， ,,a b c L ∈试证明: 若c b a ≤≤，则 )()()()(c a b a c b b a ∨∧∨=∧∨∧
3. 用推理法证明下式成立：(),,|P Q Q R R P ⌝∧⌝⌝∨⌝-⌝
4.由等值演算证明下列蕴涵式成立: (()())()x y P x Q y xP x ∃∃∧⇒∃。
