35113923_BCA114

BACHELOR OF COMPUTER APPLICATIONS MATHEMATICS 21BCA114

BACHELOR OF COMPUTER APPLICATIONS MATHEMATICS 21BCA-114 Dr. Abhilasha S. Magar

CHANDIGARH UNIVERSITY Institute of Distance and Online Learning Course Development Committee Chairman Prof. (Dr.) R.S. Bawa Vice Chancellor, Chandigarh University, Punjab Advisors Prof. (Dr.) Bharat Bhushan, Director, IGNOU Prof. (Dr.) Majulika Srivastava, Director, CIQA, IGNOU Programme Coordinators & Editing Team Master of Business Administration (MBA) Bachelor of Business Administration (BBA) Co-ordinator - Prof. Pragya Sharma Co-ordinator - Dr. Rupali Arora Master of Computer Applications (MCA) Bachelor of Computer Applications (BCA) Co-ordinator - Dr. Deepti Rani Sindhu Co-ordinator - Dr. Raju Kumar Master of Commerce (M.Com.) Bachelor of Commerce (B.Com.) Co-ordinator - Dr. Shashi Singhal Co-ordinator - Dr. Minakshi Garg Master of Arts (Psychology) Bachelor of Science (Travel & Tourism Management) Co-ordinator - Ms. Nitya Mahajan Co-ordinator - Dr. Shikha Sharma Master of Arts (English) Bachelor of Arts (General) Co-ordinator - Dr. Ashita Chadha Co-ordinator - Ms. Neeraj Gohlan Master of Arts (Mass Communication and Bachelor of Arts (Mass Communication and Journalism) Journalism) Co-ordinator - Dr. Chanchal Sachdeva Suri Co-ordinator - Dr. Kamaljit Kaur Academic and Administrative Management Prof. (Dr.) Pranveer Singh Satvat Prof. (Dr.) S.S. Sehgal Pro VC (Academic) Registrar Prof. (Dr.) H. Nagaraja Udupa Prof. (Dr.) Shiv Kumar Tripathi Director – (IDOL) Executive Director – USB © No part of this publication should be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording and/or otherwise without the prior written permission of the author and the publisher. SLM SPECIALLY PREPARED FOR CU IDOL STUDENTS Printed and Published by: Himalaya Publishing House Pvt. Ltd., E-mail: [email protected], Website: www.himpub.com For: CHANDIGARH UNIVERSITY Institute of Distance and Online Learning CU IDOL SELF LEARNING MATERIAL (SLM)

Mathematics Course Code: BCA114 Credits: 3 Course Objectives:  To develop skills and knowledge in sets and equations.  To enhance the knowledge about mathematical connectives which would enable students to devise solutions for given situations they may encounter in their profession.  To generate logic building matrices useful in programming. Syllabus Unit 1 - Sets: Sets, representation of sets, types of sets, operation on sets and Venn diagram. Unit 2 - Relation: Types of relation and equivalence relation. Unit 3 - Functions: Types of functions, composite of two functions and composite of three functions. Unit 4 - Modern Algebra 1: Algebra of logic and propositions. Unit 5 - Modern Algebra 2: Connectives, tautologies and contradiction Unit 6 - Modern Algebra 3: Equivalence and implication. Unit 7 - Modern Algebra 4: Principle of mathematical induction and quantifiers. Unit 8 - Matrices 1: Introduction of a matrix and its different kinds. Unit 9 - Matrices 2: Addition and scalar multiplication. Unit 10 - Matrices 3: Multiplication of matrices, square matrix and rank of a matrix. Unit 11 - Matrices 4: Transpose, adjoint and inverse of a matrix, eigen values and eigen vectors. Text Books: 1. Veerarajan, T. (2016). “Discrete Mathematics”, New Delhi: Tata Macgraw Hill. 2. Singaravelu (2013). “Allied Mathematics”, Chennai: Meenakshi Agency. Reference Books: 1. Vittal, P.R. (2017). “Allied Mathematics”, Chennai: Margham Publications. 2. Venkatachalapathy, S.G. (2007). “Allied Mathematics”, Chennai: Margham Publications. CU IDOL SELF LEARNING MATERIAL (SLM)

CONTENTS 1 - 15 16 - 26 Unit 1: Sets 27 - 40 Unit 2: Relation 41 - 49 Unit 3: Functions 50 - 57 Unit 4: Modern Algebra 1 58 - 66 Unit 5: Modern Algebra 2 67 - 79 Unit 6: Modern Algebra 3 80 - 87 Unit 7: Modern Algebra 4 88 - 102 Unit 8: Matrices 1 103 - 132 Unit 9: Matrices 2 133 - 196 Unit 10: Matrices 3 Unit 11: Matrices 4 197 References CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 1 UNIT 1 SETS Structure: 1.0 Learning Objectives 1.1 Introduction 1.2 Sets and its Elements 1.3 Elements of a Set 1.4 Set Description 1.5 Standard Sets and Symbols 1.6 Types of Sets 1.7 Subset 1.8 Venn-Euler Diagrams 1.9 Set Operation 1.10 Summary 1.11 Key Words/Abbreviations 1.12 Learning Activity 1.13 Unit End Questions (MCQ and Descriptive) 1.14 References 1.0 Learning Objectives After studying this unit, you will be able to:  Explain the elements of sets. CU IDOL SELF LEARNING MATERIAL (SLM)

2 Mathematics  Analyse the standard sets and their symbols.  Discuss about the types of sets. 1.1 Introduction In this chapter, we shall elaborate and discuss the “importance of set” in application of mathematics, computer science and engineering to real-life problems. Venn diagram representation of sets can be applied to understand relationship between set theory and logical arguments in Boolean algebra. Moreover, this concept simplifies, clarifies and unifies many other mathematical concepts. 1.2 Sets and its Elements Definition A set is any well-defined collection or class of distinct objects. By a well-defined collection, we mean that there exists a rule with the help of which we should be able to say whether any given object or entity belongs to or not to the collection under consideration. The following are some examples of set: (i) Students who speak either Hindi or English. (ii) Rivers in India. (iii) Countries in the world. (iv) Vowels in English alphabet. (v) Set of all points in a plane. 1.3 Elements ofa Set The objects in a set are called its elements or members. The elements in the set must be distinct and distinguishable. By ‘distinct', we mean that no element is repeated and by ‘distinguishable', we mean that given any object, it is either in the set or not in the set. Generally, capital letters A, B, C, X, Y, Z, etc. are used to denote set and its elements by lower case letters a, b, c, x, y, z, etc. CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 3 The symbol  (epsilon) is used to indicate, belongs to (a member or element of). If x is an element of set A, we symbolically write it as x  A. The symbol  is used to indicate, does not belongs to. Thus, if x is not an element of A, we write it as x  A . 1.4 Set Description The way of describing a set and its elements vary depending on the specific set. The most common methods of describing elements of sets are as follows: Roster Method In this method, elements of sets are described by enumerating (listing or writing) them exhaustively within brackets. For example, the elements of the Set V of all the vowels in the English alphabet can be represented as: V = {a, e, i, o, u} Sometimes, it is not possible to list all the elements, but after knowing a few elements, we can understand as to what the other elements are. For example, A = {a, b, c, …….}, the set of letters of English Alphabets. S = {1, 9, 25, 36, ...}, the set of squares of positive odd integers. Roster method is also known as Tabular or Enumeration method. Set Builder Method In this method, the elements of a set are represented by stating a property (qualitative, quantitative, or both) that uniquely characterize them. To understand this method, let us consider the sets: A = {2, 4, 6, 8, ….} B = {a, e, i, o, u} If we try to search out some property among elements of set A and B, we find that all elements of the set A are even positive integers; all the elements of set B are the vowels of CU IDOL SELF LEARNING MATERIAL (SLM)

4 Mathematics English alphabets. Thus, we can use the letter ‘x' to represent an arbitrary element of set together with the property of x. Therefore, sets A and B may be represented as: A = {2, 4, 6, 8, …} = {x : x is an even positive integer} B = {a, e, i, o, u, ...} = {x : x is a vowel in English alphabet} Where the colon (:) is read as: such that or where and is used interchangeably with a vertical line. The symbol {x : ….} is read ‘the set of all x such that ….'. The property follows ‘:' help us determine the element of the set that is being described. Set Builder method is also known as Set Selection Method. 1.5 Standard Sets and Symbols The choice of name for a set is much like the choice of an identifier name in programming. There are few sets of numbers that we will use frequently in the text, so that we have standard symbols for them, such as: N = {1, 2, 3, 4, 5, …}, the set of natural numbers. I = {….., –3, –2, –1, 0, 1, 2,…..}, the set of integers. I+ = {1, 2, 3, ….}, the set of positive integers. Q = {x ; x = p where p and q are integers and q  0}, the set of rational numbers. q Q+ = the set of positive rational numbers. R = the set of real numbers. C = {x : x = a + ib; a, b R, i = – 1 }, the set of complex numbers. P = the set of prime numbers. 1.6 Types of Sets 1. Finite and Infinite Sets  A set is finite if it contains finite numbers of different elements. CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 5 For example: (i) The set of months in a year. (ii) The set of students in the classrooms. (iii) The set of days in a week. (iv) The set of cities in India.  A set which contains infinite number of elements is known as infinite set. For example: N = {1, 2, 3, 4, ….}, the set of natural numbers. I = {…., –3, –2, –1, 0, 1, 2, …}, the set of integers. A = {x : x is set of points in the Euclidean planes}. 2. Singleton Set A set which contains only one element is called as singleton (or unit) set. For example: A = {x : 4 < x < 6, x is an integer} B = {5} I = {x : x2 = 9 and x is negative integer}. 3. Null Set A set which contains no element is called an empty set. This set is denoted by Greek letter  (phi) or {}. For example: (i)  = set of all those x which are not equal to x itself. = {x : x  x}. (ii) A = {x: x2 + 4 = 0, x is real}. (iii) Set of all integers whose square is equal to 5. = {x : x2 = 5, x is an integer}. CU IDOL SELF LEARNING MATERIAL (SLM)

6 Mathematics 4. Equality of Sets Two sets A and B are said to be equal if every element of A is an element of B and also every element of B is an element of A. The equality of two sets sets A and B is denoted by A = B symbolically A = B if and only if x  A ↔ x  B. This is known as Axiom of extension or identity. For example, if (a) A = {4, 3, 2, 1} and B = {1, 2, 3, 4} then A = B because both have same and equal number of elements. (b) Also if, A = {2, 3}, B = {3, 2} and C = {x: x2 – 5x + 6 = 0} then A = B = C because each element which belongs to any one of the set also belongs to the other two sets. (c) Let A = set of all integers whose squareis 25 B = set of all roots of the equation x2 – 25 = 0 C = {–5, +5} then A = B = Cs 5. Equivalent Sets If the elements of one set can be put into one-to-one correspondence with the elements of another set, then the two sets are called equivalent sets. In other words, two sets A and B are said to be equivalent sets if and only if there exists a one-to-one correspondence between their elements. By one-to-one correspondence, we mean that for each element in A, there exists and match with one element in B and vice versa. The symbol , ~ or Ξ is used to denote equivalent set. Example – A = {x : x is a letter in the word BOAT} B = {x : x is a letter in the word CART} Thus, A Ξ B. CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 7 1.7 Subset Let A and B be two non-empty sets. The set A is a subset of B (or A is contained in B) if and only if every element of A is an element of B. In other words, the set A is a subset of B if x  A  x  B. Symbolically, this relationship is written as: A  B if x  A  x  B. which is read as ‘A is a subset of B' or ‘A is contained in B'. If A  B, then B is called superset of A and we write B  A which is read as ‘B is superset of A' or ‘B contains A'. If the set A is not a subset of set B, i.e., if at least one element of A does not belong to B and we write, A  B . In other words, if x  A  x  B which is read as ‘A is not a subset of B'. Proper Subset A proper subset of a set AA is a subset of AA that is not equal to AA. In other words, if BB is a proper subset of AA, then all elements of BB are in AA but AA contains at least one element that is not in BB. For example, if A={1,3,5}A={1,3,5} then B={1,5}B={1,5} is a proper subset of AA. The set C={1,3,5}C={1,3,5} is a subset of AA, but it is not a proper subset of AA since C=AC=A. The set D={1,4}D={1,4} is not even a subset of AA, since 4 is not an element of AA. Family of Sets If the elements of a set are set themselves, then such a set is called the family of sets. The word ‘collection' and ‘class' are also used for a set of sets. For example, if A = {a, b}, then the set {  , {a}, {b}, {a, b}} is the family of sets whose elements are subset of the set A. Power Set If S is any set, then the family of all subsets of S is called the power set of S and is denoted by P(S), i.e., P = {A : A  S}. Obviously,  and S are both members of P(S). CU IDOL SELF LEARNING MATERIAL (SLM)

8 Mathematics (i) Let A = {a}, then P(A) = {, {a}}. (ii) Let A = , then P(A) = {} or {} (iii) Let A = {a, b}, then P(A) = {, {a}, {b}, {a, b}}. (iv) Let us say Set A = {a, b, c} Number of elements: 3 Therefore, the subsets of the set are: { } which is the null or the empty set, {a}, {b}, {c}, {a, b}, {b, c}, {c, d} {a, b, c} The power set P(A) = {{ } , {a}, {b}, {c}, {a, b}, {b, c}, {c, d}, {a, b, c}} Universal Set In the application of set theory, all the sets under discussion are assumed to be the subset of the fixed large set, called the universal set. This set is usually denoted by U or E. U is superset of all the sets. (i) A set of all points in the plane (ii) All the people in the world constitute universal set in any study of human population. 1.8 Venn-Euler Diagrams A device known as Venn-Euler diagram or simply Venn diagram is a pictorial representation of sets. In Venn diagrams, a universal set U is represented by the interior of rectangle and each subset of U is represented by circle inside the rectangle. If the sets A and B are equal, then the same circle represents both A and B. If the sets A and B are disjoint, i.e., they have no elements in common, then circle representing A and B are drawn in such a way that they have no common area. However, if few elements are common to both A and B, then they are represented as shown in Figure 1.1. CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 9 U U U B AB AB A (a) A  B (b) A and B are disjoint (c) and (d) Fig. 1.1 Venn diagrams are used to illustrate the set relations such as the subset and operations with sets. Example 1: Write the following set in tabular form. A= {a : a  N, a < 10, a is odd}. Solution: As per description of nature of elements of set A, it can be written as: A = {1, 3, 5, 7, 9}. The elements of all odd natural numbers are less than 10. Example 2: Which of the following sets are different? (a)  (b) {0} (c) {} Solution: Each set is different because: (a)  is a set containing no element, i.e., null set. (b) {0} is a set containing the single element ‘zero', i.e., a singleton set. (c) {} is a set containing one element, i.e., empty set , or it is a set of set. Example 3: Let A{x : x = 5n + 2, n  N} and B = {x : x = 5n – 3, n  N}. Find which of the following statements is correct and why? (a) A  B (b) B  A (c) A = B (d) None of these Solution: Puttingn = 1, 2, 3, .…, we list different elements of the set: A = {7, 12, 17, 22, ....} and B = {2, 7, 12, 17, .... } Hence, A  B. Example 4: Are the following sets equal? A = {x : x2 – 3x = –2}, B = {2, 1} and C = {1, 2, 2, 1}. CU IDOL SELF LEARNING MATERIAL (SLM)

10 Mathematics Solution: A = {x : x2 – 3x = –2} = {x : x2 – 3x + 2 = 0} = {x : (x – 2) (x – 1) = 0} = {2, 1} C = {1, 2, 2, 1} = {1, 2} Since elements of A, B and C are same and equal in number, A = B = C. 1.9 SET OPERATIONS In this section, we shall discuss certain operations on set so as to yield new sets with the given sets. These operations play an important role in many application of Discrete Mathematics. Union of Sets Let A and B be two non-empty sets. The union of A and B is the set of all elements which are either in A or in B or in both A and B. The Union of A and B is represented by A  B. It is usually read as A union B. A  B = {x : x  A or x  B} Example 1: If A = {1,2,3,4} and B = {2,6,8} then A  B = {1,2,3,4,6,8} Example 2: If A = set of all natural numbers and B = set of all even natural numbers. Then A  B = A, i.e, set of all natural numbers. Figure 1.2 is a Venn diagram in which A  B is shaded. U AB AB Fig. 1.2 Union of Sets A and B (Shaded Area) CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 11 Intersection of Sets Let A and B be the two non-empty sets. The intersection of A and B is the set of all elements which are in both A and B. Intersection of A and B is denoted by A  B. A  B = {x : x  A and x  B} To find the intersection of two sets means finding elements common to A and B. Example 1: If A = {1,2,3,4,5} and B = {4,5,6,7} then A  B = {4,5}. Example 2: If A = set of all natural numbers and B = set of all odd natural numbers. Then A  B = B, i.e, set of all odd natural numbers. Figure 1.3 is a Venn diagram in which A  B is shaded. U AB AB Fig. 1.3: Intersection of Sets A and B Complement of a Set Let A be any set. The complement of A is a set of elements that belong to the universal set but do not belong to A. Thus, if U is a Universal Set, the complement of A is the set U – A and is Denoted by A' , Ac, A , or – A . Ac = U – A = {x : x  and x  A } = { x : x  A} Example 1: If N = {1,2,3,4,….} is the universal set and A = {1,3,5,7,…}, then Ac = N – A = {2,4,6,8,….} Example 2: If U = R, then Qc = set of irrational numbers. Figure 1.4 is the Venn diagram in which Ac is shaded. CU IDOL SELF LEARNING MATERIAL (SLM)

12 Mathematics U A Ac Fig. 1.4: Complement of Set A (Shaded Area) 1.10 Summary We have explained and discuss the “ importance of set ” in application of mathematics, computer science and engineering to real-life problems. A set is any well-defined collection or class of distinct objects. The objects in a set are called its elements or members. The elements in the set must be distinct and distinguishable. The symbol  (epsilon) is used to indicate, belongs to (a member or element of). If x is an element of set A, we symbolically write it as x  A. The way of describing a set and its elements vary depending on the specific set. The most common methods of describing elements of sets are as follows: (a) Roster Method (b) Set Builder Method The different types of sets are as follows: (a) Finite and Infinite sets (b) Sigleton set (c) Null Set (d) Equality of Sets (e) Equivalent Sets The set operations are as follows Union of Sets: The Union of A and B is represented by A  B. It is usually read as A union B. Intersection of sets: Intersection of A and B is denoted by A  B. Complement of a set: It is Denoted by A' , Ac, A , or – A . CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 13 1.11 Key Words/Abbreviations  U = Universal set A, B and C are subset of universal set.   = Null Set  Power Set = P(S)  Ac = Complement of set A 1.12 Learning Activity 1. If A = {1, 2, 3} and B = {3, 4, 5}, then find A  B and A  B. 2. If A = {10, 6} and B = {5, 4}, then find A  B. Is this null set? 1.13 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Define a set and give examples to illustrate the difference between a collection and a set. What are different ways to specify a set? Give examples. 2. Prove that for all sets A, B and C if A  B, B  C and C  A, then B = C. 3. Which of the following statements are true? (i) {a, b, c} = {c, b, a} (ii) Every subset of an infinite set is infinite. (iii) The set {1, 2, 3, 4} has in all 32 subsets. 4. Write down the following sets: (ii) B = {x : x2 = 9, x – 3 = 5} (i) A = {x : x2 = 4} CU IDOL SELF LEARNING MATERIAL (SLM)

14 Mathematics (iii) C = {x : x2 + 1 = 0, x is complex number} (iv) D = {x : x2 + 1 = 0, x is a real number} 5. Find out which of the following sets are null, singleton? (i) A = {x : x2 = 1, x is an even integer} (ii) B = {0} (iii) C = {x : x + 6 = 6} (iv) D = { x : x2 = 7, 3x= 5} 6. Let A = {x : x2 – 3x = –2}, B {2, 1} and C = {2, 3, 4}. Find x if: (i) x  A, x  B (ii) x  A, x  C 7. Which of the following sets are equal? (i) A = {1, 2, 2, 3} (ii) B = {{x : x2 – 2x + 1 = 0} (iii) C = {1, 2, 3} (iv) {x : x3 – 6x2 + 11x – 6 = 0} (v) E = {3, 2, 1} 8. List the elements of the following sets: (i) A = {x : x  N, 5 < x < 14} (ii) B = {x : x  N, x is odd, x < 21} (iii) C = {x : x  N, 6 + x = 3}. 9. If A = {2,4,6,8,10} and B = {6,8,10,12,14} Find A  B and A  B. 10. Let U = {0,1,2,3,4,5,6,7}; A = {0,2,4,6} ; B = {1,3,5,7} Then find: (a) A  B, (b) Bc Hints and Answers 1. See the text. 3. (i) True (ii) False (iii) False C = {i, –i}, 4. A = {2, –2}, B = , D =  5. A = , B and C are singleton, D =  6. (i) x = 0, (ii) x = 1 CU IDOL SELF LEARNING MATERIAL (SLM)

Sets 15 7. A = C = D = E . 8. A = {6, 7, 8, ...., 12, 13} 9. A  B = {2,4,6,8,10,12,14} , A  B = {6,8,10} 10. A  B = {0,1,2,3,4,5,6,7} Bc = {0,2,4,6} B. Multiple Choice/Objective Type Questions 1. The number of elements in the power set P(S) of the set S = {{}, 1, {1, 2, 3}} is (a) 2 (b) 4 (c) 8 (d) 10 2. Let A = {3, 4, 6} and B = {1, 2}. Then A  B = . (a) {3, 4} (b) {1} (c) {2} (d) {None} 3. Let A = {a, b} and B = {b, c, d}. Then A  B = . (a) {b} (b) {a} (c) {b, c} (d) {a, b} 4. Subset is denoted by . (a)  (b)  (c)  (d)  5. Universal set is represented by . (a) U (b) A (c) B (d) None Answers: 1. (c), 2. (d), 3. (a), 4. (a), 5. (a) 1.14 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

16 Mathematics UNIT 2 RELATION Structure: 2.0 Learning Objectives 2.1 Introduction 2.2 Cartesian Product 2.3 Domain and Range of a Relation 2.4 Types of Relations 2.5 Equivalence Relation 2.6 Summary 2.7 Key Words/Abbreviations 2.8 Learning Activity 2.9 Unit End Questions (MCQ and Descriptive) 2.10 References 2.0 Learning Objectives After studying this unit, you will be able to:  Types of relations, i.e., inverse relation, identity relation, etc.  A relation R on a set A is called an equivalence relation if and only if: (i) R is reflexive (ii) R is symmetric (iii) R is transitive. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 17 2.1 Introduction The relations such as less than, perpendicular to, not equal to, subset of, etc. are often used in mathematics and computer science problems concerning discrete objects. The relationships help establishing a relation between pair of objects taken in particular order. A relation between two sets can be defined by listing their elements as an ordered pair. An ordered pair consists of two elements, say a and b in which one of them is designated as the first element and the other as the second element. An ordered pair is usually denoted by (a, b). Two ordered pairs (a, b) and (c, d) are said to be equal if and only if a = c and b = d. In other words, (a, b) = (c, d)  a = c and b = d Thus, the ordered pair (2, 3) and (2, 3) are equal while ordered pair (2, 3) and (3, 2) are different. The reader must note the difference between the set {2, 3} and ordered pair (2, 3). We have {2, 3} = {3, 2} but (2, 3) ≠ (3, 2) 2.2 Cartesian Product If A and B are any two non-empty finite sets, then the set of all distinct ordered pairs whose first member (or coordinate) belongs to A and the second member (or coordinate) belongs to B is called the Cartesian product of A and B (in that order) and is denoted by A × B (read as A cross B). Symbolically, A × B = {(a,b) :a  A, b  B} Illustration: Let R be the set of real numbers. Then R × R (=R2) denotes the Cartesian plane or Euclidean 2-space, since the elements of this product set, viz., {(x, y) : x and y are real numbers.} are the Cartesian coordinate of a point in a plane. Example 1: If A = {1,2,3} and B = {2,3} , prove that A × B ≠ B × A. Also find, n(A × B). CU IDOL SELF LEARNING MATERIAL (SLM)

18 Mathematics Solution: The product, A × B = {(1,2), (1,3),(2,2),(2,3),(3,2),(3,3)} B × A = {(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} Since, elements of A × B and B × A are not the same, therefore A × B ≠ B × A. Now, n(A × B) = n(A) × n(B) = 3 × 2 = 6 2.3 Domain and Range of a Relation If R is the relation from set A to another set B, then the set of elements in A that are related to some element or elements in B is called the domain of R and set B is called codomain of R. In other words, domain of R, a subset of A, is the set of all first elements in the ordered pairs which belong to R. Symbolically, D = {x : (x, y)  R, x  A for some y  B} The range, say E of the relation R, is the set of elements in B that appear as second element in the ordered pair which belong to R, i.e., all elements in B that are related to some element in A. Symbolically, E = {y : (x,y)  R for some x  A}. Examples: 1. Let A = {1,2,3,4} and B = {a,b,c}. Then every subset of A × B is a relation from A to B. So if R = {(2,a), (4,a), (4,c)}, then the domain of R is the set {2,4} and the range of R is the set {a,c}. 2. Let I be the set of all integers. Then ‘x is less than y for all x, y  I' is a relation R in I and is described as R = {(x, y) : x  I, y  I, x < y} CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 19 2.4 Types of Relations Some special types of relations on a set are as follows: 1. Inverse Relation Let R be any relation from a set A to a set B. The inverse relation, denoted by R–1, is a relation from B to A and is denoted by R1  (y, x) : x  A, y B, x, y R. In other words, the inverse relation is obtained by reversing each of the ordered pairs belong to R. Thus, (x, y)  R  (y, x)  R1 or xRy  yR1x. Evidently, range of R is domain of R–1 and vice versa. If A = B, then R and R–1 are both relations on A. Example: 1. Let R be the set of relations on the set R of real numbers defined by x is less than y, where x, y R. Then R–1 is the relation defined by ‘x is greater than y, where x, yR'. 2. Let A = {2, 4, 6} and B = {a, b}. Then R = {(2, a), (2, b), (4, a)} is a relation from A to B. The inverse relation of R is R–1 = {(a, 2), (a, 4), (b, 2)}. Note that Dom (R) = Ran (R–1) = {2, 4} and Ran (R) = Don (R–1) = {a, b}. Observe that if R is any relation, then (R–1) = R. If R is a relation on any set A, then R–1 is also a relation on A. 2. Identity Relation Let A be any set. Then the relation R in a set A denoted by IA is said to be identity relation if IA  (x, y) : x  A, y A, x  y. In other words, the identity relation IA in a set A is the set of all ordered pairs (x, y) of A × B for which x = y. The domain and range of IA are both A. CU IDOL SELF LEARNING MATERIAL (SLM)

20 Mathematics For example: 1. Let A = {a, b, c, d}, then the identity relation A is IA = {(a, a), (b, b), (c, c), (d, d)} 3. Universal Relation A relation in a set A is said to be universal relation provided R = A×A, In other words, universal-relation is the relation if each element of set A is related to every element of A. For example, if A = {2, 3}, then R = A×A = {(2, 2), (2, 3), (3, 2), (3, 3)} is a universal relation. 4. Void Relation A relation R in a set is said to be a void relation provided R is a null set, i.e.,R = . For example, if A = {2, 3, 5} and the relation R is defined as: aRb if and only if a divides b, then R =  and hence A × A is a void relation. 5. Reflexive Relation A relation R on a set A is reflexive if and only if each element in A is related to itself, i.e., aRa, for all a  A. In other words, for all a  A, (a, a)  R. The necessary and sufficient conditions that a relation R on A be reflexive is that IA  R. A relation R on a set A is not reflexive, if there is at least one element, say bA such that bR. Example: Let A = {1, 2, 3, 4}. Then the relation R1 = {(1, 1), (2, 4), (3, 3), (4, 1), (4, 4)} on A is not reflexive because 2  A but (2, 2) does not belong to R1, whereas relation R2 = {(1, 1), (2, 2), (3, 3), (4, 4)} is a reflexive relation on A. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 21 6. Symmetric Relation A relation R on a set A is said to be symmetric if and only if for all, a, bR aRb  bRa, i.e., (a, b)  R  (b, a)  R. The necessary and sufficient condition for relation R to be symmetric is R = R–1. Example: Let A = {1, 2, 3} and R = {(1, 2), (2, 3), (2, 1), (3, 3)}. Then R–1 = {(2, 1), (3, 2), (1, 2), (3, 3)}. Since (2, 3)  R but (2, 3)  R–1, therefore R ≠ R–1. Hence, R is not symmetric. 7. Anti-symmetric Relation Let R be a relation on a set A. Then R is anti-symmetric if and only if aRb and bRa  a = b, for a, b  R, i.e., (a, b)  R, (b, a)  R  a = b. Thus, it is evident that a relation R on a set A is anti-symmetric if R  R–1  IA, where IA represents the identity relation on A. Example: The relation in N defined by x divides y is anti-symmetric because x divides y and y divides x implies x = y. 8. Transitive Relations A relation R on a set A is transitive if and only if for all a, b, c  R, aRb and bRc  aRc, i.e., (a, b), (b, c)  R  (a, c)  R. Example: 1. The relation in N defined by x is less than y is transitive relation because x < y and y < z  x < z. 2. Let N be the set of all natural numbers. Let a relation R on N defined by x is a divisor of y where x, y  N. Then, R is transitive, since x divides y and y divides z  x divides z. CU IDOL SELF LEARNING MATERIAL (SLM)

22 Mathematics 2.5 Equivalence Relation A relation R on a set A is called an equivalence relation (denoted by ~) if and only if following three conditions are true: 1. R is reflexive 2. R is symmetric 3. R is transitive Example 1: Give an example of an relation that is reflexive but neither symmetric nor transitive. Solution: Let A = {1, 2, 3} and R is defined as R = {(1, 1), (1, 2), (2, 3), (2, 2), (3, 3)}. Then R is reflexive since (a, a)  R for all a  A. It is not symmetric since (1, 2)  R but (2, 1)  R. It is also not transitive since (1, 2)  R and (2, 3)  R but (1, 3)  R. Example 2: A relation R on the set of integers, I is defined as: aRb if and only if (a – b) is divisible by m (a positive integer). Show that R is an equivalence relation. Solution: (a) R is reflexive for each a  I. Also, (a – b) id divisible by m and hence b – a = –(a – b) is also divisible by m. Thus, aRb  bRa. Therefore, R is symmetric. (b) For a, b, c  I, we have aRb and bRc  a – b and b – c are both divisible by m. This implies that (a – b) + (b – c) is divisible by m or (a – c) is divisible by m or aRc. Therefore, R is transitive. Since R is reflexive, symmetric and transitive, therefore R is equivalence relation. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 23 Example 3: Let N be set of all natural numbers. The relation R on the set N × N of ordered pairs of natural numbers is defined as: (a, b) R (c, d) if and only if ad = bc. Prove that R is an equivalence relation. Solution: (a) R is reflexive, since for each (a, b)  N × N, we have ab = ba, i.e., (a, b) R (b, a). (b) Let (a, b) R (c, d). Then ad = bc  cb = da. Thus, (c, d) R (a, b) and R is symmetric. (c) Let (a, b) R (c, d) and (c, d) R (e, f). Then ad = bc and cf = de. Thus, (ad)(cf) = (bc)(de). Dividing both sides by dc, we get af = be, i.e. (a, b) R (e, f). Therefore, R is transitive. Since R is reflexive, symmetric and transitive, therefore R is equivalence relation. Example 4: The relation R on the set S of all real numbers is defined as: aRb if and only if 1 + ab > 0. Show that this relation is reflexive and symmetric but not transitive. Solution: (a) Let ‘a' be any real number. Then 1 + aa = 1 + a2 > 0, since a2 ≥ 0. Therefore, aRa for all a  S. Thus, R is reflexive. (b) Let a, b  S. Then aRb  1 + ab> 0  1 + ba > 0 [' ab = ba for real numbers]  bRa Thus, R is symmetric. (c) Consider three real numbers as: 1, – 1/2 and – 4. Now, we have 1 + 1(– 1/2)= (1/2)> 0 Therefore, 1R (– 1/2). CU IDOL SELF LEARNING MATERIAL (SLM)

24 Mathematics Further, 1 + (– 1/2) (– 4) = 3 > 0. Therefore (– 1/2) R (– 4). But 1 + 1(–4) = – 3 (<0). Therefore, 1 is not related to – 4. Thus, 1R (– 1/2), (– 1/2)R (–4) is not implying that 1R (– 4). Hence, R is not transitive. 2.6 Summary A relation between two sets can be defined by listing their elements as an ordered pair. An ordered pair consists of two elements, say a and b in which one of them is designated as the first element and the other as the second element. An ordered pair is usually denoted by (a, b). Some special types of relations on a set are as follows: 1. Inverse Relation 2. Identity Relation 3. Universal Relation 4. Void Relation 5. Reflexive Relation 6. Symmetric Relation 7. Anti-symmetric Relation 8. Transitive Relation A relation R on a set A is called an equivalence relation (denoted by ~) if and only if following three conditions are true: 1. R is reflexive 2. R is symmetric 3. R is transitive 2.7 Key Words/Abbreviations  N is set of natural numbers.  R is set of real numbers. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 25  Cartesian Product – A × B .  R–1 means inverse of set R  IA – Identity relation in a set A 2.8 Learning Activity 1. The number of equivalence of set {1, 2, 3} is 2. Inverse relation is denoted by . 2.9 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Find the number of relations from the set A = {a, b, c} to the set B = {1, 3}. 2. Show that relation, R = {(a, b): a – b = even integers and a, b  I} in the set I of integers is an equivalence relation. 3. Prove that if R is an equivalence relation on a set A, then R–1 is also an equivalence relation on A. 4. If R1 and R2 are equivalence relations in a set A, show that R1  R2 is also an equivalence relation on A. 5. If R is equivalence relation, then prove that R–1 is also an equivalence relation in the set A. 6. Let A = {1, 2, 3, ..., 11, 12} and let R be the relation on A × A defined by (a, b) R (c, d) if and only if a + d = b + c. (a) Prove that R is an equivalence relation. CU IDOL SELF LEARNING MATERIAL (SLM)

26 Mathematics B. Multiple Choice/Objective Type Questions . 1. Let R be a symmetric and transitive relation on set A, then (a) R is reflexive and hence an equivalence relation (b) R is reflexive and hence a partial order (c) R is not reflexive and hence not an equivalence relation (d) None of the above 2. Suppose A is a finite set with n elements. Then number of elements in the largest equivalence relation of A is . (a) 1 (b) n (c) n + 1 (d) n2 3. Binary relation S =  (Empty set) on set A = {1, 2, 3} is . (a) Symmetric and reflexive (b) Transitive and symmetric (c) (a) and (b) (d) None 4. The subset relation on a set of sets is . (a) A partial ordering (b) An equivalence relation (c) (a) and (b) (d) None 5. Inverse relation is denoted by . (a) R–1 (b) R (c) U (d) None Answers: 1. (d), 2. (d), 3. (b), 4. (a), 5. (a) 2.10 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 27 UNIT 3 FUNCTIONS Structure: 3.0 Learning Objectives 3.1 Introduction 3.2 Definition and Notation of a Function 3.3 Range and Domain of a Function 3.4 Types of Functions 3.5 Composition of Functions 3.6 Three Function Composition 3.7 Summary 3.8 Key Words/Abbreviations 3.9 Learning Activity 3.10 Unit End Questions (MCQ and Descriptive) 3.11 References 3.0 Learning Objectives After studying this unit, you will be able to learn:  Various types of functions  Range and Domain of function  Three function composition CU IDOL SELF LEARNING MATERIAL (SLM)

28 Mathematics 3.1 Introduction In this chapter, we will discuss special kind of relation called a function. The knowledge of function is very useful both in mathematics and computer science. Functions can be also used for counting and knowing the cardinality of sets. The terms such as mapping, transformations, etc. are also used for functions to depict a relation between two discrete objects. 3.2 Definition and Notation of a Function Let A and B be any two non-empty sets, not necessarily distinct. If there exists a rule or correspondence, denoted by f, which relates (or associates) each element xA, to a unique (one and only one) element y B, then such a rule is called a function from A to B. Symbolically, the function is expressed as: f: A → B such that y = f(x), for x A and y B However, a relation R from A to B may not relate an element of A to an element of B or more than one element of B may be related to an element of A. In other words, the relation f can be described as the set of elements written as: {(x, f(x)): xA, f(x) B} 3.3 Range and Domain of a Function B f(A) A f x y=f(x) Fig. 3.1: Functional relationship between sets A and B The set A is called domain of the function f and B is called the co-domain of f. The element x  A is called argument of function f and f(x) B is called the value of function for x and is also CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 29 called the image or f-image of x under f. Fig. 3.1 represents the functional relationship between two sets, set A and set B. Fig. 3.1 suggests that x may be considered as an input that is transformed by f into corresponding output f(x) = y. The range of f is the set of those elements in B which appear as the second component in the ordered pair of f, i.e., set of elements of B which appear as the image of at least one element in A. There can be more than one element in A which have the same image in B. The range of f is denoted by: f(A) = {f(x): x  A} = {y: y  B, y = f(x) for same x  A}. The sets A and B are called the domain and co-domain of f respectively. Obviously, f(A) B. For example: 1. Let A = {1, 2, 3, 4} and B = {1, 2, 3}. Then f = {(1, 2), (2, 3), (3, 3), (4, 2)} is a function from A to B. Since to each element in A we have assigned a unique element in B, therefore, f(1) = 2, f(2) = 3, f(3) = 3 and f(4) = 2. Also, range of function is f(A) = {2, 3}. 2. Let A = {1, 2, 3} and B = {x, y, z}. Consider the relations R1 = {1, x), (2, x)} and R2 = {(1, x), (1, y), (2, z), (3, y)}. The relation R2 is not a function because R2(1) = {x, y}. But relation R1 is function with domain = {1, 2} and range = {x}. 3. Let I be set of integers and A = {0, 1}. The relation between I and A defined as f: I → A, such that f (x)  0 if x isodd  if x is even 1 is a function because each set f(x) consists of a single element. 3.4 Types of Functions 1. Equal Functions: Two functions f: A → B and g: A → B are said to be equal if and only if f(x) = g(x) for every x  A and are written as f = g. CU IDOL SELF LEARNING MATERIAL (SLM)

30 Mathematics 2. Constant Functions: A function f: A → B is called a constant function, if some element yB, is assigned to every element of A, i.e., f(x) = y for every x A. In other words, f: A → B is a constant function if range of f consists of only one element. Examples: (a) f(x) = 4 (b) f(x) = 94.556 Onto and Into Functions The function f: A → B is said to be: (a) Onto (or Subjective) Functions: If every element of B is f-image of at least one element in A. In this case, the range of f is equal to B, i.e., for all y  B, y = f(x) for some x  A or f(A) = B. (b) Into Functions: If there is at least one element in B which is not the f-image of any element in A. But every element of A has f-image in B. In this case, the range of f is proper subset of B, i.e., f(A)  B and f(A) ≠ B. Many-to-one and One-to-one Functions (a) Many-to-one Functions: If two or more different elements in A have same f- image in B, i.e., f(x1) = f(x2) even when x1 ≠ x2, for all x1, x2  A. (b) One-to-one Functions (Injective Functions): If different elements in A have different f-image in B, i.e., x1 ≠ x2 implies f(x1) ≠ f(x2) for all x1, x2  A or equivalently f(x1) = f(x2)  x1 = x2 for all x1, x2  A. If f is one-to-one with A and B finite, then we must have |A| ≤ |B |. 3. One-to-one Onto (Bijective) Functions: AB ax by cz CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 31 The function f: A → B is said to be one-to-one onto function if, to every element in A, there corresponds one and only one element of B and every element of B has one and only image in A. One-to-one onto functions are also called bijective. 4. One-to-one and Into Function: AB ax by cz w The function f: A → B is said to be one-to-one into if, to each element in A, there corresponds one element of B, but there are some elements of B which do not correspond to any element in A. 5. Many-to-one Into Function: AB ax by cz The function f: A → B is said to be many-to-one into function if two or more elements of set A correspond to same element in set B and there are some elements in B which do not correspond to any of the element in A. 6. Many-to-one Onto Function: AB ax by cz d CU IDOL SELF LEARNING MATERIAL (SLM)

32 Mathematics The function f: A → B is said to be many-to-one onto function if each element of B is joined at least one element in A and two or more elements in A are joined to elements in B. Example 1: If R is set of real numbers, then show that the function, f: → R defined by f(x) = 5x3 – 1 is one-one onto function. Solution: To show f to be one-to-one function, let x1, x2  R be two different elements. Then x1  x2  5x 3 1  5x 3 1 1 2  f (x1)  f (x 2 ) This shows that different elements in R have different f-images in R. Hence, f is one-to- one. To show that f is one-to-one, let y = 5x3 – 1 be any arbitrary element in R. Then we may 1 write x  {(y  1) / 5} 3 , which is real number for all values of y  R. Now, f  1) / 5} 1   5  1) / 5} 13 31 {(y 3  {(y      5{(y 1) / 5} 1  (y 1) 1  y This shows, for every element y  R (range set), there exists a pre-image in the domain set R of f. Thus, f is an onto function. Hence, f is one-to-one onto function. Example 2: In N is set of natural numbers, then show that function, f: N → N defined by f(x) = x2 is one-to-one onto function. Solution: To show f is one-to-one function, let x1, x2  N be two different elements. Then x1  x2  x12  x 2 2  f (x1)  f (x 2 ) Thus, f is one-to-one function. CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 33 Since f-image of every element x  N (domain set) is its square, i.e., x2, therefore, we have f(2) = 4, f(3) = 9, f(4) = 16, f(5) = 25 and so on. However, there are seven natural numbers in the range set N such as 1, 3, 5, 6, 7, etc. which are not f-image of any natural number in the domain set of f. Thus, f is an into function and hence f is one-to-one into function. Example 3: If R is set of real numbers, then show that function f: R → R defined by f(x) = – sin x, is neither one-to-one nor onto. Solution: Let π/6 and 5π/6 be two different elements in domain set R of function f. Now, f(π/6)= – sin (π/6)= –1/2 and f(5π/6)= – sin 5π/6)= –1/2. This implies f(x2) = f(x1) even when x1 ≠ x2. Thus, f is not a one-to-one function. Since value of f(x) = –sin x oscillates between – 1 and 1, i.e., – 1 ≤ –sin x ≤ 1, therefore range set of f is {–1, 1}, which is subset of R. Hence, f is not onto. 7. Inverse Function: An inverse function or an anti-function is defined as a function, which can reverse into another function. In simple words, if any function f takes x to y then, the inverse of f, i.e., f–1 will take y to x. Example: Find the inverse of the function f(x) = Ln(x – 2) Solution: First, replace f(x) with y So, y = Ln(x – 2) Replace the equation in exponential way , x – 2 = ey Now, solving for x, x = 2 + ey Now, replace x with y and thus, f–1(x) = y = 2 + ey CU IDOL SELF LEARNING MATERIAL (SLM)

34 Mathematics 3.5 Composition of Functions Af Bg C x x z = g(y) y = f(x) = g(f(x)) gof Let f: A → B and g: B → C be two functions. Then the composition of function f and g is denoted by (gof) is a function from A to C and is written as (gof): A → C such that (gof) (x) = g(f(x)) for each x  A. Obviously, domain of (gof) is set A and range of (gof) is set of C. Composite Function is possible if the range of first function is a subset of the domain of second function. If this is not the case, composite function cannot be formed. Example: Show that composition of function obeys associative law. OR If A, B, C and D are four sets and f, g and h are three functions defined as f: A → B; g: B → C and h: C → A, then prove that (hog)of = ho(gof). Solution: Let x be an arbitrary element of set A. Then [(hog)of](x) = (hog)[f(x)] = (hog)(y) because y = f(x), for x  A and y  B = h[g(y)] = h(z) [Since z = g(y), for all y  B and z  C] = xA CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 35 Again, let [ho(gof)] (x) = h[(gof)(x)] = h[g{f(x)}] = h[g(y)] = h(z) =xA Hence, (hog)of = ho(gof) 3.6 Three Function Composition Let f: X → Y, g: Y → Z and h: Z → P be the given functions. Let x  X, y  Y and z  Z such that f(x) = y and g(y) = z, then we have [(hog)of](x) = (hog)[f(x)] = (hog)(y) ...(1) = h[g(y)] = h(z) ...(2)  [(hog)of](x) = h(z) On the other hand, [ho(gof)](x) = h[(gof)x] = h[g(f(x))] = h(z) From (1) and (2), we have [(hog)of](x) = [ho(gof)]x) x  X Example 1: Let f(x) = x + 3, g(x) = x – 3 and h(x) = 2x where x  R. Compute gof and hogof. Solution: gof = (gof)(x) = g(f(x)) = g(x + 3) = x + 3 – 3 = x hogof =(hogof)(x) = h[(gog)(x)] = h(x) = 2x Example 2: If f: A → B is one-to-one and onto function, then (a) f–1of = IA CU IDOL SELF LEARNING MATERIAL (SLM)

36 Mathematics (b) fof–1 = IB where IA and IB are identity functions of the set A and B respectively. Solution: (a) For every x  A, IA(x) = x = f–1[f(x)] = (f–1f)(x) Thus, f–1of is function from set A to itself. (b) Similarly, for every y  B, IB(y) = y = f [f–1(y)] = (fof–1)(y) Example 3: If f: A  B and g: B  C are invertible functions, then gof: A  C is also invertible and (gof)–1 = f–1og–1. Solution: Since f and g are one-to-one function, therefore we have f(x1)= f(x2)  x1 = x2 for all x1, x2  R g(y1) = g(y2)  y1 = y2 for all y1, y2  R (gof)(x1) = (gof)(x2)  g(f(x1) = g(f(x2))  f(x1)= f(x2)  x1 = x2 Also, as f and g are both onto functions, so for each z  C, there exists y  B such that g(y) = z and f(x) = y for each x  A. Thus, z = g(y) = g(f(x)) = (gof)(x). Hence, each element z  C has pre-image under gof and therefore gof is an onto function. Since it has been proved that gof is one-to-one onto function, therefore gof exists. This implies that if gof: A → C, then (gof)–1:C → A or g–1of–1 : C → A. CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 37 Now, (gof)–1(z) = x  (gof)(x) = z  g(f(x)) = z or g(y) = z  y = g–1(z)  f–1(y) = f–1(g–1(z)) = (f–1og–1)(z)  x = (f–1og–1)(z) Hence, (gof)–1(z) = (f–1og–1)(z) 3.7 Summary The knowledge of function is very useful both in mathematics and computer science. Functions can be also used for counting and knowing the cardinality of sets. There are some types of functions: 1. Equal Functions 2. Constant Functions – Onto & Into functions & Many to one and One to one functions 3. Bijective Functions 4. Inverse functions. The composition of function is possible if the range of the first function is a subset of the domain of second function. If this is not the case, composite function cannot be formed. And the domain and range of function is also given in the chapter. 3.8 Key Words/Abbreviations  Let A, B and C be sets and let f: A → B and g: B → C. Then the composition gof of f and g is defined by (gof)(x) = g(f(x))  x  A.  f–1(x) denotes inverse of function f. CU IDOL SELF LEARNING MATERIAL (SLM)

38 Mathematics 3.9 Learning Activity 1. Let f(x) = x + 2, g(x) = x – 2 and h(x) = 3x for x  R where R is set of real numbers. Find: (i) gof and (ii) hog. 2. Prove that composition of two injective function is injective. 3.10 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Discuss the nature of the function f defined by: (a) f: N → N such that f(n) = n – (–1)n, n  N. (b) f: R → R such that f(x) = x3 – x. (c) f: I → I such that f(x) = –x + 4. 2. Decide whether or not the following are functions from A to B where A = {1, 2, 3, 4, 5} and B = {a, b, c, d, e}. If they are functions, give range of each; if not, they why? (a) f = {(1, a), (2, b), (3, b), (5, e)} (b) g = {(1, e), (5, d), (3, a), (2, b), (1, d), (4, a)} (c) h = {(5, a), (1, e), (4, b), (3, c), (2, d)} 3. Let N be set of all natural numbers and A be set of all even natural numbers. Consider f: N → A such that f(x) = 2x, for all x  N. Show that f is one-to-one onto. Also define inverse function f–1. 4. Find the ranges of the following functions on the set of integers: (a) f = {(x, 4x + 1): x  I} (b) g = Largest integer that is greater than or equal to x . CU IDOL SELF LEARNING MATERIAL (SLM)

Functions 39 5. Let f: A → B such that f(x) = x – 1 and g: B → C such that g(y) = y2. Find: (a) (fog)(2) (b) (gof)(2) (c) (fog)(x) (d) (gof)(x) (e) (fof)(y) (f) (gof)(y) 6. Which of the following functions are one-to-one onto and one-to-one into on the set of real number? (a) f(x) = –2x (b) g(x) = x2 – 1 (c) g(x) = x, when x < 0 and x2 when x ≥ 0 7. Let f, g and h be function N → N where N is the set of natural numbers, so that f(x) = x + 1, g(x) = 2x and h(x) = 1. Determine: (a) fof, (b) fog, (c) gof, (d) goh and (e) hog. 8. Let f, g and h be function from I → I, where I is a set of integers, so that f(x) = x + 5, g(x) = x – 2 and f(x)= x3. Define: (a) fog and (b) foh. Hints and Answers 4. (a) {4x + 1 : x  1} (b) N = {0, 1, 2, 3, ...} 5. (a) 3 (b) 1 (c) x2 – 1 (d) (x– 1)2 (e) y – 2 (f) y4 6. (a) One-to-one into (b) Neither (c) One-to-one onto 7. (a) (fof)(x) = f[f(x)] = f(x + 1) = (x + 1) + 1 = x + 2 (b) (fog)(x) = f[g(x)] = f(2x) = 2(x + 1)1 = 2x + 2 (c) (gof)(x) = g[f(x)] = g(x + 1) = 2(x + 1) = 2x + 2 (d) (goh)(x) = g[h(x)] = 1 when x is odd and 0 when x is even (e) (hog)(x) = h[g(x)] = h(2x) = 1 CU IDOL SELF LEARNING MATERIAL (SLM)

40 Mathematics B. Multiple Choice/Objective Type Questions . 1. Let f(x) = x2 + x and g(x) = x + 1, then f(x) + g(x) = (a) x2 + 1 (b) (x + 1)2 (c) x + 1 (d) None 2. Each of the function 2n and nlog x has growth rate than any polynomial. (a) Greater than (b) Less than (c) Equal to (d) None 3. The number of function from an m-element set to an n-element set is . (a) m + n (b) mn (c) nm (d) m*n 4. The domain D of f (x)  1 real valued function is . x2 (a) D – R{2} (b) D = {–5, 5} (c) D = {1} (d) None 5. The solution of (n  2)! is . n! (b) 2n! (a) n (d) None (c) (n – 1) Answers: 1. (b), 2. (b), 3. (b), 4. (a), 5. (a) 3.11 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 1 41 UNIT 4 MODERN ALGEBRA 1 Structure: 4.0 Learning Objectives 4.1 Introduction 4.2 Propositions 4.3 Compound Proposition 4.4 Basic Logical Operators 4.4.1 Conjunction 4.4.2 Disjunction 4.4.3 Negation 4.5 Summary 4.6 Key Words/Abbreviations 4.7 Learning Activity 4.8 Unit End Questions (MCQ and Descriptive) 4.9 References 4.0 Learning Objectives After studying this unit, you will be able to:  Explain the basic logical operators like conjunction, disjunction, and negation and compound propositions. CU IDOL SELF LEARNING MATERIAL (SLM)

42 Mathematics 4.1 Introduction Logic is the science of reasoning. Hypothesis logically implies correct conclusion. In other words, logic is employed to establish the validity of arguments. Logic has variety of applications in each course of day-to-day life and many other engineering applications like designing of electronic circuits, computer and other robotic programming, etc. 4.2 Propositions Definition: A proposition is a declarative statement which is either true or false but not both. Example: 1. 64  8 2. 7 × 5 = 30 3. 100 – 25 = 50 4. 2 + 4 = 7 The first statement has truth value 1 and the remaining statements have truth value 0. Example: Observe statements 1. Study well 2. x2 + y2 = z2 Statement 1 is not declarative, hence it is not proposition. Statement 2 is either true or false, since they depend on the values of variables. 4.3 Compound Proposition Many propositions are composite, i.e, composed of subproposition and various connectives discussed subsequently. Such composite propositions are called compound proposition. A proposition is said to be primitive if it cannot be broken into simple propositions, i.e, if it is not composite. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 1 43 Example: If it is sunny outside then I walk to work; otherwise I drive, and if it is raining then I carry my umbrella. p = “It is sunny outside” q = “I walk to work” r = “I drive” s = “It is raining” t = “I carry my umbrella” p implies q and ((not p) implies (r and (s implies t))). (p ~ q)  (~ p ~ (r  ( s ~ t))) 4.4 Basic Logical Operators 4.4.1 Conjunction When two or more statements are joined by connective, denoted by the symbol,  , the compound statement formed so is called as conjunction. Let p and q be two statements. Then p  q forms a statement which is true if and only if both p and q are true and is false if p is false or q is false or both are false. The statement p  q is read as: p and q, and is called the conjunction of p and q. p q pq TTT TFF FTF FFF With two statements, there are 22 = 4 possible combinations. 4.4.2 Disjunction When two or more statements are joined by the connective or denoted by symbol,  , the compound statement formed so is called disjunction of two statements p and q, and is written as p or q or p  q. It is false only when both the statements are false, otherwise, it is true for all cases. CU IDOL SELF LEARNING MATERIAL (SLM)

44 Mathematics p q pq TTT FTT TFT FFF Conditional Proposition Definitions: Given propositions p and q, then p  q represents the conditional proposition “If p, then q.” or “p implies q.” The proposition p is called the antecedent and the proposition q is called the consequent. The conditional has the truth table. p q pq TTT TFF FTT FFT Example: A person makes the promise: “If I find a $20 bill, then I will take you to a movie.” Now we consider when the person has broken the promise. (1) The person finds a $20 bill and takes you to a movie. p  q is true, since the person did not break the promise. Note p and q are both true. (2) The person finds a $20 bill and does not take you to a movie. p  q is false, since the person broke the promise. Note p is true, but q is false. (3) The person did not find a $20 bill, but took you to a movie anyway. p  q is true, since the person did not break the promise. Note p is false, but q is true. (4) The person did not find a $20 bill and did not take you to a movie. p  q is true, since the person did not break the promise. Note p and q are both false. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 1 45 Bi-conditional Proposition Definition: p if and only if q is a biconditional statement and is denoted by p  q and often written as p iff q. A biconditional is true only when p and q have the same truth value. pq pq TT T TF F FT F FF T Note that p  q is equivalent to (p  q)  (q  p). Biconditional statements occur frequently in mathematics. Definitions are usually biconditionals. Example: (a) A quadrilateral is a rectangle if and only if it has four right angles. 1. I will eat lunch if and only if my mood improves. 2. My mood will improve if and only if I eat lunch. And now the other leftover:  If I ask more questions in class, then I will understand the mathematics better. (True)  If I understand the mathematics better, then I will ask more questions in class. (False) You cannot write a bi-conditional statement for this leftover; the truth values are not the same. 4.4.3 Negation If p is statement, then negation (or not) of p, denoted by ~ p is defined to form a statement that is true when p is false and false when p is true. The negation of statement p is read as ‘not p'. CU IDOL SELF LEARNING MATERIAL (SLM)