21ODMCT614-Discrete Mathematical Structure

MASTER OF COMPUTER APPLICATIONS DISCRETE MATHEMATICAL STRUCTURES MCA614 Prof. Kiran Gurbani

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) Coordinator - Prof. Pragya Sharma Coordinator - Dr. Rupali Arora Master of Computer Applications (MCA) Bachelor of Computer Applications (BCA) Coordinator - Dr. Deepti Rani Sindhu Coordinator - Dr. Raju Kumar Master of Commerce (M.Com.) Bachelor of Commerce (B.Com.) Coordinator - Dr. Shashi Singhal Coordinator - Dr. Minakshi Garg Master of Arts (Psychology) Bachelor of Science (Travel & Tourism Coordinator - Dr. Samerjeet Kaur Management) Coordinator - Dr. Shikha Sharma Master of Arts (English) Bachelor of Arts (General) Coordinator - Dr. Ashita Chadha Coordinator - Ms. Neeraj Gohlan Master of Arts (Mass Communication and Bachelor of Arts (Mass Communication and Journalism) Journalism) Coordinator - Dr. Chanchal Sachdeva Suri Coordinator - 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)

Discrete Mathematical Structures Course Code: MCA614 Credits: 3 Course Objectives:  To develop analytical ability for describing, analyzing and solving mathematical problems they may encounter in their profession in a logical and systematic fashion.  To learn simplification and evaluation of basic logic statements including compound statements, implications, inverses, converses, and contra positives using truth tables and the properties of logic.  To perform basic matrix operations including sums, products, and transpose and perform 0-1 matrix operations. Syllabus Unit 1 - Set Theory: Definition of Sets, Venn Diagrams, Complements, Cartesian Products, Power Sets, Counting Principle. Unit 2 - Set Theory: Cardinality and Count Ability (Countable and Uncountable Sets), Proofs of Some General Identities Onsets, Pigeonhole Principle. Unit 3 - Relation: Definition, Types of Relation, Composition of Relations, Domain and Range of a Relation, Pictorial Representation of Relation, Properties of Relation, Partial Ordering Relations. Unit 4 - Functions: Definition and Types of Function, Composition of Functions, Recursively Defined Functions. Unit 5 - Propositional Logic: Proposition Logic, Basic Logic, Logical Connectives, Truth Tables. Unit 6 - Combinatory: Mathematical Induction, Recursive Mathematical Definitions, basiCs of Counting, Permutations, Combinations, Inclusion-exclusion, Recurrence Relations (nth Order Recurrence Relation with Constant Coefficients. Unit 7 - Combinatory: Homogeneous Recurrence Relations, Inhomogeneous Recurrence Relation), Generating Function (Closed form Expression, Properties of G.F., Solution of Recurrence Relation Using G.F, Solution of Combinatorial Problem Using G. CU IDOL SELF LEARNING MATERIAL (SLM)

Unit 8 - Graphs: Graph Terminology, Types of Graph Connected Graphs, Components of Graph, Euler graph, Hamiltonian Path and Circuits, Graph Colorings, Chromatic Number. Unit 9 - Tree: Definition, Types of Tree (Rooted, Binary), Properties of Trees, Binary Search Tree, Tree Traversing (Preorder, in Order, Post Order). Unit 10 - Boolean Algebra: Application of Boolean Algebra to Switching Theory. Languages Recognition and Generation, Phase Structure Grammars and Languages (Finite). Unit 11 - State Machine: Recognition in Regular Languages. Text Books: 1. Makinson, D. (2011). Sets, Logic and Maths for Computing. India: Springer Indian Reprint. 2. Grimaldi, R.P., Ramana, B.V. (2006). Discrete and Combinatorial Mathematics. 5th Edition. Delhi: Pearson Education. 3. Sengadir, T. (2009), Discrete Mathematics and Combinatorics, New Delhi: Pearson Education. 4. Venkataraman, M.K. (1989). Engineering Mathematics. 2nd Edition, Volume-II, Punjab: National Publishing Company. Reference Books: 1. Rosen, K.H. (2002). Discrete Mathematics and Its Applications. 4th Edition. New York: Tata McGraw-Hill. 2. Trembley, J.P. Manohar, R. (2007). Discrete Mathematical Structures with Applications to Computer Science, New Delhi: Tata McGraw-Hill. CU IDOL SELF LEARNING MATERIAL (SLM)

CONTENTS 1 - 21 22 - 34 Unit 1: Set Theory 1 35 - 51 Unit 2: Set Theory 2 52 - 66 Unit 3: Relation 67 - 86 Unit 4: Functions 87 - 105 Unit 5: Propositional Logic 106 - 131 Unit 6: Combinatory 1 132 - 154 Unit 7: Combinatory 2 155 - 177 Unit 8: Graphs 178 - 194 Unit 9: Tree 195 - 208 Unit 10: Boolean Algebra Unit 11: State Machine CU IDOL SELF LEARNING MATERIAL (SLM)

CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 1 SET THEORY 1 Structure: 1.0 Learning Objectives 1.1 Introduction 1.2 Set Theory 1.2.1 Set-Roster Notation 1.2.2 Set-Builder Notation 1.3 Definition of Sets 1.4 Venn Diagram 1.5 Complements of Set 1.6 Ordered Pair 1.7 Cartesian Products 1.8 Power Sets 1.9 Counting Principle 1.9.1 Sum Rule 1.9.2 Product Rule 1.9.3 Two-way Counting 1.9.4 Tree Diagram 1.10 Summary 1.11 Key Words/Abbreviations

2 Discrete Mathematical Structures 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:
Define Sets.
Describe the Concepts of Venn Diagrams.
Define Cartesian Products.
Define Power Sets. 1.1 Introduction Set theory, branch of mathematics that deals with the properties of well-defined collections of objects, which may or may not be of a mathematical nature, such as numbers or functions. The theory is less valuable in direct application to ordinary experience than as a basis for precise and adaptable terminology for the definition of complex and sophisticated mathematical concepts. A set is any collection of objects, mathematical or otherwise. For example, we can think of the set of all books published in 2007. The objects in a set are referred to as elements or members of the set. The logical statement “a is a member of the set A” is written a
A. 1.2 Set Theory
A well-defined collection of distinct objects is called a set.
The objects are called elements or members of the set.
Notation: The sets are denoted by capital letters A, B, C, …
The elements of a set are represented by lower case letters a, b, c, … CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 3
If S is a set, the notation x
S means that x is an element of S.
The notation x  S means that x is not an element of S. 1.2.1 Set-Roster Notation A set may be specified using the set-roster notation by writing all of its elements between braces. For example: {1, 2, 3} denotes the set whose elements are 1, 2, 3. A variation of the notation is sometimes used to describe a very large set, as when we write {1, 2, 3, …, 99, 100}to refer to the set of all integers from 1 to 100. A similar notation can also describe an infinite set, as when we write {1, 2, 3, …} to refer to the set of all positive integers. (The symbol … is called an ellipsis and is read “and so forth.”) Example 1: Using the Set-Roster Notation (a) Let A = {1, 2, 3}, B = {3, 1, 2} and C = {1, 1, 2, 3, 3, 3}. What are the elements of A, B and C? How are A, B and C related? (b) Is {0} = 0? (c) How many elements are in the set {1, {1}}? (d) For each non-negative integer n, let Un = {–n, n}. Find U1, U2 and U0. Solution: (a) A, B and C have exactly the same three elements: 1, 2 and 3. Therefore, A, B and C are simply different ways to represent the same set. (b) {0}  0 because {0} is a set with one element, namely 0, whereas 0 is just a symbol that represents the number zero. (c) The set {1, {1}} has two elements: 1 and the set whose only element is 1. (d) U1 = {1, –1}, U2 = {2, –2}, U0 = {0, –0} = {0, 0} = {0} CU IDOL SELF LEARNING MATERIAL (SLM)

4 Discrete Mathematical Structures Example 2 Use the set-roster notation to indicate the elements in each of the following sets. (i) S = {n

│n = (–1)k, for some integer k}. Ans: {1, –1} (ii) T = {m

│m = 1 + (–1)i, for some integer i} Ans: {0, 2} (iii) U = {r

│2 ≤ r ≤ –2} Ans:  (the set has no elements) (iv) V = {s

│s > 2 or s < 3} Ans:
(every integer is in the set) (v) W = {t

│1 < t < –3} Ans: {2}  (vi) X = {u

│u ≤ 4 or u ≥ 1} Ans: {1, 2, 3, 4} 1.2.2 Set-Builder Notation Let S denote a set and let P(x) be a property that elements of S may or may not satisfy. We may define a new set to be the set of all elements x in S such that P(x) is true. We denote this set as follows: {x
S | P(x)} the set of all such that Using the Set-Builder Notation CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 5 Example 3: Given that R denotes the set of all real numbers, Z the set of all integers, and Z+ the set of all positive integers, describe each of the following sets. (a) {x
 │–2 < x < 5} (b) {x

│–2 < x < 5} (c) {x

+│–2 < x < 5} Solution: (a) {x
 │–2 < x < 5} is the open interval of real numbers (strictly) between –2 and 5. It is pictured as follows: –3 –2 –1 0 1 2 3 4 5 6 7 8 (b) {x

│–2 < x < 5} is the set of all integers (strictly) between –2 and 5. It is equal to the set {–1, 0, 1, 2, 3, 4}. (c) Since, all the integers in Z+ are positive, {x

+│–2 < x < 5} = {1, 2, 3, 4}. 1.3 Definition of Sets (i) Set: A well-defined collection of distinct objects is called a Set (ii) Cardinality: The cardinality of a set is a measure of the “number of elements of the set”. Notation: The cardinality of a set A is usually denoted | A| or n(A) CU IDOL SELF LEARNING MATERIAL (SLM)

6 Discrete Mathematical Structures (iii) Set Equality: Given sets A and B, A equals B, written A = B, if, and only if, every element of A is in B and every element of B is in A. Symbolically: A = B  A  B and B  A. (iv) Null Set: A set which contains no element is called a null set or an empty set or a void set. Notation: It is denoted by Greek letter (phi)  or { } (v) Singleton Set: A set which contains only one element is called singleton set. (vi) Finite Set: A set S is said to be finite if it contains exactly m distinct elements, where m denotes some non-negative integer. (vii) Infinite Set: A set is said to be infinite if it is not finite. (viii) Universal Set: A Universal Set is the set of all elements under consideration, denoted by capital. All other sets are subsets of the universal set. 1.4 Venn Diagram This is a diagrammatic form. In this form, a set is represented by a closed figure such as a circle, rectangle etc. An element of a set is represented by point in it. If sets A and B are represented as regions in the plane, relationships between A and B can be represented by pictures, called Venn diagrams. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 7 All possible Relation between two sets: Let A and B be two sets. Case 1: A = B A=B Case 2: A  B, A  B B A Case 3: B  A, A  B A B Case 4: A  B, B  A. A and B have some elements common A B Case 5: A and B have no elements common AB CU IDOL SELF LEARNING MATERIAL (SLM)

8 Discrete Mathematical Structures 1.5 Complements of Set The Complement of A, denoted Ac, is the set of all elements in U that are not in A. Shaded Region Represents Ac. Symbolically: Ac = {x
U | x/
A}. U AB 1.6 Ordered Pair Given elements a and b, the symbol (a, b) denotes the Ordered pair consisting of a and b together with the specification that a is the first element of the pair and b is the second element. Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d. Symbolically: (a, b) = (c, d) means that a = c and b = d Example 4: (a) Is (1, 2) = (2, 1)? (b) Is  3, 150  =  9, 12 ? (c) What is the first element of (1, 1)? Solution: (a) No. By definition of equality of ordered pairs: (1, 2) = (2, 1) if and only if 1 = 2 and 2 = 1. But 1  2 and so the ordered pairs are not equal. (b) Yes. By definition of equality of ordered pairs:  3, 150  =   9, 1  if and only if 3 9 2 and 5  1 . 10 2 CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 9 Because these equations are both true, the ordered pairs are equal. (c) In the ordered pair (1, 1), the first and the second elements are both 1. 1.7 Cartesian Products Given sets A and B, the Cartesian product of A and B, denoted A × B and read as “A cross B,” is the set of all ordered pairs (a, b), where a is in A and b is in B. Symbolically: A × B = {(a, b)│a
A, b
B} Example 5: Let A = {1, 2, 3}and B = {u, v}. (a) Find A × B (b) Find B × A (c) Find B × B (d) How many elements are in A × B, B × A and B × B? (e) Let  denote the set of all real numbers. Describe  × . Solution: (a) A × B = {(1, u), (2, u), (3, u), (1, v), (2, v), (3, v) } (b) B × A = {(u, 1), (u, 2), (u, 3), (v, 1), (v, 2), (v, 3) } (c) B × B = {(u, u), (u, v), (v, u), (v, v) } (d) A × B has six elements. Note that this is the number of elements in A times the number of elements in B. B × A has six elements, the number of elements in B times the number of elements in A. B × B has four elements, the number of elements in B times the number of elements in B. (e)  ×  is the set of all ordered pairs (x, y) where both x and y are real numbers. CU IDOL SELF LEARNING MATERIAL (SLM)

10 Discrete Mathematical Structures If horizontal and vertical axes are drawn on a plane and a unit length is marked off, then each ordered pair in  ×  corresponds to a unique point in the plane, with the first and second elements of the pair indicating, respectively, the horizontal and vertical positions of the point. The term Cartesian plane is often used to refer to a plane with this coordinate system, as illustrated in Fig. 1.1: Fig. 1.1 Example 6: Let S = {2, 4, 6} and T = {1, 3, 5}. Use the set-roster notation to write each of the following sets, and indicate the number of elements that are in each set: (a) S × T Ans: {(2, 1), (2, 3), (2, 5), (4, 1), (4, 3), (4, 5), (6, 1), (6, 3), (6, 5)} (b) T × S Ans: {(1, 2), (3, 2), (5, 2), (1, 4), (3, 4), (6, 4), (1, 6), (3, 6), (5, 6)} (c) S × S Ans: {(2, 2), (2, 4), (2, 6), (4, 2), (4, 4), (4, 6), (6, 2), (6, 2), (6, 6)} (d) T × T Ans: {(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)} CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 11 1.8 Power Sets Power set of a Set A is defined as the set of all subsets of the Set A including the Set itself and the null or empty set. It is denoted by P(A). Basically, this set is the combination of all subsets including null set, of a given set. If the given set has n elements, then its Power Set will contains 2n elements. Example 7: Let A = {0, 3} then find power set of A. Solution: P(A) = {, {0}, {3}, {0, 3}} 1.9 Counting Principle 1.9.1 Sum Rule If a first task can be performed in m ways and second task can be performed in n ways, and the two tasks cannot be performed the performing either task can be done in any one of m + n ways. Example 8: Suppose a college library has 30 textbooks on discrete mathematics and 40 text books on Descriptive statistics in how many ways a student can select a textbook? Solution: A student at this college can select among 30 + 40 = 70 textbooks. Example 9: If there are 15 boys and 13 girls in a class, find the number of ways of selecting one student as a class representative. Solution: Using sum rule, there are 15 + 13 = 28 ways of selecting one student as a class representative. CU IDOL SELF LEARNING MATERIAL (SLM)

12 Discrete Mathematical Structures 1.9.2 Product Rule If a procedure can be broken down into first and second stages and if there are m possible outcomes for the first stage and if for each of these outcomes there are n possible outcomes for the second stage, then the total procedure can be carried out in m × n ways. Example 10: Suppose a license plate contains two letters followed by four digits with the first digit not zero. How many different license plates can be printed? Solution: From six places first two places are filled by two letters, each letter can be printed in 26 different ways, First digit in 9 ways and each of other three digits in 10 ways. i.e., 26 × 26 × 9 × 10 × 10 × 10 = 60,84,000 ways. Example 11: How many bit strings of length eight either start with a 1 bit or end with the two bits 00? Solution: 1 00 1 2222211 First, Seventh and last places can be filled by one way and remaining places can be filled by 25 ways. Using product Rule the total number of ways to form the bit strings in the required format is 1 × 2 × 2 × 2 × 2 × 2 × 1 = 32 ways. Set Interpretation of Counting Principles 1. Sum rule: Suppose A and B are two non-empty disjoint sets then n(A  B) = n(A) + n(B) 2. Product rule: n(A × B) = n(A). n(B) 1.9.3 Two-way Counting The two way counting is the technique to perform the same task using different procedure. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 13 For example, if we select k distinct objects from the collection of n distinct objects then we use the formula nCk. There is an alternative method to do this. Now, we have n – k objects that are not to be selected this can be done in nCn – k ways. If we solve both we will get the same result. n Ck  n! and n Cnk  (n  n! (n  k))!  n! k!(n  k)! k)!(n  (n  k)!k! For example, 7C2 = 7C5 1.9.4 Tree Diagram Tree diagram is a tool to find all possible outcomes of a sequence of events where each event can occur in a finite number of ways. Example 12: A store keeper keeps both men and women shoes, men shoes of sizes 7, 8 and 9 available in two colours ‘Black and White’ and women shoes of sizes 4 and 5 in colours blue, pink and red. How many possible combinations of shoes are available in the store. Solution: 7 B W4B B M7B R W4R 7 7 4 7 5 7 W M7W P W4P 7 7 M8B B W5B B 7 7 8 W M8W W R W5R M 7 7 9 7 P W5R B M9B 7 W M9W Since, total number of end points is 12, hence 12 combinations of shoes are available in the store. Example 13: Sam and Vikram are to play badminton tournament. The first person to win two games in a row or who wins a total of three games wins the tournament. Find the number of ways tournament can occur. CU IDOL SELF LEARNING MATERIAL (SLM)

14 Discrete Mathematical Structures S S S S V V V S V S S V V S S VV V There are 10 ways tournaments can occur, i.e., SS, SVSS, SVSVS, SVSVV, SVV, VSS, VSVSS, VSVSV, VSVV, VV Example 14: Draw a binary tree of length 3 without two consecutive 1’s. Solution: 10 0 0 1 1 0 0 1 0 Therefore, there are five endpoints of the tree diagram as 101, 100, 010, 001, 000. are the binary numbers of length 3 without two consecutive 1’s. 1.10 Summary
A set is a collection of objects, with something in common. A set might be, for example, prime numbers, birds that come into your garden, or people to whom you have sent Christmas cards in the last five years. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 15
The elements of a set are the things within it, such as prime numbers, birds or people as in the examples above. They are also called the members of a set. The symbol
means ‘is an element of’. For example, you might write 2
A, which would mean that 2 was an element of set A. You can also write , which means ‘is not an element of’.
You can show that something is in a set in two simple ways:
In words, for example, ‘All the species of birds I have seen in my garden’, or ‘the prime numbers between 0 and 100’; and
By putting curly brackets around a list of the elements. For example, the set of prime numbers between 0 and 10 could be written {1, 2, 3, 5, 7}. You can also use ellipses if you would have to write too many numbers. For example, if your set were all the numbers between 1 and 20, you could write {1, 2, 3, …20}.
The cardinality of a set is the number of elements a set contains.
Sets that contain the same elements are said to be equal. You can also say that they are equivalent or identical. A Venn diagram can be a useful way of illustrating relationships between sets.
In a Venn diagram:
The universal set is represented by a rectangle. Points inside the rectangle represent elements that are in the universal set; points outside represent things not in the universal set. You can think of this rectangle, then, as a ‘fence’ keeping unwanted things out- and concentrating our attention on the things we’re talking about.
Other sets are represented by loops, usually oval or circular in shape, drawn inside the rectangle. Again, points inside a given loop represent elements in the set it represents; points outside represent things not in the set. CU IDOL SELF LEARNING MATERIAL (SLM)

16 Discrete Mathematical Structures 1.11 Key Words/Abbreviations Symbol Symbol Name Meaning/definition Example {} A = {3, 7, 9, 14}, set a collection of elements B = {9, 14, 28} | such that so that A = {x | x
, x < 0} AB intersection objects that belong to set A and A  B = {9, 14} AB set B AB union AB objects that belong to set A or set A  B = {3, 7, 9, 14, subset B 28} AB AB proper A is a subset of B. set A is {9, 14, 28}  {9, 14, AB subset/strict subset included in set B. 28} AB not subset 2A superset A is a subset of B, but A is not {9, 14}  {9, 14, 28} P(A) equal to B. A=B proper superset/strict set A is not a subset of set B {9, 66}  {9, 14, 28} Ac superset not superset A is a superset of B. set A {9, 14, 28}  {9, 14, power set power set includes set B 28} equality A is a superset of B, but B is not {9, 14, 28}  {9, 14} complement equal to A. set A is not a superset of set B {9, 14, 28}  {9, 66} all subsets of A all subsets of A both sets have the same members A = {3, 9, 14}, B = {3, 9, 14}, A=B all the objects that do not belong to set A CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 17 A complement all the objects that do not belong A\\B to set A relative A-B complement objects that belong to A and not A = {3, 9, 14}, to B B = {1, 2, 3}, AB relative complement A\\B = {9, 14} A
B symmetric objects that belong to A and not A = {3, 9, 14}, a
A difference to B B = {1, 2, 3}, xA (a, b) symmetric A - B = {9, 14} A×B difference |A| objects that belong to A or B but A = {3, 9, 14}, not to their intersection B = {1, 2, 3}, A ∆ B = {1, 2, 9, 14} objects that belong to A or B but A = {3, 9, 14}, not to their intersection B = {1, 2, 3}, A
B = {1, 2, 9, 14} element of, set membership A = {3, 9, 14}, 3
A belongs to not element of no set membership A = {3, 9, 14}, 1  A ordered pair collection of 2 elements cartesian set of all ordered pairs from A product and B cardinality the number of elements of set A A = {3, 9, 14}, | A | = 3 1.12 Learning Activity 1. What is Probability Tree diagram? ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

18 Discrete Mathematical Structures 2. Define Proper Subset with suitable example. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 3. Draw the Venn diagram of: (i) A U B (ii) A ⋂ B ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 1.13 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions (I) Solve the following: 1. Which of the following sets are equal? A = {a, b, c, d}, B = {d, e, a, c}, C = {d, b, a, c}, D = {a, a, d, e, c, e} 2. Which of the following sets are equal? A = {0, 1, 2} B = {x
 | −1 ≤ x < 3} C = {x
 | −1 < x < 3} D = {x

| −1 < x < 3} E = {x

+ | −1 < x < 3} 3. Let S = {2, 4, 6} and T = {1, 3, 5}. Use the set-roster notation to write each of the following sets, and indicate the number of elements that are in each set: (a) S × T (b) T × S (c) S × S (d) T × T CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 19 4. Let the universal set be the set R of all real numbers and let A = {x
 |−3 ≤ x ≤ 0}, B = {x
 | −1 < x < 2}, and C = {x
 | 6 < x ≤ 8}. Find each of the following: (a) A  B (b) A  B (c) Ac (d) A  C (e) A  C (f) Bc (g) Ac  Bc (h) Ac  Bc (i) (A  B)c (A  B)c 5. Let A = {n

| n = 5r for some integer r} and B = {m

| m = 20s for some integer s}. (a) Is A  B? Explain. (b) Is B  A? Explain. 6. Suppose A = {1, 2} and B = {2, 3}. Find each of the following: (a) P(A  B) (b) P(A) (c) P(A  B) (d) P(A × B) 7. Let A = {a, b}, B = {1, 2}, and C = {2, 3}. Find each of the following sets. (a) A × (B  C) (b) (A × B)  (A × C) (c) A × (B  C) (d) (A × B)  (A × C) (II) Solve the following: 1. Suppose there are 10 male and 6 female professors to teach Discrete mathematics. In how many ways a student can choose Discrete mathematics professor. 2. Suppose A is the event of choosing an even number and B is the event of choosing an odd number. In how many ways a person can select a number from the set of positive integers from 1 to 20. 3. In how many different ways can a housing society elect a president, treasurer and secretary out of 15 members? CU IDOL SELF LEARNING MATERIAL (SLM)

20 Discrete Mathematical Structures 4. A bank password consists of two letters of the English alphabet followed by two digits. How many different passwords are there? 5. In an experiment a person must arrange a square, a triangle, a rectangle, a circle and a hexagon in a row. How many different arrangements are possible? Answers: 1. 16 ways, 2. 20 ways, 3. 2,730, 4. 67,600, 5. 120 ways. (III) Solve the following: 1. Draw a binary tree of length 4 without four consecutive 0’s. 2. How many ways are there to colour three bicycles with two colours Green and White. Draw a tree diagram. 3. Construct a tree diagram of binary number of length 5 such that no two zeros are consecutive. 4. How many three digit numbers can be constructed from digits {2, 3, 5, 6} such that 2 is not followed 3 and 5. Answers: 1. 15 WAYS, 2. GGG, GGW, GWG, GWW, WGG,WGW, WWG, WWW, 3. 01010, 01011, 01101, 01110, 01111, 10101, 10110, 10111, 11010, 11011, 11101, 11110, 11111, 4. 72 without repetition. B. Multiple Choice/Objective Type Questions 1. A well defined Collection of objects is called as __________. (a) Subset (b) Set (c) Element (d) Empty Set 2. A set which contains only one element is called __________ Set. (a) Empty (b) Singular (c) Singleton (d) Identity CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 1 21 3. Let A = {0, 3, 9}, then P(A) = __________. (a) 8 (b) 9 (c) 3 (d) 0 4. If there are 30 boys and 3 girls in a class, the number of ways of selecting one student as a class representative are __________. (a) 30 (b) 3 (c) 33 (d) 27 5. The Cardinality of a set A = {2, 10, 12, 6} is __________. (a) 1 (b) 2 (c) 3 (d) 4 Answers 1. (b), 2. (c), 3. (a), 4. (c), 5. (d) 1.14 References References Books: 1. http://www.freebookcentre.net/maths-books-download/Descriptive-Set-Theory-by- David-Marker.html 2. https://books.google.co.in/books?id=pLxq0myANiEC&printsec=frontcover&source=gbs _ge_summary_r&cad=0#v=onepage&q&f=false Web Resources: 1. https://www.britannica.com/science/set-theory 2. https://en.wikibooks.org/wiki/Discrete_Mathematics/Set_theory 3. https://www.math.uh.edu/~dlabate/settheory_Ashlock.pdf 4. https://www.includehelp.com/basics/set-theory-and-types-of-set-in-discrete- mathematics.aspx CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 2 SET THEORY 2 Structure: 2.0 Learning Objectives 2.1 Introduction 2.2 Cardinality 2.3 Countability 2.3.1 Countable Set 2.3.2 Uncountable Set 2.4 Proofs of Some General Identities on Sets 2.5 Pigeonhole Principle 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:
Define Countable Sets.
Define Uncountable Sets.
Describe Some General Identities on Sets.

Set Theory 2 23 2.1 Introduction
Set theory is a fundamental concept throughout all of mathematics. This branch of mathematics forms a foundation for other topics.
Intuitively a set is a collection of objects, which are called elements. Although this seems like a simple idea, it has some far-reaching consequences.
The elements of a set can really be anything – numbers, states, cars, people or even other sets are all possibilities for elements.
Set theory is used throughout mathematics. It is used as a foundation for many subfields of mathematics. In the areas pertaining to statistics, it is particularly used in probability.
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. This theorem is exemplified in real life by truisms like “in any group of three gloves there must be at least two left gloves or at least two right gloves”. 2.2 Cardinality The cardinality of a set is a measure of the “number of elements of the set”. Notation: The cardinality of a set A is usually denoted | A | or n(A). Example Cardinality A = {5} |A|=1 B = {7, 2} |B|=2 C = {1, 3, 4} |C|=3 D = {9, 1, 5, 8} |D|=4 E = {5, 5, 5, 5, 5} |E|=1 CU IDOL SELF LEARNING MATERIAL (SLM)

24 Discrete Mathematical Structures 2.3 Countability 2.3.1 Countable Set Countable sets are the sets having a finite/countable number of members. Countable sets are also known as finite sets as they can be counted. The process will run out of elements to list if the elements of this set have a finite number of members. Examples 1: P ={0, 3, 6, 9, …, 99} Q ={a : a is an integer, 1 < a < 10} A set of all English Alphabets, because it is countable. Example 2: A set of months in a year. M = {January, February, March, April, May, June, July, August, September, October, November, December} n(M) = 12 It is a finite set because the number of elements are countable. Cardinality of Countable Sets If ‘a’ represents the number of elements of Set A, then the cardinality of a finite set is n(A) = a. So, as shown in the image, the cardinality of the above set is 26, because the number of elements (alphabets) is 26. Hence, n(A) = 26. 2.3.2 Uncountable Set If a set is not finite, it is called an Uncountable set because the number of elements in that set is not countable and also we cannot represent it in Roster form. Thus, infinite sets are also known as Uncountable sets. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 2 25 So, to represent the elements of an uncountable set are represented by 3 dots (ellipse) to represent the infinity of that set. Examples of Uncountable Sets:
A set of all whole numbers. W = {1, 2, 3, 4,…}
A set of all points on a line.
A set of all triangles.
The set of leaves on a tree.
The set of hair on the head.
The set of integers. Cardinality of Uncountable Sets The cardinality of a set is n(A) = x, where, x is the number of elements of a set A. The cardinality of an infinite set is n(A) = infinite as the number of elements is unlimited in it. 2.4 Proofs of Some General Identities on Sets Basic Method for Proving that Sets are Equal Two sets are equal
each is a subset of the other. Symbolically: Let sets X and Y be given. To prove that X = Y: 1. Prove that X  Y. 2. Prove that Y  X. Theorem 1: A Distributive Law for Sets For all sets A, B, and C, A  (B  C) = (A  B)  (A  C). Proof: Suppose A and B are sets. Proof that A  (B  C)  (A  B)  (A  C): Suppose x  A  (B  C). CU IDOL SELF LEARNING MATERIAL (SLM)

26 Discrete Mathematical Structures By definition of union, x  A or x  B  C. Case 1 (x  A): Since x  A, xA∪B by definition of union and also  x  A ∪ C by definition of union. Hence, x  (A ∪ B) ∩ (A ∪ C) by definition of intersection. Case 2 (x  B ∩ C): Since x  B ∩ C,  x  B and x  C by definition of intersection. Since, x  B, x  A ∪ B and since x  C, x  A ∪ C, both by definition of union. Hence, x  (A ∪ B) ∩ (A ∪ C) by definition of intersection. In both cases, x  (A ∪ B) ∩ (A ∪ C). Hence, A ∪(B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C) by definition of subset. Proof that (A ∪ B) ∩ (A ∪ C) ⊆A ∪(B ∩ C): Suppose x  (A ∪ B) ∩ (A ∪ C).  x  A ∪B and x  A ∪ C. by definition of intersection. Consider the two cases x  A and x  A. Case 1 (x  A): Since x ∈A,  x  A ∪(B ∩ C). by definition of union. Case 2 (x  A): Since x  A ∪ B,  x is in at least one of A or B. But x is not in A; hence x is in B. Similarly, since x  A ∪ C, x is in at least one of A or C. But x is not in A; hence x is in C. We have shown that both x  B and x  C so by definition of intersection, x  B ∩ C. It follows by definition of union that CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 2 27 x  A ∪ (B ∩ C). In both cases x  A ∪ (B ∩ C). Hence, by definition of subset, (A ∪ B) ∩ (A ∪ C) ⊆A ∪(B ∩ C). Conclusion: Since, both subset relations have been proved, it follows by definition of set equality that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Theorem 2: A De Morgan’s Law for Sets The complement of the union of two sets is equal to the intersection of their complements and the complement of the intersection of two sets is equal to the union of their complements. These are called De Morgan’s laws. For any two finite sets A and B; (i) (A U B)' = A' ∩ B' (which is a De Morgan's law of union). (ii) (A ∩ B)' = A' U B' (which is a De Morgan's law of intersection). (i) (A U B)' = A' ∩ B' Proof: Let P = (A U B)' and Q = A' ∩ B' Let x be an arbitrary element of P then x  P  x  (A U B)'  x  (A U B)  x  A and x  B  x  A' and x  B'  x  A' ∩ B' xQ Therefore, P  Q ... (i) Again, let y be an arbitrary element of Q then y  Q  y  A' ∩ B'  y  A' and y  B'  y  A and y  B  y  (A U B) CU IDOL SELF LEARNING MATERIAL (SLM)

28 Discrete Mathematical Structures  y  (A U B)' ... (ii) yP ... (i) Therefore, Q  P Now combine (i) and (ii) we get; P = Q i.e. (A U B)' = A' ∩ B' (ii) (A ∩ B)' = A' U B' Proof: Let M = (A ∩ B)' and N = A' U B' Let x be an arbitrary element of M then x  M  x  (A ∩ B)'  x  (A ∩ B)  x  A or x  B  x  A' or x  B'  x  A' U B' xN Therefore, M  N Again, let y be an arbitrary element of N then y  N  y  A' U B'  y  A' or y  B'  y  A or y  B  y  (A ∩ B)  y  (A ∩ B)' yM Therefore, N  M …………….. (ii) Now combine (i) and (ii) we get; M = N i.e. (A ∩ B)' = A' U B' Theorem 3: Intersection and Union with a Subset For any sets A and B, if A ⊆ B, then (a) A ∩ B = A and (b) A ∪ B = B. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 2 29 Proof: Part (a): Suppose A and B are sets with A ⊆ B. To show part (a) we must show both that A ∩ B ⊆ A and that A ⊆ A ∩ B. We already know that A ∩ B ⊆ A by the inclusion of intersection property. To show that A ⊆ A ∩ B, let x  A. [We must show that x  A ∩ B.] Since A ⊆ B, then x  B also. Hence x  A and x  B, and thus x  A ∩ B by definition of intersection [as was to be shown]. Proof: Part (b): The proof of part (b) is left as an exercise. Theorem 4: Prove that (A ∪ B) ∩ (A ∩ B) = (A − B) ∪ (B − A) Solution: LHS = (A ∪ B) ∩ (A ∩ B) = (A ∪ B) ∩ (A ∪ B ) De Morgan’s Law. = [A ∩ (A ∪ B )] ∪ [B ∩ (A ∪ B′)] Distributive Law. = [(A ∩ A ) ∪ (A ∩ B′)] ∪ [(B ∩ A ) ∪ (B ∩ B )] Distributive Law. = [ ∪ (A ∩ B )] ∪ [ ∪ (B ∩ A )] = (A ∩ B ) ∪ (B ∩ A ) = (A – B) ∪ (B – A) = RHS 2.5 Pigeonhole Principle The Pigeonhole Principle: If n pigeons occupy m pigeonholes and n > m then atleast one pigeonhole must contains two or more pigeons in it. CU IDOL SELF LEARNING MATERIAL (SLM)

30 Discrete Mathematical Structures Extended pigeonhole principle: If n pigeons are assigned to m pigeonholes then one of the pigeonholes must contain at least pigeons. Example 3: If there are 13 students in a class then show that atleast two of them must have birthdays during the same month. Solution: Number of pigeons = n = 13 students. Number of pigeonholes = m = 12 months. Since, m > n, +1 = 1 + 1 = 2. Hence, at least two students must have birthdays during the same month. Example 4: Prove that any subset of size 6 from the set A={1, 2, 3, …, 9, 10} must contains two elements whose sum is 11. Solution: Possible subsets of two elements whose sum is 11 are: {(10, 1), (9, 2), (8, 3), (7, 4), (6, 5)} when six pigeons go to the respective pigeonholes. If any six numbers are selected from the set A then two elements will fall in the same subset. Number of pigeons = n = 6 and number of pigeonholes = m = 5. +1=1+1=2 Example 5: Triangle ACE is an equilateral with AC = 1. If five points are selected from the interior of the triangle, then prove that atleast two points are less than ½ distance apart. CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 2 31 Solution: C B1D 3 24 A FE For the triangle, the four smaller triangles are congruent equilateral triangles and AB = 1/2. We break-up the interior of triangle ACE in to the following four region which are mutually disjoint in pairs. There are four pigeonholes and five pigeons are selected in the interior of triangle ACE must be such that at least two of them are in one of the four regions, where two points are separated by a distance less than ½. 2.6 Summary
Set theory begins with a fundamental binary relation between an object o and a set A. If o is a member (or element) of A, the notation o  A is used. A set is described by listing elements separated by commas, or by a characterizing property of its elements, within braces { }.
Since sets are objects, the membership relation can relate sets as well.
A derived binary relation between two sets is the subset relation, also called set inclusion. If all the members of set A are also members of set B, then A is a subset of B, denoted A  B. For example, {1, 2} is a subset of {1, 2, 3}, and so is {2} but {1, 4} is not. As insinuated from this definition, a set is a subset of itself.
For cases where this possibility is unsuitable or would make sense to be rejected, the term proper subset is defined. A is called a proper subset of B if and only if A is a subset of B, but A is not equal to B.
At first glance, the pigeonhole principle (also known as Dirichlet’s principle in honor of the eponymous German Mathematician) might appear to be too obvious to be useful; CU IDOL SELF LEARNING MATERIAL (SLM)

32 Discrete Mathematical Structures indeed, the power of the principle comes from cleverly choosing the “boxes” and “objects.” 2.7 Key Words/Abbreviations
P or
, denoting the set of all primes: P = {2, 3, 5, 7, 11, 13, 17, ...}.
N denoting the set of all natural numbers: N = {0, 1, 2, 3, ...} (sometimes defined excluding 0).
Z denoting the set of all integers (whether positive, negative or zero): Z = {..., −2, −1, 0, 1, 2, ...}.
Q or  , denoting the set of all rational numbers (that is, the set of all proper and improper fractions): Q = {a/b | a, b  Z, b  0}. For example, 1/4  Q and 11/6  Q. All integers are in this set since every integer a can be expressed as the fraction a/1 (Z  Q).
R denoting the set of all real numbers. This set includes all rational numbers, together with all irrational numbers (that is, algebraic numbers that cannot be rewritten as fractions such as 2 , as well as transcendental numbers such as , e).
C denoting the set of all complex numbers: C = {a + bi | a, b  R}. For example, 1 + 2i  C. 2.8 Learning Activity 1. State the different types of Sets. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- 2. Define Finite Set and Infinite Set. Give suitable example. ----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- CU IDOL SELF LEARNING MATERIAL (SLM)

Set Theory 2 33 2.9 Unit End Questions (MCQ and Descriptive) A. Descriptive Types Questions 1. Show that if any five numbers from 1 to 8 are chosen, then two of them will add up to 9. 2. Show that if seven integers from 1 to 12 are chosen, then two of them will add up to 13. 3. Show that if any 7 positive integers are chosen, two of them will have the same remainder when divided by 6. 4. Show that if seven colours are used to paint 50 toys, at least eight toys will be of the same colour. 5. Show that if any 11 numbers are chosen from the set {1, 2, …, 20} then one of them will be a multiple of another. B. Multiple Choice/Objective Type Questions 1. If n pigeons occupy m pigeonholes and n > m then at least __________ pigeonhole must contains two or more pigeons in it. (a) one (b) two (c) three (d) four 2. If, A = {0, 10, 20, 30, …, 1000}, then Set A is called as __________ Set. (a) Countable (b) Uncountable (c) Identity (d) Empty 3. {1, 2}  {2, 3} = __________. (a) { } (b) {1, 2, 3} (c) {1, 2} (d) {2} 4. The __________ of a set is a measure of the “number of elements of the set”. (a) Union (b) Intersection (c) Cardinality (d) None of these CU IDOL SELF LEARNING MATERIAL (SLM)

34 Discrete Mathematical Structures 5. The set of integers is an example of __________ set. (a) Countable (b) Uncountable (c) Identity (d) Empty Answers 1. (a), 2. (a), 3. (d), 4. (c), 5. (b) 2.10 References References Books: 1. http://matematicas.uis.edu.co/adrialba/sites/default/files/SetTheoryDover%20Charles% 20C%20Pinter.pdf 2. https://www.springer.com/gp/book/9783319015767 Web Resources: 1. https://en.wikipedia.org/wiki/Set_(mathematics) 2. https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_sets.htm 3. https://en.wikibooks.org/wiki/Discrete_Mathematics/Set_theory 4. https://artofproblemsolving.com/wiki/index.php/Pigeonhole_Principle CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 3 RELATION Structure: 3.0 Learning Objectives 3.1 Introduction 3.2 Definition: Relation 3.3 Types of Relation 3.4 Composition of Relations 3.5 Domain and Range of a Relation 3.6 Pictorial Representation of Relation 3.7 Properties of Relation 3.8 Partial Ordering Relations 3.9 Summary 3.10 Key Words/Abbreviations 3.11 Learning Activity 3.12 Unit End Questions (MCQ and Descriptive) 3.13 References 3.0 Learning Objectives After studying this unit, you will be able to:
Define Relation.
Define Domain and Range of a Relation.

36 Discrete Mathematical Structures
Describe Different Types of Relation.
Explain the Properties of Relation. 3.1 Introduction
Whenever sets are being discussed, the relationship between the elements of the sets is the next thing that comes up. Relations may exist between objects of the same set or between objects of two or more sets.
A relation is a relationship between sets of values. In math, the relation is between the x- values and y-values of ordered pairs. The set of all x-values is called the domain, and the set of all y-values is called the range. 3.2 Definition: Relation Let A and B be the two non-empty sets then a Relation ‘R’ from set A to set B is the subset of the Cartesian product of A and B, i.e., R
A X B. R is a set of ordered pairs (a, b), where, a  A and b  B. If R is a relation from a set A to itself, i.e., if R is a subset of A X A then, we say that R is a relation on A and denoted by aRb, where a, b  A. Example 1: Let A be the set {1, 2, 3, 4}, whose ordered pairs are in the relation R = {(a, b) |a divides b}. Find R. Solution: (a, b) is in R if and only if a and b are positive integers and a divides b. Here 1 divides 1, 1 divides 2, 2 divides 4 and so on. Therefore, R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), ((3, 3), (4, 4)} CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 37 Example 2: Let A = {2, 3, 4} and B = {3, 4, 5}. List the elements of each relation R defined below: (a) a  A is related to b  B if a < b. (b) a  A is related to b  B if a and b both are odd number. Solution: (a) R = {(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)} (b) R = {((3, 3), (3, 5)} 3.3 Types of Relation 1. Universal Relation A relation r from set a to B is said to be universal if: R = A * B Example: A = {1, 2} B = {a, b} R = {(1, a), (1, b), (2, a), (2, b) is a universal relation. 2. Compliment Relation Compliment of a relation will contain all the pairs where pair do not belong to relation but belongs to Cartesian product. R=A*B–X Example: A = {1, 2} B = {3, 4} R = {(1, 3) (2, 4)} Then the complement of R Rc = {(1, 4) (2, 3)} CU IDOL SELF LEARNING MATERIAL (SLM)

38 Discrete Mathematical Structures 3. Empty Relation A null set phie is subset of A * B. R = phie is empty relation 4. Inverse of Relation An inverse of a relation is denoted by R–1 which is the same set of pairs just written in different or reverse order. Let R be any relation from A to B. The inverse of R denoted by R–1 is the relation from B to A defined by: R–1 = {(y, x) : yEB, xEA, (x, y) E R} 5. Composite Relation Let A, B, and C be any three sets. Let consider a relation R from A to B and another relation from B to C. The composition relation of the two relation R and S be a Relation from the set A to the set C, and is denoted by RoS and is defined as follows: RoS = {(a, c) : an element of B such that (a, b) E R and (b, c) E S, when a E A, c E C} Hence, (a, b) E R (b, c) E S  (a, c) E RoS. 6. Equivalence Relation The relation R is called equivalence relation when it satisfies three properties if it is reflexive, symmetric, and transitive in a set x. If R is an equivalence relation in a set X then D(R) the domain of R is X itself. Therefore, R will be called a relation on X. The following are some examples of the equivalence relation:
Equality of numbers on a set of real numbers.
Equality of subsets of a universal set.
Similarities of triangles on the set of triangles.
Relation of lines being a parallel onset of lines in a plane.
Relation of living in the same town on the set of persons living in Canada. CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 39 7. Partial Order Relation Let, R be a relation in a set A then, R is called partial order relation if,
R is reflexive i.e., aRa, a belongs to A.
R is antisymmetric i.e., aRb, bRa  a = b, a, b belongs to a.
R is transitive aRb, bRc  aRc, a, b, c belongs to A. 8. Antisymmetric Relation A relation R on a set a is called on antisymmetric relation if for x, y if for x, y  If (x, y) and (y, x) E R then x = y Example: {(1, 2) (2, 3), (2, 2)} is antisymmetric relation. A relation that is antisymmetric is not the same as not symmetric. A relation can be antisymmetric and symmetric at the same time. 9. Irreflective Relation A relation R is said to be on irreflective relation if x E a (x, x) does not belong to R. Example: a = {1, 2, 3} R = {(1, 2), (1, 3) if is an irreflexive relation 10. Non Reflective Relation A relation R is said to be not reflective if neither R is reflexive nor irreflexive. CU IDOL SELF LEARNING MATERIAL (SLM)

40 Discrete Mathematical Structures 3.4 Composition of Relations Let A, B and C be sets, R is a relation from A to B and S is a relation from B to C then there exist a new relation SoR called composition relation from A to C defined as a (SoR) c iff for some b in B. Theorem (only Statement): Let A, B, C and D be sets. Suppose R is a relation from A to B, S is a relation from B to C and T is a relation from C to D. Then (R o S) o T = R o (S o T) Example 3: Let A = {1, 2, 3, 4}, R = {(1, 2), (1, 1), (1, 3), (2, 4), (3, 2) and S = {(1, 4), (1, 3), (2, 3), (3, 1), (4, 1)} find SoR, RoS, SoS. Solution: Since, (1, 2)  R and (2, 3)  S then (1, 3)  So R SoR = {(1, 4), (1, 3), (1, 1), (2, 1), (3, 3)} RoS = {((1, 2),(2, 2), (3,1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3)} RoR = {((1, 4), (1, 1), (1, 2), (1, 3), (3, 4)} Example 4: A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y, z} R = {(1, a), (2, d), (3, a), (3, b), (3, d)} and S = {(b, x), (b, z), (c, y), (d, z)} Find SoR, RoR, RoS. Solution: SoR = {(2, z), (3, x), (3, z), (3, z)} RoR =  RoS =  CU IDOL SELF LEARNING MATERIAL (SLM)

Relation 41 3.5 Domain and Range of a Relation Domain of R: In domain and range of a relation, if R be a relation from set A to set B, then The set of all first components of the ordered pairs belonging to R is called the domain of R. Thus, Dom(R) = {a  A: (a, b)  R for some b  B}. The domain of a relation from A to B is a subset of A. Range of R: The set of all second components of the ordered pairs belonging to R is called the range of R. Thus, range of R = {b  B: (a, b)  R for some a  A}. The range of a relation from A to B is a subset of B. Therefore, Domain (R) = {a : (a, b)  R} and Range (R) = {b : (a, b)  R}. Example 5: If A = {2, 4, 6, 8) B = {5, 7, 1, 9}. Let R be the relation ‘is less than’ from A to B. Find Domain (R) and Range (R). Solution: Under this relation (R), we have, R = {(4, 5); (4, 7); (4, 9); (6, 7); (6, 9), (8, 9) (2, 5) (2, 7) (2, 9)}. Therefore, Domain (R) = {2, 4, 6, 8} and Range (R) = {1, 5, 7, 9}. Example 6: In the given ordered pair (4, 6); (8, 4); (4, 4); (9, 11); (6, 3); (3, 0); (2, 3) find the following relations. Also, find the domain and range. (a) Is two less than (b) Is less than CU IDOL SELF LEARNING MATERIAL (SLM)

42 Discrete Mathematical Structures (c) Is greater than (d) Is equal to Solution: (a) R1 is the set of all ordered pairs whose 1st component is two less than the 2nd component. Therefore, R1 = {(4, 6); (9, 11)}. Also, Domain (R1) = Set of all first components of R1 = {4, 9} and Range (R2) = Set of all second components of R2 = {6, 11}. (b) R2 is the set of all ordered pairs whose 1st component is less than the second component. Therefore, R2 = {(4, 6); (9, 11); (2, 3)}. Also, Domain (R2) = {4, 9, 2} and Range (R2) = {6, 11, 3}. (c) R3 is the set of all ordered pairs whose 1st component is greater than the second component. Therefore, R3 = {(8, 4); (6, 3); (3, 0)}. Also, Domain (R3) = {8, 6, 3} and Range (R3) = {4, 3, 0}. (d) R4 is the set of all ordered pairs whose 1st component is equal to the second component. Therefore, R4 = {(3, 3)}. Also, Domain (R) = {3} and Range (R) = {3}. Example 7: Let A = {2, 3, 4, 5} and B = {8, 9, 10, 11}. Let R be the relation ‘is factor of’ from A to B. Write R in the roster form. Also, find Domain and Range of R. Solution: R consists of elements (a, b) where a is a factor of b. Therefore, Relation (R) in the roster form is R = {(2, 8); (2, 10); (3, 9); (4, 8), (5, 10)}. CU IDOL SELF LEARNING MATERIAL (SLM)