离散数学

Answer 1

集合论

世界上各门学科与各个领域的研究与应用中,都有特定的研究的对象与目标。这些研究对象与目标呈群体形式出现,为研究它的一般性规则与特点,就出现了集合论。

集合论是一门最基础的学科,它对人类社会中的所有学科具有指导性作用。

集合论的基本内容包括三个方面,它们是:

集合论基础。

关系:关系是建立在集合论基础上的一种特殊集合,它研究客观世界中事物间关联的规则。

函数:函数是一种特殊的规范化的关系。

集合之间的关系：相离，相交，相等。

集合概念的基本性质：

1.集合元素的确定性

2.集合元素的相异性:集合中每个元素均是不相同的。如有S={a,b},则a,b必不相同的。

3.集合元素的不重复性:集合中不出现有相重复的元素,如{a,b,b,c}与{a,b,c}是一样的。

4.集合元素的无序性:集合中元素与其排列无关。如{a,b,c}与{ b,a,c}及{ c,a,b }均是一样的。

5.集合与元素的相异性:集合与元素是两个不同概念,集合不等同于元素。

定义三个最基本的运算:并运算、交运算以及补。

给出三个运算的21个规则:

1.交换律:

A∪B=B∪A

A∩B=B∩A

2.结合律:

A∪(B∪C)=(A∪B)∪C

A∩(B∩C)=(A∩B)∩C

3.分配律:

A∪(B∩C)=(A∪B)∩(A∪C)

A∩(B∪C)=(A∩B)∪(A∩C)

4.等幕律:

A∪A=A

A∩A=A

5.双否定律:

~(~A)=A

6.互补律:

A∪~A=E

A∩~A=空集

~E=空集

~空集=E

7.同一律:

A∩E=A

A∪空=A

A∩空=空

A∪E=E

8.吸收律:

A∪(A∩B)=A

(1-18)

A∩(A∪B)=A

(1-19)

9.德.摩根(De Morgan)律:

~(A∪B)=~A∩~B

~(A∩B)=~A∪~B

集合幂运算:由集合S的所有子集(包括空集及S自身)所组成元素的运算称S幂运算,可记为p(S),也可记为2 S ,而其所得到的集合S’则称为S的幂集,即:p(S)= S’。

序偶:两个按一定次序排列的元素a与b组成一个有序序列,称为序偶,并可记为:(a,b),其中a与b分别可称为(a,b)的第一分量与第二分量。

笛卡尔乘:集合A与B中将A中元素作为第一分量,B中元素作为第二分量构作的所有序偶所形成序偶集的过程,称笛卡尔乘。可记为A×B。其所形成的结果集C是一个序偶集,叫A与B的笛卡尔乘积,也可简称笛卡尔积。可表示如下:C=A×B={(a,b)| a属于A,b属于B}。

数理逻辑

数理逻辑是用数学方法(即形式化方法)研究形式逻辑演绎推理规则的科学,是一门研究演绎推理规则的数学。

思维形式化：学习数理逻辑首先要学会将一个形式逻辑问题转换成命题逻辑或谓词逻辑中的公式,即思维的形式化。在思维形式化中用若干基本形式化符号:

(1)个体常量:a,b,c,…;

(2)个体变量:x,y,z,…;

(3)函数符:f,g,h,…;

(4)谓词符:P,Q,R,…;

(5)联结词:,∧,∨,,;

(6)量词符:,;

(7)括号:(,)。

原子公式：

设P是n元谓词符,t 1 ,t 2 ,…,t n 为项,则P(t 1 ,t 2 ,…,t n )是原子公式。

命题公式：

(1)命题是公式;

(2)如果P是公式则(非P)是公式;

( 3 ) 如 果 P , Q 是 公 式 则 ( P∨Q ) ,

(P∧Q),(P->Q)及(P<->Q)是公式;

(4)公式由且仅由有限次应用(1)(2)(3)而得。

谓词逻辑公式:

(1)原子公式是公式;

(2)如A,B是公式,则(非A),(A∨B),

(A∧B),(A->B)及(A<->B)是公式;

(3)如A是公式,x是个体变元,则(任意xA),(存在xA)为公式;

(4)公式由且仅由有限次使用(1)-(3)而得。

推理形式化

(1)初级形式化推理

包括等式推理与蕴含推理,由两部分组成:

推理规则

推理过程

应用命题逻辑、谓词逻辑中的基本等式、基本蕴含式与相应的推理规则

图论

图论用“结点”表示事物,用“边”表示事物间的联系,并用“结点”与“边”所构成的图研究客观事物。

为便于计算,建立了图的矩阵表示。这样可以将图论研究与计算相结合。

图的形式很多,重点对树进行研究。

图论应掌握的:

1、图论的基本概念

2、基本定理

3、图的矩阵运算

4、树

图论中的基本概念

1、图的概念

2、有向图与无向图

3、几种特殊的图(零图、平凡图、完全图、补图、简单图与多重图、有权图、同构图)

4、通路、回路(简单、基本)

5、图的连通性(可达性、连通图、欧拉、哈密尔顿)

图论中的的基本定理

1、结点与边的关系

2、基本通路(回路)长度的定理:(n,m)图基本通路(回路)长度小于等于n-1(n)

3、欧拉图、欧拉通路

4、哈密尔顿图、哈密尔顿通路

图的矩阵计算

1、图的邻接矩阵

2、通路计算

3、连通性计算

树

1、树的定义

2、树的性质

3、外向树与内向树

4、二元树与多元树

5、生成树

6、生成树寻找算法