DOC PREVIEW
GSU CSC 2510 - ch08s1

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Modeling Arithmetic, Computation, and LanguagesAlgebraic StructuresSlide 3Slide 4Slide 5Slide 6Slide 7Basic Results About GroupsSlide 9SubgroupsSlide 11Slide 12Isomorphic GroupsSlide 14Slide 15Modeling Arithmetic, Computation, and LanguagesMathematical Structures for Computer ScienceChapter 8Copyright © 2006 W.H. Freeman & Co. MSCS Slides Algebraic StructuresSection 8.1 Algebraic Structures 2Algebraic StructuresDEFINITIONS: PROPERTIES OF BINARY OPERATIONS Let S be a set and let - denote a binary operation on S. (Here - does not necessarily denote multiplication but simply any binary operation.)The operation is associative if(x)(y)(z)[x - (y - z) = (x - y) - z]Associativity allows us to write x - y - z without using parentheses because grouping does not matter.1. The operation is commutative if(x)(y)(x - y = y - x)2. [S, -] has an identity element if(i)( x)(x - i = i - x = x)3. If [S, -] has an identity element i, then each element in S has an inverse with respect to if(x)(x1)(x - x1 = x1 - x = i )Section 8.1 Algebraic Structures 3Algebraic StructuresDEFINITIONS: GROUP, COMMUTATIVEGROUP [S, -] is a group if S is a nonempty set and - is a binary operation on S such that- is associativean identity element exists (in S)each element in S has an inverse (in S) with respect to -A group in which the operation is commutative is called a commutative group.Section 8.1 Algebraic Structures 4Algebraic StructuresFor example, Let R+ denote the positive real numbers and let - denote real-number multiplication, which is a binary operation on R+. Then [R+, -] is a commutative group.Multiplication is associative and commutative.The positive real number 1 serves as an identity becausex - 1 = 1 - x = xEvery positive real number x has an inverse with respect to multiplication, namely the positive real number 1/x, becausex - 1/x = 1/x - x = 1Section 8.1 Algebraic Structures 5Algebraic StructuresA structure called a monoid results from dropping the inverse property in the definition of a group.A semigroup results from dropping the identity property and the inverse property in the definition of a group.Many familiar forms of arithmetic are instances of semigroups, monoids, and groups.Section 8.1 Algebraic Structures 6Algebraic StructuresAn expression of the formanxn + an1xn1 + ... + a0where ai  R, i = 0, 1, ... , n, and n  N is a polynomial in x with real-number coefficients (or a polynomial in x over R).For each i, ai is the coefficient of xi.If i is the largest integer greater than 0 for which ai  0, the polynomial is of degree i.If no such i exists, the polynomial is of zero degree. Terms with zero coefficients are generally not written.The set of all polynomials in x over is denoted by R[x].Section 8.1 Algebraic Structures 7Algebraic StructuresWe define binary operations of + and - in R[x] to be polynomial addition and multiplication.For polynomials f (x) and g(x) members of R[x], the products f (x) - g(x) and g(x) - f (x) are equal because the coefficients are real numbers, and we can use all the properties of real numbers under multiplication and addition.Similarly, for f (x), g(x), and h(x) members of R[x], ( f (x) * g(x)) - h(x) = f (x) - (g(x) - h(x)).The constant polynomial 1 is an identity because 1 - f (x) = f (x) - 1 = f (x).Thus, [R[x]], - ] is a commutative monoid.It fails to be a group because only the nonzero constant polynomials have inverses.Section 8.1 Algebraic Structures 8Basic Results About GroupsTHEOREM ON THE UNIQUENESS OF THE IDENTITY IN A GROUP In any group (or monoid) [G, -], the identity element i is unique.To prove that the identity element is unique, suppose that i1 and i2 are both identity elements. Then i1 = i1 - i2 = i2.THEOREM ON THE UNIQUENESS OF INVERSES IN A GROUP For each x in a group [G, -], x1 is unique.THEOREM ON THE INVERSE OF A PRODUCTFor x and y members of a group [G, -], (x - y) 1 = y1 - x1.DEFINITION: CANCELLATION LAWS A set S with a binary operation satisfies the right cancellation law if for x, y, z  S, x - z = y - z implies x = y. It satisfies the left cancellation law if z - x = z - y implies x = y.Section 8.1 Algebraic Structures 9Basic Results About GroupsTHEOREM ON CANCELLATION IN A GROUPAny group [G, -] satisfies the left and right cancellation laws.THEOREM ON SOLVING LINEAR EQUATIONS IN A GROUP Let a and b be any members of a group [G, -]. Then the linear equations a - x = b and x - a = b have unique solutions in G.If [G, -] is a group where G is finite with n elements, then n is said to be the order of the group, denoted by G. If G is an infinite set, the group is of infinite order.Section 8.1 Algebraic Structures 10SubgroupsDEFINITION: SUBGROUP Let [G, -] be a group and A  G. Then [A, -] is a subgroup of [G, -] if [A, -] is itself a group.To test whether [A, -] is a subgroup of [G, -], we can assume the inherited properties of a well-defined operation and associativity and check for the three remaining properties required.THEOREM ON SUBGROUPS For [G, -] a group with identity i and A  G, [A, -] is a subgroup of [G, -] if it meets the following three tests: A is closed under -. i  A.Every x  A has an inverse element in A.Section 8.1 Algebraic Structures 11SubgroupsIf [G, -] is a group with identity i, then it is true that [{i}, -] and [G, -] are subgroups of [G, -].These somewhat trivial subgroups of [G, -] are called improper subgroups. Any other subgroups of [G, -] are proper subgroups.An interesting subgroup can always be found in the symmetric group Sn for n > 1. We know that every member of Sn can be written as a composition of cycles, but it is also true that each cycle can be written as the composition of cycles of length 2, called transpositions. In S7, (5, 1, 7, 2, 3, 6) = (5, 6) ° (5, 3) ° (5, 2) ° (5, 7) ° (5, 1).We classify any permutation as even or odd according to the number of transpositions in any representation of that permutation.Section 8.1 Algebraic Structures 12SubgroupsTHEOREM ON ALTERNATING GROUPS For n  N, n > 1, the set An of even permutations determines a subgroup, called the alternating group, of [Sn, °] of order n!/2.There is a relationship between the size of a group and the size of a subgroup. This relationship is stated in Lagrange’s theorem.LAGRANGE’S THEOREM The order of a


View Full Document

GSU CSC 2510 - ch08s1

Documents in this Course
ch02s2

ch02s2

5 pages

ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch08s3

ch08s3

15 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch06s3

ch06s3

16 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch03s1

ch03s1

19 pages

ch07s1

ch07s1

11 pages

ch02s1

ch02s1

14 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Download ch08s1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch08s1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch08s1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?