《离散结构》 二元运算性质的判断 西安工程大学计算机科学学院 王爱丽
主要内容 交换律的判断 幂等律的判断 结合律的判断
内容回顾 ————运算性质的基本概念
若对任意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上满足幂等律。
交换律的判断 若运算表的元素关于主对角线对称分布，那么运算是满足交换律的。
例题 * [1] [2] [3] [4] [5] [6]
例题
如果主对角线元素的排列顺序与表头元素的排列顺序一样，那么运算是满足幂等律的。 幂等律的判断 如果主对角线元素的排列顺序与表头元素的排列顺序一样，那么运算是满足幂等律的。
例题
结合律的判断 为验证结合律是否成立，应该对S中所有元素x,y,z 验证(x ◦ y) ◦ z=x ◦(y ◦ z)是否为真。 设|S|=n,则需要验证 个式子。 当n=3时，27个； 当n=4时，64个； 当n=6时，216个； 哇哦！这个计算量蛮大的！
结合律的判断 (1)幺元不用参加判断； (2)零元不用参加判断； (3)若运算满足交换律，则形如(x◦y)◦x?=x◦(y◦x)的式子不用判断。 除去这些，结合律的判断是不是简洁多了呢？
例题 U φ {1} {2} {1,2} 关于主对角线对称，满足交换律。故形如xyx的式子不用验证
例题