离散数学重点复习

第一章.集合论

概念

1.集合是不能精确定义的基本数学概念.通常是由指定范围内的满足给定条件的所有对象聚集在一起构成的

2.制定范围内的每一个对象称为这个集合的元素

3.固定符号如下:

N:自然数集合

Z:整数集合

Q:有理数集合

R:实数集合

C:复数集合

4.集合中的元素是唯一确定并可以加以区分的对象,即集合中元素是互异且无序的

定理1.2.1(外延性原理) 两个集合A和B相等,当且仅当它们的元素完全相等,记为A=B,否则A≠B

定理1.2.3 (1)空集是一切集合的子集;(2)空集是绝对唯一的

定义1.2.6 集合A含有n个元素,称集合A为n元集,称A的含有m个(0<=m<=n)元素的子集为他的m元子集

5.n元集共用2^n个不同的子集

定义1.2.7设A为任意集合,把A的不同子集构成的集合称为A的幂集,记为P(A)或2^A

定理 1.2.5 图

题

第三章.命题逻辑

概念

定义3.2.1 具有确定真值的陈述句称为命题

1.命题一定是通过陈述句来表达的;反之并非一切陈述句都一定是命题

2.(1)原子命题,(简单命题)不能再分解为更简单命题的命题.(2)复合命题:可以分解为更简单命题的命题

3.5个联结词 图

4.命题联结词优先级如下:

(1).否定->合取->析取->蕴含->等价

(2).同级连接词,从左到右吧

(3)括号内优先

5.(1)连接词 是 两个命题真值的联结,不是命题内容的联结

6.合式公式又称命题公式由如下规则生成:

(1)命题变元本身是一个公式

(2)如果G是公式,非G也是公式

(3)见图

(4)仅通过有限步使用规则(1)(2)(3)所得到的符号串才是命题公式

定义3.3.3 设P1,P2,P3…Pn,是出现在公式G中的所有命题变元,制定P1,P2,P3…Pn一组真值,则这组真值称为G 的一个解释,常记为I

定义3.3.4 由公式G在其所有可能的解释下所有的真值构成的表

定义3.3.5

永真式.在他的所有解释下真值都为真;

永假公式(矛盾式),所有解释下真值都为假,也称为不可满足公式,

可满足的,如果不是永假;

7."="不是连接词而是一种关系,有如下三个性质:

(1)自反性,G=G.(2)对称性,G=H,H=G.(3).传递性:G=H,H=S,则G=S

8.24个等价关系见图

定义3.5.1

(1)命题变元或命题变元的否定称为文字

(2)有限个文字的析取称为析取式,也称子句

(3).有限个文字的合取称为合取式,也成短语

(4).p和非P称为互补对

定义3.5.2

(1).有限个短语的析取式称为析取范式

(2).有限个子句的合取式称为合取范式

例子见图:

定义3.5.3 极大项和极小项

含有n个命题变元P1,P2,…Pn的短语或子句中,若每个命题变元与其否定不同时存在,但二者之一恰好出现一次当且仅出现一次,并且出现的次序与P1,P2,…Pn一致,则成此短语或子句为关于P1,P2,…Pn的一个极小项或极大项.

例子见图:

n个命题变元可构成2^n 个极小项和2^n个极大项.

定义3.5.4 主析取范式和主合取范式

(1)在给定的析取范式中,若每一个短语都是极小项,则该范式为主析取范式

(2)在给定的合取范式中,若每一个子句都是极大项,则该范式为主合取范式

(3)如果主析取范式不包含任何极小项,如果主合取范式不包含任何极大项,则该范式为"空"

定理3.5.2 任何一个公式都有与之等价的主析取范式和主合取范式

9.真值表技术

见图

10.推理定律

11.证明符号:

"p"表示引入事实库中的事实

"T"表示该公式是前公示推导的逻辑结果

"I"表示使用的基本蕴含关系

"E"表示使用的基本等价关系

序号表示由那几个公式得出的

题

第四章.谓词逻辑

概念

题

第六章.二元关系

概念

题

第九章.图

概念

题