离散数学知识点.doc

第一章1. 将下列命题符号化： 解：令p：天下雨，q：我骑自行车上班，则（1）只要不下雨，我就骑自行车上班 p是q的充分条件，所以符号化为：pq（2）只有不下雨，我才骑自行车上班 p是q 的必要条件，所以符号化为：q p（3）除非下雨，否则我就骑自行车上班 p仍然是q的充分条件，所以符号化为：pq（4）如果下雨，我就不骑自行车上班 p是q的充分条件，所以符号化为：pq2.命题: 判断结果惟一的陈述句（注意: 感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题） 3. pq为假当且仅当 p 为真 q 为假4. pq （q 为 p 的必要条件）“如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p 因为.所以5. pq为真当且仅当p与q同真或同假6. p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层7.双重否定律 AA等幂律： AAA, AAA交换律: ABBA, ABBA结合律: (AB)CA(BC) (AB)CA(BC)分配律: A(BC)(AB)(AC) A(BC) (AB)(AC)德摩根律: (AB)AB (AB)AB吸收律: A(AB)A, A(AB)A零律: A11, A00 同一律: A0A, A1A排中律: AA1矛盾律: AA0蕴涵等值式: ABAB等价等值式: AB(AB)(BA)假言易位: ABBA等价否定等值式: ABAB归谬论: (AB)(AB) A8.对偶原理 设A，B为两个命题公式，若A B，则A* B*.9.求公式A的范式的步骤： (1) 消去A中的, （若存在） (2) 否定联结词的内移或消去 (3) 使用分配律 对分配（析取范式） 对分配（合取范式）（公式的范式存在，但不惟一）10.设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1.A为矛盾式 A的主析取范式为0 A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项 第二章第三章1.相对补 A-B = x | xA xB =A - (AB)对称差 AB = (A-B)(B-A)= (AB)-(AB) 绝对补 A = E-A 第四章1. R=M1 S=M2 RS = M2 * M12. (1) (F-1)-1=F (2) domF-1=ranF, ranF-1=domF (1) (FG)H=F(GH) (2) (FG)-1= G-1F-1 3.关系性质的充要条件 设R为A上的关系, 则 (1) R在A上自反当且仅当 IA R (2) R在A上反自反当且仅当 RIA= (3) R在A上对称当且仅当 R=R-1 (4) R在A上反对称当且仅当 RR-1IA (5) R在A上传递当且仅当 RRR 4. 定理1 设R为A上的关系, 则有 (1)自反闭包 r(R) = RR0 (2)对称闭包s(R) = RR-1 (3)传递闭报 t(R) = RR2R35. Mr = M + E E 是和 M 同阶的单位矩阵, M是 M 的转置矩阵. Ms = M + M 注意在上述等式中矩阵的元素相加时使用逻辑加Mt = M + M2 + M3 + 6.集合A上的恒等关系 IA 是A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系7.数集上的小于或等于关系是全序关系；整除关系不是正整数集合上的全序关系8.哈斯图特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边9.特殊元素的性质：n 对于有穷集，极小元和极大元必存在，可能存在多个. n 最小元和最大元不一定存在，如果存在一定惟一.n 最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元10.哈斯图应注意：（1）.哈斯图不应出现三角形第七章1.握手定理 任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数2.环是长度为1的圈, 两条平行边构成长度为2的圈3. Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E 为边割集，则p(G-E )=2若G连通，V 为点割集，则p(G-V )2 4.强连通单向连通弱连通 5. 定理(强连通判别法) D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法) D单向连通当且仅当D中存在经过每个顶点至少一次的通路 6.无向图的关联矩阵性质：(1) 每一列恰好有两个1或一个27.有向图的关联矩阵性质：(1) 每一列恰好有一个1和一个-1(2) 第i行1 的个数等于d+(vi), -1 的个数等于d-(vi) (3) 1的总个数等于-1的总个数, 且都等于m(4) 平行边对应的列相同8.有向图的邻接矩阵性质：9有向图的可达矩阵性质: P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1第八章1.定理8.1 无向图G=是二部图当且仅当G中无奇圈 2.欧拉图的判别法 定理8.4 无向图G为欧拉图当且仅当G连通且无奇度顶点. 无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点 定理8.5 有向图D是欧拉图当且仅当D连通且每个顶点的入度都等于出度. 有向图D具有欧拉通路当且仅当D连通且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个出度比入度大1, 其余顶点的入度等于出度.3.环不影响图的欧拉性. 环与平行边不影响图的哈密顿性4.定理8.6 设无向图G=是哈密顿图, 则对于任意V1V且V1, 均有 p(G-V1)|V1|.5.定理8.7 设G是n阶无向简单图, 若任意两个不相邻的顶点的度数之和大于等于n-1, 则G中存在哈密顿通路. 当n3时, 若任意两个不相邻的顶点的度数之和大于等于n, 则G