当前位置：文档之家 › 离散数学第六章

离散数学第六章

  • 格式：ppt
  • 大小：1.10 MB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

离散数学第六章 集合-包含与排斥原理

离散数学第六章 集合-包含与排斥原理

│A1∪A2│=│A1│+│A2│–│A1∩A2│ = 12+18-5 = 2Ar是r个有限集。则
| A1 A2 Ar | | Ai |
i 1
r
1i j r j
| A A
i
j
|

1i j k r
| A A
例 (p71-72) 求出在1和300之间，不能被2、3、5、7中 任意一个整除的整数的个数。
分析：
A1表示1和300之间能被2整除的整数集合 A2表示1和300之间能被3整除的整数集合 A3表示1和300之间能被5整除的整数集合 A4表示1和300之间能被7整除的整数集合
│A1∪A2∪A3∪A4 │=?
a1表示1和300之间能被2整除的整数集合a2表示1和300之间能被3整除的整数集合a表示1和300之间能被5整除的整数集合a3表示1和300之间能被5整除的整数集合a4表示1和300之间能被7整除的整数集合a1a2a3a4
第六章 集合
6.1 集合的基本概念 6.2 集合的基本运算 6.3 全集和集合的补 6.4 自然数与自然数集 6.5 包含与排斥原理
例 (p71-72)求出在1和300之间，不能被2、3、5、7中
任意一个整除的整数的个数。
解：设A1,A2,A3,A4分别表示1和300之间能被2整除的、能被3整除的 、能被5整除的和能被7整除的整数集合。故有： │A1│=150，│A2│=100，│A3│=60，│A4│=42， │A1∩A2│=50，│A1∩A3│=30，│A1∩A4│=21 │A2∩A3│=20，│A2∩A4│=14，│A3∩A4│=8 │A1∩A2 ∩A3 │=10，│A1∩A2 ∩A4 │=7 │A1∩A3 ∩A4 │=4， │A2∩A3 ∩A4 │=2 │A1∩A2 ∩A3 ∩A4 │=1 于是，我们有： │A1∪A2∪A3∪A4 │ =150+100+60+42– (50+30+21+20+14+8)+(10+7+4+2)–1 =231 因此, 所求个数为 300-231=69.

《离散数学》第六章 集合代数

《离散数学》第六章 集合代数

确定下列命题是否为真
（1），（3），（4）为真， （2）为假．
幂集
定义6.5 给定集合A，由集合A的所有子集为元素组 成的集合，称为集合A的幂集，记作P(A)。 设A＝{a，b，c}，则 P(A)＝{ ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}
空集是一切集合的子集
定理6.1 空集是一切集合的子集． 证明：对于任何集合A，有子集定义有
∅ ⊆A Ù∀x(x∈ ∅ → x∈A) 右边的蕴涵式为真，所以∅ ⊆A也为真。
空集是唯一的
推论 空集是唯一的。 证明 假设存在空集∅1和∅2，
∅1 ⊆ ∅2和∅2 ⊆ ∅1 根据集合相等的定义得∅1＝∅2
设x不具有性质P1,P2,…,Pm ，那么x∉Ai，i＝ 1，2，…m。则它对等式左边计数的贡献为1，对 等式右边的计数的贡献也是1。
根据牛顿二项式定理不难得到上面式子的结果是0．而 由于x具有n个性质，它对等式左边的贡献也为0。
4.3 几个例子
例1:求1-1000之间(包括1和1000)不能被5,也不能被6, 还不能被8整除的整数有多少个?
若A是n元集，则P(A)有2n个元素。
实例
全集
定义6.6 在一个具体问题中,如果所涉及的 集合都是某个集合的子集，则称这个集合为 全集，记作E(或U)
3.2 集合的基本运算
定义6.7 设A与B为集合，A与B的并集∪ ，交集 ∩ ，B对A的相对补集-分别定义如下：
A∪B={x|(x ∈A) ∨(x ∈ B)} A∩B={X | (X ∈ A) ∧(X ∈ B)} A - B = {X | (X ∈ A) ∧(X ∉B)} 当两个集合的交集是空集时，称它们是不交的。

离散数学结构第6章集合代数

离散数学结构第6章集合代数

离散数学结构第6章集合代数第六章集合代数1. 集合，相等，（真）包含，⼦集，空集，全集，幂集2. 交，并，（相对和绝对）补，对称差，⼴义交，⼴义并3. ⽂⽒图，有穷集计数问题4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同⼀律，排中律，⽭盾律，余补律，双重否定律，补交转换律等）学习要求1. 熟练掌握集合的⼦集、相等、空集、全集、幂集等概念及其符号化表⽰2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、⼴义交、⼴义并的定义及其性质3. 掌握集合的⽂⽒图的画法及利⽤⽂⽒图解决有限集的计数问题的⽅法4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零律、同⼀律、排中律、⽭盾律、余补律、双重否定律、补交转换律）5. 准确地⽤逻辑演算或利⽤已知的集合恒等式或包含式证明新的等式或包含式6.1 集合的基本概念⼀．集合的表⽰集合是不能精确定义的基本概念。

直观地说，把⼀些事物汇集到⼀起组成⼀个整体就叫集合，⽽这些事物就是这个集合的元素或成员。

例如：⽅程x2－1＝0的实数解集合；26个英⽂字母的集合；坐标平⾯上所有点的集合；……集合通常⽤⼤写的英⽂字母来标记，例如⾃然数集合N(在离散数学中认为0也是⾃然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。

表⽰⼀个集合的⽅法有两种：列元素法和谓词表⽰法，前⼀种⽅法是列出集合的所有元素，元素之间⽤逗号隔开，并把它们⽤花括号括起来。

例如A={a，b，c，…，z}Z={0，±1，±2，…}都是合法的表⽰。

谓词表⽰法是⽤谓词来概括集合中元素的属性，例如集合B＝{x|x∈R∧x2－1＝0}表⽰⽅程x2－1＝0的实数解集。

许多集合可以⽤两种⽅法来表⽰，如B也可以写成{-1，1}。

但是有些集合不可以⽤列元素法表⽰，如实数集合。

集合的元素是彼此不同的，如果同⼀个元素在集合中多次出现应该认为是⼀个元素，如{1，1，2，2，3}＝{1，2，3}集合的元素是⽆序的，如{1，2，3}＝{3，1，2}在本书所采⽤的体系中规定集合的元素都是集合。

离散数学第六章 集合 自然数与自然数集

离散数学第六章 集合 自然数与自然数集

学一：认识作者，了解作品背景作者简介：欧阳修(1007—1072)，字永叔，自号醉翁，晚年又号“六一居士”。吉州永丰(今属江西)人，因吉州原属庐陵郡，因此他又以“庐陵欧阳修”自居。谥号文忠，世
称欧阳文忠公。北宋政治家、文学家、史学家，与韩愈、柳宗元、王安石、苏洵、苏轼、苏辙、曾巩合称“唐宋八大家”。后人又将其与韩愈、柳宗元和苏轼合称“千古文章四大家”。
6.1 集合的基本概念 6.2 集合的基本运算 6.3 全集和集合的补 6.4 自然数与自然数集 6.5 包含与排斥原理
11 醉翁亭记
1．反复朗读并背诵课文，培养文言语感。
2．结合注释疏通文义，了解文本内容，掌握文本写作思路。
3．把握文章的艺术特色，理解虚词在文中的作用。
4．体会作者的思想感情，理解作者的政治理想。一、导入新课范仲淹因参与改革被贬，于庆历六年写下《岳阳楼记》，寄托自己“先天下之忧而忧，后天下之乐而乐”的政治理想。实际上，这次改革，受
当n=0时，已经证明了结论成立。 对n作归纳假设，假设对任意自然数m, 有n∊m, 或者n=m，或者m∊n三者之一成立。 现在考察对于n+=n+1的情况。
n+=n∪{n}，对于任意自然数m， 若n∊m, 则由对m用归纳法可以证明 n+∊m或者n+=m之一成立(见前页)。 若n=m，则m∊{m}={n}，即m∊n∪{n}=n+。 若m∊n，则m∊n∪{n}=n+。
，使得0=m+。 4．n和m均是自然数，如果n+=m+，那么n=m。 5．如S是N的子集，有性质
(1) 0∊S, (2) 如果n∊S，那么n+∊S ， 则有 S=N。
数学归纳法——皮亚诺公设的第5条

离散数学第六章---群论

离散数学第六章---群论
得Computer仍是字母串。
第6章 群论
定理6.1 一个半群(S，)，如果它有一个子代 数 (M， ) ，则此子代数也是一个半群。
定义6.2 一个半群(S，)的子代数 (M， )也是 半群，称为(S，)的子半群。
第6章 群论
一个半群(S，)中的元素a ，可定义它的幂： a1=a , a2=a a , …，an+1=an a
第6章 群论
定理6.5 一个单位半群(S，)，如果存在一个
子代数 (M， ) ，且其单位元 e ∈M，则 (M， )
也是一个单位半群。
定义6.5 一个单位半群(S，)，如果存在一个
子代数 (M， ) ，且其单位元 e ∈M，则 (M， )
也是一个单位半群，称为(S，)的子单位半群 。
Hale Waihona Puke 第6章 群论定义6.5 ：一个单位半群(S，)如果由它的一个 元素a 所生成，则称为由 a 所生成的循环单位半 群，元素 a 称为此单位半群的生成元素。
定理6.6 ：一个循环单位半群是一个可换单位半 群。
第6章 群论
6.2 群
一、群与群的同构 1、群的有关定义
定义6.7 如果代数系统(G， )满足 （1） (G， )为一半群； （2） (G， )中有单位元e； （3） (G，)中每一元素a∈G都有逆元 a-1 则称代数系统(G， )为群。
第6章 群论
第六章 群论 6.1 半群与单元半群 6.2 群
第6章 群论
群在代码的查错、改错的研究，自动机理论等 方面都有应用。
第6章 群论
6.1 半群与单元半群
半群与群都是具有一个二元运算的代数系 统，群是半群的特殊例子。事实上，群是历史 上最早研究的代数系统，它比半群复杂一些， 而半群概念是在群的理论发展之后才引进的。 逻辑关系见图6.1.1。

离散数学_第06章代数结构概念及性质

离散数学_第06章代数结构概念及性质

【例】（1）以实数集 R 为基集，加法运算" ＋"为二元，运算组成一代数系统，记为〈R， ＋〉。 （2）以全体n×n实数矩阵组成的集合 M为基集，矩阵加"+"为二元运算，组成一代 数系统，记为〈M,+〉。 (3)设 S A { | 是集合A上的关系}， “ ” 是求复合关系的运算。它们构成代数 系统S A , 。
有了集合上运算的概念后，便可定义代数结
构了。
定义6.1.2 设S是个非空集合且fi是S上的 ni元运算，其中i=1，2，…，m。由S及f1， f2，…，fm组成的结构，称为代数结构，记 作<S，f1，f2，…，fm>。
此外，集合S的基数即|S|定义代数结构 的基数。如果S是有限集合，则说代数结构 是有限代数结构；否则便说是无穷代数结构。
分配律，或者⊙对于○是可左分配的，即
(x)(y)(z)
(x，y，z∈S→x⊙(y○z))=(x⊙y)○(x⊙z))。
运算⊙对于○满足右分配律或⊙对于○是可 右分配的，即(x)(y)(z) (x，y，z∈S→(y○z)⊙x=(y⊙x)○(z⊙x)) 类似地可定义○对于⊙是满足左或右分配律。 若⊙对于○既满足左分配律又满足右分配律， 则称⊙对于○满足分配律或是可分配的。同样可 定义○对于⊙满足分配律。
x为关于⊙的右逆元:=(y)(y∈S∧y⊙x=e)；
x为关于⊙可逆的:=(y)(y∈S∧y⊙x=x⊙y=e)
给定<S，⊙>及幺元e；x，y∈S，则 y为x的左逆元:=y⊙x=e
y为x的右逆元:=x⊙y=e
y为x的逆元:=y⊙x=x⊙y=e
显然，若y是x的逆元，则x也是y的逆元，
因此称x与y互为逆元。通常x的逆元表为x-1。

离散数学第六章的课件

离散数学第六章的课件

05 离散随机变量
随机变量的定义与性质
随机变量定义
随机变量是从样本空间到实数的可测 函数，用于描述随机现象的结果。
随机变量性质
随机变量具有可测性、可加性和可数 性等性质，这些性质在概率论和统计 学中具有重要应用。
离散概率分布
离散概率分布定义
离散概率分布描述的是随机变量取离散值时的概率规律，通 常用概率质量函数或概率函数表示。
离散概率分布性质
离散概率分布具有非负性、归一性和可数性等性质，这些性 质是离散概率分布的基本要求。
期望与方差
期望定义
期望是随机变量所有可能取值 的概率加权和，是描述随机变 量取值“平均水平”的重要指
标。
期望性质
期望具有线性性、可加性和正 定性等性质，这些性质在概率 论和统计学中具有重要应用。
方差定义
感谢您的观看
THANKS
方差是描述随机变量取值分散 程度的重要指标，是随机变量 与期望之差的平方的期望。
方差性质
方差具有非负性、归一性和可 加性等性质，这些性质是方差
的基本要求。
06 离散概率论的应用
蒙提霍尔问题
总结词
蒙提霍尔问题是一个著名的概率论问题，涉 及到概率论中的独立性概念和组合数学。
详细描述
蒙提霍尔问题是一个经典的组合数学问题， 它涉及到概率论中的独立性概念。该问题问 的是，如果有n个盒子，每个盒子被选中的 概率是1/2，那么在最优策略下，选中至少 一个盒子的最有可能的盒子数是多少？这个 问题涉及到概率论中的独立性概念和组合数
学。
抓阉问题
要点一
总结词
抓阉问题是一个经典的离散概率论问题，涉及到概率论中 的随机性和独立性概念。
要点二

离散数学第六章

离散数学第六章

6.1.6 循环群和置换群
§循环群 在循环群G=<a>中, 生成元a的阶与群G的阶是一样 的. 如果a是有限阶元, |a|＝n, 则称G为n阶循环群. 如 果a是无限阶元, 则称G为无限阶循环群. 例如: <Z,+>是无限阶循环群; <Z6,>是n阶循环群. 注意:(1) 对9 无限阶循环群G=<a>, G的生成元是a和a-1; (2) 对n阶循环群G=<a>=<e,a,…,an-1>,G的生成元是at 当且仅当t与n互素, 如12阶循环群中, 与12互素的数 有1、5、7、11. 那么G的生成元有a1=a、a5、a7、 a11. (3) N阶循环群G=<a>, 对于n的每个正因子d, G恰好有 一个d阶子群H=<an/d>.
6.1.3 子群
例如, 群<Z6,>中由2生成的子群包含2的各次 幂, 20=e=0, 21=2, 22=22=4, 23=222=0, 所 以由2生成的子群：<2>={0,2,4}.
对于Klein四元群G={e,a,b,c}来说, 由它的每个 元素生成的子群是 <e>={e}, <a>={e,a}, <b>={e,b}, <c>={e,c}
6.1.6 循环群和置换群
§循环群
定义6.7 在群G中, 如果存在aG使得 G={ak|kZ} 则称G为循环群, 记作G=<a>,称a为G的生成元. ☆ 循环群必定是阿贝尔群, 但阿贝尔群不一定 是循环群. 证明: 设<G,*>是一个循环群, 它的生成元是a, 那么,对于任意x,yG, 必有r,sZ, 使得 x=as,y=at, 而且x*y=as*at=as+t=at*as=y*x 由此可见<G,*>是一个阿贝尔群. 例如,<Z,+>是一个循环群, 其生成元是1或-1.

离散数学第6章

离散数学第6章

33
图的运算
v2 v1 v3 v7 v2 v4 v6 v3 v8 G1∪G2 v5 v2 v4 v2 v5 v4 v6 v2 v3 v8 v7 v4 v6 v3 v8 G1 G2
34
v7 v4 v5
v1
Байду номын сангаасv1
v3 v5 G1∩G2 v5
图的运算


若V1∩V2=空集，说明图G1和G2没有公 共顶点， G1∩G2是空图。称G1和G2不 相交。 若E1∩E2=空集，说明图G1和G2没有公 共边，则
3
无向图与有向图
定义 有向图D=<V,E>, 其中 (1) V同无向图的顶点集, 元素也称 为顶点 (2) E为VV的多重子集，其元素 称为有向边，简称弧. 用无向边代替D的所有有向边 所得到的无向图称作D的基图 右图是有向图，试写出它的V和E
4
图的基本概念




边又分为两种：有向边和无向边。在有向边的两个端 点中，一个是始点，另一个是终点，有向边的箭头方 向自始点指向终点。 如果图中各边都是有向边，则称此图为有向图。 如果图中各边都是无向边，则称此图为无向图。 如果图中既有有向边又有无向边，则称此图为混合图 由于无向边可以用两条方向相反的有向边来替代，所 以混合图可以转化为有向图。
若vi vj, 则称ek与vi ( vj)的关联次 数为1; 若vi = vj, 则称ek为环, 此时称ek与 vi 的关联次数为2; 若vi不是ek端点, 则称ek与vi 的关
联次数为0.
无边关联的顶点称作孤立点.
8
定义 设无向图G=<V,E>, 边e=(a,b)，则称a,b为边e的两个端 点，称点a,b是邻接的; 关联于同一顶点的边是相邻（邻 接）的.

离散数学第6章

离散数学第6章

14
注： 此定义是由美国哈佛大学爱伦堡教授给出的； 此定义规定了严格的点、线之间的关系，适应面很广、特别 适合多重图（比如上节的七桥图）；缺点是边表示比较复杂， 简单图一般不采用。 标号实际上是为了区别两点间的平行边而设的；标号集的大 小一般就是图中平行边的最大条数(图的重数，参见下面概念)。 当图的重数为1，即图无平行边时(简单图，参见下面概念)， 有 ={1}，各边标号一样，全为1 ，这时可取掉各边标号及标 号集，定义3就变成了定义2；所以定义3适合于图的一般情况， 特别是(有平行边的)多重图，而定义2适合于(无平行边的)简单 图。
(D,PSC) (PDSC,) (DC,PS)
(PDS,C)
(PDC,S)
(S,PDC)
(,PDSC)
(PS,DC)
(C,PDS) (PSC,D) 图4 注：上述问题统称“渡河问题”。 “三对忌妒的夫妇渡河问题”参见《离散数学基础》 [美]C.L.Liu著 刘振宏译 P162； “三个传教士与三个吃人肉的野人渡河问题”参见《Prolog高 级程序设计》[美]L.斯特林 E.夏皮罗著 刘家佺 邓佑译 郑守淇校 P197； 渡河问题的条件也是可变的。比如夫妇的对数可以是四对， 五对；渡河能力或渡河工具－小船的容量也是可变的。
(13)孤立点： (isolated vertex) 不与任何边相关联的结点称为孤立点。
(14)自环： (loop ) 两个端点相同的边称为自环。
18
(15)平行边： (parallel edges ) 有相同端点(相同的起点，相同的终点)的两条边称 为平行边。
(16)重数： (multiplicity) 两结点间平行边的条数称为平行边的重数。
注：此定义的优点是简单，规定了清楚的点、线之间 的关系，很适合简单图、特别是有向图（比如第二章的 关系图、哈斯图）；缺点是无法表示平行边，因此不适 合多重图（比如上节的七桥图）。 例2. 有四个程序，它们之间存在如下的调用关系：P1 能调用P2 ， P2能调用P3 ，P2能调用P4 。 上述事实也可用一图G = (V, E)来表示。图中结点集 V={v1 , v2 , v3 , v4} ，边集E={(v1, v2), (v2, v3), (v2, v4)} 。

离散数学第六章 集合-全集和集合的补

离散数学第六章 集合-全集和集合的补
第六章 集合
6.1 集合的基本概念 6.2 集合的基本运算 6.3 全集和集合的补 6.4 自然数与自然数集 6.5 包含与排斥原理
ห้องสมุดไป่ตู้
全集
定义: 我们在研究某一个具体问题时，往往 规定一个集合，使所涉及的集合都是它 的子集合，称这个集合为全集， 记为U (或E )。
全集是个有相对性的概念，不同的问题， 可以规定不同的全集。
任一集合的补集合是唯一的。
推论
设A是任意一个集合，则
A A
定理3 德· 摩根定律
(Augustus De Morgan, 1806-1871, 英國數學家)
A B A B
A B A B
证明：( A B) ( A B)
[ A ( A B)] [ B ( A B)] [( A A) B] [(B B) A] [ B] [ A]
补运算： Ā
定义：设A是一个集合,U 是全集合，我们 称集合U–A为A的补集，记为Ā，即有： Ā={ x│x∉A且x∊U }
Ā
A
U
定理1 A是一个任意集合，则
A∪Ā= U A∩Ā= Ø
定理2 Ā=B当且仅当A∪B=U且A∩B=Ø
证明： “” 由定理1结论成立。 “” 设A∪B=U 且A∩B=Ø ，则 B =B∩U =B∩(A∪Ā)=(B∩A)∪(B∩Ā) =Ø∪(B∩Ā) = (A∩Ā) ∪(B∩Ā) =(A∪B)∩Ā=U∩Ā=Ā
因而结论得证。
例 (p68)
证明：
(A–B)∩(A–C)=A– (B∪C)
( A B) ( A C ) ( A B) ( A C ) A (B C) A (B C) A (B C)

离散数学 第6章 命题逻辑

离散数学 第6章 命题逻辑

(P Q) R m1 m3 m5 m6 m7 (1,3,5,6,7)
三、主合取范式
如组成合取范式的每一个括号中都包括所有的命题 变项或其否定形式，则该合取范式称为主合取范式。 在主合取范式中的每一个括号是一个包括所有的命题 变项或其否定形式的简单析取式，称为大项。 如果将大项中各命题变项看成为0，其否定看成为1, 按字母顺序排列后的二进制数为i,该大项表示为 M i ， 注意：M 1不是 (P Q R) ，而是 ( P Q R) 例如，在某命题公式A中P,Q,R为(0,0,1)和(1,1,1)时真 值为0，则A的主合取范式可记作为：
(P Q R) (P Q R) (1,7)
由主析取范式可直接求出主合取范式
例如，上面的例3 ( P Q) R 主析取范式已经求得，为 那么，它的主合取范式为：
(1,3,5,6,7)
( P Q R) ( P Q R) (P Q R)
5。等价 如果两个命题P和Q有 P Q P Q 的真值表 同时又有 Q P 则记作 P Q P Q P Q P Q 就是 ( P Q) (Q P) 0 0 1 合取、析取和等价都满足交换 0 1 0 律，而蕴含是不满足交换律的。 1 0 0 P 例如， Q Q P , P Q Q P 1 1 1 P Q Q P 在一个命题公式中如果没有括号， 各种联结词的运算顺序从先到后依次为：
例题5： 用真值表证明命题公式P ( P Q R) 是重言式 解： P ( P Q R) P Q R PQ R 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1

离散数学第六章

离散数学第六章

二. 格是代数系统
2.偏序集合的格、代数系统的格二者定义是等价 的
定理4.若<L, ,>是一个格（作为代数系统）， 那么，L 中存在一偏序关系≤, 使a,bL ，有 ab=lub(a,b), ab=glb(a,b). 证：在集合L上定义的二元关系如下： a,bL，若a≤b ab=a 分三步： 1) 证明’≤’是L上的偏序关系 2）证明 a,bL, {a,b}的最大下界存在， 且 ab=glb(a,b)。 3）a,bL, {a,b}的最小上界存在，且 lub(a,b)=ab
6.3布尔代数
3.原子 设<A, ≤> 是一个格，且具有全下界0，若有a盖 住0，称a为原子。
例：1盖住d,e,b，则 a,b,c为原子
1 d a 0
b
e c
6.3布尔代数
定理： 若<A, ≤>为具有0的有限格，则
bA,b≠0，aA, a为原子，且a≤b
证明：
若b为原子，则b≤b 得证。
1.定义： 若<A,≤>是一个格,由它诱导的代数系统 <A, ,>,如果对于任意的a,b,c∈A,有 b≤a a(bc)=b(ac)， 称<L, ≤>是模格。
例1：
1 a c b d
它是模格，但不是分配格 b≤a: a(cd)=a1=a (ac)(ad)=bb=b
6.2
但 a(bc)=a1=a
b(ac)=b0=b
分配格
1 a b 0 c
例2：它不是模格，b≤a,
3.分配格是模格
证:a(bc)=(ab)(ac) = b(ac)
6.3 有补格
1．全上界（全下界）定义 给定格<L,≤> ， 若存在aL， 使bL,有b≤a (a≤b)， 称a为<L,≤>的全上界（全下界）。 注：一个格的全上界（全下界）是唯一的。

离散数学第六章

离散数学第六章
2019/3/20 离散数学 2
树的举例
树G：
a
取a为根： 取b为根：b
a a d c
取e为根：
e
b
c
d
e c
b
d e a
e
d
b
取d为根： d
b
c
e
a c
显然它们是同构的。 数据结构中的树指定了一个特殊的顶点为根。
2019/3/20 离散数学
3
树的应用举例
树的用途极其广泛，比如计算机网络中的最短
2019/3/20 离散数学 6
树是点比边多一的连通图
证明：因G是树，所以G连通，
明 q=p–1： (1) p=1时，显然q=p–1 ； (2)假设对顶点数少于p的树，结论成立； (3) 对于p个顶点的树G ，p2 , 取e=uv ∈E(G) , 由 定理6.1.1知，e是唯一的(u,v)––通路，于是， G–e不连通而且恰有两个连通分支G1(p1,q1)和 G2(p2，q2),显然，p1<p且p2<p .由归纳假设， q1=p1–1 , q2=p2–1 , 从而q=q1+q2+1=p1+p2–1=p–1 。
2019/3/20
离散数学
11
少条边就不连通的图是树的证明图示
P不含e：
u
C
v
P含e：
u
C
v
x
e
y
x
e y
P
P
G
2019/3/20 离散数学
G
12
平凡树和森林
只有一个顶点的图（平凡图）称为平凡
树。 具有多个连通分支，且每个连通分支都 是树的图称为森林。
2019/3/20

离散数学-第6章.ppt

离散数学-第6章.ppt

S4={3, 4, 5}
S5={3, 5} 确定在以下条件下X是否与S1,…,S5中某个集合相等？如 果是，又与哪个集合相等？
（1）若 XS5= （2）若 XS4但 XS2=
（3）若 XS1且 X ⊈S3 （4）若 XS3= （5）若 XS3 且 X ⊈ S1
28
解答
解 (1) 和S5不交的子集不含有3和5，因此 X=S2. (2) S4的子集只能是S4和S5. 由于与S2不交，不能含有偶数，
A B AB = AB = AB = A
7
广义运算
1. 集合的广义并与广义交 定义6.10 广义并 A = { x | z ( zA xz )}
广义交 A= { x | z ( zA xz )} 实例
{{1}, {1,2}, {1,2,3}}={1,2,3} {{1}, {1,2}, {1,2,3}}={1} {{a}}={a}， {{a}}={a} {a}=a， {a}=a
8
关于广义运算的说明
2. 广义运算的性质 (1) =，无意义 (2) 单元集{x}的广义并和广义交都等于x (3) 广义运算减少集合的层次（括弧减少一层） (4) 广义运算的计算：一般情况下可以转变成初级运算 {A1, A2, … , An}=A1A2…An {A1, A2, … , An}=A1A2…An
AB = {x | xA xB}
交
AB = {x | xA xB}
相对补 AB = {x | xA xB}
定义6.8 对称差 AB = (AB)(BA)
定义6.9 绝对补 A = EA
5
集合运算的表示
文氏图
A
B
AB
A
B
AB
A

离散数学第六章课件

离散数学第六章课件
2018/11/12 4


2.格

定义6-1.1格：设<A,≤>是一个偏序集，如果 A中任意两个元素都存在着最大下界和最小上 界，则称<A，≤>是格。
以上5个图中，任何两个元素都有最小上界和最大下界
2018/11/12 5
格的判定
例6-1.1 判断下列偏序集是否是格？
e
e d
f b c
d
c
a b
2018/11/12 3
最小上界、最大下界

最小上界：设<A,≤>为一偏序集且BA，a为 B的任一上界，若对B的所有上界y均有a≤y,则 称a为B的最小上界（上确界），记作LUB B
最大下界：若b为B的任一下界，若对B的所有 下界z，均有z≤b,则称b为B的最大下界（下确 界），记作GLB B 把具有两个元素集合{a,b}的最小上界（最大 下界）称为元素a,b的最小上界（最大下界）
2018/11/12 15
6.格相关的性质定理
定理6-1.1 在一个格<A，≤>，对于任意的a,b 结论很有用！！！ A，都有 a≤a∨b, b≤a∨b a∧b≤a, a∧b≤b

证明： a和b的并是a、b的最小上界，所以 a≤a∨b 同理 b≤a∨b 由对偶原理： a∧b≤a, a∧b≤b
子格判定
注意证明方法
例6-1.4：<s,≤>是一个格，任取a s,构造s的 子集：T={x|xs且x≤a},则<T,≤>是<s,≤>的 子格.

证明：对于任意的x,yT，必有x≤a,y≤a a是x,y的上界,最小上界≤任一上界 x∨y≤a x∧y≤x≤a 所以x∨yT， x∧yT <T,≤>是<s,≤>的子格
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

6.1.1 半群与独异点
离 散 数 学
第 六 章 几 个 特 殊 代 数 系 统
例6.1 ① < Z+,+>是半群 ② <N,+>,<Z,+>,<Q,+>,<R,+>都是半群和独异点， 其中+表示普通加法,幺元是0,<N,+,0>,…,<R,+,0> ③<Mn(R),· >是半群和独异点,其中· 表示矩阵乘法,矩 阵乘法的幺元是n阶单位矩阵E.记作<Mn(R),· ,E> ④ <P(B),>是半群和独异点,其中表示集合的对称 差运算, 其幺元是, 记作<P(B),,> ⑤ <Zn,>是半群和独异点, 其中Zn ={0,1,…,n-1}, 表示模n加法, 模n加法的幺元是0. <Zn, ,0> 其中: ① ②④⑤ 为可交换半群.
离 散 数 学
6.1.1 半群与独异点
例6.2 判断下述论断正确与否, 在相应的括号中键入“Y” 或“N”.
第 六 章 几 个 特 殊 代 数 系 统
(1) 在实数集R上定义二元运算*为：对于任意的 a,b∈R, a*b=a+b+ab (a) <R,*>是一个代数系统；( Y) (b) <R,*>是一个半群； ( Y ) (c) <R,*> 是一个独异点。( Y) (2) 在实数集R上定义二元运算◦为, 对任意 a,b∈R, a◦b=|a|· b (其中·表示数学的乘法运算) (a) <R,◦>是一个代数系统； ( Y) (b) <R,◦>是一个半群； ( Y) (c) <R,◦>是一个独异点。 ( N )
半群、可交换半群和独异点
第 六 章 几 个 特 殊 代 数 系 统
定义6.1 ①设V=<S,˚>是代数系统, ˚为二元运算,如果˚是可 结合的, 则称V为半群．
② 如果半群V=<S,˚>中的二元运算含有幺元, 则称V为含幺 半群, 也可叫做独异点. 定义6.2 如果半群V=<S,˚>中的二元运算˚是可交换的, 则称 V为可交换半群. 注: 为了强调幺元的存在, 有时将独异点记为<S,˚,e>
几 个 特 殊 代 数 系 统
6.1.4 陪集与拉格朗日定理
第 六 章
Lagrange定理
对G的子群H来说, H的左陪集和右陪集一般是不相等的, 但左右陪集的个数是相等的.因此将左右陪集数统称 为H在G中的陪集数, 也叫做H在G中的指数, 记为 [G:H]. 定理6.4(定理10.10): 设G是有限群, H是G的子群, 则 |G|=|H|[G:H]. 推论1 设G是n阶群, 则aG, |a|是n的因子, 且an=e. 推论2 对阶为素数的群G, 必存在aG使得G=<a>.
定义6.4 H是G的子群, aG, 令 Ha={ha|hH} 称Ha是子群H在G 中的右陪集, 称a为Ha的代表元 素. 例6.6 设G={e,a,b,c}是Klein四元群, H={e,a}是G的子群, 那么H的所 有右陪集是: He={e,a}=H Ha={e,a}=H Hb={b,c} Hc={c,b} 注: 类似地可以定义左陪集.
6.1 半群与群
6.1.1 6.1.2 6.1.3 6.1.4 6.1.5 6.1.6 半群与独异点 群的定义与性质 子群 陪集与拉格朗日定理 正规子群与商群 循环群和置换群
6.2 环与域
6.2.1 环的定义与性质 6.2.2 整环与域
6.3 格与布尔代数
6.1 半群与群
离 散 数 学
6.1.1 半群与独异点
第 六 章 几 个 特 殊 代 数 系 统
6.1.2 群的定义与性质
离 散 数 学
群的术语
(3) 群的阶: 对于有限群G,G中的元素个数也叫做G的阶, 记作|G|. 例如: <Zn,>是有限群, 其阶是n; Klein四元群也是有限 群, 其阶是4. (4) xn定义: x0=e, xn+1=xn◦x, x-n=(x-1)n (5) 元素x的阶: 设G是群,x∈G,使得xk＝e成立的最小的正 整数k叫做x的阶(或周期).如果不存在正整数k,使xk＝e, 则称x是无限阶元. 注: 对有限阶的元素x, 通常将它的阶记为|x|. 在任何群G中幺元e的阶都是1．
第 六 章 几 个 特 殊 代 数 系 统
离 散 数 学
6.1.2 群的定义与性质 群的术语
(1) 若群G中的二元运算是可交换的, 则称群G为交换群, 也 叫做阿贝尔(Abel)群． 例 ① <Z,+>, <Q,+>,<R,+>都是群, 也是阿贝尔(Abel)群; ② <P(B),,>是群, 也是阿贝尔(Abel)群; ③ <Zn,,0>是群, 也是阿贝尔(Abel)群. ④ Klein四元群也是阿贝尔群． (2) 若群G中有无限多个元素, 则称G为无限群, 否则称为有 限群, 只含幺元的群为平凡群. 例如, <Z,＋>, <R,＋>都是无限群. <Zn,>是有限群. Klein 四元群也是有限群.
对独异点V=<S,˚,e>, <T,˚,e>构成V的子独异点,需要满 足如下条件: ① T是S的非空子集;
② T要对V中的运算˚封闭; ③ e∈T.
6.1.2 群的定义与性质
离 散 数 学
群的定义
定义6.3 设<G,◦>是代数系统,◦为二元运算.如果◦是可结 合的,存在幺元e∈G,并且G中的任意元素x,都有x-1∈G, 则称G是群. 例6.3
任取H中的元素xm,xl,都有
xm(xl)-1＝xmx-l＝xm-lH 根据判定定理二可知<x>≤G.
离 散 数 学
6.1.3 子群
例如, 群<Z6,>中由2生成的子群包含2的各次 幂, 20=0, 21=2, 22=22=4, 23=222=0, 所以 <2>={0,2,4}. 对于Klein四元群G={e,a,b,c}来说, 由它的每个 元素生成的子群是 <e>={e}, <a>={e,a}, <b>={e,b}, <c>={e,c}
6.1.1 半群与独异点
离 散 数 学
子半群和子独异点
定义: 半群的子代数叫做子半群,
即: 如果V=<S,˚>是半群, <T,˚>就是V的子半群,需要满 足如下两个条件: ① T是S的非空子集; ② T对V中的运算˚是封闭的. 定义: 独异点的子代数叫做子独异点,
第 六 章 几 个 特 殊 代 数 系 统
第 六 章 几 个 特 殊 代 数 系 统
第 六 章
6.1.2 群的定义与性质 群的术语
例.在Klein四元群中,|a|=?,|b|=?,|c|=?,|e|=?
几 个 特 殊 代 数 系 统
返回
离 散 数 学
6.1.2 群的定义与性质
群的性质
定理6.1 设G为群, 则G中的幂运算满足(群中元素的幂) (1) x∈G, (x-1)-1＝x (2) x,y∈G, (xy)-1＝y-1x-1 (3) x∈G, xnxm＝xn+m (4) x∈G, (xn)m＝xnm (5) 若G为交换群, 则(ab)n=anbn
离 散 数 学
6.1.3 子群
子群的判断方法
判定定理1 设G为群, H是G的非空子集, H是G的子群当且
仅当: (1) a,bH都有abH; (2) aH有a-1H. 判定定理2 设G为群, H是G的非空子集, 则H是G的子群当 且仅当a,bH都有ab-1H. 判定定理3 设G为群, H是G的非空子集. 若H是有穷集, 则 H是G的子群当且仅当a,bH都有abH .
6.1.4 陪集与拉格朗日定理
第 六 章
陪集的性质
定理6.3(定理10.7-10.9): 设H是G的子群, 则 (1) He=H (2) aG有aHa (3) a,bG, aHbab-1HHa=Hb (4) 在G上定义关系R:a,bG, <a,b>Rab-1H, 则 R是G上的等价关系, 且[a]R=Ha. (5) aG, H≈Ha(≈指势相等) 注意: 左陪集的性质与此类似.
•
e a b c
几 个 特 殊 代 数 系 统
e
a b c
e a b c
a e c b b c e a c b a e
6.1.4 陪集与拉格朗日定理
第 六 章
陪集的定义
例6.6 设A={1,2,3}, f1,f2,…,f6是A上的双射函数, 其 中:f1={<1,1>,<2,2>,<3,3>}, f2={<1,2>,<2,1>,<3,3>} f3={<1,3>,<2,2>,<3,1>} f4={<1,1>,<2,3>,<3,2>} f5={<1,2>,<2,3>,<3,1>} f6={<1,3>,<2,1>,<3,2>} 令G={f1,f2,f3,f4,f5,f6}, 则G关于复合(本题为右复合)运算构成了群, G的子群H={f1,f2}, 求H的全部右陪集.
① <Z,+>,<Q,+>,<R,+>都是群; ② <P(B),,>是群, 其中表示集合的对称差运算, 任意元素的逆元是其自身; ③ <Zn,,0>是群,其中Zn={0,1,…,n-1}, 表示模n加法, 0的逆元是0,非0元素的逆元是n-x.