BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 3 — Questions and Answers
Question 1: Which rule of inference allows you to conclude Q from the premises P and P ⟹ Q?
- Modus tollens
- Disjunctive syllogism
- Modus ponens (Correct answer)
- Hypothetical syllogism
Correct answer: Modus ponens
Modus ponens states: given P and P ⟹ Q, we may conclude Q directly.
Question 2: In mathematical logic, a formula is called a tautology if:
- It is false under every interpretation
- It is true under every interpretation (Correct answer)
- It is satisfiable but not valid
- It contains no variables
Correct answer: It is true under every interpretation
A tautology is a propositional formula that evaluates to true for all possible truth-value assignments to its variables.
Question 3: Which of the following correctly describes the strong form of mathematical induction?
- Prove P(1) and that P(k) ⟹ P(k+1)
- Prove P(0) and that P(n) holds for all n ≥ 0
- Prove P(1) and that P(1) ∧ … ∧ P(k) ⟹ P(k+1) (Correct answer)
- Prove P(n) directly for all n
Correct answer: Prove P(1) and that P(1) ∧ … ∧ P(k) ⟹ P(k+1)
Strong induction assumes all of P(1),…,P(k) are true (not just P(k)) to conclude P(k+1).
Question 4: A function f: A → B is injective (one-to-one) if:
- Every element of B is mapped to by at least one element of A
- f(a₁) = f(a₂) implies a₁ = a₂ (Correct answer)
- f maps A onto all of B
- f has an inverse function
Correct answer: f(a₁) = f(a₂) implies a₁ = a₂
Injectivity means distinct inputs produce distinct outputs: f(a₁) = f(a₂) ⟹ a₁ = a₂.
Question 5: De Morgan's law for quantifiers states that ¬(∀x P(x)) is equivalent to:
- ∀x ¬P(x)
- ∃x P(x)
- ¬∃x P(x)
- ∃x ¬P(x) (Correct answer)
Correct answer: ∃x ¬P(x)
Negating a universal quantifier yields an existential: ¬(∀x P(x)) ≡ ∃x ¬P(x).
Question 6: Which of the following sets is countably infinite?
- The set of all real numbers ℝ
- The set of all irrational numbers
- The power set of ℕ
- The set of all rational numbers ℚ (Correct answer)
Correct answer: The set of all rational numbers ℚ
ℚ is countably infinite; a diagonal listing argument shows a bijection between ℚ and ℕ.
Question 7: In a formal proof system, what does it mean for the system to be complete?
- Every statement is either provable or refutable
- Every provable statement is true in all models
- Every tautology is provable within the system (Correct answer)
- No contradictions can be derived
Correct answer: Every tautology is provable within the system
Completeness (semantic) means every logically valid formula (true in all models) is provable; Gödel proved this for first-order logic.
BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 3
Which rule of inference allows you to conclude Q from the premises P and P ⟹ Q?