离散数学-耿素云ppt(第5版)

32
用2叉有序树表示算式
每一个分支点放一个运算符. 二元运算符所在的分 支点有2个儿子, 运算对象是以这2个儿子为根的根 子树表示的子表达式, 并规定被减数和被除数放在 左子树上; 一元运算符所在的分支点只有一个儿 子, 运算对象是以这个儿子为根的根子树表示的子 表达式.数字和变量放在树叶上.
33
14
基本割集的性质
连通图中的任一割集都可以表成对应它所含树枝的 基本割集的对称差. 例如 {g,d}=Sd {a,b,e}=SaSb {a,e,c}=SaSc {b,e,f,d}=SbSd
15
无向图与最小生成树
对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=<V,E,W>. 设T是G的生成树, T所有边的权的和称作T的权, 记作W(T). 最小生成树: 带权图权最小的生成树 避圈法 (Kruskal) ——求最小生成树的算法 设G是n阶无向连通带权图G. (1) 按权从小到大排列边(环除外), 设W(e1)≤W(e2)≤…≤W(em). (2) 令T, i1, k0. (3) 若ei与T中的边不构成回路，则令TT{ei}, kk+1. (4) 若k<n-1, 则令ii+1, 转(3).
12
回路合并
合并回路C1和C2(C1C2): C1C2是C1和C2上的边的 对称差构成的(一条或几条)回路.



13
基本回路的性质
连通图中的任一条回路都可以表成对应它所含弦的 基本回路的合并. 例如, abcf=Cf aef=CeCf aedg=CeCg bcdgfe=CeCfCg
实例
例1 表示((b+(c+d))a)((ef)(g+h)(ij))的2叉有序树

11
二元运算的性质
定义 设 ∘ 为 S 上的二元运算, (1) 如果对于任意的 x, y S 有 x ∘ y = y ∘ x, 则称运算在 S 上满足交换律. (2) 如果对于任意的 x, y, z ∈S 有 (x ∘ y) ∘ z = x ∘ (y ∘ z), 则称运算在 S 上满足结合律. (3) 如果对于任意的 x ∈ S 有 x ∘ x = x, 则称运算在 S 上满足幂等律.
an∘an
运算表的实例
例4 A = P({a, b}), , ∼分别为对称差和绝对补运算 （{a,b}为全集） 的运算表 ∼ 的运算表 {a} {b} {a,b} {a,b} {b} {a} X ∼X {a} {b} {a} {a} {a.b} {b} {b} {a,b} {a,b} {a,b} {b} {a} {a,b} {a} {a} {b} {b} {a,b}
a ij R , i , j 1,2,..., n
矩阵加法和乘法都是 Mn(R) 上的二元运算. (6) 幂集 P(S) 上的二元运算：∪,∩,－, .
(7) SS 为 S 上的所有函数的集合：合成运算∘.
5
f ： S S S S
例题分析
例6 设 ∘ 运算为 Q 上的二元运算， x, yQ, x∘y = x+y+2xy, (1) ∘运算是否满足交换和结合律? 说明理由. (2) 求 ∘ 运算的单位元、零元和所有可逆元. 解 (1) ∘ 运算可交换，可结合. 任取x, yQ, x ∘ y = x+y+2xy = y+x+2yx = y ∘ x, 任取x, y, zQ, (x ∘ y) ∘ z= (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x ∘ (y ∘ z) = x + (y+z+2yz) + 2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz 23

x y
x∧y x y
x∨y x
x
与门
或门
非门
7
组合电路的例子
(x∨y)∧x的组合电路
x y
x y
第一种画法
x 第二种画法
8
例
例 楼梯的灯由上下2个开关控制, 要求按动任何一个 开关都能打开或关闭灯. 试设计一个这样的线路. 解 x,y:开关的状态, F:灯的状态, 打开为1, 关闭为0. 不妨设当2个开关都为0时灯是打开的.
2
复合联结词
与非式: pq(pq) 或非式: pq(pq)
和与, ∧,∨有下述关系: p(p∧p)pp p∧q( p∧q)(pq)(pq)(pq) p∨q(p∧q)(p)(q)(pp)(qq)
3
复合联结词(续)
ppp p∧q(pp)(qq) p∨q(pq)(pq)
定理 {}, {}是联结词4
表示串
0 1
标记*表示该项已被合并
14
例(续)
项 x1∧x3∧x4 x1∧x2∧x3 x2∧x3∧x4
x1∧x4
覆盖 (1,4) (2,4) (2,6) (3,5,6,7)
运算符数 3 3 3 2
选择(1,4), (2,4)和(3,5,6,7), 或者(1,4), (2,6)和(3,5,6,7). 最简展开式为
联结词的全功能集
定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表 示，则称S是联结词全功能集.
说明：若S是联结词全功能集，则任何命题公式都 可用S中的联结词表示.
设S1, S2是两个联结词集合，且S1 S2. 若S1是全
功能集，则S2也是全功能集. 反之，若S2不是全功能 集，则S1也不是全功能集.

(1)若：G1G2是满射旳，则称为满同态，这时也称
G2是G1旳同态像，记作G1 ~G2 。 (2)若：G1G2是单射旳，则称为单同态。
(3)若：G1G2是双射旳，则称为同构，记作 G1 G。2 (4)若G1=G2，则称是群G旳自同态。
39
9.2 代数系统
例16： 设V=<R+,•>，其中•为一般成法。对任意xR+令 1(x)=|x|， 2(x)=2x, 3(x)=x2, 4(x)=1/x, 5(x)=-x,则分析他们是否为V到V旳同态，假如 是，则分别为何同态。
设和*是S上旳两个可互换旳二元运算,假如对于任意旳
x，yS有
x*(xy)=x
x(x*y)=x
则称运算*和满足吸收律。 例如：幂集P(S)上旳和运算满足吸收律。即A,BP(S)
有
A(A B)=A
A(A B)=A
14
9.1二元运算及其性质
四、单位元和幺元
1. 幺元旳定义（定义9.6）
设为S上旳二元运算,假如存在 el (或 er)S使得对于任何
（2）当n=2时，则函数f:S×SS为S上旳二元运算。
(x，y)=z
（3）当n=3时，则函数f:S×S×SS为S上旳三元运算。
(x，y，z)=t
6
9.1二元运算及其性质
例4：在整数集合Z、有理数集合Q、实数集合R上，一 个数旳相反数、倒数是否为这些集合上旳一元运 算？
例5：在幂集P(S)上，假如要求全集为S，则求集合旳 绝对补运算～是否为P(S)上旳一元运算？
xS都有
el x = x(或 x er =x) 则称 el (或er )是S中有关运算旳一种左幺元(或右幺
元)。若eS有关运算既是左幺元又是右幺元，则称e 为S上有关运算旳幺元。

图论
1
图论部分
第5章 第6章 第7章
图的基本概念 特殊的图 树
2
第5章 图的基本概念
5.1 无向图及有向图
5.2 通路, 回路和图的连通性
5.3 图的矩阵表示
5.4 最短路径, 关键路径和着色
3
5.1 无向图及有向图
无向图与有向图 顶点的度数 握手定理 简单图 完全图 子图 补图
10
例
例 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D)=3.
11
图论基本定理——握手定理
定理 任意无向图和有向图的所有顶点度数之和都等 于边数的2倍, 并且有向图的所有顶点入度之和等 于出度之和等于边数. 证 G中每条边（包括环）均有两个端点，所以在计 算G中各顶点度数之和时，每条边均提供2度，m 条边共提供2m度. 有向图的每条边提供一个入度 和一个出度, 故所有顶点入度之和等于出度之和等 于边数. 推论 任意无向图和有向图的奇度顶点个数必为偶数.
4
无向图
多重集合: 元素可以重复出现的集合 无序积: AB={(x,y) | xAyB} 定义 无向图G=<V,E>, 其中 (1) 顶点集V是非空有穷集合, 其元素称为顶点 (2) 边集E为VV的多重子集， 其元素称为无向边，简称边. 例如, G=<V,E>, 其中 V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}

p q
p q p q
q p q p p q q p q p
18
注意： pq 与 qp 等值（真值相同）
联结词与复合命题(续)
5. 等价式与等价联结词“” 定义 设p，q为二命题，复合命题 “p当且仅当q”称 作p与q的等价式，记作pq. 称作等价联结词. 并规定pq为真当且仅当p与q同时为真或同时为 假. 说明: (1) pq 的逻辑关系:p与q互为充分必要条件
解令 (1) (2) (3) p：王晓用功，q：王晓聪明，则 p∧ q p∧ q p∧ q.
12
例 (续)
令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 . 说明: (1)~(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词，整个句子是 一个简单命题.
15
联结词与复合命题(续)
4.蕴涵式与蕴涵联结词“” 定义 设 p,q 为二命题，复合命题 “如果 p, 则 q”
称作 p 与 q 的蕴涵式，记作 pq ，并称 p 是蕴涵式
的前件， q 为蕴涵式的后件 . 称作蕴涵联结词，
并规定，pq为假当且仅当 p 为真 q 为假.
16
联结词与复合命题(续)

6
命题与真值
命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题
7
例 下列句子中那些是命题？
(1)
2 是无理数.
真命题 假命题 真值不确定 疑问句 感叹句

证明：设A=、B={1}、C={2}、D={3}
(AB)×(CD)={<1,2>、<1,3>}
(A×C)(B×D)={<2,1>、<2,3>}
所以：等式不成立 （3）(A-B)×(C-D)=(A×C)-(B×D)
证明：设A={1}、B={1}、C={2}、D={3}
(A-B)×(C-D)=
(xAyB) (xAyC)
<x,y>A×B <x,y>A×C
<x,y>(A×B)(A×C) PPT课件
9
4.1迪卡尔乘积与二元关系
5) 迪卡尔乘积运算对并和交运算满足分配律，即： (4)（BC）×A= (B×A)(C×A）
证明： 对于任意的<x,y>
<x,y>（BC）×A
PPT课件
24
4.1迪卡尔乘积与二元关系
例5：设A={a,b}，R是P(A)上的包含关系， R={<x,y>|x,yP(A)xy}
解：P(A)={,{a},{b},{a,b}} R={<, >,<,{a}>,<,{b}>,<,{a,b}>, <{a},{a}>,<{a},{a,b}>,<{b},{b}>, <{b},{a,b}>,<{a,b},{a,b}>}
PPT课件
16
4.1迪卡尔乘积与二元关系
例4：设A,B,C,D为任意集合，判断真假。 （1）A×B=A×CB=C 证明：若A=，B={1}，C={2} 则A×B=A×C=，而BC。 所以：命题真假不定
PPT课件
17

5,
1 1
10
2,
2 0
11
3,
2 2
01
第8页8
积代数性质
设 V1 = <S1,o>和 V2 = <S2,>是代数系统，其中 o 和 是二元运算. V1 与 V2 积代数是 V=<S1S2,∙> (1) 若 o 和 运算是可交换，那么∙ 运算也是可交换 (2) 若 o 和 运算是可结合，那么∙ 运算也是可结合 (3) 若 o 和 运算是幂等，那么∙ 运算也是幂等 (4) 若 o 和 运算分别含有单位元 e1 和 e2，那么∙ 运算
实例 N是<Z,+> 和<Z,+,0>子代数. N{0}是<Z,+> 子代数，但不是<Z,＋,0>子代数
说明： 子代数和原代数是同种代数系统 对于任何代数系统 V ，其子代数一定存在.
第6页6
关于子代数术语
最大子代数 就是V 本身. 假如V 中全部代数常数组 成集合 B，且 B 对V 中全部运算封闭，则 B 就组 成了V 最小子代数. 最大和最小子代数称为V 平凡 子代数. 若 B 是 S 真子集，则 B 组成子代数称为V 真子代数 . 例2 设V=<Z,+,0>，令 nZ = { nz | z∈Z}，n 为自然 数，则 nZ 是 V 子代数, 当 n = 1 和 0 时，nZ 是 V 平凡子代数，其它都是 V 非平凡真子代数.
第111页1
例题
例1 V=<R*,>, 判断下面哪些函数是V 自同态？ (1) f(x)=|x| (2) f(x)=2x (3) f(x)=x2 (4) f(x)=1/x (5) f(x)= x (6) f(x)=x+1