Discrete Structures Exam Solutions

Question 1 (22 marks)

a. Set equality statements (2 marks)

For each statement, we need to determine if Set A equals Set B:

i. A = {a, b, b, c}, B = {a, b, c}

• Answer: TRUE - Sets only contain unique elements, so A = {a, b, c} = B

ii. A = {a, b, c}, B = {b, c, a}

• Answer: TRUE - Order doesn't matter in sets, so A = B

iii. A = {1, 2, 3}, B = {1, 2, 3}

• Answer: TRUE - Identical sets

iv. A = {x | x(x - 1) = 0}, B = {0, 1}

• Answer: TRUE - Solving x(x-1) = 0 gives x = 0 or x = 1, so A = {0, 1} = B

b. Set operations with relations (3 marks)

Given: A = {1, 2, 3}, B = {3, 4, 5} R1 = {(1,3), (1,4), (3,3)} R2 = {(2,3), (2,4), (3,3), (2,5)}

i. R1 ∪ R2 = {(1,3), (1,4), (3,3), (2,3), (2,4), (2,5)}

ii. R1 ∩ R2 = {(3,3)}

iii. R1 \ R2 = {(1,3), (1,4)}

iv. R2 \ R1 = {(2,3), (2,4), (2,5)}

v. R1 ⊕ R2 = {(1,3), (1,4), (2,3), (2,4), (2,5)} (symmetric difference)

vi. A × B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5)}

c. Resolution Principle (6 marks)

Argument: If today is Tuesday, then I have a test in Computer science or a test in Econ. If my Econ professor is sick, then I will not have a test in Econ. Today is Tuesday and my Econ professor is sick. Therefore, I have a test in Computer science.

Let:

• P: Today is Tuesday
• C: I have a test in Computer science
• E: I have a test in Econ
• S: My Econ professor is sick

Premises in CNF:

1. P → (C ∨ E) ≡ ¬P ∨ C ∨ E
2. S → ¬E ≡ ¬S ∨ ¬E
3. P (given)
4. S (given)

Conclusion: C

Resolution steps:

• From premise 3 and clause 1: C ∨ E (resolving ¬P with P)
• From premise 4 and clause 2: ¬E (resolving ¬S with S)
• From C ∨ E and ¬E: C (resolving E with ¬E)

Therefore, the argument is valid.

Question 2 (12 marks)

a. Logic table completion (2 marks)

The table shows various logical rules. Key completions:

• Modus ponens: P, P→Q ⊢ Q
• Modus tollens: ¬Q, P→Q ⊢ ¬P
• Disjunctive syllogism: P∨Q, ¬P ⊢ Q
• Conjunction: P, Q ⊢ P∧Q
• De Morgan's: ¬(P∨Q) ≡ ¬P ∧ ¬Q

b. Logical argument validity (6 marks)

Argument:

• All men are mortal
• Socrates is a man
• ∴ Socrates is mortal

Analysis: This is a valid syllogism using universal instantiation. If all members of set "men" have property "mortal" and Socrates is in set "men", then Socrates must have property "mortal".

c. Relation properties (4 marks)

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

Reflexive: NO - For reflexivity, we need (x,x) ∈ R for all x, which means x + x = 0, so x = 0. Only true for x = 0.

Symmetric: YES - If (x,y) ∈ R, then x + y = 0, which means y + x = 0, so (y,x) ∈ R.

Antisymmetric: NO - We have (1,-1) ∈ R and (-1,1) ∈ R, but 1 ≠ -1.

Transitive: NO - We have (1,-1) ∈ R and (-1,1) ∈ R, but (1,1) ∉ R since 1 + 1 ≠ 0.

Question 3 (12 marks)

a. Permutation and combination (4 marks)

Problem: Choose 2 books of different languages from 5 Latin, 7 Greek, and 10 French books.

Solution:

• Latin and Greek: C(5,1) × C(7,1) = 5 × 7 = 35
• Latin and French: C(5,1) × C(10,1) = 5 × 10 = 50
• Greek and French: C(7,1) × C(10,1) = 7 × 10 = 70

Total: 35 + 50 + 70 = 155 ways

Question 4 (12 marks)

a. Hasse diagram analysis (5 marks)

Looking at the cube diagram, this represents a Boolean lattice with vertices labeled with letters. The structure shows:

• Bottom element: o
• Top element: s
• The lattice represents subset relationships

b. Partially ordered set analysis (7 marks)

Given: A = {1, 2, 3, 4, 5, 6, 7, 8, 9} with divisibility relation

i. Poset diagram: Elements connected by divisibility (e.g., 1 divides all, 2 divides 4, 6, 8, etc.)

ii. Minimum elements: {1} (1 divides all others)

iii. Maximum elements: {5, 7, 9} (not divisible by any other element in set)

iv. Maximal elements: {5, 7, 9}

v. 3 ∨ 5: No upper bound in this poset (3 and 5 are coprime)

vi. Antichains: Sets of mutually incomparable elements, e.g., {5, 7, 9}

vii. Longest chain: 1 → 2 → 4 → 8 (length 4)

viii. 8 ∧ 6 = 2 (greatest common divisor)

Question 5 (12 marks)

a. Minimum spanning tree using Prim's algorithm (4 marks)

Starting from S:

1. Start with S
2. Add edge S-A (weight 1) → Tree: {S, A}
3. Add edge A-C (weight 3) → Tree: {S, A, C}
4. Add edge C-D (weight 3) → Tree: {S, A, C, D}
5. Add edge A-B (weight 6) → Tree: {S, A, C, D, B}
6. Add edge B-T (weight 5) → Tree: {S, A, C, D, B, T}

MST edges: S-A(1), A-C(3), C-D(3), A-B(6), B-T(5) Total weight: 1 + 3 + 3 + 6 + 5 = 18

Question 6 (12 marks)

a. Proof by induction (5 marks)

Statement: R = {(a,b,c) | a + b = c}

Base case (n=1): R¹ contains (a,b,c) where a + b = c Inductive step: Assume true for n, prove for n+1 First three elements: (0,0,0), (0,1,1), (1,0,1)

b. Sum formula proof (7 marks)

Prove: ∑(i=1 to n) i = n(n+1)/2

Base case: n=1: ∑(i=1 to 1) i = 1, and 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 n ≥ 1.

Question 7 (12 marks)

a. Population subsets (4 marks)

Given: Population of Mando = 8300 (2500 adult females, 3800 children)

i. Subsets of concern: Adult females, children, adult males ii. Adults in Mando: 8300 - 3800 = 4500 iii. Adult males: 4500 - 2500 = 2000 iv. Females and children: 2500 + 3800 = 6300

b. Resolution principle application (3 marks)

Premises: "Paula is out for a trip or it is not raining" and "It is raining or Rafael is cooking"

Conclusion: If Paula is not out for a trip, then Rafael is cooking.

Let: P = Paula is out, R = It is raining, C = Rafael is cooking Premises: P ∨ ¬R, R ∨ C To prove: ¬P → C

Resolution: From P ∨ ¬R and R ∨ C, we get P ∨ C (resolving ¬R with R) This gives us ¬P → C, which is our conclusion.

c. Table completion and relation properties (5 marks)

The table shows different types of relations with their properties (reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive). Students need to analyze each figure and mark appropriate properties.

d. Zermelo-Fraenkel set theory (6 marks)

Natural number definitions:

• Step 0 = { }: ∅ (empty set) → 0
• Step 1 = {∅}: {0} → 1
• Step (i) = {∅}: {0} → 2
• Step (ii) = {∅,{∅}}: {0,1} → 3
• Step (v) = {∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}: {0,1,2,3} → 4

e. Kleene closure (3 marks)

Set A = {ab, bc} First four elements of A:*

1. ε (empty string)
2. ab
3. bc
4. abab

f. Circular arrangements (3 marks)

Problem: n people standing in a ring Solution: (n-1)! ways

Explanation: Fix one person's position to account for rotational symmetry, then arrange the remaining (n-1) people, giving (n-1)! arrangements.