• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

Let R_1 be a relation from A = {2, 3, 4} to B = {2, 4, 6, 8} and R_2 be another relation from B = {2, 4, 6, 8} to C = {1, 2, 3, 4} as defined below: i. An element x in A is related to an element y in B (under R_1) if y is divisible by x. ii. An element y in B is related to an element z in C (under R_2) if z is even but not divisible by y. Which is the composite relation R_1 R_2 from A to C? A. R_1 R_2 = {(2,2),(2,4),(3,2),(3,4),(4,2),(4,4)} B. R_1 R_2 = {(2,2),(2,4),(3,2),(3,4),(4,2),(4,4),(3,6)} C. R_1 R_2 = {(2,2),(2,4),(3,2),(3,4),(4,2),(4,4)} D. R_1 R_2 = {(2,4),(3,2),(3,4),(4,2),(4,4)}

GATE 2004 · Discrete Mathematics · Relations · medium

Answer: C. R_1 R_2 = {(2,2),(2,4),(3,2),(3,4),(4,2),(4,4)}

  1. Build R_1: y divisible by x (x in A, y in B): x=2: 2|2,2|4,2|6,2|8 => (2,2),(2,4),(2,6),(2,8). x=3: 3|6 => (3,6). x=4: 4|4,4|8 => (4,4),(4,8).
  2. Build R_2: z even but y does not divide z (y in B, z in C): z must be even in C, so z in {2,4}. y=2: 2|2 and 2|4, so no pairs. y=4: 4 does not divide 2 => (4,2); 4|4 excluded. y=6: 6 does not divide 2 or 4 => (6,2),(6,4). y=8: 8 does not divide 2 or 4 => (8,2),(8,4).
  3. Compute composite R_1 R_2: x=2: R_1 links 2 to {2,4,6,8}. y=4:(4,2) in R_2 => (2,2); y=4:(4,?), only (4,2) => (2,2). y=6:(6,2),(6,4) => (2,2),(2,4). y=8:(8,2),(8,4) => (2,2),(2,4). So x=2 gives {(2,2),(2,4)}. x=3: R_1 links 3 to {6}. y=6:(6,2),(6,4) => (3,2),(3,4). x=4: R_1 links 4 to {4,8}. y=4:(4,2) => (4,2). y=8:(8,2),(8,4) => (4,2),(4,4). So x=4 gives {(4,2),(4,4)}.