Software Engineering Body of Knowledge (v3) (2014) (811503), страница 72
Текст из файла (страница 72)
Mathematics is therefore the study of any and all certaintruths about any concept. This concept can beabout numbers as well as about symbols, images,sounds, video—almost anything. In short, notonly numbers and numeric equations are subject to preciseness.
On the contrary, a softwareengineer needs to have a precise abstraction on adiverse application domain.The SWEBOK Guide’s Mathematical Foundations KA covers basic techniques to identify a setof rules for reasoning in the context of the systemunder study. Anything that one can deduce following these rules is an absolute certainty withinthe context of that system. In this KA, techniquesthat can represent and take forward the reasoningand judgment of a software engineer in a precise(and therefore mathematical) manner are definedand discussed.
The language and methods of logicthat are discussed here allow us to describe mathematical proofs to infer conclusively the absolutetruth of certain concepts beyond the numbers. Inshort, you can write a program for a problem onlyif it follows some logic. The objective of this KAis to help you develop the skill to identify anddescribe such logic. The emphasis is on helpingyou understand the basic concepts rather than onchallenging your arithmetic abilities.BREAKDOWN OF TOPICS FORMATHEMATICAL FOUNDATIONSThe breakdown of topics for the MathematicalFoundations KA is shown in Figure 14.1.1. Set, Relations, Functions[1*, c2]Set. A set is a collection of objects, called elementsof the set. A set can be represented by listing itselements between braces, e.g., S = {1, 2, 3}.The symbol ∈ is used to express that an element belongs to a set, or—in other words—is amember of the set.
Its negation is represented by∉, e.g., 1 ∈ S, but 4 ∉ S.In a more compact representation of set usingset builder notation, {x | P(x)} is the set of all xsuch that P(x) for any proposition P(x) over anyuniverse of discourse. Examples for some important sets include the following:N = {0, 1, 2, 3, …} = the set of nonnegativeintegers.Z = {…, −3, −2, −1, 0, 1, 2, 3, …} = the set ofintegers.Finite and Infinite Set.
A set with a finite number of elements is called a finite set. Conversely,any set that does not have a finite number of elements in it is an infinite set. The set of all naturalnumbers, for example, is an infinite set.14-114-2 SWEBOK® Guide V3.0Figure 14.1. Breakdown of Topics for the Mathematical Foundations KACardinality. The cardinality of a finite set S isthe number of elements in S. This is represented|S|, e.g., if S = {1, 2, 3}, then |S| = 3.Universal Set. In general S = {x ∈ U | p(x)},where U is the universe of discourse in whichthe predicate P(x) must be interpreted.
The “universe of discourse” for a given predicate is oftenreferred to as the universal set. Alternately, onemay define universal set as the set of all elements.Set Equality. Two sets are equal if and only ifthey have the same elements, i.e.:X = Y ≡ ∀p (p ∈ X ↔ p ∈ Y).Subset. X is a subset of set Y, or X is containedin Y, if all elements of X are included in Y. This isdenoted by X ⊆ Y. In other words, X ⊆ Y if andonly if ∀p (p ∈ X → p ∈ Y).For example, if X = {1, 2, 3} and Y = {1, 2, 3,4, 5}, then X ⊆ Y.If X is not a subset of Y, it is denoted as X Y.Proper Subset. X is a proper subset of Y (denotedby X ⊂ Y) if X is a subset of Y but not equal to Y,i.e., there is some element in Y that is not in X.In other words, X ⊂ Y if (X ⊆ Y) ∧ (X ≠ Y).For example, if X = {1, 2, 3}, Y = {1, 2, 3,4}, and Z = {1, 2, 3}, then X ⊂ Y, but X is not aproper subset of Z.
Sets X and Z are equal sets.If X is not a proper subset of Y, it is denotedas X ⊄ Y.Superset. If X is a subset of Y, then Y is calleda superset of X. This is denoted by Y ⊇ X, i.e., Y⊇ X if and only if X ⊆ Y.For example, if X = {1, 2, 3} and Y = {1, 2, 3,4, 5}, then Y ⊇ X.Empty Set. A set with no elements is called anempty set.
An empty set, denoted by ∅, is alsoreferred to as a null or void set.Power Set. The set of all subsets of a set X iscalled the power set of X. It is represented as℘(X).For example, if X = {a, b, c}, then ℘(X) = {∅,{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. If|X| = n, then |℘(X)| = 2n.Venn Diagrams. Venn diagrams are graphic representations of sets as enclosed areas in the plane.For example, in Figure 14.2, the rectangle represents the universal set and the shaded regionrepresents a set X.Figure 14.2. Venn Diagram for Set X1.1. Set OperationsIntersection.
The intersection of two sets X andY, denoted by X ∩ Y, is the set of common elements in both X and Y.In other words, X ∩ Y = {p | (p ∈ X) ∧ (p ∈ Y)}.As, for example, {1, 2, 3} ∩ {3, 4, 6} = {3}If X ∩ Y = f, then the two sets X and Y are saidto be a disjoint pair of sets.Mathematical Foundations 14-3A Venn diagram for set intersection is shown inFigure 14.3. The common portion of the two setsrepresents the set intersection.The shaded portion of the Venn diagram in Figure 14.5 represents the complement set of X.Set Difference or Relative Complement. The setof elements that belong to set X but not to set Ybuilds the set difference of Y from X.
This is represented by X − Y.In other words, X − Y = {p | (p ∈ X) ∧ (p ∉ Y)}.As, for example, {1, 2, 3} − {3, 4, 6} = {1, 2}.It may be proved that X − Y = X ∩ Y’.Set difference X – Y is illustrated by the shadedregion in Figure 14.6 using a Venn diagram.Figure 14.3. Intersection of Sets X and YUnion. The union of two sets X and Y, denotedby X ∪ Y, is the set of all elements either in X, orin Y, or in both.In other words, X ∪ Y = {p | (p ∈ X) ∨ (p ∈ Y)}.As, for example, {1, 2, 3} ∪ {3, 4, 6} = {1, 2,3, 4, 6}.Figure 14.6.
Venn Diagram for X − YFigure 14.4. Union of Sets X and YIt may be noted that |X ∪ Y| = |X| + |Y| − |X∩ Y|.A Venn diagram illustrating the union of twosets is represented by the shaded region in Figure14.4.Complement. The set of elements in the universal set that do not belong to a given set X is calledits complement set X'.In other words, X' ={p | (p ∈ U) ∧ (p ∉ X)}.Cartesian Product. An ordinary pair {p, q} isa set with two elements.
In a set, the order of theelements is irrelevant, so {p, q} = {q, p}.In an ordered pair (p, q), the order of occurrences of the elements is relevant. Thus, (p, q) ≠(q, p) unless p = q. In general (p, q) = (s, t) if andonly if p = s and q = t.Given two sets X and Y, their Cartesian productX × Y is the set of all ordered pairs (p, q) such thatp ∈ X and q ∈ Y.In other words, X × Y = {(p, q) | (p ∈ X) ∧ (q∈ Y)}.As for example, {a, b} × {1, 2} = {(a, 1), (a, 2),(b, 1), (b, 2)}1.2. Properties of SetSome of the important properties and laws of setsare mentioned below.Figure 14.5.
Venn Diagram for Complement Set of X1. Associative Laws:X ∪ (Y ∪ Z) = (X ∪ Y) ∪ ZX ∩ (Y ∩ Z) = (X ∩ Y) ∩ Z14-4 SWEBOK® Guide V3.02. Commutative Laws:X ∪ Y = Y ∪ XX∩Y=Y∩X3. Distributive Laws:X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z)X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)4. Identity Laws:X ∪ ∅ = X X ∩ U = X5. Complement Laws:X ∪ X' = U X ∩ X' = ∅6. Idempotent Laws:X ∪ X = XX∩X=X7.
Bound Laws:X ∪ U = UX∩∅=∅8. Absorption Laws:X ∪ (X ∩ Y) = XX ∩ (X ∪ Y) = X9. De Morgan’s Laws:(X ∪ Y)' = X' ∩ Y'(X ∩ Y)' = X' ∪ Y'1.3. Relation and FunctionA relation is an association between two sets ofinformation. For example, let’s consider a setof residents of a city and their phone numbers.The pairing of names with corresponding phonenumbers is a relation. This pairing is ordered forthe entire relation. In the example being considered, for each pair, either the name comes firstfollowed by the phone number or the reverse.The set from which the first element is drawn iscalled the domain set and the other set is calledthe range set.
The domain is what you start withand the range is what you end up with.A function is a well-behaved relation. A relation R(X, Y) is well behaved if the function mapsevery element of the domain set X to a single element of the range set Y. Let’s consider domain setX as a set of persons and let range set Y store theirphone numbers. Assuming that a person may havemore than one phone number, the relation beingconsidered is not a function. However, if we drawa relation between names of residents and theirdate of births with the name set as domain, thenthis becomes a well-behaved relation and hence afunction. This means that, while all functions arerelations, not all relations are functions.
In caseof a function given an x, one gets one and exactlyone y for each ordered pair (x, y).For example, let’s consider the following tworelations.A: {(3, –9), (5, 8), (7, –6), (3, 9), (6, 3)}.B: {(5, 8), (7, 8), (3, 8), (6, 8)}.Are these functions as well?In case of relation A, the domain is all thex-values, i.e., {3, 5, 6, 7}, and the range is all they-values, i.e., {–9, –6, 3, 8, 9}.Relation A is not a function, as there are twodifferent range values, –9 and 9, for the samex-value of 3.In case of relation B, the domain is same as thatfor A, i.e., {3, 5, 6, 7}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
