Software Engineering Body of Knowledge (v3) (2014) (811503), страница 77
Текст из файла (страница 77)
Zerois not in this group. There are no negative or fractional numbers in the group of natural numbers.The common mathematical symbol for the set ofall natural numbers is N.Whole Numbers. This group has all of the natural numbers in it plus the number 0.Unfortunately, not everyone accepts the abovedefinitions of natural and whole numbers. Thereseems to be no general agreement about whetherto include 0 in the set of natural numbers.Many mathematicians consider that, in Europe,the sequence of natural numbers traditionallystarted with 1 (0 was not even considered to bea number by the Greeks). In the 19th century, settheoreticians and other mathematicians startedthe convention of including 0 in the set of naturalnumbers.Integers. This group has all the whole numbersin it and their negatives.
The common mathematical symbol for the set of all integers is Z, i.e., Z ={…, −3, −2, −1, 0, 1, 2, 3, …}.Rational Numbers. These are any numbers thatcan be expressed as a ratio of two integers. Thecommon symbol for the set of all rational numbers is Q.Rational numbers may be classified intothree types, based on how the decimals act. Thedecimals either do not exist, e.g., 15, or, whendecimals do exist, they may terminate, as in 15.6,or they may repeat with a pattern, as in 1.666...,(which is 5/3).Irrational Numbers. These are numbers thatcannot be expressed as an integer divided by aninteger.
These numbers have decimals that neverterminate and never repeat with a pattern, e.g., PIor √2.Real Numbers. This group is made up of all therational and irrational numbers. The numbers thatare encountered when studying algebra are realnumbers. The common mathematical symbol forthe set of all real numbers is R.Imaginary Numbers.
These are all based on theimaginary number i. This imaginary number isequal to the square root of −1. Any real numbermultiple of i is an imaginary number, e.g., i, 5i,3.2i, −2.6i, etc.Complex Numbers. A complex number is acombination of a real number and an imaginarynumber in the form a + bi. The real part is a, andb is called the imaginary part. The common mathematical symbol for the set of all complex numbers is C.For example, 2 + 3i, 3−5i, 7.3 + 0i, and 0 + 5i.Consider the last two examples:7.3 + 0i is the same as the real number 7.3.Thus, all real numbers are complex numbers withzero for the imaginary part.Similarly, 0 + 5i is just the imaginary number5i.
Thus, all imaginary numbers are complexnumbers with zero for the real part.Elementary number theory involves divisibilityamong integers. Let a, b ∈ Z with a ≠ 0.The expression a|b, i.e., a divides b if ∃c ∈ Z: b = ac, i.e., thereis an integer c such that c times a equals b.For example, 3|−12 is true, but 3|7 is false.If a divides b, then we say that a is a factor ofb or a is a divisor of b, and b is a multiple of a.b is even if and only if 2|b.Let a, d ∈ Z with d > 1. Then a mod d denotesthat the remainder r from the division algorithmwith dividend a and divisor d, i.e., the remainderwhen a is divided by d. We can compute (a modd) by: a − d * ⎣a/d⎦, where ⎣a/d⎦ represents thefloor of the real number.Let Z+ = {n ∈ Z | n > 0} and a, b ∈ Z, m ∈ Z+,then a is congruent to b modulo m, written as a ≡b (mod m), if and only if m | a−b.Mathematical Foundations 14-19Alternately, a is congruent to b modulo m if andonly if (a−b) mod m = 0.10.2. Prime Number, GCDAn integer p > 1 is prime if and only if it is notthe product of any two integers greater than 1,i.e., p is prime if p > 1 ∧ ∃ ¬ a, b ∈ N: a > 1, b >1, a * b = p.The only positive factors of a prime p are 1and p itself.
For example, the numbers 2, 13, 29,61, etc. are prime numbers. Nonprime integersgreater than 1 are called composite numbers. Acomposite number may be composed by multiplying two integers greater than 1.There are many interesting applications ofprime numbers; among them are the publickey cryptography scheme, which involves theexchange of public keys containing the productp*q of two random large primes p and q (a privatekey) that must be kept secret by a given party.The greatest common divisor gcd(a, b) of integers a, b is the greatest integer d that is a divisorboth of a and of b, i.e.,d = gcd(a, b) for max(d: d|a ∧ d|b)For example, gcd(24, 36) = 12.Integers a and b are called relatively prime orcoprime if and only if their GCD is 1.For example, neither 35 nor 6 are prime, butthey are coprime as these two numbers have nocommon factors greater than 1, so their GCD is 1.A set of integers X = {i1, i2, …} is relativelyprime if all possible pairs ih, ik, h ≠ k drawn fromthe set X are relatively prime.11. Algebraic StructuresThis section introduces a few representationsused in higher algebra.
An algebraic structureconsists of one or two sets closed under someoperations and satisfying a number of axioms,including none.For example, group, monoid, ring, and latticeare examples of algebraic structures. Each ofthese is defined in this section.11.1. GroupA set S closed under a binary operation • forms agroup if the binary operation satisfies the following four criteria:• Associative: ∀a, b, c ∈ S, the equation (a • b)• c = a • (b • c) holds.• Identity: There exists an identity element I ∈S such that for all a ∈ S, I • a = a • I = a.• Inverse: Every element a ∈ S, has an inversea' ∈ S with respect to the binary operation,i.e., a • a' = I; for example, the set of integersZ with respect to the addition operation is agroup.
The identity element of the set is 0 forthe addition operation. ∀x ∈ Z, the inverseof x would be –x, which is also included in Z.• Closure property: ∀a, b ∈ S, the result of theoperation a • b ∈ S.• A group that is commutative, i.e., a • b = b • a,is known as a commutative or Abelian group.The set of natural numbers N (with the operation of addition) is not a group, since there is noinverse for any x > 0 in the set of natural numbers.Thus, the third rule (of inverse) for our operationis violated.
However, the set of natural numberhas some structure.Sets with an associative operation (the firstcondition above) are called semigroups; if theyalso have an identity element (the second condition), then they are called monoids.Our set of natural numbers under addition isthen an example of a monoid, a structure thatis not quite a group because it is missing therequirement that every element have an inverseunder the operation.A monoid is a set S that is closed under a singleassociative binary operation • and has an identityelement I ∈ S such that for all a ∈ S, I • a = a • I= a.
A monoid must contain at least one element.For example, the set of natural numbers Nforms a commutative monoid under addition withidentity element 0. The same set of natural numbers N also forms a monoid under multiplicationwith identity element 1. The set of positive integers P forms a commutative monoid under multiplication with identity element 1.It may be noted that, unlike those in a group,elements of a monoid need not have inverses. A14-20 SWEBOK® Guide V3.0monoid can also be thought of as a semigroupwith an identity element.A subgroup is a group H contained within abigger one, G, such that the identity element ofG is contained in H, and whenever h1 and h2 arein H, then so are h1 • h2 and h1−1. Thus, the elements of H, equipped with the group operation onG restricted to H, indeed form a group.Given any subset S of a group G, the subgroupgenerated by S consists of products of elementsof S and their inverses.
It is the smallest subgroupof G containing S.For example, let G be the Abelian group whoseelements are G = {0, 2, 4, 6, 1, 3, 5, 7} and whosegroup operation is addition modulo 8. This grouphas a pair of nontrivial subgroups: J = {0, 4} andH = {0, 2, 4, 6}, where J is also a subgroup of H.In group theory, a cyclic group is a group thatcan be generated by a single element, in thesense that the group has an element a (called thegenerator of the group) such that, when writtenmultiplicatively, every element of the group is apower of a.A group G is cyclic if G = {an for any integer n}.Since any group generated by an element in agroup is a subgroup of that group, showing thatthe only subgroup of a group G that contains a isG itself suffices to show that G is cyclic.For example, the group G = {0, 2, 4, 6, 1, 3, 5,7}, with respect to addition modulo 8 operation,is cyclic.
The subgroups J = {0, 4} and H = {0, 2,4, 6} are also cyclic.11.2. RingsIf we take an Abelian group and define a secondoperation on it, a new structure is found that isdifferent from just a group. If this second operation is associative and is distributive over thefirst, then we have a ring.A ring is a triple of the form (S, +, •), where (S,+) is an Abelian group, (S, •) is a semigroup, and• is distributive over +; i.e., “ a, b, c ∈ S, the equation a • (b + c) = (a • b) + (a • c) holds. Further, if• is commutative, then the ring is said to be commutative.
If there is an identity element for the •operation, then the ring is said to have an identity.For example, (Z, +, *), i.e., the set of integers Z,with the usual addition and multiplication operations, is a ring. As (Z, *) is commutative, this ringis a commutative or Abelian ring. The ring has 1as its identity element.Let’s note that the second operation may nothave an identity element, nor do we need to findan inverse for every element with respect to thissecond operation. As for what distributive means,intuitively it is what we do in elementary mathematics when performing the following change: a* (b + c) = (a * b) + (a * c).A field is a ring for which the elements of theset, excluding 0, form an Abelian group with thesecond operation.A simple example of a field is the field of rational numbers (R, +, *) with the usual additionand multiplication operations.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
