Difference between revisions of "Chapter 14: Mathematical Foundations"

From SWEBOK
Jump to: navigation, search
(Relation and Function)
(Basic Logic)
Line 409: Line 409:
  
 
¬ (p ∨ q) ≡ ¬ p ∧ ¬ q
 
¬ (p ∨ q) ≡ ¬ p ∧ ¬ q
 +
 +
===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.

Revision as of 12:06, 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.

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.