Discrete Mathematics

MARWARI COLLEGE, RANCHI

(AN AUTONOMOUS UNIT OF RANCHI UNIVERSITY FROM 2009)

- Prakash Kumar, Dept. of CA

-Raju Manjhi, Dept of CA

__________________________________________________________________________________

Discrete Mathematics –

The concept involving distinct values in known as Discrete Mathematics.

According to Discrete Mathematics, there are countable numbers of points between any two numbers. For instance, in case of finite set of objects, discrete mathematics is defined as the list of ordered pair than have these objects and which is presented as complete list of the pairs.

What is a Set?

The concept of Sets is introduced by G. Cantor. According to him, a collection of definite and distinguishable objects which are selected by means of description or certain rules is defined as a set.

The basis of many fields such as counting theory, relations, graph theory and finite state machines etc is formed by Set theory.

Set - Definition

An unordered collection of different elements is defined as a set. A set bracket is used for listing all the elements and thus set is written. The changes in the order of the set do not make any changes in the set.

Some of the examples of sets are as follows:

·         A set of all positive integers

·         A set of all the planets in the solar system

·         A set of all the states in India

·         A set of all the lowercase letters of the alphabet

What are the different types of Sets?

There are different types of sets such as finite, infinite, subset, universal, proper, singleton set, etc.

Finite Set

In a finite set, there are a definite number of elements.

Example − S={x|x∈N and 70>x>50}

Infinite Set

In an infinite set, there are a infinite number of elements

Example − S={x|x∈NS and x>10}

Subset

If every element of X is an element of Y, then a set X is a subset of set Y which is written as X⊆Y.

Example 1 − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y is a subset of set X as all the elements of set Y is in set X. Hence, it is written as Y⊆X.

Example 2 − Let, X={1,2,3} and Y={1,2,3}. Here set Y is a subset (Not a proper subset) of set X as all the elements of set Y is in set X. Hence, it is represented as Y⊆X.

Proper Subset

The subset which is not equal to is known as a proper subset. A Set X is a proper subset of set Y (Written as X⊂Y) if every element of X is an element of set Y and |X|<|Y|.

Example − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y⊂X as all elements in Y are contained in X too and X has at least one element is more than set Y.

Universal Set

A collection of elements in a particular context or application is known as Universal Set. The sets in that context or application are considered as the subsets of the universal sets. U is used for representing Universal Set.

Example – The set of all the animals on the earth can be defined as U. Set of mammals is considered as subset of U, set of fishes is also subset of U, etc.

Empty Set or Null Set

If the set does not have any elements, then such a set is known as Empty set, which is represented by ∅. The cardinality of the null set or empty set is considered as zero, as there are no elements.

Example − S={x|x∈N and 7<x<8}=∅

Singleton Set or Unit Set

When a set has only one element then such a set is known as Singleton set and is denoted by {s}.

Example − S={x|x∈N, 7<x<9} = {8}

Equal Set

When two sets have the same number of elements, then they are said to be equal sets.

Example − If A={1,2,6} and B={6,1,2}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.

Equivalent Set

Equivalent sets have same cardinalities.

Example − If A={1,2,6} and B={16,17,22} they are equivalent as cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3

Overlapping Set

When there is at least one common element in two sets, they are called as overlapping sets.

In case of overlapping sets −

·         n(A∪B)=n(A)+n(B)−n(A∩B)

·         n(A∪B)=n(A−B)+n(B−A)+n(A∩B)

·         n(A)=n(A−B)+n(A∩B)

·         n(B)=n(B−A)+n(A∩B)

Example − Let, A={1,2,6} and B={6,12,42}. Here the common element is 6 and hence the two sets are known to be overlapping.

Disjoint Set

If not even one element is common among both the sets, then the sets are known to be disjoint sets. The properties of disjoint sets are as follows:

·         n(A∩B)=∅

·         n(A∪B)=n(A)+n(B)

Example − Let, A={1,2,6} and B={7,9,14}, the two sets are disjoint sets as they do not have any common single element.

 

What are Venn Diagrams?

All possible logical relations between different mathematical sets are represented by Venn diagrams, which are invented by John Venn in 1880.

Examples

What are Set Operations?

Some of the operations on sets such as Set Union, Set Interaction, Set Difference, and Set complement etc come under Set Operations.

Set Union

The union of sets A and B (denoted by A∪B) is the set of elements which are in A, in B, or in both A and B. Hence, A∪B={x|x∈A OR x∈B}

Example − If A={10,11,12,13} and B = {13,14,15} then A∪B={10,11,12,13,14,15}. Here the common element is considered only once.

Set Intersection

The set of elements which appear in both the sets A and B is known as intersection of sets A and B and is denoted by A∩B.

Hence, A∩B={x|x∈A AND x∈B}.

Example − If A={11,12,13} and B={13,14,15}, then A∩B={13}

Set Difference/ Relative Complement

The set of elements that are only in A but not in B is the difference between the Sets A and B is denoted as A–B.

Hence, A−B={x|x∈A AND x∉B}.

Example − If A={10,11,12,13} and B={13,14,15} then (A−B)={10,11,12} and (B−A)={14,15}. Here, it is to be noted that (A−B)≠(B−A)

Complement of a Set

All the elements that are not In set A are known as complement of set A. Hence, A′={x|x∉A}.

More specifically, A′=(U−A) where U is a universal set which contains all objects.

Example − If A={x|x belongs to set of odd integers} then A′={y|y does not belong to set of odd integers}

Power Set

The set of all the subsets of S, which are included in the empty set, is known as the power set of set S. The cardinality of a power set of a set S of cardinality n is 2n. Power set is denoted as P(S).

Example −

For a set S={a,b,c,d}, the subsets are calculated as

·         Subsets with 0 elements − {∅}(the empty set)

·         Subsets with 1 element − {a},{b},{c},{d}

·         Subsets with 2 elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}

·         Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}

·         Subsets with 4 elements − {a,b,c,d}

Hence, 

P(S)={{∅},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}

|P(S)|=2⁴=16

Note: The power set of an empty set is also an empty set.

|P({∅})|=2⁰=1

Partitioning of a Set

The collection of n disjoint subsets is known as a partition of a set S. Say P1,P2,…Pn satisfy the conditions:

·         Pi does not contain the empty set.

[Pi≠{∅} for all 0<i≤n]

·         The union of the subsets must equal the entire original set.

[P1∪P2∪⋯∪Pn=S]

·         The intersection of any two distinct sets is empty.

[Pa∩Pb={∅}, for a≠b where n≥a,b≥0]

Example

Let S={a,b,c,d,e,f,g,h}

One probable partitioning is {a},{b,c,d},{e,f,g,h}

Another probable partitioning is {a,b},{c,d},{e,f,g,h}

Bell Numbers

The number of ways in which a set can be portioned, is provided by Bell Numbers, and are denoted by B_n, where n belongs to the cardinality of the set.

Example −

Let S={1,2,3}, n=|S|=3

The alternate partitions are −

1.   ∅,{1,2,3}

2.   {1},{2,3}

3.   {1,2},{3}

4.   {1,3},{2}

5.   {1},{2},{3}

Hence B₃=5

 

 

Properties Common to Logic and Sets: 

Duality Principle: The ‘duality principle’ is very convenient for dealing with theorems about sets. Basically if any theorem is given to you, by applying the duality principle you can get another theorem (the dual of the previous one). In any statement involving the union and intersection of sets, we can get from one of the statements to the other by interchanging ∩ with ∪ andφ with U.

For example, the dual of A∪ (B∩ C) is A∩ (B∪ C) and the dual of U∪ φ =U is

U∩ φ =φ . So, for example what is true for A∪ (B∩ C) will be true for A (B C) too. This is why if the first property in each of the pairs below is proved the second one follows immediately.

For any universal set U and subsets A, B and C of U, the following properties hold.

i) Associative properties:

Union: A∪ (B∪ C)= (A∪ B) ∪ C

Intersection: A ∩ (B ∩ C) = (A ∩ B) ∩ C

ii) Commutative properties:

Union: A∪ B= B∪ A

Intersection: A∩ B = B ∩ A.

iii) Identity:

Union: A∪ φ = A

Intersection: A∩ U=A.

iv) Complement:

Union: A∪ A′ = U

Intersection: A∩ A′ = φ

v) Distributive properties:

Union: A∪ (B∩ C) = (A∪ B)∩ (A∪ C)

Intersection: A∩ (B∪ C) = (A∩ B)∪ (A∩ C)

De Morgan’s Laws:

For any two sets A and B the following laws known as De Morgan’s laws, hold

1. (A∪ B)′ = A′∩ B ′, and

2. (A∩ B)′ = A′∪ B′

De Morgan’s laws can also be expressed as

1. A ~ (B ∪ C) = (A~ B) ∩ (A~ C)

2. A ~ (B ∩ C)= (A~ B) ∪ (A~ C)

 

RELATIONS

 

Cartesian Product / Cross Product

The Cartesian product of n number of sets A1,A2,…An denoted as A1×A2⋯×An can be defined as all possible ordered pairs (x1,x2,…xn)where x1∈A1,x2∈A2,…xn∈An

Example – Two sets are considered, A={a,b} and B={1,2}.

The Cartesian product of A and B is written as − A×B={(a,1),(a,2),(b,1),(b,2)}

The Cartesian product of B and A is written as − B×A={(1,a),(1,b),(2,a),(2,b)}

Relations and their Types

Definition: A relation between two sets A and B is a subset of A × B. Any subset of A × A is a relation on the set A.

For instance, if A ={1,2,3} and B = {p,q}, then the subset {(1,p),(2,q),(2,p)} is a

relation on A × B. And {(1,1), (2,3)} is a relation on A.

Also, R= {(x,y) ∈ N × N : x > y} is a relation on N, the set of natural numbers,

since R ⊆ N × N.

If R⊆A ×B,. we write x Ry if and only if (x,y) ∈R( xRy is read as ‘x is related to y’).

Theorem 2: The total number of distinct relations between a finite set A and a finite set B is 2^mn, where m and n are the number of elements in A and B, respectively.

For example, R1 = N × L, where L is set of straight lines, in this relation we can give different ordering of the straight lines.

If the relation R2 = {1,2,3} × { l1,l2}, then line l1 and l2 can get three different ordering.

 

Properties of Relations:

Reflexive Relations: A relation R on a set A is called a reflexive relation if

(a,a)∈R∀ a∈ A.

In other words, R is reflexive if every element in A is related to itself.

Thus, R is not reflexive if there is at least one element a ∈ A such that (a,a) ∉ R.

For example, if A= {1,2,3,4}, then the relation R1= {(1,1), (2,2), (3,3), (4,4)} in A is reflexive because for x ∈ A,(x,x) ∈ R1. However, R2= {(1,1), (2,1), (4,4)} is not reflexive since 2 ∈ A, but (2,2) ∉R2.

Symmetric Relations: A relation R on a set A is called a symmetric relation if (a,b) ∈ R ⇒ (b,a) ∈ R.Thus, R is symmetric if bRa holds whenever aRb holds.

A relation R in a set A is not symmetric if there exist two distinct elements a, b ∈ A, such that aRb, but not bRa.

For example, if L is the set of all straight lines in a plane, then the relation R in L,

defined by ‘x is parallel to y’, is symmetric, since if a straight line a is parallel to a straight line b, then b is also parallel to a. Thus, (a,b) ∈ R ⇒(b,a) ∈ R.

However, if R is the relation on N defined by ‘xRy iff x–y>0’, then R is not symmetric, since, 4−2>0 but 2−4 _ 0.Thus, (4,2) ∈ R but (2,4) ∉ R.

Transitive Relations: A relation R on a set A is called a transitive relation if whenever (a,b) ∈ R and (b,c)∈ R, then (a,c)∈R for a,b,c ∈A .

Thus, [(a,b),∈R,(b,c)∈ R⇒(a,c)∈R] ,∀ a,b,c∈A⇒ R is transitive.

A relation R in a set A is not transitive if there exist elements a,b,c ∈A, not necessarily distinct, such that (a,b) ∈ R, (b,c) ∈ R but (a,c) ∉ R.

For example, if L is the set of all straight lines in a plane and R is the relation on L defined by ‘ x is parallel to y’ then if a is parallel to b and b is parallel to c, then a is parallel to c. Hence R is transitive. However, the relation ‘xSy’on L defined by ‘iff x intersects y’ is not transitive.

Also, the relation R on A, the set of all Indians, defined by ‘xRy iff x loves y’, is not a transitive relation.

Equivalence Relations: A relation R on a set A is called an equivalence relation if and only if

(i) R is reflexive, i.e., for all a ∈ R, (a, a) ∈ R,

(ii) R is symmetric, i.e., (a, b) ∈ R ⇒ (b, a) ∈ R, for all a, b ∈ A, and

(iii) R is transitive, i.e., (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R, for all a, b, c ∈ A.

One of the most trivial examples of an equivalence relation is that of ‘equality’.

For any elements a,b,c in a set A,

(i) a = a, i.e., reflexivity

(ii) a = b⇒ b = a, i.e., symmetricity

(iii) a = b and b = c ⇒ a = c , i.e., transitivity.

Now let us see if ‘xRy iff ’ ‘x ≤ y’ gives an equivalence relation on R.

(i) x≤x, i.e., (x,x) ∈R, i.e., R is reflexive.

(ii) However, 2 ≤ 3 but 3 ≤ 2. So, R is not symmetric.

Thus, R is not an equivalence relation.

 

FUNCTIONS

Definition: A function from a non-empty set A to a non-empty set B is a subset R of AxB such that for each a ∈A ∃ a unique b∈B such that (a,b)∈R. So, this relation satisfies the following two conditions:

(i) for each a ∈A, there is some b∈B such that (a,b) ∈R

(ii) if (a,b) ∈R and (a,b´) ∈R then b = b´.

 

We usually present functions as a rule associating elements of one set with another.

 

Types of Functions

Onto Mapping: A mapping f: A-> B is said to an onto (or surjective) mapping if

f(A)= B, that is, the range and co-domain coincide. In this case we say that f maps A onto B.

Injective Mapping: A mapping f: A-> B is said to be injective (or one-one) if the images of distinct elements of A under f are distinct, i.e., if x1 ≠ x2 in A, then

f(x1) ≠ f(x2) in B. This is briefly denoted by saying f is 1–1.

Bijective Mapping: A mapping f: A-> B is said to be bijective (or one-one onto,) if f is both injective and surjective, i.e., one-one as well as onto.

 

 Operations on Functions

If given whose domains ranges are subsets of the real numbers, we define the

function f+g by (f + g)(x) to be the function whose value at x is the sum of f(x) and

g(x). Symbolically,

(f + g)(x) = f(x) + g(x). This is called pointwise addition of f and g.

The domain of f+g is the intersection of the domains of f and g since to compute

(f + g)(x) it is necessary and sufficient to compute both f(x) and g(x).

Other operations on functions are defined similarly:

• (fg)(x) = f(x)g(x) (pointwise multiplication)

• f p (x) = (f(x))p for any real exponent p with the domain of f p consisting of those

points for which the p-th power of f(x) makes sense.

• (f/g)(x) = f(x)/g(x), for g(x) ≠ 0 (pointwise multiplication)

 

 
Permutation of a set:

Let A be a non-empty finite set. A bijective mapping f: A->A is said to be a permutation on A. Let A={ a1,a2,……an}. Then the total number of bijections from A onto A is n!.

Multiplication of permutations:

The product of two permutations f anf g of same degree is denoted by f_og or f_g.

Note:

 f_οg ≠ g_οf. Thus the multiplication of permutations is not commutative.