离散数学期末总复习.ppt

析取范式——由有限个简单合取式组成的析取式 主析取范式——由极小项构成的析取范式 例2 (1) 求公式 A=(p ? q) ∨r 的主析取范式 求公式的主合取范式的步骤: 设公式A含命题变项p1,p2,…,pn (1) 求A的合取范式A?=B1?B2? … ?Bs , 其中Bj是简单析取式 j=1,2, … ,s (2) 若某个Bj既不含pi, 又不含?pi, 则将Bj展开成 Bj ? Bj?(pi??pi) ? (Bj?pi)?(Bj??pi) 重复这个过程, 直到所有简单析取式都是长度为n的极大项为止 (3) 消去重复出现的极大项, 即用Mi代替Mi?Mi (4) 将极大项按下标从小到大排列 例3 （2）求公式 A =(p ? q) ∨r的主合取范式 例6 将下列命题符号化: ? (1)有的兔子比所有的乌龟跑得快. ??(2)并非兔子都比乌龟跑得快. 在公式 ?xA和?xA 中，称x为指导变元，A为相应量词的辖域. 在?x和?x的辖域中, x 的所有出现都称为约束出现. A中不是约束出现的其他变项均称为是自由出现的. 例 7 指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项: 定义 设A,B为集合,A与B的差运算定义如下: 定义 　设A, B为集合, A与B 的对称差集 A⊕B,定义为 A⊕B = {x|x∈ A∪B ∧x ? A∩B } 设R为非空集合上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系. 例12 A＝{1,2,3}上等价关系有多少个？ 解 如下图, 做出A的所有划分： （1）哈斯图 （大题） 特点： （1）每个结点没有环; （2）两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前, 即：若x y ,则x画在y的下层; （3）具有覆盖关系的两个结点之间连边. （2）最小元、最大元、极小元、极大元 设A,?为偏序集, B?A, y∈B. （1）若?x(x∈B→y?x)成立, 则称y为B的最小元. （2）若?x(x∈B→x?y)成立, 则称y为B的最大元. （3）若?x(x∈B∧x?y→x=y)成立, 则称y为B的极小元. （4）若?x(x∈B∧y?x→x=y)成立, 则称y为B的极大元. 设G=V，E为一无向图，?v?V，称v作为边的端点的次数之和为v的度数，简称为度，记为d(v)。 设D=V,E为有向图，?v?V，称v作为边的起点的次数之和为v的出度，记为d-(v) 称v作为边的终点的次数之和为v的入度，记为d+(v) 称d+(v)+d-(v)为v的度数，记作d(v)。 （无向图握手定理）设G=V，E为任意的无向图，V={v1, v2,…, vn}，|E|=m，则 设R是非空集合A上的关系, R的自反（对称或传递）闭包是A上的关系R?, 使得R?满足以下条件： （1）R?是自反的（对称的或传递的） （2）R?R? （3）对A上任何包含R的自反（对称或传递）关系R?? 有R??R??. 一般将R的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R). 6、关系的闭包 7、等价关系（大题） A上的等价关系与A的集合划分是一一对应的. 例11 课本133页36题（1） 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 因此 A＝{1,2,3}上等价关系有5个. 8、偏序关系 例13 (课本135页46题) 1、顶点的度 第五部分 （有向图握手定理）设D=V，E为任意的有向图，V={v1, v2,…, vn}，|E|=m，则 2、握手定理 期末考试的题型： 一、选择题：10题*2分 二、填空题：5题*2分 三、计算题：5题*9分 四、证明题：2题*8分 五、综合题：1题:9分 第一部分 1、命题 指真假唯一的陈述句。 （1）否定“ ┐” 2、5个逻辑联结词及其真值表 p ┐ p 0 1 1 0 （2）合取“ ∧ ” p q p∧q 0 0 1 1 0 1 0 1 0 0 0 1 (3)析取“∨ ” p q P∨q 0 0 1 1 0 1 0 1 0 1 1 1 （4）蕴含 “→ ” p q P→q 0 0 1 1 0 1 0 1 1 1 0 1 只要p,就有q. p→q P仅当q. 只有p,才q. 除非p,才有q. 除非p,否则没有q. p→q q→p q→