离散数学小结课件

《离散数学小结课件》由会员分享，可在线阅读，更多相关《离散数学小结课件（84页珍藏版）》请在金锄头文库上搜索。

1、7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,1,Discrete Math. 离散数学 研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。（辞海） 离散数学的内容：基础、原理、应用,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,2,基础部分: 逻辑(Logic) 集合(Sets) 算法(Algorithms) 数论(Number Theory),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,3,原理部分: 数学推理(Reasoning) 计数原

2、理(Counting) 关系(Relations),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,4,应用部分: 图(Graphs) 树(Trees) 布尔代数(Boolean Algebra),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,5,逻辑（LOGIC）： 1.命题逻辑 Proposition Logic 2.命题演算 Propositional Equivalences 3.谓词和量词 Predicates and Quantifiers,7/2/2019 7:52 PM,Discrete Ma

3、th. , DeRen Chen,6,（1）命题的概念：定义、逻辑值、 符号化表示 （2）从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级 （3）从命题常量到命题变量， 从复合命题到命题公式： 命题公式的真值描述：真值表 （4）命题公式的分类： 永真公式、永假公式、可满足公式 、一般公式 （5）命题公式的判定、分类与标准化描述 （6）从命题到命题函数：N元谓词、个体、个体变量、个体域 （7）从命题公式到谓词公式：存在量词、全称量词,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,7,命题公式： 1、原子命题是命题公式； 2、设P是命题公式，则P

4、也是命题公式； 3、设P、Q是命题公式，则（P Q）、（P Q）、（P Q）、（P Q）也是命题公式； 4、有限次地使用1、2、3所得到的也是命题公式。 Proposition Formulas, Well-Formed Formulas(wff),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,8,永真命题公式（Tautology） 公式中的命题变量无论怎样代入，公式对应的真值恒为T。 永假命题公式（Contradiction) 公式中的命题变量无论怎样代入，公式对应的真值恒为F。 可满足命题公式（Satisfaction） 公式中的命题变量无论怎样

5、代入，公式对应的真值总有一种情况为T。 一般命题公式（Contingency） 既不是永真公式也不是永假公式。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,9,Table 5,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,10,Table 6,p q T p q F p (p q) p Absorption Laws/吸收律 p (p q) p p q p q p q (p q) ( q p),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,11,判断命题公式逻辑

6、等价的方法： 1、真值表 2、命题公式的演算 基本等值定理； 公式的代入不变性； 等值关系的传递性。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,12,命题公式逻辑等价关系的应用： 1、判定是否逻辑等价； 2、判断是否为永真公式或永假公式； 3、命题公式的化简 命题公式的标准化描述： 表达、分类、判定、应用,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,13,文字（literal）/符号（symbol）： 原子命题或其否定 小项（small item）/合取式（ conjunctive form ）: 若

7、干个文字的合取。 大项（large item）/析取式（ disjunctive form ）: 若干个文字的析取。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,14,合取范式（conjunctive normal form): 若干个大项的合取。 析取范式（disjunctive normal form): 若干个小项的析取。 标准句(standard sentence)：合取范式或析取范式 子句（clause）:合取范式中的大项或 析取范式中的小项。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,15

8、,令A（a1、a2、an）包含有n个变量的公式， 极小项(extremal ):小项中恰包含n个变量或其否定。 极大项( extremal ):大项中恰包含n个变量或其否定。 主合取范式（Unique conjunctive normal form): 若干个极大项的合取。 主析取范式（Unique disjunctive normal form): 若干个极小项的析取。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,16,定理：令A（a1、a2、an）包含有n个变量的公式，则有： 1、如果A存在与之等价的主析取范式，则必唯一； 2、如果A存在与之等

9、价的主合取范式，则必唯一； 3、A是永真公式当且仅当与A等价的主析取范式恰有2n个极小项或没有主合取范式； 4、A是永假公式当且仅当与A等价的主合取范式恰有2n个极大项或没有主析取范式； 5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,17,定义 一个谓词P连同相关的n（n0）个个体变量组成的表达式称为n元谓词（n-predicate），记P（x1, x2, , xn），其中n是该表达式中不同个体变量的数目。n元谓词也称简单命题函数，将简单命题函数视为命题，按1.1.1节定义10得

10、到的递归定义的表达式称为复合命题函数。简单命题函数和复合命题函数，统称为命题函数（proposition function）。,DEFINITION .,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,18,为了进一步讨论命题函数P(x)的真值情况，首先需要指定个体变量x可选择的范围，即个体域（universe of discourse, or domain）。每一个个体变量x都有自己的个体域。如果没有特别指定的个体域，则缺省为一个全个体域（total universe of discourse）即任意个体均可以作为常量对x代入。,7/2/2019 7

11、:52 PM,Discrete Math. , DeRen Chen,19,定义2 命题函数P(x)的全称量化（universal quanification）是一个按如下规则确定真值的命题：如果对每一个个体a代入得到的P(a)均为T。则该命题为T。记为VxP(x)。这里V是全称量词（universal quantifier），表示为“对任意的”、“所有的”、“对每一个”等等。,DEFINITION 2.,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,20,定义3 命题函数P(x)的存在量化（existential quantification）是一

12、个按如下规则确定真值的命题：如果个体域中存在一个个体a代入后得到P(a)为T，则该命题为T，否则为F。记或 。这里称为存在量词（existential quantification）。表示为“有一个”、“某些”、“某个”等等。,DEFINITION 3.,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,21,定义4 谓词公式定义为 （1）n元谓词是一个谓词公式； （2）若A是谓词公式，则（A）也是谓词公式； （3）若A，B是谓词公式，则（AB）、（AB）、（AB）、（AB）也是谓词公式； （4）若A是谓词公式且含有未被量化的个体变量x，则 VxA(x)

13、，XA(x)也是谓词公式。 （5）有限次地使用（1）（4）所得到的也是谓词公式。,DEFINITION 4.,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,22,定理2 （基本量词等值定律） E14：量词分配律 Vx（A(x)B(x)）VxA(x)VxB(x) x(A(x)B(x)） xA(x) xB(x) 另两种情况的思考：V与， 与,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,23,E15：量词扩张/收缩律 Vx(PB(x)PVxB(x) Vx(PB(x)PVxB(x) x(PB(x)P xB(x)

14、x(PB(x)P x B(x) 这里A、B是任意包括个体变量x的谓词公式，P是不包括个体变量x的任意谓词公式。,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,24,1.2 集合（ Sets） 1.2.1 集合的概念 Concepts of Sets 1.2.2 集合的运算 Operating of Sets 1.2.3 函数 Functions 1.2.4 语言 Language,7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,25,The objects in a set are also called t

15、he elements, or members, of the set. A set is said to contain its elements. A = a, b, c, n 枚举法 A = x | xP(x) 谓词公式法,Null Set: There are no anything in the set. =x | xP(x) (x P(x) ),7/2/2019 7:52 PM,Discrete Math. , DeRen Chen,26,DEFINTION 2.,Two sets are equal if and only if they have the same elemen

16、ts. Presented as A=B otherwise A B,A = B x ( x A x B),The set A is said to be a subset of B if and only if every element of A is also an element of B. We use the notation AB to indicate that A is a subset of the set B.,The set A is said to be a proper subset of B if AB and there is aB and aA,7/2/2019 7:52