复旦大学：《离散数学》PPT教学课件（赵一鸣）21/28

Chapter 6 Abstract algebra Groups v Rings√ Field√ a Lattics and boolean algebra

Chapter 6 Abstract algebra  Groups   Rings   Field   Lattics and Boolean algebra

6.1 Operations on the set o Definition 1: An unary operation on a nonempty set S is an everywhere function ffrom S into S; A binary operation on a nonempty set S is an everywhere function f from sXSinto S; A n-ary operation on a nonempty set s is an everywhere function f from Sn into S closed

6.1 Operations on the set ⚫ Definition 1：An unary operation on a nonempty set S is an everywhere function f from S into S; A binary operation on a nonempty set S is an everywhere function f from S×S into S; A n-ary operation on a nonempty set S is an everywhere function f from S n into S.  closed

Associative law: Let s be a binary operation on a set S. a*(b*c=(a*b)*c for Va,b,c∈S Commutative law: Let *k be a binary operation on a set s. a*b=b*a for Va, bES Identity element: Let be a binary operation on a set s. An element e of s is an identity element if=e*a=afor all a ∈S Theorem 6.1: If s has an identity element, then it is unique

 Associative law: Let  be a binary operation on a set S. a(bc)=(ab)c for a,b,cS  Commutative law: Let  be a binary operation on a set S. ab=ba for a,bS  Identity element: Let  be a binary operation on a set S. An element e of S is an identity element if ae=ea=a for all a S.  Theorem 6.1: If  has an identity element, then it is unique

Inverse element: Let s be a binary operation on a set S with identity element e Let a ES. Then b is an inverse ofa a*b b*ka=e o Theorem 6.2: Let a be a binary operation on a set a with identity element e. ifthe operation is associative, then inverse element of a is unique when a has its inverse

• Inverse element: Let  be a binary operation on a set S with identity element e. Let a S. Then b is an inverse of a if ab = ba = e. • Theorem 6.2: Let  be a binary operation on a set A with identity element e. If the operation is Associative, then inverse element of a is unique when a has its inverse

■ Distributive laws:Let*and● be two binary operations on nonempty s. For va,b,c∈S, a●(b*C)=(a·b*(a·),b*c)●a=(b●a)*(c●a) Associative law commutative Identity Inverse law elements element 0 -a for a l/a for ≠=0

 Distributive laws: Let  and • be two binary operations on nonempty S. For a,b,cS,  a•(bc)=(a•b)(a•c), (bc)•a=(b•a)(c•a) Associative law commutative law Identity elements Inverse element + √ √ 0 -a for a  √ √ 1 1/a for a0

Definition 2: An algebraic system is a nonempty set s in which at least one or more operations C1…Q1(k≥1),are defined. We denoted by s; Qis, QkI Z;+] ●[Z;+,2 ]is not an algebraic system

• Definition 2: An algebraic system is a nonempty set S in which at least one or more operations Q1 ,…,Qk (k1), are defined. We denoted by [S;Q1 ,…,Qk ]. • [Z;+] • [Z;+,*] • [N;-] is not an algebraic system

Definition 3: Let [S; and T; are two algebraic system with a binary operation. A function (p from s to T is called a homomorphism from S;* to T; o if cp(a*b=p(ao(b)for Va, bES

 Definition 3: Let [S;*] and [T;•] are two algebraic system with a binary operation. A function  from S to T is called a homomorphism from [S;*] to [T;•] if (a*b)=(a)•(b) for a,bS

Theorem 6.3 Let p be a homomorphism from S; to T;. If p is onto, then the following results hold ()If x is Associative on S, then is also Associative on a (2)If x is commutative on S, then is also commutation on T 3)If there exist identity element e in S; l, then cp(e)is identity element of T (4)Let e be identity element of [s;. If there is the inverse element al of dES, then op(a-l)is the inverse element (p(a

 Theorem 6.3 Let  be a homomorphism from [S;*] to [T;•]. If  is onto, then the following results hold.  (1)If * is Associative on S, then • is also Associative on T.  (2)If * is commutative on S, then • is also commutation on T  (3)If there exist identity element e in [S;*],then (e) is identity element of [T;•]  (4) Let e be identity element of [S;*]. If there is the inverse element a -1 of aS, then (a -1 ) is the inverse element (a)

a Definition 4: Let be a homomorphism from|S;]to[T;● is called an isomorphism if p is also one-to-one correspondence. We say that two algebraic systems [S; and t; o are isomorphism, if there exists an isomorphic function. We denoted by s; =T; I(S=T)

 Definition 4: Let  be a homomorphism from [S;*] to [T;•].  is called an isomorphism if  is also one-to-one correspondence. We say that two algebraic systems [S;*] and [T;•] are isomorphism, if there exists an isomorphic function. We denoted by [S;*][T;•](ST)

6.2 Semigroups, monoids and groups 6.2.1 Semigroups, monoids Definition 5: A semigroup S; is a nonempty set together with a binary operation satisfying associative law. Definition 6: A monoid is a semigroup [ s; a that has an identity

6.2 Semigroups,monoids and groups • 6.2.1 Semigroups, monoids • Definition 5: A semigroup [S;] is a nonempty set together with a binary operation  satisfying associative law. • Definition 6: A monoid is a semigroup [S; ] that has an identity