离散数学课件(英文版)----Semigroup.ppt

Algebraic Systems and Groups Lecture 13 Discrete Mathematical Structures Algebraic Operations Function ?:An?B is called an n-nary operation from A to B. Binary operation: ?:A?A?B (?:A?A?A) An example: a new operation “*” defined on the set of real number, using common arithmetic operations: x*y = x+y-xy Note: 2*3 = -1； 0.5*0.7 = 0.85 Closeness of Operations For any operation ?:An?B, if B?A, then it is said that A is closed with respect to ?. Or, we say that ? is closed on A. Example: Set A={1,2,3,…,10}, gcd is closed, but lcm is not. Operation Table Operation table can be used to define unary or binary operations on a finite set (usually only with several elements) Association Operation “?” defined on the set A is associative if and only if: For any x, y, z ?A, (x?y)?z = x?(y?z) If “?” is associative, then x1?x2?x3?…? xn can be computed by any order of among the (n-1) operations, with the constraint that the order of all operands are not changed. Commutation Operation “?” defined on the set A is associative if and only if: For any x, y ?A, x?y = y?x If “?” is commutative and associative, then x1?x2?x3?…? xn can be computed by any order of the operations, and in any permutation of all operands. Distribution Two different operations must be defined for an algebraic system for discussion of distribution. Operation “?” is distributive over “?” (both operations defined on the set A) if and only if : For any x, y, z ?A, x?(y?z) = (x?y)?(x?z) (Exactly speaking, this is the first distributive property) Identity of an Algebraic System For arithmetic multiplication on the set of real number, there is a specific real number 1，satisfying that for any real number x, 1?x=x?1=x An element e is called the identity element of an algebraic system (S,?) if and only if : For any x?S, e?x=x?e=x。 Denotation: 1S, or simply 1, but remember that it is not that “1”. It is not that every algebraic system has its identity elemen