下载文档原格式
1 / 1 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (∃x)((Ax)∨(Bx))<=>( ∃x)(Ax)∨(∃x)(Bx) (∀x)((Ax)∧(Bx))<=>(∀x)(Ax)∧(∀x)(Bx) —┐(∃x)(Ax)<=>(∀x)┐(Ax) —┐(∀x)(Ax)<=>(∃x)┐(Ax) (∀x)(A ∨(Bx))<=>A ∨(∀x)(Bx) (∃x)(A ∧(Bx))<=>A ∧(∃x)(Bx) (∃x)((Ax)→(Bx))<=>(∀x)(Ax)→(∃x)(Bx) (∀x)(Ax) →B <=>(∃x) ((Ax)→B) (∃x)(Ax) →B <=>(∀x) ((Ax)→B) A →(∀x)(Bx) <=>(∀x) (A →(Bx)) A →(∃x)(Bx) <=>(∃x) (A →(Bx)) (∀x)(Ax)∨(∀x)(Bx) =>(∀x)((Ax)∨(Bx)) (∃x)((Ax)∧(Bx)) =>(∀x)(Ax)∧(∀x)(Bx) (∀x)(Ax)→(∀x)(Bx) =>(∀x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={<x,y>|x,y 属于A ，y 盖住x}； 9.极小元：集合A 中没有比它更小的元素(若存在可能不唯一)； 极大元：集合A 中没有比它更大的元素(若存在可能不唯一)； 最小元：比集合A 中任何其他元素都小(若存在就一定唯一)； 最大元：比集合A 中任何其他元素都大(若存在就一定唯一)； 10.前提：B 是A 的子集 上界：A 中的某个元素比B 中任意元素都大，称这个元素是B 的上界(若存在，可能不唯一)； 下界：A 中的某个元素比B 中任意元素都小，称这个元素是B 的下界(若存在，可能不唯一)； 上确界：最小的上界(若存在就一定唯一)； 下确界：最大的下界(若存在就一定唯一)； 6.函数 1.若|X|=m,|Y|=n,则从X 到Y 有mn 2种不同的关系，有m n 种不同的函数； 2.在一个有n 个元素的集合上，可以有2n2种不同的关系，有nn 种不同的函数，有n!种不同的双射； 3.若|X|=m,|Y|=n ，且m<=n ，则从X 到Y 有A m n 种不同的单射； 4.单射：f:X-Y ，对任意1x ,2x 属于X,且1x ≠2x ，若f(1x )≠f(2x )； 满射：f:X-Y ，对值域中任意一个元素y 在前域中都有一个或多个元素对应； 双射：f:X-Y ，若f 既是单射又是满射，则f 是双射； 5.复合函数：f ºg=g(f(x)); 5.设函数f:A-B ，g:B-C ，那么 ①如果f,g 都是单射，则f ºg 也是单射； ②如果f,g 都是满射，则f ºg 也是满射； ③如果f,g 都是双射，则f ºg 也是双射； ④如果f ºg 是双射，则f 是单射，g 是满射； 7.代数系统 1.二元运算：集合A 上的二元运算就是2A 到A 的映射； 2. 集合A 上可定义的二元运算个数就是从A ×A 到A 上的映射的个数，即从从A ×A 到A 上函数的个数，若|A|=2,则集合A 上的二元运算的个数为2*22=42=16种； 3. 判断二元运算的性质方法： ①封闭性：运算表内只有所给元素； ②交换律：主对角线两边元素对称相等； ③幂等律：主对角线上每个元素与所在行列表头元素相同； ④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同； ⑤有零元：元素所对应的行和列的元素都与该元素相同； 4.同态映射：<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f 为由<A,*>到<B,^>的同态映射；若f 是双射，则称为同构； 8.群 广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群(独异点)：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元，有逆元； 2.群没有零元； 3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律； 4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群； 10.格与布尔代数 1.格：偏序集合A 中任意两个元素都有上、下确界； 2.格的基本性质： 1) 自反性a ≤a 对偶: a ≥a 2) 反对称性a ≤b ^ b ≥a => a=b 对偶:a ≥b ^ b ≤a => a=b 3) 传递性a ≤b ^ b ≤c => a ≤c 对偶:a ≥b ^ b ≥c => a ≥c 4) 最大下界描述之一a^b ≤a 对偶 avb ≥a A^b ≤b 对偶 avb ≥b 5）最大下界描述之二c ≤a,c ≤b => c ≤a^b 对偶c ≥a,c ≥b =>c ≥avb 6) 结合律a^(b^c)=(a^b)^c 对偶 av(bvc)=(avb)vc 7) 等幂律a^a=a 对偶 ava=a 8) 吸收律a^(avb)=a 对偶 av(a^b)=a 9) a ≤b <=> a^b=a avb=b 10) a ≤c,b ≤d => a^b ≤c^d avb ≤cvd 11) 保序性b ≤c => a^b ≤a^c avb ≤avc 12） 分配不等式av(b^c)≤(avb)^(avc) 对偶 a^(bvc)≥(a^b)v(a^c) 13）模不等式a ≤c <=> av(b^c)≤(avb)^c 3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)； 4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构； 5.链格一定是分配格，分配格必定是模格； 6.全上界：集合A 中的某个元素a 大于等于该集合中的任何元素，则称a 为格<A,<=>的全上界，记为1；(若存在则唯一) 全下界：集合A 中的某个元素b 小于等于该集合中的任何元素，则称b 为格<A,<=>的全下界，记为0；(若存在则唯一) 7.有界格：有全上界和全下界的格称为有界格，即有0和1的格； 8.补元：在有界格内，如果a^b=0,avb=1，则a 和b 互为补元； 9.有补格：在有界格内，每个元素都至少有一个补元； 10.有补分配格(布尔格)：既是有补格，又是分配格； 布尔代数：一个有补分配格称为布尔代数； 11.图论 1.邻接：两点之间有边连接，则点与点邻接； 2.关联：两点之间有边连接，则这两点与边关联； 3.平凡图：只有一个孤立点构成的图； 4.简单图：不含平行边和环的图； 5.无向完全图：n 个节点任意两个节点之间都有边相连的简单无向图； 有向完全图:n 个节点任意两个节点之间都有边相连的简单有向图； 6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边； 7.r-正则图：每个节点度数均为r 的图； 8.握手定理：节点度数的总和等于边的两倍； 9.任何图中，度数为奇数的节点个数必定是偶数个； 10.任何有向图中，所有节点入度之和等于所有节点的出度之和； 11.每个节点的度数至少为2的图必定包含一条回路； 12.可达：对于图中的两个节点i v ,j v ，若存在连接i v 到j v 的路，则称i v 与j v 相互可达，也称i v 与j v 是连通的；在有向图中，若存在i v 到j v 的路，则称i v 到j v 可达； 13.强连通：有向图章任意两节点相互可达； 单向连通：图中两节点至少有一个方向可达； 弱连通：无向图的连通；(弱连通必定是单向连通) 14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集； 割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点； 15.关联矩阵：M(G)，mij 是vi 与ej 关联的次数，节点为行，边为列； 无向图：点与边无关系关联数为0，有关系为1，有环为2； 有向图：点与边无关系关联数为0，有关系起点为1终点为-1， 关联矩阵的特点： 无向图： ①行：每个节点关联的边，即节点的度；②列：每条边关联的节点； 有向图： ③所有的入度(1)=所有的出度(0); 16.邻接矩阵：A(G)，aij 是vi 邻接到vj 的边的数目，点为行，点为列； 17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列； P(G)=A(G)+2A (G)+3A (G)+4A (G) 可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路； A(G)中所有数的和：表示图中路径长度为1的通路条数； 2A (G)中所有数的和：表示图中路径长度为2的通路条数； 3A (G)中所有数的和：表示图中路径长度为3的通路条数； 4A (G)中所有数的和：表示图中路径长度为4的通路条数； P(G)中主对角线所有数的和：表示图中的回路条数； 18.布尔矩阵：B(G)，i v 到j v 有路为1，无路则为0，点为行，点为列； 19.代价矩阵：邻接矩阵元素为1的用权值表示，为0的用无穷大表示，节点自身到自身的权值为0； 20.生成树：只访问每个节点一次，经过的节点和边构成的子图； 21.构造生成树的两种方法：深度优先；广度优先； 深度优先： ①选定起始点0v ； ②选择一个与0v 邻接且未被访问过的节点1v ； ③从1v 出发按邻接方向继续访问，当遇到一个节点所有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次； 广度优先： ①选定起始点0v ； ②访问与0v 邻接的所有节点v1,v2,……,vk,这些作为第一层节点； ③在第一层节点中选定一个节点v1为起点； ④重复②③，直到所有节点都被访问过一次； 22.最小生成树：具有最小权值(T)的生成树； 23.构造最小生成树的三种方法： 克鲁斯卡尔方法；管梅谷算法；普利姆算法； （1）克鲁斯卡尔方法 ①将所有权值按从小到大排列； ②先画权值最小的边，然后去掉其边值；重新按小到大排序； ③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序； ④重复③，直到所有节点都被访问过一次； （2）管梅谷算法(破圈法) ①在图中取一回路，去掉回路中最大权值的边得一子图； ②在子图中再取一回路，去掉回路中最大权值的边再得一子图； ③重复②，直到所有节点都被访问过一次； （3）普利姆算法 ①在图中任取一点为起点1v ，连接边值最小的邻接点v2； ②以邻接点v2为起点，找到v2邻接的最小边值，如果最小边值比v1邻接的所有边值都小(除已连接的边值)，直接连接，否则退回1v ，连接1v 现在的最小边值(除已连接的边值)； ③重复操作，直到所有节点都被访问过一次； 24.关键路径 例2 求PERT 图中各顶点的最早完成时间, 最晚完成时间, 缓冲时间及关键路径. 解：最早完成时间 TE(v1)=0 TE(v2)=max{0+1}=1 TE(v3)=max{0+2,1+0}=2 TE(v4)=max{0+3,2+2}=4 TE(v5)=max{1+3,4+4}=8 TE(v6)=max{2+4,8+1}=9 TE(v7)=max{1+4,2+4}=6 TE(v8)=max{9+1,6+6}=12 最晚完成时间 TL(v8)=12 TL(v7)=min{12-6}=6 TL(v6)=min{12-1}=11 TL(v5)=min{11-1}=10 TL(v4)=min{10-4}=6 TL(v3)=min{6-2,11-4,6-4}=2 TL(v2)=min{2-0,10-3,6-4}=2 TL(v1)=min{2-1,2-2,6-3}=0 缓冲时间 TS(v1)=0-0=0 TS(v2)=2-1=1 TS(v3)=2-2=0 TS(v4)=6-4=2 TS(v5=10-8=2 TS(v6)=11-9=2 TS(v7)=6-6=0 TS(v8)=12-12=0 关键路径: v1-v3-v7-v8 25.欧拉路：经过图中每条边一次且仅一次的通路； 欧拉回路：经过图中每条边一次且仅一次的回路； 欧拉图：具有欧拉回路的图； 单向欧拉路：经过有向图中每条边一次且仅一次的单向路； 欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路； 26.（1）无向图中存在欧拉路的充要条件： ①连通图；②有0个或2个奇数度节点； （2）无向图中存在欧拉回路的充要条件： ①连通图；②所有节点度数均为偶数； （3）连通有向图含有单向欧拉路的充要条件： ①除两个节点外，每个节点入度=出度； ②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少1； （4）连通有向图含有单向欧拉回路的充要条件： 图中每个节点的出度=入度； 27.哈密顿路：经过图中每个节点一次且仅一次的通路； 哈密顿回路：经过图中每个节点一次且仅一次的回路； 哈密顿图：具有哈密顿回路的图； 28.判定哈密顿图（没有充要条件） 必要条件： 任意去掉图中n 个节点及关联的边后，得到的分图数目小于等于n ； 充分条件： 图中每一对节点的度数之和都大于等于图中的总节点数； 29.哈密顿图的应用：安排圆桌会议； 方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图)，即可； 30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图； 31.面次：面的边界回路长度称为该面的次； 32.一个有限平面图，面的次数之和等于其边数的两倍； 33.欧拉定理：假设一个连通平面图有v 个节点，e 条边，r 个面，则 v-e+r=2； 34.判断是平面图的必要条件：(若不满足，就一定不是平面图) 设图G 是v 个节点，e 条边的简单连通平面图，若v>=3，则e<=3v-6； 35.同胚：对于两个图G1,G2，如果它们是同构的，或者通过反复插入和除去2度节点可以变成同构的图，则称G1，G2是同胚的； 36.判断G 是平面图的充要条件： 图G 不含同胚于K3.3或K5的子图； 37.二部图：①无向图的节点集合可以划分为两个子集V1，V2； ②图中每条边的一个端点在V1，另一个则在V2中； 完全二部图：二部图中V1的每个节点都与V2的每个节点邻接； 判定无向图G 为二部图的充要条件： 图中每条回路经过边的条数均为偶数； 38.树：具有n 个顶点n-1条边的无回路连通无向图； 39.节点的层数：从树根到该节点经过的边的条数； 40.树高：层数最大的顶点的层数； 41.二叉树： ①二叉树额基本结构状态有5种； ②二叉树内节点的度数只考虑出度，不考虑入度； ③二叉树内树叶的节点度数为0，而树内树叶节点度数为1； ④二叉树内节点的度数=边的总数(只算出度)；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立； ⑤二叉树内节点的总数=边的总数+1； ⑥位于二叉树第k 层上的节点，最多有12-k 个(k>=1)； ⑦深度为k 的二叉树的节点总数最多为k 2-1个，最少k 个(k>=1)； ⑧如果有0n 个叶子，n2个2度节点，则0n=n2+1； 42.二叉树的节点遍历方法： 先根顺序（DLR ）； 中根顺序（LDR ）； 后根顺序（LRD ）； 43.哈夫曼树：用哈夫曼算法构造的最优二叉树； 44.最优二叉树的构造方法： ①将给定的权值按从小到大排序； ②取两个最小值分支点的左右子树(左小右大)，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值； ③重复②，直达所有权值构造完毕； 45.哈夫曼编码：在最优二叉树上，按照左0右1的规则，用0和1代替所有边的权值； 每个节点的编码：从根到该节点经过的0和1组成的一排编码；。
《离散数学》期末复习题一．选择题：1.下列句子为真命题的是（） A(a)能整除7 的正整数只有1 和7 本身。
(b) 胡戈由于导演了“无极”而于2005年获得奥斯卡金像奖。
(c) 买两张星期五去“大剧院”音乐会的票。
(d) 地球是宇宙中惟一存在生命的星球。
2．下列语句中是真命题的是（） DA．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的3．设P：我们划船，Q：我们跑步。
命题“我们不能既划船又跑步”符号化为（） B A．⎤ P∧⎤ QB．⎤ P∨⎤ QC．⎤（P↔Q）D．⎤（⎤ P∨⎤ Q）4．命题公式（P∧（P→Q））→Q是（） BA．矛盾式B．蕴含式C．重言式D．等价式5．在公式（）F（x，y）→（y）G（x，y）中变元x是（） BA．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6、下列语句不是命题的是（） AA.∀xP(x,y)B. ∀xP(x)C. （）F（x，y）→（y）G（x，y）D. ∀x (x2 - 1 > 0)7.集合X = {a, b, c, d}上的关系R = {(a, a), (b, c), (c, b), (d, d)} 是（） DA) 自反的、 B) 传递的、 C) 等价的 D) 对称的8、设R 是X = {1, 2, 3, 4}上的关系，x, y ∈X，如果x ≤ y，则(x, y)∈R。
下列关于关系R的说法错误的是：（） AA)关系R是等价关系，B) 关系R 是自反的C) 关系R 是传递的 D) 以上都不是。
9、集合X = {a, b, c}上的关系 R = {(a, a), (b, b), (c, c)}是（） DA) 自反的、非对称的；B) 自反的、非传递的C) 对称的、非传递的；D) 自反的、对称的和传递的10、令X={1,2,…,10}。
定义xRy的意义是3整除x-y。
则关系R是（） DA) 自反的、非对称的；B) 自反的、非传递的C) 对称的、非传递的D) 自反的、对称的和传递的11、下列S不是集合X＝{1, 2, 3, 4, 5, 6, 7, 8}的一个划分的是（） DA)S＝{{1, 4, 5}, {2, 6}, {3}, {7, 8}}B)S＝{{1, 4}, {2, 6}, {3,5}, {7, 8}}C)S＝{{1, 4, 5}, {2,3, 6}, {7, 8}}D)S＝{{1, 4}, {2, 6}, {3}, {7, 8}}12、从X = {1, 2, 3}到Y = {a, b, c, d}的函数 f = {(1, b), (3, a), (2,c)} 是( ) AA) 一对一的B) 映上的C) 双射D) 都不是13、设R是X＝{1, 2, 3, 4}上的关系，x, y∈X，如果x≤y，则(x,y)∈R。
离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。
其它疑问句、祈使句、感叹句、悖论等皆不是。
详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。
特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q →P；除非P否则Q，应为┐P→Q。
B设出原子命题写出符号化公式。
详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。
详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。
②对每个指派，以二进制数从小到大或从大到小顺序列出。
③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。
详见P8。
6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15,7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A B的充要条件是A B且B A。
主要等价式：(1)双否定：A A。
(2)交换律：A∧B B∧A，A∨B B∨A，A B B A。
3)结合律：(A∧B)∧C A ∧(B∧C)，(A∨B)∨C A∨(B∨C)，(A B)C A(B C)。
(4) 分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。
(5) 德·摩根律：(A∧B)A∨B，(A∨B)A∧B。
(6) 等幂律：A∧A A，A∨A A。
(7) 同一律：A∧T A，A∨F A。
(8) 零律：A∧F F，A∨T T。
(9) 吸收律：A∧(A∨B)A，A∨(A∧B)A。
(10) 互补律：A ∧A F，(矛盾律)，A∨A T。
(排中律)(11) 条件式转化律：A→B A∨B，A→B B→A。
《离散数学》期末复习一、期末考试题型试题类型及分数分别为单项选择题和填空题各有15题，分数占60％；化简解答题与计算题及证明题，共占40％。
各章分数的比例大致与其所用课时比例相同。
单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算。
单项选择题给出四个备选答案，其一正确。
填空题只需填写正确结论，不写计算、推论过程或理由。
化简解答题与计算题主要考核同学们的基本运算技能和速度，要求写出计算过程。
证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。
二、各章复习要求和重点第1章命题逻辑复习要求1. 命题及其联结词。
命题表述为具有确定真假意义的陈述句。
命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义，六个联结词。
2. 命题公式及分类。
在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；真值表3. 命题的判定及命题演算的推理理论。
推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.。
第2章一阶逻辑复习要求1.谓词与量词谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。
谓词是用来刻划个体词的性质或事物之间关系的词 量词，是在命题中表示数量的词，量词有两类：全称量词∀，表示“所有的”或“每一个”；存在量词∃，表示“存在某个”或“至少有一个”2. 2.公式与解释谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材).命题的符号化结果都是谓词公式.例如∀x(F(x)→G(x))，∃x(F(x)∧G(x))，∀x∀y(F(x)∧F(y)∧L(x,y)→H(x,y))等都是谓词公式3. 解释(赋值)，谓词公式A的个体域D是非空集合，则(1) 每一个常项指定D中一个元素；(2) 每一个n元函数指定D n到D的一个函数；(3) 每一个n元谓词指定D n到{0,1}的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值。
第一部分：集合论知识点：集合关系（∈，⊆,⊂,∉,=）集合运算（并、交、差、对称差、补集、幂集），特殊集合（∅，E，P(A)）集合恒等式（幂等律、交换律、结合律、分配律、吸收律、德摩根律、补交转换律(A-B=A⋂~B)、德·摩根律~(B⋃C)=~B~⋂C，A-(B⋃C)=(A-B)⋂(A-C)）证明集合包含或相等（根据定义, 通过逻辑等值演算证明、利用已知集合等式或包含式, 通过集合演算证明）1. 证:A⋃(B⋂C)=(A⋃B)⋂(A⋃C)证∀x x∈A⋃(B⋂C)⇔ x∈A∨(x∈B∧ x∈C) (并,交的定义)⇔(x∈A∨x∈B)∧(x∈A∨x∈C) (逻辑演算的分配律)⇔x∈(A⋃B)⋂(A⋃C)2. 证明(A-B)-C=(A-C)-(B-C)证(A-C)-(B-C)= (A ⋂ ~C) ⋂ ~(B ⋂ ~C) (补交转换律)= (A ⋂ ~C) ⋂ (~B ⋃ ~~C) (德摩根律)= (A ⋂ ~C) ⋂ (~B ⋃ C) (双重否定律)= (A ⋂ ~C ⋂ ~B) ⋃(A ⋂ ~C ⋂ C) (分配律)= (A ⋂ ~C ⋂ ~B) ⋃(A ⋂∅) (矛盾律)= A ⋂ ~C ⋂ ~B (零律,同一律)= (A ⋂ ~B) ⋂ ~C (交换律,结合律)= (A – B) – C第二部分：逻辑学命题的定义（凡具有确定真假意义的陈述句均称为命题。
）联结词（⌝、∧、∨、→、↔、↑、↓（公式转化为只含↑、↓的表达形式））例：将p → q化为只含↑的公式p → q ⇔⌝p ∨q⇔⌝(p∧⌝q) ⇔ p↑⌝q⇔p↑⌝( q∧q)⇔ p↑ q↑ q命题符号化(1、王晓虽然聪明，但不用功.2、张辉与王丽都是三好生.3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服.5、除非小王穿羽绒服，否则天不冷.)等值演算（幂等律、交换律、结合律、分配律、吸收律、蕴涵等值式A→B⇔⌝A∨B等价等值式A↔B⇔(A→B)∧(B→A)假言易位等值式A→B⇔⌝B→⌝A等价否定等值式A↔B⇔⌝A↔⌝B）证明p→(q→r) ⇔ (p∧q)→r证p→(q→r)⇔⌝p∨(⌝q∨r) （蕴涵等值式）⇔ (⌝p⌝∨q)∨r （结合律）⇔⌝(p∧q)∨r （德摩根律）⇔ (p∧q) →r （蕴涵等值式）判断下列公式的类型q⌝∧(p→q)解q⌝∧(p→q)⇔ q⌝∧(⌝p∨q) （蕴涵等值式）⇔ q∧(p⌝∧q) （德摩根律）⇔ p∧(q⌝∧q) （交换律，结合律）⇔ p∧0 （矛盾律）⇔ 0 （零律）该式为矛盾式.命题公式（重言式、矛盾式、可满足式），利用真值表判断，等值演算，范式。
离散数学期末复习要点与重点离散数学计算机科学与技术专业的一门统设必修学位课程，共60学时，开设一学期．该课程的主要内容包括：数理逻辑、集合论、图论等．第1章 命题逻辑复习要点1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定⌝P 、析取∨、合取∧、条件→、和双条件↔及其真值表，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．了解公式的概念(公式、赋值、成真赋值和成假赋值)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等值演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等值演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念以及和成真赋值、成假赋值的关系，熟练掌握它们的求法．命题公式的范式不惟一，但主范式是惟一的．5．了解C 是前提集合{A 1,A 2,…,A m }的有效结论或由A 1, A 2, …, A m 逻辑地推出C 的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论.第2章 谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词∀，存在量词∃.命题符号化注意：使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．在谓词公式∀xA 或∃xA 中，x 是指导变元，A 是量词的辖域．会区分约束变元和自由变元．在非空集合D (个体域)上谓词公式A 的一个解释或赋值有3个条件．在任何解释下，谓词公式A 取真值1，A 为逻辑有效式(永真式)；公式A 取真值0，A 为永假式；至少有一个解释使公式A 取真值1，A 称为可满足式．会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等． 掌握谓词演算的等值式和重言蕴含式．并进行谓词公式的等价演算．3．了解前束范式的概念，会求公式的前束范式的方法.若一个谓词公式F 等价地转化成 B x Q x Q x Q k k ...2211，那么B x Q x Q x Q k k ...2211就是F 的前束范式，其中Q 1，Q 2，…，Q k 只能是∀或∃，而x 1, x 2, …, x k 是个体变元，B 是不含量词的谓词公式．前束范式仍然是谓词公式．重点：谓词与量词，公式与解释，谓词演算．第3章 集合及其运算复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，∈与⊂(⊆),空集∅与所有集合等的关系. 空集∅，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ⊆， A 的所有子集构成的集合．若∣A ∣＝n ，则∣P (A )∣=2n ．2．熟练掌握集合A 和B 的并A ⋃B ，交A ⋂B ，补集~A (~A 补集总相对于一个全集).差集A －B ，对称差⊕，A ⊕B ＝(A －B )⋃(B －A )，或A ⊕B ＝(A ⋃B )－（A ⋂B ）等运算，并会用文氏图表示．掌握集合运算律.3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A ＝B ，只需证明A ⊆B ，又A ⊇B ；(2)通过运算律进行等式推导．重点：集合概念，集合的运算，集合恒等式的证明．第4章 关系与函数复习要点1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．有序对就是有顺序二元组，如<x , y >，x , y 的位置是确定的，不能随意放置．注意：有序对<a ，b >≠<b , a >，以a , b 为元素的集合{a , b }={b , a }；有序对<a , a >有意义，而集合{a , a }是单元素集合，应记作{a }．集合A ，B 的笛卡儿积A ×B 是一个集合，规定A ×B ＝{<x ,y >∣x ∈A ,y ∈B }，是有序对的集合.笛卡儿积也可以多个集合合成，A 1×A 2×…×A n ．2．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法．二元关系是一个有序对集合，},{B y A x y x R ∈∧∈><=，记作xRy ．空关系∅是唯一、是任何关系的子集的关系；全关系},,{A b a b a E A ∈><=A A ⨯≡；恒等关系},{A a a a I A ∈><=，恒等关系的矩阵M I 是单位矩阵．关系的集合运算有并、交、补、差和对称差．复合关系}),,(,{2121R c b R b a b c a R R R >∈<∧>∈<∃><=•=；复合关系矩阵：21R R R M M M ⨯=(按布尔运算)；有结合律：(R •S )•T ＝R •(S •T )，一般不可交换．逆关系},,{1R y x x y R >∈<><=-；逆关系矩阵满足：T R R M M =-1；复合关系与逆关系存在：(R •S )－1=S －1•R －1．3．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包的定义和求法．注：(1)关系性质的充分必要条件：① R 是自反的⇔I A ⊆R ；②R 是反自反的⇔I A ⋂R ＝∅；③R 是对称的 ⇔R ＝R －1；④R 是反对称的⇔R ⋂R －1⊆I A ；⑤R 是传递的⇔R •R ⊆R .(2)I A 具有自反性，对称性、反对称性和传递性．E A 具有自反性，对称性和传递性．故I A ，E A 是等价关系．∅具有反自反性、对称性、反对称性和传递性．I A 也是偏序关系．4．理解等价关系和偏序关系概念，理解集合上等价关系与划分一一对应的关系、掌握划分的求法和做偏序集哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、上界和下界、最小上界和最大下界．等价关系和偏序关系是具有不同性质的两个关系.⎩⎨⎧==+⎭⎬⎫⎩⎨⎧+偏序关系等价关系传递性反对称性对称性自反性 知道等价关系图的特点和等价类定义，会求等价类．一个子集的极大(小)元可以有多个，而最大(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大(小)元，极大(小)元．5．理解函数概念：函数(映射)，函数相等，复合函数和反函数。
离散数学课程测试题一、判断（）1. 若wff A是可满足式，那么~A是矛盾式。
（）2. P=>P∨Q是合适公式。
（）3.∃x(A(x)→B)→(∃xA(x) →B)是重言式。
（）4. 可满足式的代入实例一定是可满足式。
（）5. wff A(P)=P的对偶式为~P。
（）6. 若A*和B*是wff A和B的对偶式，且A=>B，则A*=>B*。
（）7. 重言式的主析取范式为T。
（）8. 空集是非空集合的一个元素。
（）9. 设A和X是集合，则X∈2A iff X⊂A。
（）10. 设A、B、C和D是四个非空集合, 且A×C ⊂B×D，则A⊂B且C⊂D。
（）11. 传递关系的对称闭包仍是传递的。
（）12. 非空集合上的关系不是对称的，则必是反对称的。
（）13. 若R和S是二个有完全相同的二元组的集合，则称它们是相等的二元关系。
（）14. 设Ａ是一个非空集合，则Ａ上的等价关系都不是偏序关系。
（）15. 有限集上的全序关系必是良序关系。
（）16. 有限集上的偏序关系必是全序关系。
（）17 . <A;R>是偏序集，则Ａ的任何非空子集必有极小元。
（）18. <A;R>是偏序集，则Ａ的非空子集Ｂ的上确界必是Ｂ的最大元。
（）19. <A;R>是全序集，则Ａ的任何非空子集必有唯一极小元。
（）20. <A;R>是全序集，则Ａ的非空子集Ｂ的下确界必是Ｂ的最小元。
（）21. 无限集必与它的真子集等势。
（）22. 若A⊂B，且A与B等势，则B是无限集。
（）23. 若A⊂B，则#A<#B。
（）24. 连通的4度正则图一定没有桥。
（）25. p阶图的直径不可能等于p。
二、选择（）1. 是wff （P→Q）∧R∧(S→(P→Q))的代入实例的有①P∧R∧(S→P) ②(~P→Q)∧~R∧(~S→(~P→Q))③(P→Q)∧S∧(R→(P→Q)) ④(P→Q)∧R∧(R→(P→Q))（）2. 与公式∃x ((P(x)∧∀y Q(y))∧∀z R(z)) →S(t)等价的有：①∃u ((P(u)∧∀y Q(y))∧∀z R(z)) →S(t)②∃u ((P(u)∧∀u Q(u))∧∀z R(z)) →S(t)③∃u ((P(u)∧∀u Q(u))∧∀u R(u)) →S(t)④∃u ((P(u)∧∀u Q(u))∧∀u R(u)) →S(u)（）3. 下列关系中正确的有：①{a}∈{a, {a}} ②{a}⊆{a, {a}}③{a}∈{a, {{a}}} ④{a}⊆{a, {{a}}}⑤{a}∈{{a}, {{a}}} ⑥{a}⊆{{a}, {{a}}}（）4.设A=P(P(P(Φ)))，下列关系式中正确的有：①Φ∈A ②Φ⊆A ③{Φ}∈A④{Φ}⊆A ⑤{{Φ}}∈A ⑥{{Φ}}⊆A（）5.下列说法中正确的有：①任何集合都不是它自身的元素②任何集合的幂集都不是空集③若Ａ×Ｂ＝Φ，则Ａ＝Ｂ＝Φ④任意两集合的笛卡尔积都不是空集（）6. {1,2,3,4,5}上的关系R={<1,1>,<1,3>,<2,3>}是①自反的②反自反的③对称的④反对称的⑤传递的（）⒎空集上的空关系是关系。
测试三一、填空题1、二极管加正向电压，二极管（导通），相当于开关（闭合）；二极管加反向电压，二极管（截止），相当于开关（断开）。
2、在模拟电路中，主要利用三极管的（放大）状态，在数字电路中，则利用三极管的（饱和）和（截止），实现输出端高、低电平的转换。
工作在（截止区）时，相当于开关断开，工作在（放大区）时，相当于开关闭合。
3、在模拟电路中，主要利用MOS的（截止）状态，在数字电路中，则利用MOS 的（可变电阻区）和（恒流区），实现输出端高、低电平的转换。
工作在（）时，相当于开关断开，工作在（）时，相当于开关闭合。
4、三态门包括（高电平）、（低电平）和（高阻态）三态。
5、根据电路的逻辑功能的不同，数字电路分为两类：（组合逻辑电路）和（时序逻辑电路）。
6、产生竞争冒险的原因是（时间延迟）。
7、数码管分为（）和（），其中（）数码管是高电平有效。
8、七段显示译码器74LS48是一种与（）数码管配合使用的集成译码器。
9、7段共阴极数码管abcdefg分别为1111001时，显示的数字为（）。
10、试灯输入端LT低电平有效，表明当为（）时，无论输入端状态怎样，数码输出端全为高电平，数码管全亮。
11、8选1数据选择器的数据输入端有（8）个，地址输入端有（3）个。
12、JK触发器的逻辑功能有（置0）（置1）（保持）和（）。
13、JK触发器转换为D触发器时，J=（D），K=（D非）。
14、JK触发器转换为T触发器时，J=（T），K=（T）。
15、时序逻辑电路由（组合逻辑电路）和（触发器电路）两部分组成，其中（触发器电路）必不可少。
16、时序逻辑电路根据触发器元件的动作特点的不同，可以分为（同步时序逻辑电路）和（异步时序逻辑电路）。
17、半导体存储器分为（只读存储器）和（随机存储器）。
18、只读存储器主要由（地址译码器）和（存储矩阵）两部分组成。
19、随机存储器主要由（地址译码器）（存储矩阵）和（控制电路）三部分组成。
离散数学期末复习要点与重点离散数学是计算机科学及其他相关学科中的一门重要的基础课程。
它主要研究离散的结构和对象，以及它们之间的关系和性质。
离散数学的核心内容包括集合论、关系、图论、布尔代数和逻辑等。
下面是离散数学期末复习的要点与重点。
一、集合论1.集合的基本概念，包括元素、子集、幂集、集合的运算等。
2.集合的性质，如交换律、结合律、分配律等。
3.集合的表示方法，包括列举法、描述法、特征函数法等。
4.集合的运算，如并、交、差、对称差等。
5.集合的关系，包括子集关系、相等关系、真子集关系等。
二、关系1.关系的基本概念，包括序偶、笛卡尔积、关系的定义等。
2.关系的性质，如自反性、对称性、传递性等。
3.关系的表示方法，包括关系矩阵、关系图、关系表等。
4.关系的运算，如复合、逆、幂等等。
5.等价关系和偏序关系的特性和性质。
6.关系的闭包，包括自反闭包、对称闭包、传递闭包等。
三、图论1.图的基本概念，包括顶点、边、路径、环等。
2.不同类型的图，包括无向图、有向图、简单图、多重图等。
3.图的表示方法，包括邻接矩阵、邻接表等。
4.图的遍历算法，包括深度优先（DFS）和广度优先（BFS）。
5. 最小生成树算法，包括Prim算法和Kruskal算法。
6. 最短路径算法，包括Dijkstra算法和Floyd-Warshall算法。
四、布尔代数1.布尔代数的基本运算，包括与、或、非等。
2.布尔函数的最小项和最大项表示方法。
3.布尔函数的化简，包括代数化简和卡诺图化简。
4.布尔函数的特性，包括恒等律、零律、单位律等。
5.布尔函数的逻辑门电路实现，包括与门、或门、非门等。
五、逻辑1.命题逻辑的基本概念，包括命题、命题变量、逻辑联结词等。
2.命题逻辑的语法，包括命题公式的形式化定义和语法规则。
3.命题逻辑的证明方法，包括直接证明、间接证明、反证法等。
4.谓词逻辑的基本概念，包括谓词、量词、合取范式等。
5.谓词逻辑的语义，包括赋值、满足关系等。
《离散数学》期末复习第一篇：《离散数学》期末复习《离散数学》期末复习内容：第一章~第七章题型：一、选择题（20%，每题2分）二．填空题（20%，每题2分）三、计算题（20%，每题5分）四、证明题（20%，每题5分）五、判断题（20%，每题2分）第1章数学语言与证明方法1.1 常用的数学符号1.计算常用的数学符号式子 1.2 集合及其表示法1.用列举法和描述法表示集合2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集(∅)4.计算集合的幂集5.求集合的运算：并、交、相对补、对称差、绝对补6.用文氏图表示集合的运算7.证明集合包含或相等方法一：根据定义, 通过逻辑等值演算证明方法二：利用已知集合等式或包含式, 通过集合演算证明1.3 证明方法概述1、用如下各式方法对命题进行证明。
π直接证明法：A→B为真π间接证明法：“A→B为真” ⇔“ ¬B→¬A为真” π归谬法(反证法)： A∧¬B→0为真π穷举法： A1→B, A2→B,…, Ak→B 均为真π构造证明法：在A为真的条件下, 构造出具有这种性质的客体B π空证明法：“A恒为假” ⇒“A→B为真” π平凡证明法：“B恒为真” ⇒“A→B为真” π数学归纳法：第2章命题逻辑2.1 命题逻辑基本概念1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。
命题的定义和联结词(¬, ∧, ∨, →, ↔)2、判断命题公式的类型赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。
2.2 命题逻辑等值演算1、用真值表判断两个命题公式是否等值2、用等值演算证明两个命题公式是否等值3、证明联结词集合是否为联结词完备集 2.3 范式1、求命题公式的析取范式与合取范式2、求命题公式的主析取范式与主合取范式（两种主范式的转换）3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效第3章一阶逻辑3.1 一阶逻辑基本概念1、用谓词公式符号命题（正确使用量词）2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算1、证明谓词公式的等值式2、求谓词公式的前束范式第4章关系4.1 关系的定义及其表示1、计算有序对、笛卡儿积2、计算给定关系的集合3、用关系图和关系矩阵表示关系 4.2 关系的运算1、计算关系的定义域、关系的值域2、计算关系的逆关系、复合关系和幂关系3、证明关系运算满足的式子 4.3 关系的性质1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系1、判断关系是否为等价关系2、计算等价关系的等价类和商集3、计算集合的划分4、判断关系是否为偏序关系5、画出偏序集的哈期图6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界7、求偏序集的拓扑排序第5章函数1.判断关系是否为函数2.求函数的像和完全原像3.判断函数是否为满射、单射、双射4.构建集合之间的双射函数5.求复合函数6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系7.判断函数的反函数是否存在，若存在求反函数第6章图1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度3.根据握手定理顶点数、边数等4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边5.判断给定的度数列能否构成无向图6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图7.求给定图的补图、生成子图、导出子图8.判断两个图是否同构6.2 图的连通性1.求图中给定顶点通路、回路的距离2.计算无向图的连通度、点割集、割点、边割集、割边3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示1.计算无向图的关联矩阵2.计算有向无环图的关联矩阵3.计算有向图的邻接矩阵4.计算有向图的可达矩阵5.计算图的给定长度的通路数、回路数6.4 几种特殊的图1、判断无向图是否为二部图、欧拉图、哈密顿图第7章树及其应用 7.1 无向树1.判断一个无向图是否为树2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系3.给定无向树的度数列，画出非同构的无向树4.求生成树对应的基本回路系统和基本割集系统5.求最小生成树 7.2 根树及其应用1.判断一个有向图是否为根树2.求根树的树根、树叶、内点、树高3.求最优树4.判断一个符号串集合是否为前缀码5.求最佳前缀码6.用三种方法遍历根树第二篇：离散数学期末复习试题及答案(二)第二章二元关系1.设A={1,2,3,4},A上二元关系R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y=x2} 求R⋅S,S⋅R,S⋅R⋅S,S2,S3,S⋅Rc。
《离散数学》期末复习提要课程的主要内容1、集合论部分（集合的基本概念和运算、二元关系和函数）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本概念、特殊的图，树及其性质）。
一、各章复习要求与重点第一章命题逻辑[复习知识点]１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题２、命题公式与解释，真值表，公式分类（永真、矛盾、可满足），公式的等价３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）５、全功能集６、推理理论本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、推理理论[复习要求]１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。
３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。
４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。
掌握24个重要等值式。
５、掌握推理理论，会写出推理的证明，掌握附加前提证明法和归谬发。
[本章重点习题]习题P31-36: 1.1,1.7-1.9,1.12,1.18,1.19，1.15 [疑难解析]1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。
具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。
二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
