Discrete Mathematics Solutions

Question 1 (22 marks)

a. Set Operations (2 marks)

Given sets A and B:

• i. A = {a, b, c} and B = {a, b, c} → A equals B
• ii. A = {a, b, c} and B = {b, c, a} → A equals B (order doesn't matter in sets)
• iii. A = {1, 2, 5} and B = {1, 2, 5} → A equals B
• iv. A = {x | x(x-1) = 0} and B = {0, 1} → A equals B since x(x-1) = 0 gives x = 0 or x = 1

b. Truth Tables (3 marks)

For propositional variables P, Q, R:

• If BASE[K] denotes the minimum number of times a proposition remains constant
• The truth table algorithm computes BASE[K] for P, Q, and R respectively

c. Logic Module Code (2 marks)

For each propositional formula:

• i. ¬P → ¬P ∨ Q
• ii. P → Q
• iii. P ∧ Q
• iv. P ↔ Q

d. Zermelo-Fraenkel Set Theory (6 marks)

Natural number construction table:

e. Directed Graph (Adjacency Matrix)

For the graph with vertices {a, b, c, d}: The adjacency matrix representation shows connections between vertices.

f. Poset Properties (3 marks)

In any poset P, if meets and joins exist, they must satisfy four lemmas (laws). The absorption law states: x ∧ (x ∨ y) = x

g. Composite Relations (5 marks)

Given relations R and S:

• R is the relation from set A = {1,2,3} to set B = {3,4,5}
• S is the relation from set B = {3,4,5} to set C = {1,2,3,4}
• R = {(1,3), (1,4), (1,5), (2,3), (3,3)}
• S = {(3,1), (3,2), (3,3), (4,3), (4,4)}

First, draw the arrow diagram, then compute the composite relation R∘S.

h. Hasse Diagram (2 marks)

The complement of O is the set of all elements not in O. The complement of {a} includes all other elements in the universal set.

Question 2 (12 marks)

a. Rules of Inference Table (2 marks)

Fill the table with logical rules:

b. Argument Validity (6 marks)

To determine if the argument is valid:

• If horses fly or cows eat grass, then the mosquito is the national bird
• If the mosquito is the national bird, then peanut butter tastes good on hot dogs
• But peanut butter tastes terrible on hot dogs
• Therefore, cows don't eat grass

This requires logical analysis using contraposition and modus tollens.

c. Relation Properties (4 marks)

For relation R = {(x,y) | (x + y = 0)} on real numbers:

• Reflexive: NO (x + x = 0 only when x = 0)
• Symmetric: YES (if x + y = 0, then y + x = 0)
• Antisymmetric: NO (both (1,-1) and (-1,1) are in R, but 1 ≠ -1)
• Transitive: NO (if (a,b) and (b,c) are in R, then a + b = 0 and b + c = 0, but a + c ≠ 0 generally)

Question 3 (12 marks)

a. De Morgan's Law Verification (4 marks)

To prove ¬(P ∧ Q) ⟺ P ∧ ¬Q using truth tables:

The propositions are equivalent as both columns match.

b. Simple Graph Theorem (4 marks)

For a simple graph with e edges and v vertices: Theorem: 2e ≤ v² Proof: In a simple graph, each vertex can connect to at most (v-1) other vertices. The maximum number of edges is C(v,2) = v(v-1)/2. Therefore: e ≤ v(v-1)/2, which gives us 2e ≤ v(v-1) < v².

Question 4 (12 marks)

a. Hasse Diagram Analysis (5 marks)

For each diagram, determine if it's a distributive lattice:

• (i): This is a distributive lattice
• (ii): This is NOT a distributive lattice (diamond shape violates distributivity)
• (iii): This is a distributive lattice
• (iv): This is NOT a distributive lattice (pentagon shape violates distributivity)

b. Poset Diagram Analysis (2 marks)

For the partially ordered set A = {2, 3, 4, 5, 7, 8, 9} with relation ≤:

• Minimum: 2
• Maximum: 9
• Maximal elements: 9
• Minimal elements: 2
• Antichain: {3, 5, 7} (mutually incomparable elements)
• Chain length: 4 (longest chain: 2 → 4 → 8 → 9)

Question 5 (12 marks)

a. Poisson Distribution (2 marks)

For G(t) = e^(3t-3):

• (i) E(X) = 3 (coefficient of t in exponent)
• (ii) Var(X) = 3 (for Poisson distribution, mean = variance)

b. Binary Relations (3 marks)

Draw the digraph of the less-than relation on A = {1, 2, 3, 4, 5}: This creates a directed graph where there's an arrow from i to j if i < j.

c. Existential Quantifiers (3 marks)

For predicates with unique existential quantifiers:

• x < x + 1: ∃x (x < x + 1) - TRUE for all real x
• x = 3: ∃!x (x = 3) - TRUE (exactly one x satisfies this)
• x = x + 1: ∃x (x = x + 1) - FALSE (no real x satisfies this)

d. Graph Theory (1 mark)

The shortest walk from a vertex to another vertex is usually called a shortest path or geodesic.

Question 6 (12 marks)

a. Logical Notation (2 marks)

Express each statement:

• i. x is even or x is greater than 5: E(x) ∨ G(x)
• ii. x is prime then x is greater than 2: P(x) → G(x)
• iii. If x is prime then x is positive: P(x) → Q(x)
• iv. If x is even then x is not odd: E(x) → ¬O(x)

b. Mathematical Induction (7 marks)

Prove that the sum of n natural numbers is given by: ∑(i=1 to n) i = n(n+1)/2

Base case: n = 1 ∑(i=1 to 1) i = 1 = 1(1+1)/2 = 1 ✓

Inductive step: Assume true for n = k ∑(i=1 to k) i = k(k+1)/2

Prove for n = k+1: ∑(i=1 to k+1) i = ∑(i=1 to k) i + (k+1) = k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2

Therefore, the formula holds for all natural numbers.

c. Tree Diagrams (2 marks)

For the three diagrams:

• (i) Tree: This is NOT a tree (contains cycles)
• (ii) Tree: This is a tree (connected, no cycles)
• (iii) Tree: This is a tree (connected, no cycles)

d. Relations on Sets (1 mark)

For sets A = {1,2,3} and B = {3,4,5}:

• R₁ ∩ R₂: Intersection of the two relations
• R₁ ⊕ R₂: Symmetric difference of the relations

Question 7 (12 marks)

a. Relation Properties Table (10 marks)

Fill Table (7) by analyzing each figure:

b. Probability Generating Function (2 marks)

For G(t) = (1/4)t + (1/2)t² + (1/4)t³: This represents a discrete probability distribution where:

• P(X = 1) = 1/4
• P(X = 2) = 1/2
• P(X = 3) = 1/4