Wipro Class 1

DISCRETE MATHEMATICAL STRUCTURES

There are no formal prerequisites for this chapter, the reader is encouraged to read carefully and work through all examples. In this class we introduce some basic tools of Discrete Mathematics. 1.

We begin with sets, subsets and their operations, notions with which you may already be familiar.

2.

We deal with sequences, using both explicit and recursive patterns.

3.

Some of the basic divisibility properties of the integers.

4.

Matrices and their operations,

This is the little bit background need to begin our exploration of Mathematical Structures. Set and Subsets A set is a collection of well defined objects, called the elements or members of the set. Ex:

Collection of all members used for counting. Collections of all paintings of an artist.

If the numbers of elements in a set is finite, then we say that the set is a finite set. Sets having infinitely many elements are called infinite sets. A set having only one element is called Singleton Set. Examples: 1.

The set of all students in a corporate training, the students are the elements of the set and

the set is finite. 2.

The set of all natural numbers (non-negative integers) the numbers 0,1,2,3,…… are the

elements of this set and this set is infinite. 3.

The set of all integers between 2 and 8 that are squares of integers is the singleton set

consisting of the integer 4. Usually, Sets are denoted by the Upper case letters A,B,C,….. and the elements are denoted by Lower case letters such as a,b,c,…… Null Set: The set which contains no object ( element) at all. The set is called the null set or the Empty set and is denoted by Example:

{ } or φ

.

The set of all positive integers less than 10 which are divisible by 11. The set of all real numbers whose squares are less than 10 is also null set.

Equal Set: Two sets A and B are said to be equal if they have precisely the same elements. Then we write A=B

{

}

Ex: A = {1, 2 ,3 ,4} , B = x / x is a positive int eger with x 2 < 20 . Then A=B.

{

}

A = {1, 2 ,3 } , B = x / x is a positive int eger with x 2 < 12 . . Then A=B Subset:. Given two sets A and B, we say that A is a subset of B or that A is contained in B if every element of A is an element of B as well. If A contains an element which isnot in B then A is not a subset of B. Ex: A = {1, 2, 3

}

B = {1, 2, 3, 4, 5 }, C = {2, 3, 5, 6} here A ⊆ B and A ⊄ C

A = {1 ,2, 3, 4, 5, 6} B = {2, 4, 5} and C = {1, 2, 3, 4, 5}. Then B ⊆ A, B ⊆ C and C ⊆ A. However A ⊄ B, A ⊄ C , C ⊄ B. If A is any set then A ⊆ A.That is, every set is a subset of itself. Note: Diagrams which are used to show the relationship between the sets, are called Venn

diagrams (After the British Logician John Venn). Venn diagrams will be used extensively to study operation on sets. Proper Subset: A set A is proper subset of B if

(i) A ⊆ B (ii) B possesses at least one element that is not in A, In such situation, we write A ⊂ B. Universal Set: All sets are the subsets of a certain set U. This set U is called the universal set. Power Set: Given a set A, suppose we construct the set consisting of all subsets of A.the set so

obtained is called the power set of A and is denoted by P(A). Ex: A = {a, b

} then

P ( A) = {φ , A, {a} , {b}}

A = {1, 2 ,3} then P ( A) = {φ , {1,}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A} .

We observe that in the first example, set A is two elements and the power set P(A) has four elements, i.e., 22. and in the second example, the set has three elements and the power set P(A) has 8 elements i.e., 23. Therefore , In general if the set A has n elements then power set P(A) has 2n elements. Theorem

If a finite set A has n-elements, prove that the power set has 2n elements. Proof: If a finite set A has n-elements, then a subset of A can have no-element, one-element, two-elements, three-elements, ……….(n-1) elements and n-elements. The subset having no-

element is the null set and the subset having all n-elements is A itself. Each element of A gives a Singleton subset of A and they are n-in number. Each combination of two elements of A gives a subset of A containing n-elements; their number is nC2. Similarly the number of subsets of A having three elements if nC3 and so on . Therefore, the total number of subsets of A is 1+1+nC2+nC3+nC4+…………..+nCn-1.= 1+nC2+nC3+nC4+…………..+nCn-1.+nCn =2n. Operation on Sets: Union of two sets: Consider two sets A and B. Then the set consisting of all elements that

belongs

to

A

or

B

is

called

the

union

of

A

and

B

and

is

denoted

by

A ∪ B. Thus A ∪ B = {x / x ∈ A or x ∈ B} .

Intersection of two sets: Consider two sets A and B. Then the set consisting of all elements that

belongs to both A and B is called the intersection of A and B and is denoted by A ∩ B. Thus A ∩ B = {x / x ∈ A and x ∈ B} .

Disjoint Sets: Two sets A and b are said to be disjoint whenever A ∩ B = φ . Complement of a set: Given a universal set U and a set A contained in U, the set of all elements

that belongs to U but not in A is called the complement of A and is denoted by A . A = {x / x ∈ U and x ∉ A} . Relative complement: Given two sets A and B .The set all elements the belongs to B but not in

A is called the complement of A relative to b and is denoted by B-A; B − A = {x / x ∈ B and x ∉ A} . The set A-B is defined similarly.

Symmetric difference For two sets A and B , the relative complement of A ∩ B in A ∪ B is

called the symmetric difference of A and B and is denoted by A∆B . Thus A ∆ B = {x / x ∈ A ∪ B and x ∉ A ∩ B} = ( A ∪ B ) − ( A ∩ B) . Laws of Set theory

1.

Commutative Law A ∪ B = B ∪ A, A ∩ B = B ∩ A.

2.

Associative Law: A ∪ (B ∪ C ) = ( A ∪ B ) ∪ C , A ∩ (B ∩ C ) = ( A ∩ B ) ∩ C ,

3.

Distributive law: A ∩ (B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ), A ∪ (B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )

4.

Idempotent law: A ∪ A = A, A ∩ A = A

5.

Identity Law: A ∪ φ = A, A ∩ U = A.

6.

Laws of double complement: A = A

7.

Inverse law: A ∪ A = U , A ∩ A = φ

8.

De Morgan’s Law A ∪ B = A ∩ B , A ∩ B = A ∪ B

9.

Absorption Law: A ∪ ( A ∩ B ) = A, A ∩ ( A ∪ B ) = A

(

)

(

)

Addition principle:

Consider a finite set S containing p number of elements. Here the number p is called the order or size or the cardinality of the set S and is denoted by o(S) or n(S) or S Ex: A={1,2,3}, B={a,b,c,d} then o(A)=3 and o(B)=4. Suppose we want to consider the union of two finite sets A and B and wish to determine the order of A ∪ B which is obviously a finite set. Since the the elements of A ∪ B consist of all elements which are in A or in B or both A and B. The number of elements in A ∪ B is equal to the number of elements in A+ the number of elements in B- the number of elements in both A and B. The above notation mathematically written as A ∪ B = A + B − A ∩ B This result can also be explained by using Venn diagram.

In the diagram, the set A is made up of two parts P1and P2 and the set B is made up of two parts P2 and P3 where P2= A ∩ B and A ∪ B is made up of three parts P1 , P2 and P3. A = P1 + P2 , B = P3 + P2 , A ∩ B = P2 , A ∪ B = P1 + P2 + P3 A ∪ B = P1 + P2 + P3 = P1 + P2 + P3 − P2 + P2 = A + B − A ∩ B This result is known as Addition Principle or the Principle of Inclusion-Exclusion Ex.

If A,B,C are finite sets prove the following 1.

A∪ B∪C = A + B + C − A∩ B − B∩C − C ∩ A + A∩ B∩C

2.

A− B −C = A − A∩ B − A∩C + A∩ B∩C

Example:

1.

A computer company requires 30 programmers to handle system programming jobs and 40 programmers for application programming. If the company appoints 55 programmers to carry out these jobs. How many of these perform jobs of both the types? How many handle only application programming?

Ans: 15 and 25. 2.

In a class of 52 students, 30 are studying c++, 28 are studying Pascal and 13 are studying both the languages. How many in this class are studying atleast one of the languages? How many are studying neither of the language? Ans: 45 and 7

3.

In a sample of 100 logic chips, 23 have a defect D1, 26 have a defect D2 30 have defect D3 , 7have defects D1and D2, 8have defects D1 and D3, 10 have defects D2 and D3 and 3 have all three defects. Find the number of chips having (i) atleast one defect (ii) no defect. Ans: 57 and 43

4.

A survey of 500 television viewers of a sport channel produced the following information 285 watch cricket, 195 watch hockey, 115 watch football, 45 watch cricket and football, 70 watch cricket and hockey, 50 of them donot watch any of three kinds of games (a) How many viewers in the survey watch all three kinds of games (b) How many viewers watch exactly one of the sports? Ans: 20 and 325

5.

A survey of a sample of 25 new cars being sold by an auto dealer was conducted to see which of the three popular options: air-conditioning, radio, and power windows were installed. The survey found: 15 had air conditioning , 12 had radio, 11 had power windows , 5 had AC and Power windows 9 had Ac and radio, 4 has radio and Power windows and 3 had all three options. Find the number of cars that had (1) only power windows (2) only AC’s (3) only radio (4) Only one of the options (5) atleast one of the potions (6) none of the options

Examles: 1.

If U={1,2,3,4,5,6,7,8,9}, A={1,2,4,6,8}and B={2,4,5,9} Compute the following A , B , A ∪ B , A ∪ B, A ∩ B , A ∩ B, A ∩ B, A − B, B − A, and A∆B .

2.

Determine the sets A and B given that A-B={1,3,7,11} and B-A={2,6,8} and A ∩ B={4.9}. Hint: A = ( A ∩ B ) ∪ ( A − B ), B = ( A ∩ B ) ∪ (B − A),

3.

Determine the sets A and B given that A-B={1,2,4}, B-A={7,8} and A ∪ B = {1,2,4,5,7,8,9}

Hint: A = ( A ∪ B ) − (B − A) ; B = ( A ∪ B ) − ( A − B ) For any two statements A and B prove that P ( A ∩ B) = P( A) ∩ P( B)

4.

Soln: Take any x ∈ P( A ∩ B), Then x ⊆ ( A ∩ B), ∴ x ⊆ A and x ⊆ B Hence, x ∈ P( A) and x ∈ P( B ). Thus x ∈ P( A) ∩ P( B).

This Pr oves that P( A ∩ B ) ⊆ P( A) ∩ P( B )..................(1)

Take any, y ∈ P( A) ∩ P( B). Then y ∈ P( A) and y ∈ P( B) This means that , y ⊆ A, and y ⊆ B. ∴ y ⊆ A ∩ B Hence, y ∈ P( A ∩ B ). This proves that , P( A) ∩ P( B) ⊆ P( A ∩ B)............(2) From (1) and (2) we notice that , P( A ∩ B ) = P( A) ∩ P( B). Note: P ( A ∪ B ) ≠ P ( A) ∪ P ( B ) ,

A={1.2},

A ∪ B = {1,2,3,4}

B={3,4},

Evidently,

{1,2,3} ⊆ A ∪ B, so that , {1,2,3}∈ P( A ∪ B ),

But {1,2,3} ∉ A, and {1,2,3} ∉ B, {1,2,3} ∉ P( A) ∪ P( B) . hence, P( A ∪ B) ≠ P( A) ∪ P( B)

5.

For any three sets prove associative, distributive and De-Morgan’s lawlaws

6.

For any two sets A and b prove the following

A − B = A ∩ B , A − B = A ∩ B,

A − B = A − ( A ∩ B)

Matrices

A matrix is rectangular array of numbers arranged in m horizontal rows and n vertical columns. ⎡ a11 ⎢a ⎢ 21 ⎢a A = ⎢ 31 ⎢ − ⎢ − ⎢ ⎣⎢a m1

a12

− − −

a 22

− − −

a32

− − −

− −

− − − − − −

am2

− − −

a1n ⎤ a 2 n ⎥⎥ a3n ⎥ ⎥ The ith row of A is [ai1 − ⎥ − ⎥ ⎥ a mn ⎦⎥

ai 2

ai 3

− ain ] and jth column of

⎡ a1 j ⎤ ⎢a ⎥ ⎢ 2j⎥ A is ⎢ a3 j ⎥ .We say that A is m by n written as m × n .If m=n then we say A is a square matrix of ⎢ ⎥ ⎢ − ⎥ ⎢ a mj ⎥ ⎣ ⎦

n. We often write the matrix A =[aij] . Example: ⎡− 1⎤ ⎡ 1 0 − 1⎤ ⎡ 2 3⎤ ⎡2 3 5⎤ ⎢ ⎥ , B=⎢ , C = [1 − 1 3 4], D = ⎢ 2 ⎥, E = ⎢⎢− 1 2 3 ⎥⎥ . A=⎢ ⎥ ⎥ ⎣ 4 6⎦ ⎣0 − 1 2⎦ ⎢⎣ 0 ⎥⎦ ⎢⎣ 2 4 5 ⎥⎦

Here A is 2 × 3, B is 2 × 2, C is 1 × 4, D is 3 × 1 and E is 3 × 3. A square matrix A=[aij] for which every entry off the main diagonal is zero that is aij=0 for i ≠ j is called a diagonal matrix. Matrices are used in many applications in computer science and we shall see them in relations and graphs. Two matrices A and B are said to be equal if the corresponding elements are the same. If A and B are two matrices then their sum is denoted by C=A+B.That is C is obtained by adding the corresponding elements of A and B. A matrix whose entries are zero is called a zero matrix and is denoted by 0. Multiplication of Two Matrices Boolean matrix operation

A Boolean matrix is an m × n matrix whose entries are either zero or one. We shall now define three operations on Boolean matrices that are useful Apllications Let A and b are two Boolean matrices, then we define the following ⎧ 1 if a ij = 1 or bij = 1 A ∨ B = C = [cij ] by cij = ⎨ read as A joins B. ⎩0 if aij = 0 and bij = 0 ⎧ 1 if aij = 1 and bij = 1 2. A ∧ B = C = [cij ] by cij = ⎨ read as A meet B. ⎩0 if aij = 0 or bij = 0 3. The boolean product A and B denoted by A ⊗ B and is defined as follows

1.

.

⎧1 if aik = 1 and bkj = 1 A ⊗ B = C = [cij ] by cij = ⎨ Denoted by AB. 0 otherwise ⎩

This multiplication is similar to ordinary matrix multiplication. Examples: 1.

⎡2 − 3 − 1⎤ ⎡ 2 x − 1⎤ ⎢ ⎥ A = ⎢0 5 2 ⎥ , B = ⎢⎢ y 5 2 ⎥⎥ then A=B if and only if x=-3, y=0 and z=6. ⎢⎣4 − 4 6 ⎥⎦ ⎢⎣ 4 − 4 z ⎥⎦

2.

⎡3 4 − 1 ⎤ ⎡ 4 5 3⎤ ⎡7 9 2 ⎤ A=⎢ ,B=⎢ , then A + B = ⎢ ⎥ ⎥ ⎥ ⎣5 0 − 2⎦ ⎣0 − 3 2⎦ ⎣5 − 3 0 ⎦

3.

1⎤ ⎡3 ⎡ 2 3 − 4⎤ ⎡− 20 − 20⎤ ⎢ , B = ⎢− 2 2 ⎥⎥, then AB = ⎢ A=⎢ ⎥ − 4 ⎥⎦ ⎣1 2 3 ⎦ ⎣ 14 ⎢⎣ 5 − 3⎥⎦

4.

⎡2 1 ⎤ ⎡1 − 1⎤ ⎡ 4 − 5⎤ ⎡ − 1 3⎤ A=⎢ ,B=⎢ , then AB = ⎢ , BA = ⎢ ⎥ ⎥ ⎥ ⎥ ⎣ 3 − 2⎦ ⎣2 − 3⎦ ⎣− 1 3 ⎦ ⎣− 5 8⎦

5.

⎡1 ⎢0 A=⎢ ⎢1 ⎢ ⎣0

0 1 1 0

1⎤ ⎡1 ⎥ ⎢1 1⎥ B=⎢ ⎢0 0⎥ ⎥ ⎢ 0⎦ ⎣1

0⎤ ⎡1 ⎥ ⎢1 1⎥ , then A ∨ B = ⎢ ⎢1 1⎥ ⎥ ⎢ 0⎦ ⎣1

1 1 1 1

1⎤ ⎡1 ⎥ ⎢0 1⎥ ,A∧ B = ⎢ ⎢0 1⎥ ⎥ ⎢ 0⎦ ⎣0

6.

⎡1 ⎢0 A=⎢ ⎢1 ⎢ ⎣0

1 1 1 0

0⎤ ⎡1 ⎡1 0 0 0 ⎤ ⎥ ⎢0 1⎥ , B = ⎢⎢0 1 1 0⎥⎥, A ⊗ B = ⎢ ⎢1 0⎥ ⎢⎣1 0 1 1⎥⎦ ⎥ ⎢ 1⎦ ⎣1

1 1 1 0

1 1 1 1

1 0 0 1

0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦

If A , B and C are Boolean matrices of compatible sizes, then 1.

A ∨ B = B ∨ A, A ∧ B = B ∧ A.

2.

( A ∨ B ) ∨ C = A ∨ ( B ∨ C ), ( A ∧ B ) ∧ C = A ∧ ( B ∧ C )

3.

( A ∧ B ) ∨ C = ( A ∨ C ) ∧ (B ∨ C ), ( A ∨ B ) ∧ C = ( A ∧ C ) ∨ (B ∧ C ),

4.

( A ⊗ B ) ⊗ C = A ⊗ (B ⊗ C )

0 0 0 0

0⎤ 1⎥⎥ 0⎥ ⎥ 0⎦