Download presentation
Presentation is loading. Please wait.
1
《离散结构》 二元运算性质的判断 西安工程大学计算机科学学院 王爱丽
2
主要内容 交换律的判断 幂等律的判断 结合律的判断
3
内容回顾 ————运算性质的基本概念
4
若对任意x∈S 有 x◦x=x, 则称运算在S上满足幂等律。
二元运算的性质 若对任意x,y,z∈S有 (x◦y)◦z=x◦(y◦z), 则称运算在S上满足结合律。 设◦为S上的二元运算,若对任意x,y∈S 有 x◦y=y◦x, 则称运算在S上满足交换律。 若对任意x∈S 有 x◦x=x, 则称运算在S上满足幂等律。
5
交换律的判断 若运算表的元素关于主对角线对称分布，那么运算是满足交换律的。
6
例题 * [1] [2] [3] [4] [5] [6]
![例题 * [1] [2] [3] [4] [5] [6]](http://slidesplayer.com/slide/16901618/97/images/6/%E4%BE%8B%E9%A2%98+%2A+%5B1%5D+%5B2%5D+%5B3%5D+%5B4%5D+%5B5%5D+%5B6%5D.jpg "例题 * [1] [2] [3] [4] [5] [6]")
7
例题
8
如果主对角线元素的排列顺序与表头元素的排列顺序一样，那么运算是满足幂等律的。
幂等律的判断 如果主对角线元素的排列顺序与表头元素的排列顺序一样，那么运算是满足幂等律的。
9
例题
10
结合律的判断 为验证结合律是否成立，应该对S中所有元素x,y,z 验证(x ◦ y) ◦ z=x ◦(y ◦ z)是否为真。
设|S|=n,则需要验证 个式子。 当n=3时，27个； 当n=4时，64个； 当n=6时，216个； 哇哦！这个计算量蛮大的！
11
结合律的判断 (1)幺元不用参加判断； (2)零元不用参加判断；
(3)若运算满足交换律，则形如(x◦y)◦x?=x◦(y◦x)的式子不用判断。 除去这些，结合律的判断是不是简洁多了呢？
12
例题 U φ {1} {2} {1,2} 关于主对角线对称，满足交换律。故形如xyx的式子不用验证
13
例题
Similar presentations
