1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsMathematical Structures （数学结构）2* College of Computer Science & Technology, BUPT Mathematical structuren A collection of objects with operations defined on them and the accompanying properties form a mathema
2、tical structure or system. n In this book we deal only with discrete mathematical structures.3* College of Computer Science & Technology, BUPT Example 1n The collection of sets with the operations of union, intersection, and complement and their accompanying properties is a (discrete) mathematical s
3、tructure. We denote this structure by sets, , , . 4* College of Computer Science & Technology, BUPT Example 2n The collection of 3 3 matrices with the operations of addition, multiplication, and transpose（ 转置） is a mathematical structure denoted by 3 3 matrices, +, , T .5* College of Computer Scienc
4、e & Technology, BUPT Closure（ 封闭性）n A structure is closed with respect to an operation if that operation always produces another member of the collection of objects.6* College of Computer Science & Technology, BUPT Examplesn The structure 5 5 matrices, +, *, T is closed with respect to addition beca
5、use the sum of two 5 5 matrices is another 5 5 matrix.n The structure odd integers, +, * is not closed with respect to addition. n The sum of two odd integers is an even integer.n This structure does have the closure property for multiplication, since the product of two odd numbers is an odd number.
6、 7* College of Computer Science & Technology, BUPT Binary operation（ 二元运算）n An operation that combines two objects is a binary operation. n An operation that requires only one object is a unary operation（ 一元运算） . n Binary operations often have similar properties, as we have seen earlier.n Examplen (
7、a) Set intersection is a binary operation since it combines two sets to produce a new set.n Producing the transpose of matrix is a unary operation.8* College of Computer Science & Technology, BUPT Commutative （ 交换性）n Common properties have been given names. n For example, if the order of the objects
8、 does not affect the outcome of a binary operation, we say that the operation is commutative. n That is, if x y = y x, where is some binary operation, is commutative .n Example n (a) Join and meet for Boolean matrices are commutative operations.n AB=B A and AB=B A.n (b) Ordinary matrix multiplicatio
9、n is not a commutative operation ABBA.9* College of Computer Science & Technology, BUPT Noten an operation has a property means the statement of the property is true when the operation is used with any objects in the structure. n If there is even one case when the statement is not true, the operation does not have that property. 10* College of Computer Science & Technology, BUPT Associative（ 结合性）n If n is a binary operation, then n is associative or has the associative property if (x y) z =x (y z).n Examplen Set union is an associative operation, since (A B) C = A (B C) is always true.
