21ODMCT614-Discrete Mathematical Structure

Relation 43 Therefore, Domain (R) = Set of all first components of R = {2, 3, 4, 5} and Range (R) = Set of all second components of R = {8, 10, 9}. 3.6 Pictorial Representation of Relation The directed graph of a relation (Digraph): The pictorial representation of a relation from a set to itself is called digraph. Steps to draw a digraph: (i) Write down the elements of the set inside the circles these circles are called vertex of the digraph. (ii) Draw an arrow from each x to each element y whenever x is related to y. Example 8: Let R ={(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)} is a relation defined on A = {1, 2, 3, 4} then the digraph is 12 44 Fig. 3.1 3.7 Properties of Relation (a) Reflexive Relation: A relation R on a set A is reflexive if a R a for every a  A, i.e., if (a, a)  R for every a  A. For example, (a) If R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3} then R1 is reflexive relation since for every a  A, (a, a)  R1. CU IDOL SELF LEARNING MATERIAL (SLM)

44 Discrete Mathematical Structures (b) If R2 = {(1, 1), (1, 2), (2, 3), (3, 3) be a relation on A = {1, 2, 3} then R2 is not a reflexive relation since (2, 2)  R. In reflexive relation, all elements in the principle diagonal of the matrix representation of a relation are 1, i.e., mii = 1. 1 1 0 MR  0 1 0 is the representation of reflexive relation. 1 0 1 (b) Irreflexive Relation: A relation R on a set A is irreflexive if for every a  A, (a, a)  R. In other words there is no a  A, (a, a)  R1 for every x  R1. If all aii = 0 then it is an irreflexive relation. 0 1 0 For example, 0 0 0 1 0 0 If R1 = {((1, 2), (2, 3), (3, 1)} be a relation on A = {1, 2, 3} then R1 is irreflexive, since for every a  A, (a, a)  R1. (c) Symmetric Relation: A relation R on a set A is symmetric if whenever (a, b)  R then (b, a)  R, i.e., if a R b bRa R1 = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 1)} on A is symmetric. For symmetric Relation mij = mji for all values of i and j in matrix representation of relation. 1 0 1 For example, 0 1 0 1 0 0 Either mij = mji = 1 or 0 (d) Asymmetric Relation: A relation R on a set A is asymmetric if whenever aRb, bRa. If mij = 1 then mji = 0 and all principle diagonal elements are 0. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 45 0 0 1 For example, 1 0 0 0 1 0 (e) Antisymmetric Relation: A Relation R on a set A is an antisymmetric if whenever (a, b)  R then (b, a)  R  a = b for all a, b  A. If i j then either mij = 0 or mji = 0. Principle diagonal elements may or may not be equals to zero. For example, R1 = {(1, 2), (2, 2), (2, 3)} on A={1, 2, 3} is an antisymmetric relation. Matrix representation of antisymmetric relation is 0 0 1 0 1 0 0 1 0 (f) Transitive Relation: A relation R on a set A is transitive if whenever aRb and bRc then aRc, i.e., if (a, b) & (b, c)  R then (a, c)  R. R1 = {(1, 2), (2, 3), (1, 3)} If MR . MR = MR then the relation is transitive. (g) Equivalence Relation: A relation R on a set A is called an equivalence relation if it is reflexive, symmetric and transitive. Example 9: Determine the types of relation for the following defined on A = {1, 2, 3} (a) R1: {(1, 1), (2, 2), (3, 3), (1, 3)} (b) R2:{(1, 1), (3, 3), (1, 3), (3, 1)} Solution: R1: {(1, 1), (2, 2), (3, 3), (1, 3)} Reflexive Relation: (1, 1), (2, 2), (3, 3)  R1, R1 is reflexive. CU IDOL SELF LEARNING MATERIAL (SLM)

46 Discrete Mathematical Structures Symmetric Relation: As (1, 3)  R1 but (3, 1)  R1 hence R1 is not Symmetric. Transitive Relation: (1, 3), (1, 1)  R1 but (3, 1)  R1 hence R1 is not Transitive Antisymmetric Relation: As (1, 3)  R1 but (3, 1)  R1 hence R1 is an antisymmetric Relation. Asymmetric Relation: As all diagonal elements are 1, therefore, it is not an asymmetric relation. Therefore, R1 is Reflexive and antisymmetric. R2 :{(1, 1), (3, 3), (1, 3), (3, 1)} Reflexive Relation: (1, 1), (3, 3)  R2 but (2, 2)  R2 hence R2 is not reflexive. Symmetric Relation: As (1, 3)  R2 but (1, 3)  R2 hence R2 is Symmetric. Transitive Relation: (1, 3), (3, 1)  R2 and (1, 1)  R2 hence R2 is Transitive. Antisymmetric Relation: As (1, 3)  R2 but (3, 1)  R2 hence it is not an antisymmetric Relation. Example 10: Let A is a set of positive integers and let R = {(a, b)  A X A|a divides b} Is R Symmetric, Antisymmetric, reflexive or transitive? Solution: a|a therefore (a, a)  R, hence reflexive. If a|b, it does not follow that b|a, So, R is not symmetric. If a|b and b|a,then a = b, So R is antisymmetric. Suppose a|b and b|c.  b = ak1 & c = bk2 from above equations c = (ak1)k2 CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 47  c = ak1k2  c = ak  a|c a Rc hence R is transitive. Example 11: Let A = {1, 2, 3, 4, 5}, Let R be a relation on A such that R = {(x, y)|y – x = 2}. Is R is an equivalence relation. Solution: R = {(1, 3), (2, 4), (3, 5)}. R is not reflexive as (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)  R. Neither (3, 1), (4, 2) nor (5, 3) ∈R hence not symmetric. (1, 3) and (3, 5)  R but (1, 5)  R hence not transitive. Neither reflexive, symmetric or transitive. Hence, R is not an equivalence relation. 3.8 Partial Ordering Relations A relation R on a set A is called a partial order if R is reflexive, antisymmetric and transitive. Partial Order Set: The set A together with the partial order relation ‘R’ is called partially ordered set or POSET denoted by (A, R). Example 12: Let A be a collection of sets S and ⊆ is defined on A. Is (A, ⊆) is partially ordered set? Solution: A ⊆ A, A can be subset of itself hence reflexive. Antisymmetric: If A ⊆ B and B ⊆ A  B ⊆ B. Hence, antisymmetric. CU IDOL SELF LEARNING MATERIAL (SLM)

48 Discrete Mathematical Structures Transitive: If A ⊆ B and B ⊆ C  A ⊆ C ⊆ is reflexive, antisymmetric and Transitive hence partially ordered relation.  (A, ⊆) is a partially ordered set or poset. Example 13: Check whether the given relation is equivalence or partially ordered. (a) R = {(a, a), (a, c), (b, a), (b, b), (c, a)}. (b) R ={(1,1), (2, 2), (3, 3), (1, 3), (3, 2), (2, 1)}. Solution: (a) R= {(a, a), (a, c), (b, a), (b, b), (c, a)}. R is not reflexive as (c, c)  R. R is not symmetric as (b, a)  R but (a, b)  R. R is transitive. R is neither an equivalence relation nor a partially ordered relation. (b) R = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 2), (2, 1)}. R is reflexive as (1, 1), (2, 2) and (3, 3) to R. R is not symmetric as (1, 3) belongs to R but (3, 1) does not belongs to R. R is not transitive as (1, 3), (3, 2) belongs to R but (1, 2) does not belongs to R. R is antisymmetric as (1, 3) and (3, 2) belongs to R and (3, 3) also belongs to R. R is neither an equivalence relation nor a partially ordered relation. 3.9 Summary
A relation is any association or link between elements of one set, called the domain or (less formally) the set of inputs, and another set, called the range or set of outputs. Some people mistakenly refer to the range as the codomain (range), but as we will see, that really means the set of all possible outputs—even values that the relation does not actually use. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 49
A relation R on a set A is called a partial order if R is reflexive, antisymmetric and transitive.
The set A together with the partial order relation ‘R’ is called partially ordered set or POSET denoted by (A, R).
A relation can be represented using a directed graph. The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined.
For each ordered pair (x, y) in the relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’. If there is an ordered pair (x, x), there will be self-loop on vertex ‘x’. 3.10 Key Words/Abbreviations
Relation: Relationship between sets of values.
Domain: What can go into a function?
Co-domain: What may possibly come out of a function.
Range: The set of elements that get pointed to in B (the actual values produced by the function) are the Range.
POSET: A set whose elements are ordered but not all pairs of elements are required to be comparable in the order. 3.11 Learning Activity 1. What is matrix representation of digraph? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. What is the Composition of relation? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

50 Discrete Mathematical Structures 3.12 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions 1. Draw a directed graph for the given relation defined on A = {a, b, c, d} R = {(a, a), (a, c), (b, d), (b, c) , (c, c) , (c, d)}. 2. If A = {1, 2, 3, 4, 5} a R b iff b < a for all a, b  A. Find relation R and also write its matrix relation also draw its digraph. 3. Determine whether the relation r on the set A is reflexive, irreflexive, symmetric, antisymmetric or transitive. (i) A = Z; a R b if and only if a ≤ b + 1, (ii) A = Z; a Rb iff | a – b | = 2. 4. Determine whether the relation R on the set A is an equivalence relation. A = {a, b, c, d}. R = {(a, a), (b, a), (b, b), (c, c), (d, d), (d, c)}. B. Multiple Choice/Objective Type Questions 1. If (a, b) and (b, a)  R then the relation is __________. (a) Asymmetric (b) Symmetric (c) Transitive (d) Reflexive 2. The set of all second components of the ordered pairs belonging to R is called the __________ of R. (a) domain (b) codomain (c) range (d) element 3. The pictorial representation of a relation from a set to itself is called __________. (a) graph (b) digraph (c) matrix (d) range CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 51 4. A relation R on a set A is __________ if (a, b) & (b, c)  R then (a, c)  R. (a) Asymmetric (b) Symmetric (c) Transitive (d) Reflexive 5. (1, 1), (2, 2), (3, 3)  R1, then R1 is __________ relation. (a) Asymmetric (b) Symmetric (c) Transitive (d) Reflexive Answers 1. (b), 2. (c), 3. (b), 4. (c), 5. (d) 3.13 References References Books: 1. https://www.cis.upenn.edu/~jean/discmath-root-b.pdf 2. http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf Web Resources: 1. https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_relations. htm 2. https://www.geeksforgeeks.org/relations-and-their-types/ 3. https://www.javatpoint.com/composition-of-relations 4. https://study.com/academy/lesson/partially-ordered-sets-lattices-in-discrete- mathematics.html CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 4 FUNCTIONS Structure: 4.0 Learning Objectives 4.1 Introduction 4.2 Functions 4.2.1 Definition 4.2.2 Domain 4.2.3 Codomain 4.2.4 Range of a Function 4.2.5 Direct Image 4.2.6 Inverse Image 4.3 Types of Functions 4.4 Composition of Functions 4.5 Recursively Defined Functions 4.6 Summary 4.7 Key Words/Abbreviations 4.8 Learning Activity 4.9 Unit End Questions (MCQ and Descriptive) 4.10 References

Functions 53 4.0 Learning Objectives After studying this unit, you will be able to:
Define Function, Domain, Codomain and Range of a Function.
Describe Different Types of Function.
Describe the Composition of Functions. 4.1 Introduction
A Function is a rule that assigns each input exactly one output. We call the output the image of the input. The set of all inputs for a function is called the domain. The set of all allowable outputs is called the codomain.
We would write f : X
Y, f : X
Y to describe a function with name f, domain X and codomain Y. This does not tell us which function f is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule). 4.2 Functions 4.2.1 Definition Let A and B be two non-empty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. It is written as f: A
B or f(a) = b. A function can be represented pictorially as in Fig. 4.1. Let A = {a, b, c, d) and B = { 1, 2, 3, 4} then f(a) = 1, f(b) = 2, f(c) = 2 and f(d) = 4. Since, each element of A is assigned with exactly one element of B therefore f : A
B is function. CU IDOL SELF LEARNING MATERIAL (SLM)

54 Discrete Mathematical Structures A B a1 b2 c3 d4 Fig. 4.1 Let A = {a, b, c, d) and B = {1, 2, 3} then f(a) = 1, f(b) = 2, f(c) = 2 and f(d) = 3. Since, each element of A is assigned with exactly one element of B therefore f : A
B is function. AB a1 b2 c d3 Fig. 4.2 Let A = {a, b, c, d) and B = {1, 2, 3} then f(a) = 1, f(b) = 2, f(c) = 3 but no image of d.  This is not a function. AB a1 b2 c d3 Fig. 4.3 Let A = {a, b, c, d) and B = {1, 2, 3, 4} then f(a) = 1, f(b) = 2, f(b) = 3, f(c) = 3 and f(d) = 4 CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 55 Element b is not uniquely related to the element of B. B  This is not a function. A a1 b2 c3 d4 Fig. 4.4 4.2.2 Domain If f is a function from A to B then A is called the domain of f, its members are the first coordinates of the ordered pairs belonging to f. It is denoted by dom(f). 4.2.3 Codomain If f is a function from A to B then Set B is called the codomain. 4.2.4 Range of a Function If (x, y)  f and we write y = f(x) then y is called the image of x and x is called preimage of y. The set consisting of all the images of the elements of A under the function f is called the range of f. It is denoted by Ran(f) or f(A). Thus, range of f = {f(x) : for all x  A}. The range of f is a subset of codomain which may or may not be equal to codomain. Example 1: Let A = {1, 2, 3, 4, 5} and B = {0, 1, 2, 3, 5, 7, 9, 12, 13} and f1 = {(1, 3), (2, 3), (3, 5), (4, 9), (5, 9)}, then f1 is a function from A to B because each element of A has unique image in B. f2 = {(1, 1), (2, 3), (4, 7), (5, 12)}, then f2 is not a function because the element 3 of A has no image in B. CU IDOL SELF LEARNING MATERIAL (SLM)

56 Discrete Mathematical Structures f3 = {(1, 1), (2, 3), (3, 5), (3, 7), (4, 9)}, then f3 is not a function because different pairs (3, 7) and (3, 5) have the same first component. Example 2: Let A = {1, 2, 3, 4, 5} and B = {0, 1, 2, 3, 5, 7, 9, 12, 13} and f = {(1, 3), (2, 3), (3, 5), (4, 9), (5, 9)}. Find dom(f), codomain, ran(f). Solution: Since function f = {(1, 3), (2, 3), (3, 5), (4, 9), (5, 9)} Then dom(f) = {1, 2, 3, 4, 5} Codomain = {0, 1, 2, 3, 5, 7, 9, 12, 13} Ran(f) = {3, 5, 9}. 4.2.5 Direct Image Let A and B be sets and let f: A
B. Let X ⊆ A. Then, we define f(x) by f(x) = {y  B : (∃x  X) = {y = f(x) | f(x)  B:x  X} we refer f(x) as the direct image of X. 4.2.6 Inverse Image Let A and B are the two sets and f: A
B. Let Y ⊆ B. Then, we define f–1 (y) by f–1 (y) = {x  A : (∃y  Y) [y = f(x)}. we refer f –1 (Y) as the inverse image of Y. Example 3: Let A = {1, 2, 3, 4}, B = {6, 9, 12, 15, 16} and f : A
B is defined as 1
6, 2
15, 3
6, 4
9 then. 1. find the direct image of f(1, 2, 3) 2. find the inverse image of (6, 9) off –1 (6, 9) CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 57 Solution: f(1, 2, 3) = {6, 15} f –1 (6, 9) = {1, 3, 4} 4.3 Types of Functions Injective Function (one-to-one function): Let A and B are two sets. A function from A into B is one-to-one if all elements x1, x2 in A such that f(x1) = f(x2) implies x1 = x2. i.e., if no element of A is assigned to the same element in B then the function is Injective. AB a1 b2 c3 d4 Fig. 4.5 Surjective function (Onto Function) Let A and B be the two sets and f : A
B be a function then f is surjective if every element of B is the image of some elements in A. To check onto function write x in terms of y and see if for every y  B, x  A. AB a1 b2 c d3 Surjective Fig. 4.6 CU IDOL SELF LEARNING MATERIAL (SLM)

58 Discrete Mathematical Structures Bijective Function A function f from A to B is said to be bijective if f is both injective and surjective. Identity Function Let A be non-empty set then the identity function on A is I(a) = a and is denoted by IA. Inverse Function The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f(a) = b. The inverse function of f is denoted by f –1 (b) = a when f(a) = b. Example 4: Determine whether the function f(x) = x + 1 from a set of real number to itself is one-to-one. Solution: Given f(x) = x + 1 Consider f(x1) = f(x2)  x1 + 1 = x2 + 1  x1 = x2 Hence, One-to-one function. Example 5: Determine whether the function f(x) = x2 from a set of real number to itself is one-to-one. Solution: The function f(x) = x2 is not one-to-one because f(1) = f(–1) = 1 but 1  –1. Example 6: Let f be function from A to B, where, A = {1, 2, 3, 4} and B = {x, y, z, w} with f(1) = w, f(2) = y, f(3) = x, f(4) = z then show that f is bijective. Solution: f is one-to-one since the function takes on distinct values. It is also onto since every element of B is the image of some element of A. Hence, f is bijective. CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 59 4.4 Composition of Functions Let A, B and C be the three sets and f, g be the functions such that f : A
B and g : B
C then there exists a new function from A to C called composition function. Denoted by gof(x) = g(f(x)) for all x in A. Example 7: Let A = {1, 2, 3}, B = {x, y}, C = {p, q} and f : A
B be defined by f(1) = x, f(2) = x, f(3) = y and g : B
C be defined as g(x) = p, g(y) = q. Then gof : A
C is defined by gof(1) = g(f(1)) = g(x) = p gof(2) = g(f(2)) = g( x) = p gof(3) = g(f(3)) = g(y) = q. Example 8: If f(x) = 3x2 – 1 and g(x) = 5 –2x then find gof(3). Solution: gof(3) = g(f(3))  g(3x2 – 1) = g(26)  5 – 2(26) = 5 – 52 = –47 Example 9: If f(x) = 3x, g(x) = 2x + 1 and h(x) = x2 then find fogoh(2) and hogof(1). Solution: (a) fogoh(2) = f(g(h(2))) = f(g(4)  f(2(4) + 1) = f(9) = 27  fogoh(2) = 27. CU IDOL SELF LEARNING MATERIAL (SLM)

60 Discrete Mathematical Structures (b) hogof(1)  h(g(f(1))) = h(g(3) = h(2(3) + 1) = h (7) = 49  hogof(1) = 49. Note: Let f : A
B and g : B
C be invertible then gof is invertible. 4.5 Recursively Defined Functions (i) We can also define functions recursively: in terms of the same function of a smaller variable. In this way, a recursive function “builds” on itself. Here is an example of a recursively defined function: f (0)  5 f (n)  f (n 1) 2 We can calculate the values of this function: f(0) = 5 f(1) = 1.f(0) = 1(1) = 1 f(2) = 2.f(1) = 2(1) = 2 f(3) = 3.f(2) = 3(2) = 6 f(4) = 4.f(3) = 4(6) = 24 f(5) = 5.f(4) = 5(24) = 120 … This recursively defined function is equivalent to the explicitly defined function f(n) = 2n + 5. However, the recursive function is defined only for non-negative integers. (ii) Here is another example of a recursively defined function: f (0)  0 f (n)  f (n 1) 2n 1 CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 61 The values of this function are: f(0) = 0 f(1) = f(0) + (2)(1) – 1 = 0 + 2 – 1 = 1 f(2) = f(1) + (2)(2) – 1 = 1 + 4 – 1 = 4 f(3) = f(2) + (2)(3) – 1 = 4 + 6 – 1 = 9 f(4) = f(3) + (2)(4) – 1 = 9 + 8 – 1 = 16 … This recursively defined function is equivalent to the explicitly defined function f (n) = n2. Again, the recursive function is defined only for nonnegative integers. (iii) Here is one more example of a recursively defined function: f (0)  1 f (n)  n  f (n 1) The values of this function are: f(0) = 1 f(1) = 1ƒf(0) = 1ƒ1 = 1 f(2) = 2ƒf(1) = 2ƒ1 = 2 f(3) = 3ƒf(2) = 3ƒ2 = 6 f(4) = 4ƒf(3) = 4ƒ6 = 24 f(5) = 5ƒf(4) = 5ƒ24 = 120 … This is the recursive definition of the factorial function, F(n) = n!. (iv) The Fibonacci Numbers. One special recursively defined function, which has no simple explicit definition, yields the Fibonacci numbers: CU IDOL SELF LEARNING MATERIAL (SLM)

62 Discrete Mathematical Structures f (1)  1 f (2)  1  f (n)  f (n 2) f (n 1) The values of this function are: f(1) = 1 f(2) = 1 f(3) = 1 + 1 = 2 f(4) = 1 + 2 = 3 f(5) = 2 + 3 = 5 f(6) = 3 + 5 = 8 f(7) = 5 + 8 = 13 f(8) = 8 + 13 = 21 f(9) = 13 + 21 = 34 … Thus, the sequence of Fibonacci numbers is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .... These numbers have many interesting properties that will be studied in higher math. They recur often in mathematics and even in nature. 4.6 Summary
A function is defined as a relation f from A to B (where A and B are two non-empty sets) such that for every a  A, there is a unique element b  B such that (a, b)  f. Hence, if f : A
B is a function, then for each element of set A, there is a unique element in set B. There are different types of functions which are given below:  One-one Function (or Injective Function)  Many-One Function CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 63  Onto Function (Surjective Function)  One-One Onto Function (Bijective Function)
In mathematics, a function is like a machine. It performs a set of operations on an input in order to produce an output. Therefore, a composition of functions occurs when the output, or result, of one function becomes the input of another function.
For functions represented by f(x) or g(x), the composition would be represented by f(g(x)) or g(f(x)). It’s important to know that f(g(x)) does not usually have the same value as g(f(x)), so order matters when calculating their composition. 4.7 Key Words/Abbreviations
Surjective: Onto or a Surjection.
Injective: one-to-one or a Injection.
Bijection: a mathematical function that is a one-to-one and onto mapping.
f(g(x)): Funtion of f of g of variable x.
g(f(x)): Funtion of g of f of variable x. 4.8 Learning Activity 1. State the difference between Injective and Surjective function. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Why the One-one Function is also called as Injective Function. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. Define Recurrence Relation. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

64 Discrete Mathematical Structures 4. Why the Onto Function is also called as Surjective Function. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 4.9 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions (I) Solve the Following: 1. State which ordered pair is a function from A into A. (a) {(3, 1), (2, 2), (3, 0), (1, 1), (1, 3)} (b) {(3, 1), (2, 2), (1, 2), (0, 3)} (c) {(x, y): x2 = y, x, y  Z} (d) The relation {(x, y): x, y  N, x < y} 2. Find the direct and inverse image of f: A
A where f is defined as {(b, a), (c, d), (d, a), (a, d) (a) f(a, b) (b) f –1(a, b) 3. Let f: A
B be a function. Check whether the function is one-to-onto, everywhere also find f –1 if it exist. A = R – [7/3] and B = R – {4/3} F(x) = (4x – 5)/(3x – 7). 4. Check which of the following functions are one to one, onto and bijective. (a) f : N
N, f(x) = x2 + 2 (b) f : N
N, f(x) = x (mod 3) (c) f : N
N, f(x) = {1 x is odd} = 0 x is even. 5. Let f: Z
Z, g : Z
Z, h : Z
Z defined by f(x) = x2, g(x) = x + 1 and h(x) = x – 1. Find CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 65 (a) gofoh (b) fogoh (c) hofog B. Multiple Choice/Objective Type Questions 1. Injective function is also called as __________. (a) one-to-one (b) one-to-many (c) many-to-one (d) None of these 2. An onto function is called as __________. (a) Injective (b) Bijective (c) Surjective (d) All of these 3. A function is invertible if it is __________. (a) Injective (b) Surjective (c) Bijective (d) None of these 4. A function f from A to B is said to be __________ if f is both injective and surjective. (a) Bijective (b) Surjective (c) Injective (d) Both a and b 5. If f is a function from A to B then Set B is called the __________ . (a) domain (b) codomain (c) range (d) relation Answers 1. (a), 2. (c), 3. (c), 4. (a), 5. (b) CU IDOL SELF LEARNING MATERIAL (SLM)

66 Discrete Mathematical Structures 4.10 References References Books: 1. https://www.cis.upenn.edu/~jean/discmath-root-b.pdf 2. http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf Web Resources: 1. https://www.tutorsonnet.com/types-of-functions-in-discrete-math-homework-help.php 2. https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_functions.htm 3. https://en.wikibooks.org/wiki/Discrete_Mathematics/Functions_and_relations 4. https://www.toppr.com/guides/maths/relations-and-functions/types-of-functions/ CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 5 PROPOSITIONAL LOGIC Structure: 5.0 Learning Objectives 5.1 Introduction 5.2 Propositional Logic 5.3 Logical Connectives 5.4 Logical Equivalence 5.5 Conditional Statements 5.6 Types of Propositions based on Truth Values 5.7 Summary 5.8 Key Words/Abbreviations 5.9 Learning Activity 5.10 Unit End Questions (MCQ and Descriptive) 5.11 References 5.0 Learning Objectives After studying this unit, you will be able to:
Define Proposition Logic.
Explain Truth Table of Various Proposition Logic.
Describe Operation of Logics.

68 Discrete Mathematical Structures 5.1 Introduction
In any ordinary language, a statement would never consist of a single word, but would always at the very least consist of a noun or pronoun along with a verb. However, because propositional logic does not consider smaller parts of statements, and treats simple statements as indivisible wholes, the language PL uses uppercase letters ‘A’, ‘B’, ‘C’, etc., in place of complete statements.
The logical signs ‘&’, ‘v’, ‘
’, ‘’, and ‘’ are used in place of the truth-functional operators, “and”, “or”, “if... Then...”, “if and only if”, and “not”, respectively.
Propositional logic, also known as Sentential logic, is that branch of logic that studies ways of combining or altering statements or propositions to form more complicated statements or propositions.
Joining two simpler propositions with the word “and” is one common way of combining statements. When two statements are joined together with “and”, the complex statement formed by them is true if and only if both the component statements are true. 5.2 Propositional Logic A proposition is the basic building block of logic. It is defined as a declarative sentence that is either True or False, but not both. The Truth Value of a proposition is True (denoted as T) if it is a true statement, and False (denoted as F) if it is a false statement. For Example, 1. The sun rises in the East and sets in the West. 2. 1 + 1 = 2 3. ‘b’ is a vowel. All of the above sentences are propositions, where the first two are Valid (True) and the third one is Invalid (False). Some sentences that do not have a truth value or may have more than one truth value are not propositions. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 69 To represent propositions, propositional variables are used. By Convention, these variables are represented by small alphabets. The area of logic which deals with propositions is called propositional calculus or propositional logic. It also includes producing new propositions using existing ones. Propositions constructed using one or more propositions are called compound propositions. The propositions are combined together using Logical Connectives or Logical Operators. 5.3 Logical Connectives A statement formed by combining two or more simple statements by using one or more of the words ‘and/or/not’ (with definite meaning in the language of logic, called object language) is called compound statement. These words or group of words are called logical connectives or connectives. Sr. No. Connective Symbol Name of the corresponding compound statement 1 and  2 or  Conjunction 3 not  Disjunction Negation (i) Conjunction If two simple statements, p and q are connected by the word ‘and’ then the resulting compound statement ‘p and q’ called conjunction of p and q and is written in symbolic form as ‘p  q’ (read as ‘p and q’). Example: Let P : Paris is in England. I : Delhi is in India. The conjunction of the statements p and q given by p  q: Paris is in England and Delhi is in India. Note: Sometimes you can use ‘but’ in place of ‘and’ in the conjuctive sense. CU IDOL SELF LEARNING MATERIAL (SLM)

70 Discrete Mathematical Structures Example: (i) He was blind and he stood first in examination. (ii) He was blind but he stood first in examination. Truth table Conjunction (p  q): p q pq TTT TFF FTF FFF Note: If both p and q are true statements that p  q is true statement. If anyone of p and q, both p and q are false statement p  q is false statement. (ii) Disjunction If two simple statements p and q are connected by the word ‘or’ then the resulting compound statement ‘p or q’ is called disjunction of p and q and is written in symbolic form as ‘ p  q’ (read as ‘p or q’). Example: p : It is cold. q : It is raining. The disjunction of the statement p and q is given by p  q. It is cold or it is raining. Truth table of Disjunction (p  q). p q pq TTT TFT FTT FFF Note: If both p and q are false statements then p  q is false otherwise p  q is true. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 71 (iii) Negation The negative of a statement is generally formed by inserting the word ‘not’ at some proper place in the statement or by prefixing the statement with. ‘It is not the case that’ or ‘It is false that’ or ‘It I not true that’. The negation of a statement p in symbolic form is written as p (read ‘negation p’ or ‘not p’). e.g., let p: 2 + 5 = 7 Then negation of p is given by ~p : 2 + 5 = 7 or ~p : It is not case that 2 + 5 = 7 or ~p : It is false that 2 + 5 = 7. Truth table of p: P p TF FT Example 1: Prepare the truth tables for each of the following statement patterns. (a) p   q (b) (p  q)  (p  r) Solution (a): p q q pq T TFT T FTT F TFF F FTT CU IDOL SELF LEARNING MATERIAL (SLM)

72 Discrete Mathematical Structures (b) (p  q)  (p  r) T p q r pq pr T T TTTTT T T TTFTT F F TFTTT F TFFTT FTTTT FTFTF FFTFT FFFFF 5.4 Logical Equivalence (1) Idempotent Law: (a) p  p  p (b) p  p  p (2) Commutative Law: (a) p  q  p  p (b) p  q  q  p (3) Associative Law: (a) (p  q)  r  p  (q  r)  p  q  r (b) (p  q)  r  p  (q  r)  p  q  r (4) Distributive Law: (a) p  (q  r)  (p  q)  (p  r) (b) p  (q  r)  (p  q)  (p  r) CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 73 (5) Identity Law: (a) p  F  p (b) p  F  F (c) p  T  T (d) p  T  p (6) Complement Law: (a) p   p  T (b)  ( p)  p (c) p   p  F (d)  T  F (e)  F  T (7) De Morgan’s Laws: (a)  (p  q)   p   q (2)  (p  q)   p   q (1) (2) (3) (4) (5) (6) (7) pq p TT F q pq  (p  q)  p   q TF F FT T FTFF FF T TTFF From (6) and (7) FTFF  (p  q)   p   q TFTT CU IDOL SELF LEARNING MATERIAL (SLM)

74 Discrete Mathematical Structures (b) (3) (4) (5) (6) (7) p (1) (2) F q pq  (p  q)  p   q pq F TT T FTFF TF T FT TFTT FF FFTT From (6) and (7) TFTT  (p  q)   p   q 5.5 Conditional Statements I. Conditional Statement (Implication): If two simple statements p and q are connected by the group of words ‘If… then…’ then resulting compound statement, If ‘p then q’ is called conditional (implication) of p and q and is written in symbolic form as ‘p
q’ (read as ‘p implies q’). Example: Let p : You like mathematics. q : You like statistics. The implication of the statement p and q is given by p
q : If you like Mathematics then you like statistics. The truth table for conditional statements (p
q) p q p
q TTT TFF FTT FFT Note: An implication p
q is false if p is true and q is false, otherwise p
q is true. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 75 Converse, Inverse and Contrapositive: If p and q are two statements, then, (a) The implication (conditional statement) q
p is called converse of the conditional statement p
q. (b) The implication (conditional statement) p
q is called inverse of the conditional statement p
q. (c) The implication (conditional statement) q
p is called contrapositive of the conditional statement p
q. Example 2: Write the converse, inverse and contrapositive of the following statements: (i) If you study hard then you will get success. (ii) A family becomes literate if the women in it are literate. Solution: (i) Let p : You study hard. q : You will get success  Symbolic form is p
q. Converse: q
p i.e., if you will get success then you study hard, Inverse: p
q i.e., If you do not study hard. then you will not get success. Contrapositive: q
p i.e., If you will not get success then you do not study hard. (ii) Let p : The women in a family are literate. q : A family becomes literate  Symbolic form is p
q CU IDOL SELF LEARNING MATERIAL (SLM)

76 Discrete Mathematical Structures Converse: q
p i.e., If a family becomes literate then women in it are literate. Inverse:  p
 q i.e., If the women in the family are not literate then family does not become literate. Contrapositive:  q
 p i.e., If a family does not become literate then the women in it are not literate. II. Biconditional Statement (Equivalence): If two simple statements p and q are connected by the group of words ‘If and only if’ (iff) then the resulting compound statement ‘p if and only if q’ is called biconditional of p and q and is written in symbolic form as p  q and (read as ‘p if and only if q’). Example: Let p : A triangle is equilateral. q : A triangle is equiangular. Then biconditional statement of p and q is given by p  q : A triangle is equilateral if and only if it is equiangular triangle. The Truth table for Biconditional (p  q) p q pq TTT TFF FTF FFT Note: From the table, it is clear that p  q is true when both p and q have same truth values otherwise false. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 77 Example 3: Prepare the truth table for each of the following statement pattern. (a) [(p
q)  q]
p (b) (p  q)
(p  q) (c) (p
q)  (p  q) (d) (p  r)  (q  p) Solution: (a) q p
q (p
q)  q [(p
q)  q]
p p TTT T T T FFF T F F TTT F (b) FTF T p q pq pq (p  q)
(p  q) T T TTT T F F FFT T (c) TFT T p FFF T T T q p p
q p  q (p
q)  (p  q) F F TFTT T (d) FFFF T p TTTT T T T FTTT T q r pr qp (p  r)  (q  p) TTTT T TFFT F CU IDOL SELF LEARNING MATERIAL (SLM)

78 Discrete Mathematical Structures TFTTF F TFFFF F FTTFF F FTFTF F FFTFT F FFFTT T 5.6 Types of Propositions based on Truth Values There are three types of propositions when classified according to their truth values: Tautology, Contradiction and Contingency. (i) Tautology A statement pattern having truth value always T, irrespective of the truth values of it’s component statement is called tautology. Example: (p  q)  (q  p) p q pq qp (p  q)  (q  p) TT T T T TF F F T FT F F T FF T T T In the above truth table, all the entries in the lost column are T.  The given statement pattern is a tautology. (ii) Contradiction: A statement pattern having truth value always F, irrespective of the truth values of it’s component statement is called a contradiction. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 79 Example: (p   q)  (p
q) p q q pq p
q (p   q)  (p
q) F TTFFT F F TFTTF F FTFFT FFTFT In the above truth table, all the entries in the last column are F.  The given statement pattern is a contradiction. (iii) Contingency: A statement pattern which is neither a tautology nor a contradiction is called contingency. Example: (p  q)   (p
 q) p q  q p
 q p  q (p
 q) (p  q)  (p
 q) TTF F T T T T FTT F F F F TF T F F F F FTT T F F In the above truth table, the entries in the last column are a combination of T and F.  The given statement pattern is neither a tautology nor a contradiction, it is a contingency. Example 4: Determine whether the following statement pattern is a tautology, contradiction or contingency. (a) ( p  q)  (q
p) (b) ( p   q)  (q  r) (c) ( p
q)  (p
q) CU IDOL SELF LEARNING MATERIAL (SLM)

80 Discrete Mathematical Structures Solution: q p pq q
p ( p  q)  (q
p) (a) TFT T T FFF T T P TTT F T T FTT T T T F F  ( p  q)  (q
p) is a Tautology (b) pq qr ( p   q)  (q  r) F T F p q r p q F F F TTTFF F F F TTFFF F F F TFTFT F T F TFFFT F F F FTTTF T F F FTFTF T F F FFTTT FFFTT  ( p   q)  (q  r) is a contradiction (c) p
q ( p
q)  (p
q) T T p q p p
q F F TTFT T T TFFT T F FTTT FFTF  ( p
q)  (p
q) is a contingency CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 81 Example 5: (8) Using truth table verify pq (a)  (p
 q)  p   ( q)  p  q T (b)  ( p
 q)   p  q F (c) p  ( q  r)   [P
(q   r)] F F Solution: (a) (4) (5) (6) (7)  ( q) p
q  (p
 q) p   ( q) (7) (1) (2) (3) pq p q q T F T T TTF F T F F F TFT T T F F F FTF F T F F T FFT F From (6), (7) and (8)  (p
 q)  p   ( q)  p  q (b) (3) (4) (5) (6) p (1) (2) F  q  p
 q  ( p
 q) Pq F TT T FT F TF T FT TT F FF FF T  From (6) and (7) TT F  ( p
 q)   p  q CU IDOL SELF LEARNING MATERIAL (SLM)

82 Discrete Mathematical Structures (c) 123 4 5 67 8 9 10  q  r p  ( q  r) qr p
 [p
p q r q r (q   r) (q   r)] TT F TTT F F FF T F T TTF F T TT F T F TFTT F TT F F T TFFT T TF F F T FTT F F FF T T F FTF F T TF F T F FFTT F TF F T F FFFT T T F  from (7) and (10) p  ( q  r)   [p
(q   r)] 5.7 Summary
Propositional logic, also known as sentential logic and statement logic, is the branch of logic that studies ways of joining and/or modifying entire propositions, statements or sentences to form more complicated propositions, statements or sentences, as well as the logical relationships and properties that are derived from these methods of combining or altering statements. In propositional logic, the simplest statements are considered as indivisible units, and hence, propositional logic does not study those logical properties and relations that depend upon parts of statements that are not themselves statements on their own, such as the subject and predicate of a statement.
However, more must be said about the meaning or semantics, of the logical operators ‘&’, ‘v’, ‘
’, ‘’, and ‘’. As mentioned above, these are used in place of the English words, ‘and’, ‘or’, ‘if... Then...’, ‘if and only if’, and ‘not’, respectively.
Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements. CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 83
It is important to be conversant with the following concepts related to the use and outcomes of truth tables: (i) Inclusive disjunction: Where both disjuncts can be true at the same time. (ii) Exclusive disjunction: Where both disjuncts cannot be true at the same time. (iii) Order of operations: The order of handling the logical operators within a truth- functional proposition; it is a step-by-step method of generating a complete truth table. (iv) Contingent statements: Statements that are neither necessarily true nor necessarily false (they are sometimes true, sometimes false). (v) Non-contingent statements: Statements such that the truth values in the main operator column do not depend on the truth values of the component parts. (vi) Tautology: A statement that is necessarily true. (vii) Self-contradiction: A statement that is necessarily false. 5.8 Key Words/Abbreviations Word Connective Symbol Logical gate “” AND and conjunction “” AND “” AND and then conjunction “” OR “” XOR and then within conjunction “” XOR “
” IMPLY or disjunction “” “
” IMPLY either...or exclusive disjunction “” XNOR “” XNOR either, but not both exclusive disjunction implies material implication is implied by converse implication if...then material implication if and only if biconditional just in case biconditional CU IDOL SELF LEARNING MATERIAL (SLM)

84 Discrete Mathematical Structures 5.9 Learning Activity 1. What is Logic? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. What is a Proposition? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. What is Logical Equivalence? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 4. What are different Logical Operators? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 5. What is Symbolic Logic? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 5.10 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Which of the following sentences are statements? In case of statements, write down their truth values. (a) Every natural number is a real number (b) 4 is a rational number (c) Please come here CU IDOL SELF LEARNING MATERIAL (SLM)

Propositional Logic 85 (d) He is a bad person (e) Two is the only even prime number 2. Construct the truth table for each of the following statement patterns. (a) p
(q
p) (b) ( p   q)  [ (p  q)] (c) [(p  q)  r]  [ r  (p  q)] 3. Determine whether the following statement pattern is a tautology, contradiction or contingency. (a) [p  (p
q)]
q (b) (p
q)  (p   q) (c) [(p   q)  (p  q)]  r 4. While the converse, inverse and contrapositive of the following statements. (a) If a man is bachelor then he is unhappy. (b) If two triangles are congruent then their areas are equal. 5. Without using truth table show that (a) p  ( p  q)  p  q (b) (p  q)  (p   q)  ( p   q)  p   q (c) [p  ( p   q)]  [p  (q  r)  p  (q  r) (d) p  [(p  q)  q]  p 6. Using truth table, prove the following logical equivalence. (a) p  q   (p   q)   (q   p) (b)  (p  q)  ( p  q)   p (c)  p  q  (p  q)   p B. Multiple Choice/Objective Type Questions 1. The conditional (p  q)
p is (a) Tautology (b) Contradiction (c) Contingency (d) None of these CU IDOL SELF LEARNING MATERIAL (SLM)

86 Discrete Mathematical Structures 2. ~ (p  q) is __________. (a) ~ p  ~ q (b) (p   q)  (~ p  q) (c) ~ p   q (d) None of these 3. p
q can also be written as __________. (a) p
~ q (b) ~ q
~ p (c) ~ p  q (d) None of these 4. The proposition p  ~ p is a (a) Tautology and contradiction (b) Contingency (c) Tautology (d) Contradiction 5. The logically equivalent proposition of p  q is (a) (p  q)  (q  p) (b) (p
q)  (q
p) (c) (p  q)  (q
p) (d) (p  q)
(q  p) Answers 1. (a), 2. (b), 3. (c), 4. (d), 5. (b) 5.11 References References Book: 1. https://www.cs.cornell.edu/~rafael/discmath.pdf Web Resources: 1. https://www.iep.utm.edu/prop-log/ 2. http://discrete.openmathbooks.org/dmoi2/sec_propositional.html 3. https://www.wisdomjobs.com/e-university/discrete-mathematics-tutorial-471/discrete- mathematics-propositional-logic-25641.html CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6 COMBINATORY 1 Structure: 6.0 Learning Objectives 6.1 Introduction 6.2 Mathematical Induction 6.2.1 Definition 6.2.2 Strong Induction 6.3 Recursive Mathematical Definitions 6.4 Basics of Counting 6.5 Permutations 6.6 Combinations 6.7 Principle of Inclusion-Exclusion 6.8 Recurrence Relations 6.9 Summary 6.10 Key Words/Abbreviations 6.11 Learning Activity 6.12 Unit End Questions (MCQ and Descriptive) 6.13 References

88 Discrete Mathematical Structures 6.0 Learning Objectives After studying this unit, you will be able to:
Explain Mathematical Induction.
Describe Inclusion-Exclusion Principle.
Describe Recurrence Relations.
Describe the Concept of Permutations, Combinations. 6.1 Introduction
Combinatory is a branch of mathematics with applications in fields like physics, economics, computer programming, and many others. In particular, probability theory is one of the fields that makes heavy use of combinatorics in a wide variety of contexts.
For example, when calculating probabilities, you often need to know the number of possible orderings or groupings of events, outcomes of experiments, or generally any kind of objects.
Combinatorics, also called combinatorial mathematics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Included is the closely related area of combinatorial geometry. 6.2 Mathematical Induction Mathematical induction is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples. 6.2.1 Definition Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. The technique involves two steps to prove a statement, as stated below − Step 1 (Base step) − It proves that a statement is true for the initial value. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 89 Step 2 (Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n + 1)th iteration (or number n + 1). How to Do It. Step 1 − Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value. Step 2 − Assume the statement is true for any value of n = k. Then prove the statement is true for n = k + 1. We actually break n = k + 1 into two parts, one part is n = k (which is already proved) and try to prove the other part. Example 1: 3n − 13n − 1 is a multiple of 2 for n = 1, 2, ... Solution: Step 1 − For n = 1, 31 − 1 = 3 − 1 = 2n = 1, 31 − 1 = 3 − 1 = 2 which is a multiple of 2. Step 2 − Let us assume 3n − 13n − 1 is true for n = kn = k, Hence, 3k − 13k − 1 is true (It is an assumption). We have to prove that 3k + 1 − 13k + 1 − 1 is also a multiple of 2. 3k + 1 − 1 = 3 × 3k − 1 = (2 × 3k) + (3k − 1)3k + 1 − 1 = 3 × 3k − 1 = (2 × 3k) + (3k − 1) The first part (2 × 3k) (2 × 3k) is certain to be a multiple of 2 and the second part (3k − 1) (3k − 1) is also true as our previous assumption. Hence, 3k + 1 – 13k + 1 – 1 is a multiple of 2. So, it is proved that 3n – 13n – 1 is a multiple of 2. Example 2: 1 + 3 + 5 + ... + (2n − 1) = n2 for n = 1, 2, … Solution: Step 1: prove that the equation is valid when n = 1 When n = 1, we have (2(1) – 1) = 12, so the statement holds for n = 1. CU IDOL SELF LEARNING MATERIAL (SLM)

90 Discrete Mathematical Structures Step 2: Assume that the equation is true for n, and prove that the equation is true for n + 1. Assume: 1 + 3 + 5 + ... + (2n – 1) = n2 Prove: 1 + 3 + 5 + ... + (2(n + 1) – 1) = (n + 1)2 Proof: 1 + 3 + 5 + ... + (2(n + 1) – 1) = 1 + 3 + 5 + ... + (2n - 1) + (2n + 2 – 1) = n2 + (2n + 2 – 1) (by assumption) = n2 + 2n + 1 = (n + 1)2 So, by induction, for every positive integer n, Hence, 1 + 3 + 5 + ... + (2n − 1) = n2 is proved. Example 3: Prove that (ab)n = anbn(ab)n = anbn is true for every natural number nn. Solution: Step 1 − For n = 1, (ab)1 = a1b1 = abn = 1, (ab)1 = a1b1 = ab, Hence, step 1 is satisfied. Step 2 − Let us assume the statement is true for n = kn = k, Hence, (ab)k = akbk(ab)k = akbk is true (It is an assumption). We have to prove that (ab)k + 1 = ak + 1bk + 1(ab)k + 1 = ak + 1bk + 1 also hold. Given, (ab)k = akbk(ab)k = akbk or, (ab)k(ab) = (akbk) (ab) (ab)k(ab) = (akbk) (ab) [Multiplying both side by 'ab'] or, (ab)k + 1 = (aak) (bbk) (ab)k + 1 = (aak) (bbk) or, (ab)k + 1 = (ak + 1bk + 1) (ab)k + 1 = (ak + 1bk + 1) Hence, step 2 is proved. So, (ab)n = anbn(ab)n = anbn is true for every natural number n. CU IDOL SELF LEARNING MATERIAL (SLM)

Combinatory 1 91 6.2.2 Strong Induction Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, P(n)P(n) is true for all positive integers, nn, using the following steps −
Step 1 (Base step) − It proves that the initial proposition P(1)P(1) true.
Step 2 (Inductive step) − It proves that the conditional statement [P(1)
P(2)
P(3)
...
P(k)]  P(k + 1)[P(1)
P(2)
P(3)
...
P(k)]  P(k + 1) is true for positive integers k. 6.3 Recursive Mathematical Definitions (i) To define a function on the set of non-negative integers 1. Specify the value of the function at 0. 2. Give a rule for finding the function's value at n + 1 in terms of the function's value at integers i ≤ n. Example: factorial function definition
0! = 1
n! = n (n–1)!
recursive or inductive definition of a function on non-negative integers. Example (i): Assume a recursive function on positive integers:
f(0) = 3
f(n + 1) = 2f(n) + 3
What is the value of f(0)? 3
f(1) = 2f(0) + 3 = 2(3) + 3 = 6 + 3 = 9
f(2) = f(1 + 1) = 2f(1) + 3 = 2(9) + 3 = 18 + 3 = 21 CU IDOL SELF LEARNING MATERIAL (SLM)

92 Discrete Mathematical Structures
f(3) = f(2 + 1) = 2f(2) + 3 = 2(21) = 42 + 3 = 45
f(4) = f(3 + 1) = 2f(3) + 3 = 2(45) + 3 = 90 + 3 = 93 Example (ii): Define the sequence: an = n2 for n = 1,2,3, ... recursively.
a1 = 1
an + 1 = an 2 + (2n + 1), n ≥ 1 (ii) Some important functions or sequences in mathematics are defined recursively Factorials
n! = 1 if n = 1
n! = n.(n-1)! if n≥1 Fibonacci numbers:
F(0) = 0, F(1) = 1 and
F(n) = F(n-1) + F(n-2) for n = 2,3, … 6.4 Basics of Counting In daily lives, many a times one needs to find out the number of all possible outcomes for a series of events. For instance, in how many ways can a panel of judges comprising of 6 men and 4 women be chosen from among 50 men and 38 women? How many different 10 lettered PAN numbers can be generated such that the first five letters are capital alphabets, the next four are digits and the last is again a capital letter? For solving these problems, mathematical theory of counting are used. Counting mainly encompasses fundamental counting rule, the permutation rule, and the combination rule. CU IDOL SELF LEARNING MATERIAL (SLM)