Difference between revisions of "Chapter 14: Mathematical Foundations"

From SWEBOK
Jump to: navigation, search
(Set, Relations, Functions)
(Set, Relations, Functions)
Line 109: Line 109:
 
If X is not a proper subset of Y, it is denoted
 
If X is not a proper subset of Y, it is denoted
 
as X ⊄ Y.
 
as X ⊄ Y.
 +
 +
''Superset''. If X is a subset of Y, then Y is called
 +
a 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.

Revision as of 10:32, 28 August 2015

Introduction

Software professionals live with programs. In a very simple language, one can program only for something that follows a well-understood, nonambiguous logic. The Mathematical Foundations knowledge area (KA) helps software engineers comprehend this logic, which in turn is translated into programming language code. The mathematics that is the primary focus in this KA is quite different from typical arithmetic, where numbers are dealt with and discussed. Logic and reasoning are the essence of mathematics that a software engineer must address.

Mathematics, in a sense, is the study of formal systems. The word “formal” is associated with preciseness, so there cannot be any ambiguous or erroneous interpretation of the fact. Mathematics is therefore the study of any and all certain truths about any concept. This concept can be about numbers as well as about symbols, images, sounds, video—almost anything. In short, not only numbers and numeric equations are subject to preciseness. On the contrary, a software engineer needs to have a precise abstraction on a diverse application domain.

The SWEBOK Guide’s Mathematical Foundations KA covers basic techniques to identify a set of rules for reasoning in the context of the system under study. Anything that one can deduce following these rules is an absolute certainty within the context of that system. In this KA, techniques that can represent and take forward the reasoning and judgment of a software engineer in a precise (and therefore mathematical) manner are defined and discussed. The language and methods of logic that are discussed here allow us to describe mathematical proofs to infer conclusively the absolute truth of certain concepts beyond the numbers. In short, you can write a program for a problem only if it follows some logic. The objective of this KA is to help you develop the skill to identify and describe such logic. The emphasis is on helping you understand the basic concepts rather than on challenging your arithmetic abilities.

Figure 14.1: Breakdown of Topics for the Mathematical Foundations KA
Breakdown of Topics for Mathematical Foundations

The breakdown of topics for the Mathematical Foundations KA is shown in Figure 14.1.

Set, Relations, Functions

[1, c2]

Set. A set is a collection of objects, called elements of the set. A set can be represented by listing its elements 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 a member of the set. Its negation is represented by ∉, e.g., 1 ∈ S, but 4 ∉ S.

In a more compact representation of set using set builder notation, {x | P(x)} is the set of all x such that P(x) for any proposition P(x) over any universe of discourse. Examples for some important sets include the following:

  • N = {0, 1, 2, 3, …} = the set of nonnegative integers.
  • Z = {…, −3, −2, −1, 0, 1, 2, 3, …} = the set of integers.

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 natural numbers, for example, is an infinite set.

Cardinality. The cardinality of a finite set S is the 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 which the predicate P(x) must be interpreted. The “universe of discourse” for a given predicate is often referred to as the universal set. Alternately, one may define universal set as the set of all elements.

Set Equality. Two sets are equal if and only if they have the same elements, i.e.:

  • X = Y ≡ ∀p (p ∈ X ↔ p ∈ Y).

Subset. X is a subset of set Y, or X is contained in Y, if all elements of X are included in Y. This is denoted by X ⊆ Y. In other words, X ⊆ Y if and only 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 (denoted by 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 a proper subset of Z. Sets X and Z are equal sets. If X is not a proper subset of Y, it is denoted as X ⊄ Y.

Superset. If X is a subset of Y, then Y is called a 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.