EXAMSHARE

Western Delta University, Oghara Delta State

department of computer science
college of computing
western delta university

first semester examination 2023/2023 session

CSC205 - discrete structures time: 2hrs: 30mins

Answer question one (1) and choose three (3) other questions

  1. Question 1 (Compulsory) (25 Marks)

    Given the following expression: S = (6, 10, 14), T = (4, 10, 16) and Y = (X, Y, Z)
    1. Power Sets. P(S)
    2. Cartesiam Product. S * T
    3. Union. S ∪ T
    4. Intersection. S ∩ T
    5. Difference. S - T

  2. Question 2 (15 Marks)

    1. Given that R = {(1,2),(2,3),(1,4)} be a relation (say on set Z). Then (1,3) ∈ R* (since (1,2),(2,3) ∈ R), but (2,4) ∈/R*. Draw the diagram, the graph of a relation and its transitive closure. (10 marks)
    2. Define the following:
      1. Set cardinality, Set equality (2.5 marks)
      2. Subsets (2.5 marks)

  3. Question 3 (15 Marks)

    1. Define the following:
      1. A function.
      2. Injection
      3. Surjection
      4. Bijection
      5. Inverse relation
      6. Set cardinality
      (12 marks)
    2. Given two functions X, Y - Draw a:
      1. What are nested loops? (2 marks)
      2. A surjective function from X to Y (1.5 marks)

  4. Question 4 (15 Marks)

    1. Define the following terms:
      1. A directed graph (2.5 marks)
      2. Undirected graph (2.5 marks)
      3. Define Graph Isomorphism and show a diagram of an isomorphic diagram and a non-isomorphic graph (10 marks)

  5. Question 5 (15 marks)

    1. Consider the formula (P ∧ ¬Q) ⇒ (¬P ∨ Q), where P and Q are atoms.
      1. Is the formula valid? Justify your answer. (5 marks)
      2. Is the formula satisfiable? Justify your answer. (5 marks)
    2. Show with a diagram a strongly connected graph and a weakly connected graph. (5 marks)

  6. Question 6 (15 Marks)

    1. Suppose we have an undirected graph G such taht the degree of each vertex is a multiple of 10 or 15. Show that the number of edges in G must be a multiple of 5. (10 marks)
    2. Give the table below, fill in the expected outcome for A and B. (5 marks)
      A B¬AA ∧ BA ∨ BA → BA ⟷ B
      T T
      T F
      F T
      F F