Content is user-generated and unverified.

Discrete Mathematics Exam Solutions

CSC208 - Second Semester Examination 2020/2021

Question 1 (25 marks)

a. Set Operations Given: A = {7, 1, 2, 3, 6}, B = {2, 3, 4}, C = {1, 6, 7}, D = {3, 4, 9} Subsets of U = {n ∈ N : 1 ≤ n ≤ 10}

i. A ∪ C = {1, 2, 3, 6, 7} ∪ {1, 6, 7} = {1, 2, 3, 6, 7}

ii. (A ∩ D) ∪ (A ∩ B)

  • A ∩ D = {7, 1, 2, 3, 6} ∩ {3, 4, 9} = {3}
  • A ∩ B = {7, 1, 2, 3, 6} ∩ {2, 3, 4} = {2, 3}
  • Therefore: {3} ∪ {2, 3} = {2, 3}

iii. ∅ ∪ B = ∅ ∪ {2, 3, 4} = {2, 3, 4}

iv. (A ∪ B)ᶜ

  • A ∪ B = {7, 1, 2, 3, 6} ∪ {2, 3, 4} = {1, 2, 3, 4, 6, 7}
  • (A ∪ B)ᶜ = U - (A ∪ B) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} - {1, 2, 3, 4, 6, 7} = {5, 8, 9, 10}

b. Truth Value Evaluation Given: A = {a, b, c, v, w}, B = {∅, a}, C = {1, 2, 4}, D = {2, 4, 8}

i. w ∈ A → TRUE (w is an element of A) ii. ∅ ∈ B → TRUE (∅ is an element of B) iii. D ⊃ C → FALSE (D does not contain all elements of C; 1 ∉ D) iv. {2, 4} ⊂ A → FALSE (2 and 4 are not elements of A)

c. Matrix Operations Given: A = [3 1; 2 4], A' = [0 1; 0 2]

i. (A')ᵀ ∧ A (interpreting as (A')ᵀ · A)

  • (A')ᵀ = [0 0; 1 2]
  • (A')ᵀ · A = [0 0; 1 2] · [3 1; 2 4] = [0 0; 7 9]

ii. (A')ᵀ = (A')ᵀ → TRUE (trivially true)

d. De Morgan's Laws Verification i. ¬(¬P ∧ Q) ≡ (P ∨ ¬Q) → VALID ii. P ∧ Q ≡ ¬(¬P ∨ ¬Q) → VALID

e. Handshaking Problem In a classroom, 9 students shake hands with 5 others. Total handshakes = (9 × 5) ÷ 2 = 22.5

Since we can't have half a handshake, this scenario is impossible under normal handshaking rules. Each handshake involves exactly 2 people, so the total number of handshake participations must be even.

f. Conditional Propositions (¬→) i. If 10:00am is morning, then 11:00pm is night → TRUE ii. If Abuja is in Kaduna, then Kaduna is the FCT → TRUE (vacuously true, since premise is false) iii. If Africa is a country, then Europe is a continent → TRUE (vacuously true, since premise is false) iv. If 9 > 1, then AFIT offers degree courses → Depends on whether AFIT offers degree courses

Question 2 (15 marks)

a. Student Course Preferences Given: 240 students total, 160 prefer programming, 120 prefer math, 90 prefer both

i. Programming-based courses only: 160 - 90 = 70 students ii. Math-based courses only: 120 - 90 = 30 students iii. Neither course type: 240 - (70 + 30 + 90) = 50 students iv. Only one type (programming OR math, not both): 70 + 30 = 100 students

b. Set Cardinality i. |A| = {4, 5, 6, ..., 18} → |A| = 15 ii. |B| = {n ∈ N : 2 < n ≤ 150} → |B| = 148 iii. |C| = {1, a, b, c, b1, ∅} → |C| = 6 iv. |A ∩ B| when A = {x ∈ N : 5 ≤ x < 22} and B = {x ∈ N : x is prime} - A = {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21} - Primes in A: {5, 7, 11, 13, 17, 19} - |A ∩ B| = 6

c. Singleton and Doubleton Subsets Let A = {n ∈ N : 1 ≤ n ≤ 10}

i. Singleton subsets: Each element forms one singleton subset

  • Number of singleton subsets = 10

ii. Doubleton subsets: Choose 2 elements from 10

  • Number of doubleton subsets = C(10,2) = 45

d. Set Operations with Conditions Let A = {x ∈ N : 4 ≤ x < 12} and B = {x ∈ N : x is even}

i. Find A ∩ B

  • A = {4, 5, 6, 7, 8, 9, 10, 11}
  • B = {2, 4, 6, 8, 10, 12, 14, ...}
  • A ∩ B = {4, 6, 8, 10}

ii. Find A \ B

  • A \ B = {5, 7, 9, 11}

Question 3 (15 marks)

a. Logical Translation Given: P: register for CSC208, Q: in FoC, R: freshman

i. "You can register for CSC208 only if you are in FoC or not a freshman"

  • P → (Q ∨ ¬R)

ii. "You cannot register for CSC208 if you are a freshman"

  • R → ¬P

iii. "If you are in FoC and a freshman, you cannot register for CSC208"

  • (Q ∧ R) → ¬P

iv. "You cannot register for CSC208 if you are not in FoC"

  • ¬Q → ¬P

b. Logical Expression Translation The logical expressions appear to be partially cut off in the image, but the format would be to convert symbolic logic back to English statements using the same propositions P, Q, and R.

Question 4 (15 marks)

a. Graph Isomorphism To determine if graphs are isomorphic, we need to check:

  • Same number of vertices
  • Same number of edges
  • Same degree sequence
  • Structural equivalence

Without being able to clearly see all details of the graphs, a complete analysis would require examining the degree of each vertex and attempting to find a valid mapping.

b. Hasse Diagram Analysis For the given Hasse diagram with elements {a,b}:

  • Complements: In a Boolean lattice, each element has a unique complement
  • Need to identify the complement relationships based on the structure

c. Define "subgraph" and "induced subgraph"

  • Subgraph: A graph G' = (V', E') is a subgraph of G = (V, E) if V' ⊆ V and E' ⊆ E
  • Induced subgraph: Given a subset S of vertices, the induced subgraph contains all edges from the original graph that connect vertices within S

d. Subgraph Analysis For each graph G₁, G₂, G₃, G₄, determine which are subgraphs or induced subgraphs of G by examining their vertex and edge relationships.

Question 5 (15 marks)

a. Matrix Multiplication Proof Given: A and B are square and non-singular matrices Prove: AB + BA

This requires showing that if A and B are both invertible (non-singular), then their sum AB + BA has certain properties. The complete proof would involve properties of matrix inverses and matrix operations.

b. Matrix Equation Given: C = [1 3 5; 2 3 6; 4 0 2] Prove: CC^T = I₃ or C^T C = I₃

To prove this, we need to:

  1. Calculate C^T (transpose of C)
  2. Compute CC^T or C^T C
  3. Show it equals the identity matrix I₃

If this is true, then C is an orthogonal matrix.

Question 6 (15 marks)

a. Distributive Lattices Determine if the given posets/lattices are distributive by checking if they satisfy the distributive laws:

  • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
  • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

b. Poset Analysis For the set A = {1, 2, 3, 4, 5, 6} with binary relation "divides":

i. Draw Hasse diagram ii. Greatest and least elements:

  • Least element: 1 (divides all others)
  • Greatest element: None (no single element is divisible by all others) iii. Maximal elements: Elements with no successors iv. Meet and join of (2,3):
  • Meet: gcd(2,3) = 1
  • Join: lcm(2,3) = 6 v. Meet and join of (3,5):
  • Meet: gcd(3,5) = 1
  • Join: lcm(3,5) = 15 (not in set, so no join exists) vi. Lattice determination: Not a lattice because not all pairs have joins within the set
Content is user-generated and unverified.
    Discrete Mathematics Exam Solutions | Claude