总结 离散数学知识点
第二章 命题逻辑
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.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|；
3. 集： 定集合 A，以集合 A 的所有子集 元素 成的集合，
P(A) 4.若集合 A 有 n 个元素， 集 P(A) 有 2n 个元素， |P(A)|= 2| A|
= 2n
；
5.集合的分划： (等价关系 )
①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交 空，相并 全
(A)；
6.集合的分划与覆盖的比 ：
分划：每个元素均 出 且 出 一次在子集中；
覆盖：只要求每个元素都出 ，没有要求只出 一次；
第五章
关系
1.若集合 A 有 m 个元素，集合 B 有 n 个元素， 笛卡 A×B 的基数mn，A 到 B 上可以定 2mn 种不同的关系；
2.若集合 A 有 n 个元素， |A ×A|= n2 ，A 上有 2n2 个不同的关系； 3.全关系的性 ：自反性， 称性， 性；
空关系的性 ：反自反性，反 称性， 性；
；
全封 的性 ：自反性， 称性，反 称性， 性；
4.前域 (domR) ：所有元素 x 成的集合；
后域 (ranR) ：所有元素 y 成的集合； 5.自反 包： r(R)=RU I x ;
称 包： s(R)=RU R-1 ;
包： t(R)=RU R2 U R3 U?? 6.等价关系：集合 R 称 等价关系； 7.偏序关系：集合
A 上的关系 R 足自反性，反 称性和 性， A 上的二元关系 R 足自反性， 称性和 性，
称 R 是 A 上的一个偏序关系；
8.covA={
9.极小元：集合 A 中没有比它更小的元素 (若存在可能不唯一 )；极大元：集合 A 中没有比它更大的元素 (若存在可能不唯一 )；最小元：比集合 A 中任何其他元素都小 (若存在就一定唯一 )；最大元：比集
合 A 中任何其他元素都大 (若存在就一定唯一 )；
10.前提： B 是 A 的子集
上界： A 中的某个元素比 B 中任意元素都大，称 个元素是
B 的
上界 (若存在，可能不唯一 )；
下界： A 中的某个元素比 B 中任意元素都小，称 个元素是
B 的
下界 (若存在，可能不唯一 )；
上确界：最小的上界 (若存在就一定唯一 )；
下确界：最大的下界 (若存在就一定唯一 )；
(完整word版)离散数学必备知识点总结.docx
