笔记离散数学.docx

《笔记离散数学.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学复习笔记数理逻辑逻辑：以研究人的思维形式及思维规律为目的的一门学科数理逻辑：利用数学符号来协助推理的一门形式逻辑学命题：能表达判断并具有确定真值的陈述句真值：每个命题都具有的一个值，要么为真，要么为假，不能随着环境变化原子命题：不能再分解的命题复合命题：由原子命题符号及联结词组成的有意义的命题表达式否定非P合取P而且Q 析取P可兼或Q排斥析取P不可兼或Q单条件若P则Q双条件P当且仅当Q命题公式：满足特定条件的合法的命题表达式分量：命题公式中的原子命题翻译：将自然语言转化为数理逻辑语言真值表：对一个命题公式而言，将对于其分量的各种可能的真值指派汇聚成的表两个命题等价：对两个命题公式

2、A,B,若对于AB中的所有命题变元P1P2..对天安门的任一组真值指派A，B相同对应的行的真值相同，则称A与B等价等价定律：交换律，结合律，分配律，摩根律，否定律，同一律重言式：永真式，无论对命题变元作何种真值指派，它都等价于T的命题公式永假式：无论对命题变元作何种真值指派，它都等价于F的命题公式用一个命题公式代替重言式中同一个分量，依然为重言式蕴含式：若A->B永真则称A蕴含B，记做A=>B原命题等价于它的逆否命题三个性质：传递性，A=>BA=>CA=>(B^C)，A=>BC=>BAvC=>B有效结论：H1，H2、、、、Hn，C为一组命题公式，若H1^H2^...^Hn=>C,称C

3、是一组条件下的有效结论三种方法：真值表法，直接证法，间接证法其他连接词：条件否定，与非，或非规范命题表达式：只含非且或合取范氏：当且仅当具有A1^A2^...^An形式，A1，A2...An都是命题变元或其否定组成的析取式析取范式：当且仅当具有A1vA2v...vAn形式，A1，A2...An都是命题变元或其否定组成的合取式一个命题公式的合取范氏或析取范氏并不是唯一的n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次P^QP^非Q一般n个命题变元共有2^n个小项n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存

4、在，但两者必须出现且仅出现一次PvQPv非Q主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则称该等价式为原式的主析取范式主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则称该等价式为原式的主合取范式集合论集合：满足一定特征的对象的全体扩张原则：两个集合相等，当且仅当他们有相同的元素抽象原则：任给一个集合U和一个性质P，存在一个集合A，使得A的各个元素恰好是U的具有性质P的那些成员集合表示：列举法，特征法幂集：对给定的集合A，称以A的全体子集为元素的集合为A的幂集集合的基数：

5、A

6、元素的个数无限集合：元素个数能与某个真子集一一对应的

7、集合序偶：有序的二元数组笛卡尔积：称A*B={

8、x属于A且y属于B}二元关系：以序偶作为元素的集合即关系xRy，关系前域指x，关系值域指y，关系域是前域和值域的并集。两集合A与B的笛卡尔积的任一子集，称为A到B的一个关系，若A=B，则称该子集为A上的一个关系关系表示：集合表示法，关系矩阵法，关系图表示法关系性质：自反关系（x属于X，属于R），反自反关系（x属于X，不属于R）【存在既不反自反也不自反的关系】对称性x，y属于X，且属于R，则属于R，反对称关系x属于X，y属于X，且属于R，属于R，则x=y【存在既对

9、称又反对称的关系，存在既不对称又不反对称的关系】传递性x,y,z属于X，且都属于R，则属于R复合关系:属于R,属于S，则属于R复合S逆关系:{

10、属于R,x属于X,y属于Y}闭包运算：通过往已知关系中添加序偶让它达到某种要求的运算，叫闭包运算覆盖：A为非空集合，S={s1,s2...sm}其中Si属于A，且S的并集为A，则S是A的一个覆盖划分：若对一个覆盖而言，S任意两个子集的交集为空，则称S是A的一个划分注：两划分的交叉划分也是原集合A的一个划分交叉划分是原两划分的加细等价关系：同时具备自反，对称和传递三个性

11、质的关系即等价关系等价类：A上的等价关系R，A中的任意a，x属于A，属于R，为元素a生成的R等价类商集：若R是A上的一个等价关系，则称以A的所有等价类为元素的集合为A关于R的商集，为A/R定理：A上的一个等价关系R确定了A的一个划分A/RA上的一个划分也能确定A上的一个等价关系A上的两个等价关系R1，R2，则成立A/R1=A/R2等价于R1=R2A上的等价关系与划分是一一对应的相容关系：给定集合A上的关系r，若r是自反的、