离散数学第二版知识点总结

总结 离散数学知识点

第二章 命题逻辑

1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；

5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项；

7.n个变元共有2n个极小项或极大项，这2n为(0~2n-1)刚好为化简完后的主析取加主合取；

8.永真式没有主合取范式，永假式没有主析取范式；

9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则

①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑

1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;

3.既有存在又有全称量词时，先消存在量词，再消全称量词；

离散数学第一章知识点总结（仅供参考）

1.判断给定的句子是否为命题的基本步骤：首先应是陈述句；其次要有唯一的真值。 例：（1）我正在说谎。

不是命题。因为无法判定其真假值，若假设它为假即我正在说谎，则意味着它的反为真，即我正在说实话，二者相矛盾；若假定它为真即我正在说实话，则意味着它的反为假，我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题 （2）x-y ＞2。

不是命题。因为x, y的值不确定，某些x, y使x?y＞2为真，某些x, y使x?y＞2为假，即x?y＞2的真假随x, y的值的变化而变化。因此x?y＞2的真假无法确定，所以x?y＞2不是命题。

2.命题可以分为两种类型：原子命题（不能再分解为更简单命题，又可称为简单命题）； 复合命题(通过联结词、标点符号将原子命题联结而成的命题） 3.命题常元：一个命题标识符如果表示确定的简单命题，就称为命题常元

命题变元：如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元 注：当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派

4.联接词：（1）否定联

数理逻辑部分

第1章 命题逻辑 1.1 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题

注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化

用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示 简单命题

用“1”表示真，用“0”表示假

例如，令 p： 是有理数，则 p 的真值为 0

q：2 + 5 = 7，则 q 的真值为 1

联结词与复合命题 1.否定式与否定联结词“?”

定义 设p为命题，复合命题 “非p”（或 “p的否定”）称

为p的否定式，记作?p. 符号?称作否定联结词，并规定?p 为真当且仅当p为假.

2.合取式与合取联结词“∧”

定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真

注意：描述合取

2.1 等值式

一、等值式的概念

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。

定义2.1 设A,B式两个命题公式，若A,B构成的等价式A

B是等值的，记作A

B.

B为重言式，则称A与

定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。 判断等值式有如下方法： 1.真值表

2.等值演算

3.范式

二、用真值表判断公式的等值

例2.1 判断下面两个公式是否等值：

┐(p∨q)与┐p∧┐q

解 用真值表法判断┐(p∨q)

(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1

(┐p∧┐q)。

所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)

其实，在用真值表法判断AB是否为重言式时，真值表的最后一

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

集合论部分

第四章、二元关系和函数

集合的笛卡儿积与二元关系有序对

定义由两个客体x 和y，按照一定的顺序组成的

二元组称为有序对，记作

实例：点的直角坐标(3,4)

有序对性质

有序性 （当x y时）

与 相等的充分必要条件是= x=u y=v

例1 <2, x+5> = <3y4, y>，求x, y.

解 3y 4 = 2, x+5 = y y = 2, x = 3

定义一个有序n (n3) 元组 是一个

有序对，其中第一个元素是一个有序n-1元组，即

= < , x n>

当n=1时, 形式上可以看成有序 1 元组.

实例 n 维向量是有序 n元组.

笛卡儿积及其性质

定义设A,B为集合，A与B 的笛卡儿积记作A B，即A B ={ | x A y B }

例2 A={1,2,3}, B={a,b,c}

A B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,

<3,a>,<3,b>,<3,c>}

B A ={,,,,,,

, ,}

A={}, P(A)A={<,>, <{},>}

性质：

不适合交换律A B B A (A B, A, B)

不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律

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

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

A(B C

1 / 13

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图

多重集合: 元素可以重复出现的集合 无序积: A &B ={(x ,y ) | x ∈A ∧y ∈B } 定义 无向图G =, 其中 (1) 顶点集V ≠?，元素称为顶点

(2) 边集E 为V &V 的多重子集，其元素称为无向边，简称边.

例如, G =如图所示, 其中V ={v 1, v 2, …,v 5}, E ={(v 1,v 1), (v 1,v 2),

(v 2,v 3), (v 2,v 3), (v 2,v 5), (v 1,v 5), (v 4,v 5)} ,

定义 有向图D =, 其中

(1) V 同无向图的顶点集, 元素也称为顶点

(2) 边集E 为V ?V 的多重子集，其元素称为有向边，简称边.

用无向边代替D 的所有有向边所得到的无向图称作D 的基图，右图是有向图，试写出它的V 和E

注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G 表示无向图, D 表示有向图, 也常用G 泛指 无向图和有向图, 用e k 表示无向边或有向边.

V (G ), E (G ), V (D ), E (D ): G 和D 的顶点集, 边集. n 阶图:

绪论

*学习生态学的三条原则：

1、扎实的博物学知识基础；

2、把生物作为生态学研究的基本单位；

3、进化论思想在生态学研究中具有核心地位。

当代生物进化论的三大理论来源及其发展

*当代生物进化论学派林立，但都来自三个不同而又相互关联的基本学说：拉马克学说、达尔文的自然选择学说和孟德尔遗传理论。

1.新拉马克主义

*拉马克是第一个从科学角度提出进化论的学者，主要观点：①在生物演化的动力上，尽管他们也承认自然选择的作用，但认为用进废退和获得性遗传意义更大；②生物演化有内因（遗传、变异）与外因（环境），两者相比，他们更强调环境的作用；③生物的身体结构与其生理功能是协调一致的，但在因果关系上，即他们认为生理功能决定了结构特征，最典型的例子是对长颈鹿的脖子的解释。

2.孟德尔遗传理论

孟是奥地理利学者，1843年因生活所迫进入修道院，自不成才，1849年任大学预科的代课教师，1851年入维也纳大学深造，1856年开始了豌豆杂交试验，他的颗粒遗传理论与达尔文1859年的《物种起源》几乎同时完成，但却没人理解他为遗传学和进化论做出的杰出贡献。1884年，在达尔文去逝不到两年，孟与世长辞。直到1900年他的遗传学成果才被科学界重新发现，并概括为―孟德尔定律‖。

3.达尔文学说

集合论部分

第三章、集合的基本概念和运算

3.1 集合的基本概念集合的定义与表示

集合与元素

集合 没有精确的数学定义

理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员 集合的表示

列元素法 A={ a, b, c, d }

谓词表示法 B={ x | P(x) }

B 由使得 P(x) 为真的 x 构成常用数集

N, Z, Q, R, C 分别表示自然数、整数、有理数、

实数和复数集合，注意 0 是自然数.

元素与集合的关系：隶属关系

属于 ，不属于

实例

A={ x | x R x2-1=0 }, A={-1,1}

1 A, 2 A

注意：对于任何集合 A 和元素 x (可以是集合)，

x A和 x A 两者成立其一，且仅成立其一.

集合之间的关系

包含（子集） A B x (x A x B)

不包含 A B x (x A x B)

相等 A = B A B B A

不相等 A B

真包含 A B A B A B

不真包含 A B

思考：

2.13 设解释I为：个体域DI ={-2,3,6},一元谓词F（X）：X（X）：X>5,R(X):X（1） 解：

x(F(x)x(F(x)(F(-2) ((-2((1 00

(2)

x(R(x)

F(x))

G(5) G(5)

F(3)) (( 3

(R(6)7)

(3

F(6))3))

03)

7。在I下求下列各式的真值。

3，G

G(x)) G(x)) G(-2))

(F(3) ((3((0 G(3)) 3)

(F(6) (3>5)) 0))

G(6)) ((6

3)

(6<5))

(-2>5))

0))

0))((1 0

解：x(R(x)(R(-2)((-2

F(x))

F(-2)) (R(3)7)

(-2

3))

G(5)

7)

(( 6

(63)) (5>5) (1 10

1) 1

(1 0

1) 0

(1

0)

0

(3)解：

x(F(x)x(F(x)

G(x)) G(x))

(F(3)

((3 (0

G(3)) 3) 1)

(F(6) (3>5))

G(6)) ((6

3)

(6>5))

(F(-2) ((-2(1

G(-2)) 3)

(-2>5)) (1

0)

0)

1 1

1 1

2.14 求下列各式的前束范式，要求