离散数学期末总复习PPT课件

期末考试的题型 一 选择题 10题 2分 二 填空题 5题 2分 三 计算题 5题 9分 四 证明题 2题 8分 五 综合题 1题 9分 第一部分 1 命题 指真假唯一的陈述句 1 否定 2 5个逻辑联结词及其真值表 2 合取 0 0 0 1 3 析取 0 1 1 1 4 蕴含 1 1 0 1 只要p 就有q p q P仅当q 只有p 才q 除非p 才有q 除非p 否则没有q p q q p q p q p 5 等价 1 0 0 1 3 真值表 大题 p q r 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 例1写出真值表 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 4 定义 1 若A在它的任何赋值下均为真 则称A为重言式或永真式 2 若A在它的任何赋值下均为假 则称A为矛盾式或永假式 3 若A不是矛盾式 则称A是可满足式 5 主析取范式与主合取范式 大题 相关知识点 1 等值式 分配律A B C A B A C A B C A B A C 蕴涵等值式A B A B 假言易位A B B A 2 析取范式与合取范式 文字 命题变项及其否定的总称 例如 p q r p q r 例如 p q p q p q r 例如 p q p q p q r 简单合取式 有限个文字构成的合取式 简单析取式 有限个文字构成的析取式 析取范式 由有限个简单合取式组成的析取式 例如 p p q p q p q p q r q r 合取范式 由有限个简单析取式组成的合取式 例如 p p q p q p q p p q r 范式 析取范式与合取范式的总称 3 主析取范式与主合取范式 在含有n个命题变项的简单合取式 简单析取式 中 若每个命题变项和它的否定式恰好出现且仅出现一次 而且命题变项和它的否定式按下标从小到大或按字典顺序排列 称这样的简单合取式 简单析取式 为极小项 极大项 每个极小项只有一个成真赋值 用m表示 每个极大项只有一个成假赋值 用M表示 用mi表示第i个极小项 其中i是该极小项成真赋值的十进制表示 用Mi表示第i个极大项 其中i是该极大项成假赋值的十进制表示 mi Mi 称为极小项 极大项 的名称 主析取范式 由极小项构成的析取范式 主合取范式 由极大项构成的合取范式 2 若某个Bj既不含pi 又不含 pi 则将Bj展开成Bj Bj pi pi Bj pi Bj pi 重复这个过程 直到所有简单合取式都是长度为n的极小项为止 3 消去重复出现的极小项 即用mi代替mi mi 4 将极小项按下标从小到大排列 1 求A的析取范式A B1 B2 Bs 其中Bj是简单合取式j 1 2 s 求公式主析取范式的步骤 设公式A含命题变项p1 p2 pn 例2 1 求公式A p q r的主析取范式 解 p q p q r r p q r p q r m6 m7 r p p q q r p q r p q r p q r p q r m1 m3 m5 m7 所以A p q r m1 m3 m5 m6 m7 求公式的主合取范式的步骤 设公式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的主合取范式 A p q r p r p r q r p q r p q r p q q r M0 M2 q r p p q r M0 M4 p q r p q r A p q r M0 M2 M4 6 联结词完备集 设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 推论以下都是联结词完备集 1 S1 2 S2 3 S3 4 S4 5 S5 不是联结词完备集 7 自然推理系统P 大题 假言推理 A B A B 拒取式规则 例4构造推理的证明 课本54页18题 8 一阶逻辑命题符号化 例5将下面两个命题符号化 1 凡人都呼吸 2 有的人用左手写字 解 令M x 是人 F x x呼吸 G x x用左手写字 于是 1 2 的符号化形式分别为 M x F x M x F x 例6将下列命题符号化 1 有的兔子比所有的乌龟跑得快 2 并非兔子都比乌龟跑得快 解 令F x x是兔子 G y y是乌龟 H x y x比y跑得快 这2个命题分别符号化为 9 辖域 自由与约束 在公式 xA和 xA中 称x为指导变元 A为相应量词的辖域 在 x和 x的辖域中 x的所有出现都称为约束出现 A中不是约束出现的其他变项均称为是自由出现的 例7指出下列各公式中的指导变元 各量词的辖域 自由出现以及约束出现的个体变项 x是指导变元 量词 x的辖域是F x y G x z 其中 x是约束出现的 y和z均为自由出现的 x F x y G x z 定义设A B为集合 A与B的差运算定义如下 A B x x A x B 由定义可知A B A A B 1 集合的运算 第二部分 定义设A B为集合 A与B的对称差集A B 定义为A B x x A B x A B 也可定义为A B A B B A 也可定义为A B A B A B 2 有穷集的计数 大题 例8某班有25个学生 其中14人会打篮球 12人会打排球 6人会打篮球和排球 5人会打篮球和网球 还有2人会打这三种球 已知6个会打网球的人都会打篮球或排球 求不会打球的人数 解 2 4 3 5 1 0 5 5 所以不会打球的人数是5个人 3 关系的运算 大题 1 R中所有有序对的第一元素构成的集合称为R的定义域 domain 记为domR 2 R中所有有序对的第二元素构成的集合称为R的值域 range 记作ranR 3 R的定义域和值域的并集称为R的域 field 记作fldR 例如R 则domR 1 2 4 ranR 2 3 4 fldR 1 2 3 4 4 设F G为二元关系 G对F的复合记作F G 其中F G y F G 例9 课本131页16题 4 幂运算的性质 定理设R是A上的关系 若存在自然数s t s t 使得Rs Rt 则 1 对任何k N有Rs k Rt k 2 对任何k i N有Rs kp i Rs i 其中p t s 例10 若R3 R7 试化简R2013 解 由R3 R7可知p 7 3 4因此 2013 3 2010 3 4 502 2R2013 R3 2 R5 5 关系的性质 设R为A上的关系 1 自反性与反自反性 1 若 x x A R 则称R在A上是自反的 2 若 x x A R 则称R在A上是反自反 2 对称性与反对称性 1 若 x y x y A R R 则称R为A上对称的关系 2 若 x y x y A R R x y 则称R为A上反对称的关系 3 传递性若 x y z x y z A R R R 则称R是A上的传递关系 设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 关系的闭包 设R为非空集合上的关系 如果R是自反的 对称的和传递的 则称R为A上的等价关系 7 等价关系 大题 A上的等价关系与A的集合划分是一一对应的 例11课本133页36题 1 例12A 1 2 3 上等价关系有多少个 解如下图 做出A的所有划分 因此A 1 2 3 上等价关系有5个 8 偏序关系 1 哈斯图 大题 特点 1 每个结点没有环 2 两个连通的结点之间的序关系通过结点位置的高低表示 位置低的元素的顺序在前 即 若x y 则x画在y的下层 3 具有覆盖关系的两个结点之间连边 2 最小元 最大元 极小元 极大元设为偏序集 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的极大元 例13 课本135页46题 设G 为一无向图 v V 称v作为边的端点的次数之和为v的度数 简称为度 记为d v 设D 为有向图 v V 称v作为边的起点的次数之和为v的出度 记为d v