《离散数学》总复习.ppt

adfadffd 离散数学 总复习 adfadffd 第一部分数理逻辑 包括命题逻辑和谓词逻辑 一 离散数学的主要内容有哪些 离散数学的主要内容可以分为四个部分 第二部分集合论 包括集合 关系和函数 第三部分代数系统 包括代数系统的一般概念 几类典型的代数系统 第四部分图论 包括图的基本概念 几种特殊的图 adfadffd 二 考试 1 题型考试试题的题型有 单项选择题 10道题 占10分 填空题 共10个空 占10分 计算题 共4小题 占20分 证明题 共5题 占30分 2 难易程度考试题的难度不会超过教材 参考书和模拟试题的难度 以简单题占60 较难题占30 难题占10 3 考试范围考试试题覆盖 离散数学 的全部内容 adfadffd 第一部分数理逻辑 一 内容提要1 命题及其联结词 非 与 或 单条件 双条件 2 命题公式的析取范式和合取范式 主范式 3 命题公式间的等价关系和蕴含关系 4 命题演算的推理理论 5 谓词公式的有关概念 量词 谓词 变元 真值指派等 6 谓词公式间的等价关系和蕴含关系 7 谓词演算的推理理论 adfadffd 二 重点和难点1 命题公式间的等价关系和蕴含关系 2 命题演算的推理理论 包括命题符号化 3 谓词公式间的等价关系和蕴含关系 4 谓词演算的推理理论 包括命题符号化 adfadffd 三 例题1 证明推理 x P x Q x R x x P x x P x R x 证 x P x P P c ES x P x Q x R x P P c Q c R c US Q c R c T I R c T I P c R c T I x P x R x EG adfadffd 2 证明推理 P Q R S Q P R R P Q证 RP Q P RP Q P T I R ST I P Q R S P P QT I P QT I adfadffd 第二部分集合论 集合论包括集合 二元关系和函数 它们之间的关系是 二元关系是一种特殊的集合 集合中的元素都是序偶 函数是一种特殊的二元关系 一 内容提要1 集合的两种表示方法 列举法和描述法 2 特殊的集合 空集 全集 子集和幂集 3 集合的运算 并 交 差和对称差 各种运算的性质 4 集合运算的基本定律 交换律 结合律 分配律 吸收律 德 摩根律等 5 有序n元组 n维笛卡尔积 6 关系的定义 笛卡尔积的子集 adfadffd 7 关系的表示方法 集合 矩阵和关系图 8 关系的性质 自反性 反自反性 对称性 反对称性和传递性 9 关系的运算 复合运算 逆运算和闭包运算 10 特殊的二元关系及其相关特性 等价关系 自反性 对称性 传递性 偏序关系 自反性 反对称性 传递性 等价类 偏序关系中的特殊元素 极大元 上界等 11 函数的定义 函数的定义域和值域 12 函数的性质 单射 满射和双射 13 函数的运算 复合函数 逆函数 14 集合的基数 adfadffd 二 重点和难点1 掌握元素与集合之间的关系 集合与集合之间的关系 2 运用集合运算的基本定律去化简集合表达式或证明集合等式 3 掌握二元关系的五个性质和二元关系的运算 4 等价关系的证明 等价类的求解 偏序关系的特定元素的求解 5 函数的性质 求复合函数和逆函数 adfadffd 三 例题1 这两个关系是否正确 答 正确 在 中 表示元素 在 中 表示空集 2 求R 的传递闭包 解 R的传递闭包 注意 求传递闭包是一个不断重复合并有序对的过程 有序对往往被漏掉 3 化简集合表达式 A B A B B A B B 解 A B A B B A B B 吸收律和零律 A A U 同一律 A A U 零律 U U adfadffd 4 设集合A a b c d e 偏序关系R的哈斯图如图所示 若A的子集B c d e 求 1 用列举法写出偏序关系R的集合表达式 2 写出集合B的极大元 极小元 最大元 最小元 上界 下界 上确界 下确界 解 1 R IA 2 集合B的极大元 c 极小元 d e 最大元 c 最小元 无 上界 c a 上确界 c 下界 无 下确界 无 adfadffd 5 已知f R R且f x x 4 3 2 已知g R R且g x 3x 5 求 f与g的合成函数 并求3在f与g的合成函数下的函数值 解 1 f g R R 且 f g x g f x g x 4 3 2 3 x 4 3 2 5 3 x 4 3 1 f g 3 3 3 4 3 1 1028 adfadffd 第三部分代数系统 一 内容提要1 代数系统的定义 封闭性 特殊元素 幺元 零元 逆元 幂等元 2 代数系统之间的关系 子代数 同态 单同态 满同态 同构 3 同余关系的定义和商代数 4 半群 独异点和群的定义及其相互间的关系 5 群的基本性质 消去律 元素的阶 6 循环群的性质及生成元 7 子群的定义及判定方法 正规子群的定义及判定方法 子群的陪集 拉格朗日定理 adfadffd 8 环和域的定义 9 子环的定义及其判定方法 10 格的定义及其性质 11 特殊的格 分配格 有界格 有补格 有补分配格 12 布尔代数及其性质 二 重点和难点1 代数系统的定义及特异元素 如何证明两个代数系统同态与同构 2 循环群的定义及其性质 3 子群的定义及其判定方法 4 格的定义及其性质 adfadffd 三 例题1 设R是实数集 在R上定义二元运算 x y R 定义x y x y 2xy 试说明 是否满足结合律 交换律 是否存在幺元 若存在请求出幺元 解 x y z R x y z x y 2xy z x y 2xy z 2 x y 2xy z x y z 2yz 2x y z 2yz x y z 2yz x y z 运算可结合 x y x y 2xy y x 运算可交换 设幺元为e x R e x x e x e 2xe x 由x的任意性 得e 0 R 幺元为0 adfadffd 2 给定代数系统U V W 设f X Y是从U到V的同态 g Y Z是从V到W的同态 则g f X Z必是从U到W的同态 证 对任意的a b X 证明 g f a b g f a g f b g f a b g f a b g f a f b f是同态映射 g f a g f b g是同态映射 g f a g f b adfadffd 3 设是群 a b G 且 a b 2 a2 b2 证明a b b a 证 因为群满足消去律 所以 a b 2 a2 b2 a b a b a a b b 因 可结合 a b a b a a b b 群满足左右消去律 b a a b adfadffd 4 设 运算是X中的可结合的二元运算 并且对任意的x y X 若x y y x 则x y 证明 X中的每个元素都是等幂的 证 对任意的x X 要证明x是等幂的 即证明 x x x因为 运算是X中的可结合的二元运算所以 x x x x x x由已知 x y y x x y得 x x x adfadffd 5 设是个代数系统 使得对任意的a b c d A有 a a a a b c d a c b d 证明 a b c a b a c 证 左式 a b c 因为a a a a a b c 因为 a b c d a c b d a b a c 右式 adfadffd 6 设 为集合 证明 X 与 X 是同构的 证 对任意的S X 设f S S 1 来证f是个同态映射 即证 f S1 S2 f S1 f S2 f S1 S2 S1 S2 S1 S2 f S1 f S2 2 来证f是个双射函数任取S1 S2 X 且S1 S2 f S1 S1 f S2 S2因为S1 S2 所以 S1 S2 即f S1 f S2 故f是单射的 又因为f是 X 到 X 的自身的映射 故f是满射的 即f为双射 adfadffd 7 设是半群 对于A中的每一个元素a和b 若a b 则a b b a a b b a a b 1 证明对于A中的一切a 有a a a 2 对于A中任意的a和b 证明a b a a 3 对于A中任意的a b和c 证明a b c a c 证 1 a a a因为是半群 运算可结合 所以 a a a a a a a a a adfadffd 2 证明 对于A中任意的a和b 证明a b a a 证 能推出 a b a a a a b a 即可 a b a a 运算可结合 a b a a a b a 由 1 知 a a b a 由 1 知 a a b a 由提示 即 a b a a a a b a 故有a b a a adfadffd 3 对于A中任意的a b和c 证明a b c a c 证 能推出 a b c a c a c a b c 即可 a b c a c 运算可结合 a b c a c 由 2 a b c 由 2 a c a b c 运算可结合 a c a b c 由提示 即 a b c a c a c a b c 故 a b c a c adfadffd 8 设是一个群 b G 定义函数f G G且给定成 对任意的x G f x b x b 1 证明 f是从到的一个同构映射 证 1 显然与同类型 2 单射 对任意的x y G 证明 f x f y x yf x f y b x b 1 b y b 1 消去律 x b 1 y b 1 消去律 x y adfadffd 3 满射 f G G f x b x b 1 对任意的y G 证明 在G中至少存在一个原像b 1 y b 使得 f b 1 y b b b 1 y b b 1 b b 1 y b b 1 e y e y adfadffd 4 证明f是个同态映射 即 运算的像 像的运算 对任意的x y Gf x y b x y b 1 由f的定义 b x e y b 1 群中存在幺元e b x b 1 b y b 1 b x b 1 b y b 1 结合律 f x f y 由f的定义 或 f x y b x y b 1f x f y b x b 1 b y b 1 因 可结合 b x b 1 b y b 1 b x e y b 1 b x y b 1 adfadffd 第四部分图论 一 内容提要1 图的基本概念 无向图 有向图 简单图 结点的度数 子图 补图 图的同构 2 握手定理 所有结点的度数之和等于边数的2倍 3 图的连通性 割边 割点 边割集 点割集 通路 回路 连通分支 4 图的矩阵表示 邻接矩阵 关联矩阵 5 欧拉图和哈密尔顿图的定义和判定条件 6 树的定义 性质 判定条件和遍历 7 二部图和平面图的定义 性质和判定条件 adfadffd 二 重点和难点1 掌握图的基本概念 2 运用握手定理解题 3 利用图的矩阵求两个结点间的通路条数 4 欧拉图和哈密尔顿图的判定 5 树的遍历方法 adfadffd 三 例题1 设T是完全2杈树 有t片树叶 i个分支点 证明 i t 1 即 在完全2杈中 分支结点数比树叶数少1 证 由握手定理知 2 t i t 1 t 3 2m 2 t i 1 即 t 3i 1 2t 2i 2解得 i t 12 设T是完全2杈树 有t片树叶 i个分支点 证明T的边数m 2t 2 证 设T有m条边 根据握手定理可得 2 t i t 1 t 3 2m即 3i t 1 2m i t 13 t 1 t 1 2m 4t 4 2m解得 m 2t 2 故结论成立 adfadffd 3 在n阶简单有向图中 完全有向图的边数为n n 1 证 完全有向图中任意两个结点间都有方向相反的两条边 所以 m 2Cn2 2 n n 1 2 n n 1 4 对于 n n 1 的图G 则G中至少有一个点的度大于等于3 证 现假设图G中所有结点的度均小于3 即 2 由握手定理知 2 n 1 矛盾 2n 又因为 则 即得 2 n 1 2n adfadffd 5 设n阶无向图G有m条边 其中 nk个结点的度为k 其余结点的度为k 1 证明 nk n k 1 2m证 由握手定理知 nk k n nk k 1 2m整理得 nk n k 1 2m 6 一棵树有2个点的度为2 1个点的度为3 3个点的度为4 其余结点的度为1 问该树有多少度为1的点 解 设有x个结点的度为1 则 2 2 1 3 3 4 x 1 2 2 1 3 x 1 19 x 10 2x解得 x 9 adfadffd 7 证明在完全2杈树中 边的总数m 2 nt 1 证 设完全2杈树有m条边 则有m 1个结点根结点的度为2 叶结点的度为1 其余结点的度为3 则 2 nt m 1 1 nt 3 2m2 nt 3m 3nt 2m解得 m 2 nt 1 adfadffd 3 每个自然数不是奇数就是偶数 如果自然数是偶数 当且仅当它能被2整除 并非每个自然数都能被2整除 因此 有的自然数是奇数 提示 P x x是自然数 Q x x是奇数 R x x是偶数 S x x能被2整出 证 先符号化 x P x