Q1 [10 marks]
Problem:
Suppose ( u ) represents “you understand the material” and ( s ) represents “you study the theory”. Write the following compound proposition using ( u ), ( s ), and appropriate connectives.
“Studying the theory is sufficient for understanding the material.”
Answer:
The phrase “Studying the theory is sufficient for understanding the material” means that if you study the theory, then you will understand the material. In logical terms, this is an implication from ( s ) to ( u ).
[
s \rightarrow u
]
Q2 [10 marks]
Problem:
Prove that
[
\neg \left[ r \lor \left( q \land \left( \neg r \rightarrow \neg p \right) \right) \right] \equiv \neg r \land \left( p \lor \neg q \right)
]
by using a truth table.
Answer:
We will construct a truth table for all possible truth values of the propositions ( p ), ( q ), and ( r ), and show that both sides of the equivalence have the same truth values.
Truth Table:
+----+----+----+-----+-----+-----+------------------+----------------------------+------------------------------+-----+--------+-------------------------+-----+
| p | q | r | ¬p | ¬q | ¬r | ¬r → ¬p | q ∧ (¬r → ¬p) | r ∨ [q ∧ (¬r → ¬p)] | LHS | p ∨ ¬q | ¬r ∧ (p ∨ ¬q) | RHS |
+----+----+----+-----+-----+-----+------------------+----------------------------+------------------------------+-----+--------+-------------------------+-----+
| T | T | T | F | F | F | F → F = T | T ∧ T = T | T ∨ T = T | F | T | F ∧ T = F | F |
| T | T | F | F | F | T | T → F = F | T ∧ F = F | F ∨ F = F | T | T | T ∧ T = T | T |
| T | F | T | F | T | F | F → F = T | F ∧ T = F | T ∨ F = T | F | T | F ∧ T = F | F |
| T | F | F | F | T | T | T → F = F | F ∧ F = F | F ∨ F = F | T | T | T ∧ T = T | T |
| F | T | T | T | F | F | F → T = T | T ∧ T = T | T ∨ T = T | F | F | F ∧ F = F | F |
| F | T | F | T | F | T | T → T = T | T ∧ T = T | F ∨ T = T | F | F | T ∧ F = F | F |
| F | F | T | T | T | F | F → T = T | F ∧ T = F | T ∨ F = T | F | T | F ∧ T = F | F |
| F | F | F | T | T | T | T → T = T | F ∧ T = F | F ∨ F = F | T | T | T ∧ T = T | T |
+----+----+----+-----+-----+-----+------------------+----------------------------+------------------------------+-----+--------+-------------------------+-----+
**Explanation:**
- **Columns \( ¬p \), \( ¬q \), and \( ¬r \):** Negations of \( p \), \( q \), and \( r \).
- **Column \( ¬r → ¬p \):** The implication \( \neg r \rightarrow \neg p \). Remember that an implication \( A \rightarrow B \) is false only when \( A \) is true and \( B \) is false; otherwise, it is true.
- **Column \( q ∧ (¬r → ¬p) \):** The conjunction of \( q \) and \( \neg r \rightarrow \neg p \).
- **Column \( r ∨ [q ∧ (¬r → ¬p)] \):** The disjunction of \( r \) and the result from the previous column.
- **Column LHS:** The negation of \( r ∨ [q ∧ (¬r → ¬p)] \).
- **Column \( p ∨ ¬q \):** The disjunction of \( p \) and \( \neg q \).
- **Column RHS:** The conjunction of \( \neg r \) and \( p ∨ \neg q \).
**Result:**
By comparing the LHS and RHS columns, we see that they have the same truth values for all possible combinations of \( p \), \( q \), and \( r \). Therefore, the equivalence is proven.
---
**Q3 [10 marks]**
**Problem:**
Prove that
\[
\neg \left[ r \lor \left( q \land \left( \neg r \rightarrow \neg p \right) \right) \right] \equiv \neg r \land \left( p \lor \neg q \right)
\]
by using a series of logical equivalences.
**Answer:**
We will start with the left-hand side and simplify step by step using logical equivalences to reach the right-hand side.
**Proof:**
1. **Start with the left-hand side (LHS):**
\[
\neg \left[ r \lor \left( q \land \left( \neg r \rightarrow \neg p \right) \right) \right]
\]
2. **Rewrite the implication \( \neg r \rightarrow \neg p \) as \( r \lor \neg p \):**
\[
\neg r \rightarrow \neg p \equiv r \lor \neg p
\]
Substituting back:
\[
\neg \left[ r \lor \left( q \land \left( r \lor \neg p \right) \right) \right]
\]
3. **Distribute \( q \) over the disjunction inside the parentheses:**
\[
q \land \left( r \lor \neg p \right) \equiv \left( q \land r \right) \lor \left( q \land \neg p \right)
\]
So the expression becomes:
\[
\neg \left[ r \lor \left( \left( q \land r \right) \lor \left( q \land \neg p \right) \right) \right]
\]
4. **Simplify \( r \lor \left( q \land r \right) \):**
Since \( r \lor \left( q \land r \right) \equiv r \), because \( q \land r \) is a subset of \( r \).
So we have:
\[
\neg \left[ r \lor \left( q \land \neg p \right) \right]
\]
5. **Now, our expression is:**
\[
\neg \left[ r \lor \left( q \land \neg p \right) \right]
\]
6. **Apply De Morgan's Law to the negation of a disjunction:**
\[
\neg \left( A \lor B \right ) \equiv \neg A \land \neg B
\]
Applying this to our expression:
\[
\neg r \land \neg \left( q \land \neg p \right)
\]
7. **Simplify \( \neg \left( q \land \neg p \right) \) using De Morgan's Law for negation of a conjunction:**
\[
\neg \left( q \land \neg p \right ) \equiv \neg q \lor p
\]
8. **Substitute back into the expression:**
\[
\neg r \land \left( \neg q \lor p \right )
\]
9. **Rewriting the expression for clarity:**
\[
\neg r \land \left( p \lor \neg q \right )
\]
**Conclusion:**
We have shown that:
\[
\neg \left[ r \lor \left( q \land \left( \neg r \rightarrow \neg p \right) \right) \right] \equiv \neg r \land \left( p \lor \neg q \right)
\]
---
**Q4 [10 marks]**
**Problem:**
Suppose that \( A \) is the set of sophomores at your school and \( B \) is the set of students in discrete mathematics at your school. Express each of these sets in terms of \( A \) and \( B \).
**a) The set of sophomores taking discrete mathematics in your school**
**Answer:**
This set is the intersection of \( A \) and \( B \):
\[
A \cap B
\]
---
**b) The set of sophomores at your school who are not taking discrete mathematics**
**Answer:**
This set includes sophomores who are not in discrete mathematics, which is the difference between \( A \) and \( B \) or the intersection of \( A \) and the complement of \( B \):
\[
A \setminus B = A \cap B'
\]
---
**c) The set of students at your school who either are sophomores or are taking discrete mathematics**
**Answer:**
This set is the union of \( A \) and \( B \):
\[
A \cup B
\]
---
**d) The set of students at your school who either are not sophomores or are not taking discrete mathematics**
**Answer:**
This set is the union of the complements of \( A \) and \( B \):
\[
A' \cup B'
\]
Alternatively, by De Morgan's Law:
\[
A' \cup B' = \left( A \cap B \right )'
\]
---
**Q5 [15 marks]**
**Problem:**
Give a big-\( O \) estimate for each of these functions. Use a simple function in the big-\( O \) estimate.
**a) \( f(n) = 3n + n^3 + 4 \)**
**Answer:**
- The term \( n^3 \) dominates the growth of the function for large \( n \).
- The terms \( 3n \) and 4 become insignificant compared to \( n^3 \) as \( n \) increases.
- Therefore:
\[
f(n) = O(n^3)
\]
---
**b) \( f(n) = 1 + 2 + 3 + \dots + n \)**
**Answer:**
- The sum of the first \( n \) positive integers is:
\[
f(n) = \frac{n(n + 1)}{2}
\]
- The highest-degree term is \( \frac{n^2}{2} \).
- Therefore:
\[
f(n) = O(n^2)
\]
---
**c) \( f(n) = \log_{10}(2n) + 10^{10} n^2 \)**
**Answer:**
- The term \( 10^{10} n^2 \) dominates the growth of the function for large \( n \).
- The logarithmic term \( \log_{10}(2n) \) grows much more slowly.
- Therefore:
\[
f(n) = O(n^2)
\]
---
**Q6 [15 marks]**
**Problem:**
Use the definition of big-\( O \) to prove that \( f(x) = 3x + x^3 + 4 \) is \( O(x^3) \).
**Answer:**
**Definition:**
A function \( f(x) \) is \( O(g(x)) \) if there exist positive constants \( C \) and \( x_0 \) such that for all \( x \geq x_0 \):
\[
|f(x)| \leq C |g(x)|
\]
**Proof:**
Let \( g(x) = x^3 \).
For \( x \geq 1 \):
1. \( 3x \leq 3x^3 \) since \( x^3 \geq x \) when \( x \geq 1 \).
2. \( 4 \leq 4x^3 \) for the same reason.
Adding up:
\[
f(x) = 3x + x^3 + 4 \leq 3x^3 + x^3 + 4x^3 = 8x^3
\]
Therefore, we can choose constants:
- \( C = 8 \)
- \( x_0 = 1 \)
So, for all \( x \geq 1 \):
\[
f(x) \leq 8x^3
\]
Thus, by definition, \( f(x) = O(x^3) \).
---
**Q7 [10 marks]**
**Problem:**
Suppose an algorithm takes a sequence of \( n \) (\( n \geq 2 \)) integers and determines if it contains an integer that is a repeat of the first integer in the list. Find the complexity function for the:
**a) Best case analysis.**
**Answer:**
- **Best Case Scenario:**
- The first integer repeats immediately, i.e., the second integer is the same as the first.
- The algorithm makes one comparison and finds the repeat.
- **Complexity Function:**
\[
T(n) = O(1)
\]
- **Explanation:**
- The time taken is constant and does not depend on \( n \).
---
**b) Worst case analysis.**
**Answer:**
- **Worst Case Scenario:**
- The first integer does not repeat in the sequence.
- The algorithm must compare the first integer with each of the remaining \( n - 1 \) integers.
- **Number of Comparisons:**
\[
n - 1
\]
- **Complexity Function:**
\[
T(n) = O(n)
\]
- **Explanation:**
- The time taken grows linearly with the size of the input sequence.