Here is the complete solution to all questions, rewritten from scratch in English, with a
different step-by-step approach and detailed explanations.
---
Q−1: [8 marks]
a) [3 marks] Determine whether the following proposition is a tautology:
\bigg( \Big( (x \vee y) \wedge (x \to z) \Big) \wedge (y \to z) \bigg) \to z
Step 1: Rewrite implications using \neg and \vee.
We know p \to q \equiv \neg p \vee q.
So:
x \to z \equiv \neg x \vee z,\qquad y \to z \equiv \neg y \vee z
Step 2: Combine (x \to z) \wedge (y \to z).
(\neg x \vee z) \wedge (\neg y \vee z) \equiv (\neg x \wedge \neg y) \vee z
Using De Morgan: \neg x \wedge \neg y \equiv \neg (x \vee y).
Thus:
(\neg x \vee z) \wedge (\neg y \vee z) \equiv \neg (x \vee y) \vee z \equiv (x \vee y) \to z
Step 3: Substitute back into the original proposition.
The proposition becomes:
\bigg( (x \vee y) \wedge \big( (x \vee y) \to z \big) \bigg) \to z
Step 4: Let p = x \vee y.
Then we have (p \wedge (p \to z)) \to z.
But p \wedge (p \to z) \equiv p \wedge (\neg p \vee z) \equiv (p \wedge \neg p) \vee (p \
wedge z) \equiv F \vee (p \wedge z) \equiv p \wedge z.
Step 5: The proposition simplifies to (p \wedge z) \to z.
This is always true because (A \wedge B) \to B is a tautology.
Answer: The proposition is a tautology.
---
b) [2 marks] Determine whether p \leftrightarrow q and (\neg p \wedge \neg q) \vee (p \
wedge q) are logically equivalent (without truth tables).
Step 1: Start with p \leftrightarrow q.
p \leftrightarrow q \equiv (p \to q) \wedge (q \to p) \equiv (\neg p \vee q) \wedge (\neg q
\vee p)
Step 2: Interpret the meaning.
The expression (\neg p \vee q) \wedge (\neg q \vee p) says:
· If p is true, then \neg p \vee q requires q to be true.
· If p is false, then \neg q \vee p requires \neg q to be true, i.e., q false.
So p and q are either both true or both false. That is exactly:
(p \wedge q) \vee (\neg p \wedge \neg q)
Answer: Yes, they are logically equivalent.
---
c) [1+1+1 marks] True or False with justification.
i. \forall n \in \mathbb{Z}^+,\; n^2 + n + 41 \text{ is prime}
· Check small values:
n = 1: 1 + 1 + 41 = 43 prime.
n = 2: 4 + 2 + 41 = 47 prime.
It works for n = 0 to 39, but fails at n = 40:
40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2
· Answer: False
ii. For integers a, b, c: if a \mid bc, then a \mid b or a \mid c
· Counterexample: Let a = 6, b = 2, c = 3.
bc = 6, so 6 \mid 6 is true. But 6 \nmid 2 and 6 \nmid 3.
· Answer: False
iii. \forall x \in \mathbb{R},\; -|x| \le x \le |x|
· Case 1: x \ge 0: |x| = x, inequality becomes -x \le x \le x.
Right part x \le x is true. Left part -x \le x means 0 \le 2x, true for x \ge 0.
· Case 2: x < 0: |x| = -x, inequality becomes x \le x \le -x.
Left part x \le x is true. Right part x \le -x means 2x \le 0, true for x \le 0.
· Answer: True
---
Q−2: [8 marks]
a) [4 marks] For any sets A, B: If (A \cup B) \subseteq (A \cap B), then A = B.
Proof by double inclusion:
Step 1: Show A \subseteq B.
Take any x \in A. Then x \in A \cup B.
Since A \cup B \subseteq A \cap B, we have x \in A \cap B.
Therefore x \in B. So A \subseteq B.
Step 2: Show B \subseteq A.
Take any x \in B. Then x \in A \cup B.
Since A \cup B \subseteq A \cap B, we have x \in A \cap B.
Therefore x \in A. So B \subseteq A.
Step 3: Conclusion.
A \subseteq B and B \subseteq A imply A = B.
Answer: The statement is true.
---
b) [2 marks] Prove that \lceil x \rceil = -\lfloor -x \rfloor.
Step 1: Let n = \lfloor -x \rfloor. By definition of floor:
n \le -x < n + 1
Step 2: Multiply by -1 (reverse inequalities):
-n \ge x > -n - 1
Rewrite as:
-n - 1 < x \le -n
Step 3: From x \le -n, we see that -n is an upper bound.
From x > -n - 1, we see that -n - 1 is less than x.
Therefore, the smallest integer greater than or equal to x is -n:
\lceil x \rceil = -n
Step 4: Substitute n = \lfloor -x \rfloor:
\lceil x \rceil = -\lfloor -x \rfloor
---
c) [2 marks] If S is the set of primes less than 15, find \displaystyle \sum_{i \in S} i^2.
Step 1: List the primes less than 15:
S = \{2, 3, 5, 7, 11, 13\}
Step 2: Square each:
2^2 = 4,\; 3^2 = 9,\; 5^2 = 25,\; 7^2 = 49,\; 11^2 = 121,\; 13^2 = 169
Step 3: Add step by step:
4 + 9 = 13
13 + 25 = 38
38 + 49 = 87
87 + 121 = 208
208 + 169 = 377
Answer: 377