Discrete Maths Finals Work PDF

# PRINCIPLE OF INCLUSION AND EXCLUSION: - As we know that the cardinality of the set P is the number of unique elements in P. It is denoted by |P|. - **FIRST PRINCIPLE:** If P and Q are disjoint sets, then |PUQI = |P| + |Q|. - **Theorem 1:** Let P and Q be any two non-disjoint sets, Then |PUQI = |P|...

# PRINCIPLE OF INCLUSION AND EXCLUSION: - As we know that the cardinality of the set P is the number of unique elements in P. It is denoted by |P|. - **FIRST PRINCIPLE:** If P and Q are disjoint sets, then |PUQI = |P| + |Q|. - **Theorem 1:** Let P and Q be any two non-disjoint sets, Then |PUQI = |P| + |Q| - |PAQI|. - **Theorem 2:** Let P, Q and R are three finite sets, then |PUQURI = |P| + |Q| + |R| - |PAQI| - |PMRI| - |QARI| + |PAOARL|. ## Q#1 - Out of 1200 students in a college: - 582 took Gronomics - 627 took English - 543 took Mathematics - 217 took both Gronomics and English - 807 took both Economics and Mathematics - 250 took both English and Mathematics - 222 took all three courses - **Sol:** - |A| = 582 (Gronomics) - |B| = 627 (English) - |C| = 543 (Mathematics) - |A∩B| = 217 - |A∩C| = 307 - |B∩C| = 250 - |A∩B∩C| = 222 - **(a) How many who took none?** - **Name** - No of None = Total Students - Opt subject. - AUBUCI = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| - **Sol)** - 582 + 627 + 543 - 217 - 307 - 250 + 222 . - 1200 - 1200 - = **0 Any** ## Q#2 - Among the first 500 +ve integers. Determine the integer which are not divisible by 2 nor by 3, nor by 5. - **Sol:** - A = no of integer divisible by 2 - B = no of integer divisible by 3 - C = no of integer divisible by 5. - **Sol:** - |A| = 500/2 = 250, |B| = 500/3 = 166, |C| = 500/5 = 100. - |A∩B| = 500/(2 * 3) = 83 - |A∩C| = 500/(2 * 5) = 50 - |B∩C| = 500/(3 * 5) = 33 - |A∩B∩C| = 500/(2 * 3 * 5) = 16 - **|AUBUCI = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|** . - **Sol:** - Total - |ABBeret| - = 500 - . - 250+ 166 + 100 - 83 - 33 - 50 + 16 - = 500 - 335 = 366 - = **134 Ans** ## Q#3 - A survey of household in U.S.A. reveals that 86% have atleast one television set, 98% have atleast one television telephone service, and 95% have telephone device service and atleast one television set what percentage of household in the U.S.A have neither telephone service nor a television set? - **Solution:** - |A| = television set = 96 - |B| = telephone service = 98 - |A∩B|= 95 - |AUBI = |A| + |B| - |A∩B| - = 96 + 98 - 95 = 99% - **Neither telephone nor television set** - = 100 - 99 = **1% Ans** # THE PIGEON HOLE PRINCIPLE: - If K is a positive integer and K+1 or more objects are placed into K boxes, then there is atleast one box Containing two or more objects. - A general principle called the Pigeonhole principle, which states that if there are more pigeons than pigeon holes then there must be at least one pigeonhole with atleast two pigeons on it. # RELATION ## BINARY RELATION: - Let P and Q be two non-empty sets. A binary relation R from a set P to Q. If (a,b) ∈ R and R ⊆ P x Q then a is related to b by R ie arb. - 1) A = {a,b,c}, B = {r,i,s,t} - A x B = {(a,r), (a,i), (a,s), (a,t), (b,r), (b,i), (b,s), (b,t), (c,r), (c,i), (c,s), (c,t)} - **Eg:** A = m, B = n element - Relation? >> 2^m x n Ans - **Eg:** A = {1,2}, Determine relation A to B - Sol. - 2^2 = 4 - {}{}{}{1,2} Ans ## DOMAIN OF RELATION: - **Eg:** R = {(1,a), (1,b), (1,c), (2,b), (2,c), (2,d)} - Domain R = (1,2) - Range R = (a,b,c,d) # THE GENERALIZED PIGEON HOLE: - If N objects are placed into R boxes, then there is atleast one box containing at least [N/R] objects. - **Ex:** Among 100 people there are at least [100/12] = 9 who were born in the same month. - **Example:** Show that if there are 30 students in a class then atleast two have last names that begin with the same letter? - **Ans:** - [30/26] = 1.15 = 2 Ans # #RELATION of a matrix: - M_ij = 0 - (a,b) ∉ R - 1 -(a,b) ∈ R - **Solve** - P = {1,2,3,4}, Q = {a,b,c,d} - R = {(1,a), (1,b), (1,c), (2,b), (2,c), (2,d), (3,a), (3,d), (4,b), (4,c)} - **Sol:** | | a | b | c | d | |-------|--------|--------|--------|--------| | P= 1 | 1 | 1 | 0 | 0 | | P= 2 | 0 | 1 | 1 | 0 | | P= 3 | 1 | 0 | 0 | 1 | | P= 4 | 0 | 1 | 1 | 0 | ## #ANTI SYMMETRIC: - (a,b) ∈ R (b,a) ∉ R - **Eg:** A = {4,5,6} - R = {(4,4), (4,5), (5,6), (4,6)} - It is anti symmetric - **Eg:** A = {4,5,6} - R = {(4,4), (4,5), (5,6), (6,5), (4,6)} - It is anti symmetry # #DIRECTED GRAPH - **Eg:** P = {1,2,3,4} - R = {(1,1), (1,2), (2,1), (2,2), (3,2), (3,4), (4,1), (4,4), (4,2)} # #ARROW DIAGRAM: - **Eg:** P = {1,2,3,4}, Q = {a,b,c,d} - R = {(1,a), (2,a), (3,a), (1,b), (4,b), (4,c), (4,d)} # #PROPERTIES OF RELATION: 1. Reflexive (a,a) ∈ R 2. Symmetry (a,a) ∈ R (b,a) ∈ R 3. Transitive (a→b) (b→c) and (a→c) # #Complement of Relation - R = (A x B )-R - **eg** X = {1,2,3}, Y = {8,9} - R = {(1,8),(2,8),(1,9),(3,9)} - R' = ? - R = {(2,9),(3,8)} - **Eg#6** Let A = {7,8,9}, B = {k,l,m,n} and R = {(7,k),(7,l),(7,m),(7,n),(8,k),(8,l),(8,m),(8,n),(9,k),(9,l),(9,m),(9,n)} - R' = {(7,k),(7,m),(7,n),(8,l),(9,k),(9,l)} # #Inverse of a Relation (R^-1) - **Eg#7** A = {2,3,4,5}, B = {a,b,c} and R = {(2,a),(2,b),(3,c),(4,a),(5,b),(5,b)} - R^-1 = {(a,2),(b,2),(c,3),(a,4),(b,5),(b,5)} # Q#1 - A = {1,2.3}, R = {(1,2),(2,2),(2,1),(1,1)} then R is transitive Relation. - **Sol:** - #(1,2) -> (2,2) -> (2,1) - a,b b,c a,c - (a,c) ->(1,2) -> Transitive - #(1,2) (2,1)->(1,1) - a,b b,c a,c - Transitive # Q#2 - A = {3,4,5} , R = {(3,4), (4,3), (5,4), (3,3)} - **Sol:** - (3,4) (4,3) -> (3,3) - a,b b,c - (4,3) (3,3) -> (4,3). ✓ - a,b b,c - (5,4) (4,3) -> (5,3) ✓ - a,b b,c - (5,3) (3,4) -> (5,4) ✓ - a,b b,c - (3.3) (3.4) -> (3,4) - a,b b,c # #EQUIVALENT RELATION: - * Reflexive - * Symmetry - * Transitive (Hold these 3 properties # Q# - Let A = {1,2,3,4}, R = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4),(1,4),(4,2),(4,1)} - **Is it Equivalent Relation?** - **Sol:** 1. **Reflexive Relation:** - (a,a) ∈ R - (1,1), (2,2), (3,3), (4,4) - **Hold** 2. **Symmetry Relation:** - (a,b) ∈ R and (b,a) ∈ R - **Hold** 3. **Transitive Relation:** - (a,b) ∈ R (b,c) ∈ R, so (a,c) ∈ R - **Hold** - **This Relation hold equivalent Relation** # #PARTIAL ORDER EQUIVALENCE RELATION: - a) Reflexive - b) Antisymmetry - c) Transitive # Q# - A = {1,2,3,4}, R = {(1,1),(2,2),(3,3),(4,4),(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)} - **Is it partial order relation?** - **Sol:** 1. **Reflexive Relation:** - (a,a) ∈ R - (1,1), (2,2), (3,3) (4,4) - **Hold** 2. **Antisymmetry Relation:** - (a,b) ∈ R and (b,a) ∈ R - **Hold** 3. **Transitive Relation:** - (a,b) ∈ R (b,c) ∈ R, so (a,c) ∈ R - **Hold** - **This relation hold partial order equivalence** # CLOSURE PROPERTIES OF RELATION: 1. **Reflexive Closure: R^f, R ∪ A** - Q# A = {7,8,9} R = {(7,8),(7,9),(8,8),(9,7)} - find Reflexive closure. - **Solve:** - A = {(7,7),(8,8),(9,9)} - R' = R ∪ A - R' = {(7,8),(7,9),(8,8),(9,7)} ∪ {(7,7),(8,8),( 9,9)} - R' = {(7,8),(7,9),(8,8),(9,7),(7,7),(9,9)} Ans 2. **Symmetric Closure R^s = R ∪ R^-1, R = (2,1) R-¹ = (1,2):** - Q#2 A = {4,5,6,7}, R = {(4,5),(5,5),(5,6),(6,7),(7,4),( 7,7)} - Find symmetry closure - **Solve:** - R^-1 = {(5,4),(5,5),(6,5),(7,6),(4,7),(7,7)} - R^s = R ∪ R^-1 - R^s = {(4,5),(5,5),(5,6),(6,7),(7,4),(7,7)} ∪ {(5,4),(5,5),(6,5),(7,6),(4,7),(7,7)} - R^s = {(4,5),(4,7),(5,5),(5,4),(5,6),(6,5),(6,7),(7,4),(7,6),(7,7)} Ans # #Transitive Closure: - R^t = R ∪ R* - Q#3 A = {4,6,8,10}, R = {(4,4),(4,10),(4,6),(6,8),(8,10)} - find transitive closure. - **Solve:** - R = {(4,4),(4,10),(6,6),(6,8),(8,10)} - (4,4)(4,10) -> (4,10) - (4,10) - (6,6)(6,8) -> (6,8)* - (6,8)(8,10) -> (6,10)* - (8,10) - R* = {(6,10)} - R^t = R ∪ R* - => {(4,4),(4,10),(6,6),(6,8),(8,10)} ∪ {(6,10)} - => {(4,4),(4,10),(6,6),(6,8),(6,10),(8,10)} Ans # Q# - Let A = {1,2,3,4}, R = {(1,1),(1,2),(2,1),(2,2),(3,4),(3,2),(1,4),(4,2),(4,1)} - **Solve:** 1. **Reflexive Closure:** - R = R ∪ A - A = {(1,1),(2,2),(3,3),(4,4)} - R = {(1,1),(1,2),(2,1),(2,2),(3,4),(3,2),(1,4),(4,2),(4,1)} ∪ {( 1,1),( 2,2), (3,3), (4,4)} - R = {(1,1),(1,2),(2,1),(2,2),(3,4),(3,2),(1,4), (4,2), (4,1), (4,4)} Ans 2. **Symmetric Closure:** - R^s = R ∪ R^-1 - R^-1 = {(1,1),(2,1),(1,2),(2,2),(4,3),(2,3),(4,1),(2,4),(1,4),(4,4)} - R^s ={(1,1),(1,2),(2,1),(2,2),(3,4),(3,2),(1,4),(4,2),(4,1)} ∪ {(1,1),(2,1),(1,2),(2,2),(4,3),(2,3),(4,1),(2,4),(1,4),(4,4)} - R^s = {(1,1),(1,2),(1,4),(2,1),(2,2),(2,3),(2,4),(3,4),(4,3),(3,2),(4,2),( 4,1)} 3. **TRANSITIVE CLOSURE:** - R^t = R ∪ R* - R* = {(2,4),(3,1),(4,4)} - R^t = {(2,4),(3,1),(4,4)} ∪ {(1,1),(1,2),(2,1),(2,2),(3,4),(3,2),(1,4),(4,2),(4,1)} - R^t = {(2,4),(3,1),(4,4),(1,1),(1,2),(2,1),(2,2),(3,4),(3,2)(1,4),(4,2),(4,1)} Ans # GRAPHS - **Definition:** A graph G_o ( V, E) consists of V, a non-empty set of vertices (or nodes), and E, a set of edges (or arcs, or lines). Each edge has either one or two vertices associated with it, called its end-points. An edge is said to connect its endpoints - **A graph with an infinite number of vertices is called an infinite graph otherwise a finite graph** - **DEFINITION:** Graphs that may have multiple edges connecting the same vertices are called multigraphs - **LOOPS:** Edges that connect a vertex to itself are called loops. - **PSEUDOGRAPH:** Graphs that may include loops, a possibly multiple edges connecting the same pair of vertices, are called ‘pseudo graph’. - **UNDIRECTED GRAPHS AND EDGES.** The graphs and their edges which do not indicate any direction are called undirected graphs and edges # DIRECTED GRAPHS: - A directed graph (or digraph), (V, E) consists of a non-empty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at U and end at V. - **SIMPLE GRAPHS:** When a digraph has no loops and has no multiple directed edges that connect u and v, it is called a simple graph - **MULTI GRAPHS:** Directed graphs that may have multiple directed edges from a vertex to a second vertex are called directed multigraphs. - **ISOLATED VERTEX:** A vertex of degree zero is called isolated. An isolated vertex is not adjacent to any vertex - **PENDANT VERTEX:** A vertex is called pendant if it has degree one. A pendant value is adjacent to only one vertex. # Ex: Let V= {1, 2, 3, 4}, E={(1, 2), (1, 4), (3, 4), (3, 2)} - The graph can be drawn in several ways. Two of which are as follows: - **(a)**  - **undirected** - **simple edges** = 2, b = 3, c = 2, d = 2 - **No loops, simple graph** - **(b)**  - **undirected** - **simple edges a = 3, b = 5, C = 2, d = 4** - **No loop, Multi graph** - **(c)**  - **undirected** - **Multiple edges a = 5, b = 6, c = 3, d = 2** - **3 loops, Pseudo graph** - **(d)**  - **Directed** - **Yes, a = 1, b = 2, c = 2, d = 2, e = 2** - **2 loops** - **Directed Multigraph** # GRAPH TERMINOLOGY - **ENDPOINTS OF THE EDGE:** - In an undirected graph, two vertices u and v (or neighbours in G_o (u, v) is an edge of G_o. - If e = (u,v) the edge e is called incident with vertices u and v. The edge e is also said to connect u and v. The vertices u and v are called endpoints of the edge (u,v). - **DEGREE OF THE VERTEX:** - The degree of a vertex is on an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of a vertex (v) is denoted by deg (v). - **Ex: 1** what are the degrees of the vertices in the graph G and H? - **G:**  - **a** - **b = 2** - **c = 4** - **d = 4** - **e = 1** - **f = 3** - **g = 2** - **Sum = 18** - **H:**  - **a = 4** - **b = 6** - **c = 4** - **d = 2** - **e = 6** - **Sum = 22** - **HANDSHAKING THEOREM:** - **Eg:** 2e = ∑ deg (v) - **In eg ‘H’** ∑ deg (v) = 22 - **e?** - **Sol:** - Using theorem: - ∑ deg (v) = 22 - 2²•e - 22*e - e = 11 - **In eg ‘G’ edges?** - **e?** - **Sol** - ∑ deg (v) = 18 - Using theorem: - ∑ deg (v) = 2e - 18 = 2e - 18/2 = e - **e = 9 Ans** - **Eg:** How many edges are there in a graph with 10 vertices each of degree = 6. - **Sol:** - 10 x 6 = 60 - Using Theorem: - ∑ deg (v) = 2e - 60 z 2e - 60/2 = e - **e = 30 Ans**