Chapter 14: Mathematical Foundations

From SWEBOK
Revision as of 13:30, 28 August 2015 by Daniel Robbins (Talk | contribs) (Basics of Counting)

Jump to: navigation, search
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.

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.

Empty Set. A set with no elements is called an empty set. An empty set, denoted by ∅, is also referred to as a null or void set.

Power Set. The set of all subsets of a set X is called 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 region represents a set X.

Figure 14.2: Venn Diagram for Set X

1.1 Set Operations

Intersection. The intersection of two sets X and Y, 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 said to be a disjoint pair of sets.

A Venn diagram for set intersection is shown in Figure 14.3. The common portion of the two sets represents the set intersection.

Figure 14.3: Intersection of Sets X and Y

Union. The union of two sets X and Y, denoted by X ∪ Y, is the set of all elements either in X, or in 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}. It may be noted that |X ∪ Y| = |X| + |Y| − |X ∩ Y|.

A Venn diagram illustrating the union of two sets is represented by the shaded region in Figure 14.4.

Figure 14.4: Union of Sets X and Y

Complement. The set of elements in the universal set that do not belong to a given set X is called its complement set X'. In other words, X' ={p | (p ∈ U) ∧ (p ∉ X)}. The shaded portion of the Venn diagram in Figure 14.5 represents the complement set of X

Figure 14.5: Venn Diagram for Complement Set of X

Set Difference or Relative Complement. The set of elements that belong to set X but not to set Y builds 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 shaded region in Figure 14.6 using a Venn diagram.

Figure 14.6: Venn Diagram for X − Y

Cartesian Product. An ordinary pair {p, q} is a set with two elements. In a set, the order of the elements 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 and only if p = s and q = t. Given two sets X and Y, their Cartesian product X × Y is the set of all ordered pairs (p, q) such that p ∈ 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 Set

Some of the important properties and laws of sets are mentioned below.

1. Associative Laws:

X ∪ (Y ∪ Z) = (X ∪ Y) ∪ Z

X ∩ (Y ∩ Z) = (X ∩ Y) ∩ Z

2. Commutative Laws:

X ∪ Y = Y ∪ X

X ∩ Y = Y ∩ X

3. Distributive Laws:

X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z)

X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)

4. Identity Laws:

X ∪ ∅ = X

X ∩ U = X

5. Complement Laws:

X ∪ X' = U

X ∩ X' = ∅

6. Idempotent Laws:

X ∪ X = X

X ∩ X = X

7.Bound Laws:

X ∪ U = U

X ∩ ∅ = ∅

8. Absorption Laws:

X ∪ (X ∩ Y) = X

X ∩ (X ∪ Y) = X

9. De Morgan’s Laws:

(X ∪ Y)' = X' ∩ Y'

(X ∩ Y)' = X' ∪ Y'

1.3 Relation and Function

A relation is an association between two sets of information. For example, let’s consider a set of residents of a city and their phone numbers. The pairing of names with corresponding phone numbers is a relation. This pairing is ordered for the entire relation. In the example being considered, for each pair, either the name comes first followed by the phone number or the reverse. The set from which the first element is drawn is called the domain set and the other set is called the range set. The domain is what you start with and 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 maps every element of the domain set X to a single element of the range set Y. Let’s consider domain set X as a set of persons and let range set Y store their phone numbers. Assuming that a person may have more than one phone number, the relation being considered is not a function. However, if we draw a relation between names of residents and their date of births with the name set as domain, then this becomes a well-behaved relation and hence a function. This means that, while all functions are relations, not all relations are functions. In case of a function given an x, one gets one and exactly one y for each ordered pair (x, y).

For example, let’s consider the following two relations.

  • 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 the x-values, i.e., {3, 5, 6, 7}, and the range is all the y-values, i.e., {–9, –6, 3, 8, 9}. Relation A is not a function, as there are two different range values, –9 and 9, for the same x-value of 3. In case of relation B, the domain is same as that for A, i.e., {3, 5, 6, 7}. However, the range is a single element {8}. This qualifies as an example of a function even if all the x-values are mapped to the same y-value. Here, each x-value is distinct and hence the function is well behaved. Relation B may be represented by the equation y = 8.

The characteristic of a function may be verified using a vertical line test, which is stated below:

Given the graph of a relation, if one can draw a vertical line that crosses the graph in more than one place, then the relation is not a function.

In this example, both lines L1 and L2 cut the graph for the relation thrice. This signifies that for the same x-value, there are three different y-values for each of case. Thus, the relation is not a function

Figure 14.7: Vertical Line Test for Function

2 Basic Logic

[1, c1]

2.1 Propositional Logic

A proposition is a statement that is either true or false, but not both. Let’s consider declarative sentences for which it is meaningful to assign either of the two status values: true or false. Some examples of propositions are given below.

  • 1. The sun is a star
  • 2. Elephants are mammals.
  • 3. 2 + 3 = 5.

However, a + 3 = b is not a proposition, as it is neither true nor false. It depends on the values of the variables a and b.

The Law of Excluded Middle: For every proposition p, either p is true or p is false.

The Law of Contradiction: For every proposition p, it is not the case that p is both true and false.

Propositional logic is the area of logic that deals with propositions. A truth table displays the relationships between the truth values of propositions.

A Boolean variable is one whose value is either true or false. Computer bit operations correspond to logical operations of Boolean variables.

The basic logical operators including negation (¬ p), conjunction (p ∧ q), disjunction (p ∨ q), exclusive or (p ⊕ q), and implication (p → q) are to be studied. Compound propositions may be formed using various logical operators.

A compound proposition that is always true is a tautology. A compound proposition that is always false is a contradiction. A compound proposition that is neither a tautology nor a contradiction is a contingency.

Compound propositions that always have the same truth value are called logically equivalent (denoted by ≡). Some of the common equivalences are:

Identity laws:

p ∧ T ≡ p

p ∨ F ≡ p

Domination laws:

p ∨ T ≡ T

p ∧ F ≡ F

Idempotent laws:

p ∨ p ≡ p

p ∧ p ≡ p

Double negation law:

¬ (¬ p) ≡ p

Commutative laws:

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

Associative laws:

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributive laws:

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

De Morgan’s laws:

¬ (p ∧ q) ≡ ¬ p ∨ ¬ q

¬ (p ∨ q) ≡ ¬ p ∧ ¬ q

2.2 Predicate Logic

A predicate is a verb phrase template that describes a property of objects or a relationship among objects represented by the variables. For example, in the sentence, The flower is red, the template is red is a predicate. It describes the property of a flower. The same predicate may be used in other sentences too.

Predicates are often given a name, e.g., “Red” or simply “R” can be used to represent the predicate is red. Assuming R as the name for the predicate is red, sentences that assert an object is of the color red can be represented as R(x), where x represents an arbitrary object. R(x) reads as x is red

Quantifiers allow statements about entire collections of objects rather than having to enumerate the objects by name.

The Universal quantifier ∀x asserts that a sentence is true for all values of variable x. For example, ∀x Tiger(x) → Mammal(x) means all tigers are mammals.

The Existential quantifier ∃x asserts that a sentence is true for at least one value of variable x. For example, ∃x Tiger(x) → Man-eater(x) means there exists at least one tiger that is a man-eater.

Thus, while universal quantification uses implication, the existential quantification naturally uses conjunction.

A variable x that is introduced into a logical expression by a quantifier is bound to the closest enclosing quantifier. A variable is said to be a free variable if it is not bound to a quantifier.

Similarly, in a block-structured programming language, a variable in a logical expression refers to the closest quantifier within whose scope it appears.

For example, in ∃x (Cat(x) ∧ ∀x (Black(x))), x in Black(x) is universally quantified. The expression implies that cats exist and everything is black.

Propositional logic falls short in representing many assertions that are used in computer science and mathematics. It also fails to compare equivalence and some other types of relationship between propositions.

For example, the assertion a is greater than 1 is not a proposition because one cannot infer whether it is true or false without knowing the value of a. Thus, propositional logic cannot deal with such sentences. However, such assertions appear quite often in mathematics and we want to infer on those assertions. Also, the pattern involved in the following two logical equivalences cannot be captured by propositional logic: “Not all men are smokers” and “Some men don’t smoke.” Each of these two propositions is treated independently in propositional logic. There is no mechanism in propositional logic to find out whether or not the two are equivalent to one another. Hence, in propositional logic, each equivalent proposition is treated individually rather than dealing with a general formula that covers all equivalences collectively.

Predicate logic is supposed to be a more powerful logic that addresses these issues. In a sense, predicate logic (also known as first-order logic or predicate calculus) is an extension of propositional logic to formulas involving terms and predicates.

3 Proof Techniques

[1, c1]

A proof is an argument that rigorously establishes the truth of a statement. Proofs can themselves be represented formally as discrete structures.

Statements used in a proof include axioms and postulates that are essentially the underlying assumptions about mathematical structures, the hypotheses of the theorem to be proved, and previously proved theorems.

A theorem is a statement that can be shown to be true.

A lemma is a simple theorem used in the proof of other theorems.

A corollary is a proposition that can be established directly from a theorem that has been proved.

A conjecture is a statement whose truth value is unknown.

When a conjecture’s proof is found, the conjecture becomes a theorem. Many times conjectures are shown to be false and, hence, are not theorems.

3.1 Methods of Proving Theorems

Direct Proof. Direct proof is a technique to establish that the implication p → q is true by showing that q must be true when p is true.

For example, to show that if n is odd then n2−1 is even, suppose n is odd, i.e., n = 2k + 1 for some integer k: ∴ n2 = (2k + 1)2 = 4k2 + 4k + 1

As the first two terms of the Right Hand Side (RHS) are even numbers irrespective of the value of k, the Left Hand Side (LHS) (i.e., n2) is an odd number. Therefore, n2−1 is even.

Proof by Contradiction. A proposition p is true by contradiction if proved based on the truth of the implication ¬ p → q where q is a contradiction.

For example, to show that the sum of 2x + 1 and 2y − 1 is even, assume that the sum of 2x + 1 and 2y − 1is odd. In other words, 2(x + y), which is a multiple of 2, is odd. This is a contradiction. Hence, the sum of 2x + 1 and 2y − 1 is even.

An inference rule is a pattern establishing that if a set of premises are all true, then it can be deduced that a certain conclusion statement is true. The reference rules of addition, simplification, and conjunction need to be studied.

Proof by Induction. Proof by induction is done in two phases. First, the proposition is established to be true for a base case—typically for the positive integer 1. In the second phase, it is established that if the proposition holds for an arbitrary positive integer k, then it must also hold for the next greater integer, k + 1. In other words, proof by induction is based on the rule of inference that tells us that the truth of an infinite sequence of propositions P(n), ∀n ∈ [1 … ∞] is established if P(1) is true, and secondly, ∀k ∈ [2 ... n] if P(k) → P(k + 1).

It may be noted here that, for a proof by mathematical induction, it is not assumed that P(k) is true for all positive integers k. Proving a theorem or proposition only requires us to establish that if it is assumed P(k) is true for any arbitrary positive integer k, then P(k + 1) is also true. The correctness of mathematical induction as a valid proof technique is beyond discussion of the current text. Let us prove the following proposition using induction.

Proposition: The sum of the first n positive odd integers P(n) is n2.

Basis Step: The proposition is true for n = 1 as P(1) = 12 = 1. The basis step is complete.

Inductive Step: The induction hypothesis (IH) is that the proposition is true for n = k, k being an arbitrary positive integer k.

∴ 1 + 3 + 5+ … + (2k − 1) = k2

Now, it’s to be shown that P(k) → P(k + 1).

P(k + 1) = 1 + 3 + 5+ … +(2k − 1) + (2k + 1) = P(k) + (2k + 1) = k2 + (2k + 1) [using IH] = k2 + 2k + 1 = (k + 1)2

Thus, it is shown that if the proposition is true for n = k, then it is also true for n = k + 1.

The basis step together with the inductive step of the proof show that P(1) is true and the conditional statement P(k) → P(k + 1) is true for all positive integers k. Hence, the proposition is proved.

4 Basics of Counting

[1, c6]

The sum rule states that if a task t1 can be done in n1 ways and a second task t2 can be done in n2 ways, and if these tasks cannot be done at the same time, then there are n1+ n2 ways to do either task.

  • If A and B are disjoint sets, then |A ∪ B|=|A| + |B|.
  • In general if A1, A2, …. , An are disjoint sets, then |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2| + … + |An|.

For example, if there are 200 athletes doing sprint events and 30 athletes who participate in the long jump event, then how many ways are there to pick one athlete who is either a sprinter or a long jumper? Using the sum rule, the answer would be 200 + 30 = 230.

The product rule states that if a task t1 can be done in n1 ways and a second task t2 can be done in n2 ways after the first task has been done, then there are n1 * n2 ways to do the procedure.

  • If A and B are disjoint sets, then |A × B| = |A| * |B|.
  • In general if A1, A2, …, An are disjoint sets, then |A1 × A2 × … × An| = |A1| * |A2| * …. * |An|.

For example, if there are 200 athletes doing sprint events and 30 athletes who participate in the long jump event, then how many ways are there to pick two athletes so that one is a sprinter and the other is a long jumper? Using the product rule, the answer would be 200 * 30 = 6000.

The principle of inclusion-exclusion states that if a task t1 can be done in n1 ways and a second task t2 can be done in n2 ways at the same time with t1, then to find the total number of ways the two tasks can be done, subtract the number of ways to do both tasks from n1 + n2.

  • If A and B are not disjoint, |A ∪ B| = |A| + |B| − |A ∩ B|.

In other words, the principle of inclusionexclusion aims to ensure that the objects in the intersection of two sets are not counted more than once.

Recursion is the general term for the practice of defining an object in terms of itself. There are recursive algorithms, recursively defined functions, relations, sets, etc.

A recursive function is a function that calls itself. For example, we define f(n) = 3 * f(n − 1) for all n ∈ N and n ≠ 0 and f(0) = 5.

An algorithm is recursive if it solves a problem by reducing it to an instance of the same problem with a smaller input.

A phenomenon is said to be random if individual outcomes are uncertain but the long-term pattern of many individual outcomes is predictable.

The probability of any outcome for a random phenomenon is the proportion of times the outcome would occur in a very long series of repetitions.

The probability P(A) of any event A satisfies 0 ≤ P(A) ≤ 1. Any probability is a number between 0 and 1. If S is the sample space in a probability model, the P(S) = 1. All possible outcomes together must have probability of 1.

Two events A and B are disjoint if they have no outcomes in common and so can never occur together. If A and B are two disjoint events, P(A or B) = P(A) + P(B). This is known as the addition rule for disjoint events.

If two events have no outcomes in common, the probability that one or the other occurs is the sum of their individual probabilities.

Permutation is an arrangement of objects in which the order matters without repetition. One can choose r objects in a particular order from a total of n objects by using nPr ways, where, npr = n! / (n − r)!. Various notations like nPr and P(n, r) are used to represent the number of permutations of a set of n objects taken r at a time.

Combination is a selection of objects in which the order does not matter without repetition. This is different from a permutation because the order does not matter. If the order is only changed (and not the members) then no new combination is formed. One can choose r objects in any order from a total of n objects by using nCr ways, where, nCr = n! / [r! * (n − r)!].

5 Graphs and Trees

[1, c10, c11]

5.1 Graphs

A graph G = (V, E) where V is the set of vertices (nodes) and E is the set of edges. Edges are also referred to as arcs or links.

F is a function that maps the set of edges E to a set of ordered or unordered pairs of elements V. For example, in Figure 14.8, G = (V, E) where V = {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (C, B)), (e3, (B, A))}.

Figure 14.8: Example of a Graph

The graph in Figure 14.8 is a simple graph that consists of a set of vertices or nodes and a set of edges connecting unordered pairs. The edges in simple graphs are undirected. Such graphs are also referred to as undirected graphs. For example, in Figure 14.8, (e1, (A, C)) may be replaced by (e1, (C, A)) as the pair between vertices A and C is unordered. This holds good for the other two edges too. In a multigraph, more than one edge may connect the same two vertices. Two or more connecting edges between the same pair of vertices may reflect multiple associations between the same two vertices. Such edges are called parallel or multiple edges.

For example, in Figure 14.9, the edges e3 and e4 are both between A and B. Figure 14.9 is a multigraph where edges e3 and e4 are multiple edges.

Figure 14.9: Example of a Multigraph

In a pseudograph, edges connecting a node to itself are allowed. Such edges are called loops.

For example, in Figure 14.10, the edge e4 both starts and ends at B. Figure 14.10 is a pseudograph in which e4 is a loop.

A directed graph G = (V, E) consists of a set of vertices V and a set of edges E that are ordered pairs of elements of V. A directed graph may contain loops.

Figure 14.10: Example of a Pseudograph

For example, in Figure 14.11, G = (V, E) where V = {A, B, C}, E = {e1, e2, e3}, and F = {(e1, (A,C)), (e2, (B, C)), (e3, (B, A))}.

In a weighted graph G = (V, E), each edge has a weight associated with it. The weight of an edge typically represents the numeric value associated with the relationship between the corresponding two vertices.

Figure 14.11: Example of a Directed Graph

For example, in Figure 14.12, the weights for the edges e1, e2, and e3 are taken to be 76, 93, and 15 respectively. If the vertices A, B, and C represent three cities in a state, the weights, for example, could be the distances in miles between these cities.

Figure 14.12: Example of a Weighted Graph

Let G = (V, E) be an undirected graph with edge set E. Then, for an edge e ∈ E where e = {u, v}, the following terminologies are often used: