离散数学复习

Ch1命题逻辑数理逻辑：研究一种形式语言，其本质是将数学中的逻辑证明加以符号化，因而推动各数学分支的迅速发展。命题：表示判断的具有确定真值的陈述句。命题只要能判断真假，不一定已知真假非陈述性语句不是命题方程不是命题悖论不是命题联结词1.否定2.合取∧3.析取：∨4.条件双条件翻译提示：不可兼或：(PQ)当P则Q(如果P，那么Q):

PQP仅当Q(仅当Q，则P):

PQ除非P否则Q：PQ只要Ｐ，就有Ｑ：P

Q只有Ｐ，才能Ｑ：

Q

P定义一般翻译为双条件优先级：

高低1、只有你主修计算机科学或者不是新生，才能从校园内访问因特网。

解：设P：你能从校园内访问因特网；Q：你是新生；

R：你主修计算机科学。则原题译为：

P(R∨

Q)2、除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。解：设P：你已满16周岁；

Q：你身高不足4英尺；

R：你能乘公园滑行铁道。则原题译为：

P(Q

R)推理理论P规则T规则证明方法：直接证法反证法CP规则(CP规则可以连续使用)原子命题拆成：客体＋谓词全称量词“”，存在量词“”翻译注意：特性谓词的位置：在全称量词的作用域内作条件句的前件，在存在量词的作用域内作合取项。课后习题、上课例题看看Ch2谓词逻辑量化断言与命题的关系假设个体域D={a1,a2，…，an}(x)(P(x))P(a1)∧P(a2)∧…

∧P(an)(x)(P(x))P(a1)∨P(a2)∨…∨P(an)谓词演算的推理理论消去、添加量词规则全称指定US全称推广UG存在指定ES存在推广EG在谓词推理中，必须注意的两点：不能在量词的作用域内使用等价式和蕴含式在同一证明中，若既要使用存在指定，又要使用全称指定，则先用存在指定，后用全称指定。谓词推理理论P规则、T规则、US、UG、ES、EG证明方法：直接证法反证法CP规则课后习题、上课例题看看Ch3集合与关系定理集合A和B相等的充分必要条件是这两个集合互为子集。集合的运算、、－(相对补)、～(绝对补)、(对称差)运算的性质序偶与笛卡儿积关系的性质自反、对称、传递、反自反、反对称关系性质的证明方法：要证明R在X上自反假设x∈X，证出<x,x>∈R

要证明R在X上对称对x,y∈X,设<x,y>∈R，证出

<y,x>∈R

要证明R在X上传递对x,y,z∈X,设<x,y>∈R∧<y,z>∈R，证出<x,z>∈R

要证明R在X上反自反假设x∈X，证出<x,x>∉R）要证明R在X上反对称对x,y∈X，设<x,y>∈R∧<y,x>∈R，证出x＝y关系的的运算：、、－(相对补)、～(绝对补)、(对称差)关系的复合、关系的逆、关系的闭包运算集合的划分与覆盖划分可以确定一个等价关系覆盖可以确定一个相容关系(不同的覆盖可能构造出相同的相容关系)。等价关系与等价类及其性质序关系偏序关系、哈斯图、极大元、极小元、最大元、最小元、上界、下界、上确界、下确界函数函数的概念入射、满射、双射逆函数(当f是双射函数时逆函数才有意义。)复合函数(注意写法与关系的复合不同。)求gof时，若ranf

不包含于

domg，则gof为空复习书上定理和课后习题Ch5代数系统运算的性质(封闭性、交换性、结合性、分配律、吸收律、等幂律)特殊的元素(幺元、零元、逆元)广群、半群、独异点、群和子群阿贝尔群和循环群设<S，*>是一个半群，如果S是一个有限集，则必有对于bS

,

b*bS，记b2=b*bb2*b=b*b2S，记b3=b2*b=b*b2……由于S是有限集，所以必存在j>i，使得bi=bj……证明方法举例：证明a是b的逆元?

a*b=b*a=e

例如：(a*b)-1=b-1*a-1群中满足消去律群中不可能有零元。任何一个循环群必定是阿贝尔群。群<G,*>中的幺元e必定也是其子群<S,*>中的幺元。子群的判定定理：当Ｓ是有限集：*在Ｓ上封闭当Ｓ是无限集：a，b∈S，

有a*b-1∈S任何质数阶的群必定是循环群。

陪集与拉格朗日定理设<H，*>是群<G,*>的一个子群，a∈G，则集合{a}H称为由a所确定的H在G中的左陪集，记为aH。拉格朗日定理。书上定理和课后习题。每个图中结点度数的总和等于边数的两倍。

Σdeg(v)=2|E|在任何有向图中，所有结点的出度之和等于所有结点的入度之和。无向图的连通性:连通性是结点集合上的一种等价关系。点割集、边割集有向图的可达性：强连通=>单侧连通＝>弱连通强分图、单侧分图、弱分图在有向图G=<V,E>中，它的每一个结点位于且只位于一个强分图中。Ch7图论欧拉图与汉密尔顿图给定无孤立结点图G，若存在一条回路，经过图中的每边一次且仅一次，该回路为欧拉回路。具有欧拉回路的图，称为欧拉图。无向图G具有一条欧拉回路当且仅当G是连通的，且所有结点度数全为偶数。

给定图G，若存在一条回路，经过图中每个结点恰好一次，这条回路称为汉密尔顿回路。具有哈密尔顿回路的图，称为汉密尔顿图。平面图一个有限平面图，面的次数之和等于其边数的两倍。设有一个连通的平面图G，共有v个结点e条边和r个面，则欧拉公式v－ｅ＋r＝２成