BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 5 — Questions and Answers
Question 1: Which of the following correctly expresses the negation of 'P if and only if Q'?
- ¬P if and only if ¬Q
- P if and only if ¬Q
- (P ∧ ¬Q) ∨ (¬P ∧ Q) (Correct answer)
- (P ∨ Q) ∧ (¬P ∨ ¬Q)
Correct answer: (P ∧ ¬Q) ∨ (¬P ∧ Q)
¬(P ↔ Q) ≡ (P ∧ ¬Q) ∨ (¬P ∧ Q), meaning exactly one of P, Q is true.
Question 2: A set S is said to be closed under an operation * if:
- * is associative on S
- Applying * to elements of S always yields an element of S (Correct answer)
- S contains an identity element for *
- * is commutative on S
Correct answer: Applying * to elements of S always yields an element of S
Closure means for all a, b ∈ S, the result a * b is also in S, keeping results within the set.
Question 3: In proof by contrapositive, to prove P ⟹ Q one instead proves:
- Q ⟹ P
- ¬P ⟹ ¬Q
- ¬Q ⟹ ¬P (Correct answer)
- P ∧ ¬Q leads to contradiction
Correct answer: ¬Q ⟹ ¬P
Since P ⟹ Q is logically equivalent to its contrapositive ¬Q ⟹ ¬P, proving the latter establishes the original implication.
Question 4: Which of the following is NOT a valid rule of inference in classical propositional logic?
- Modus ponens: P, P ⟹ Q ∴ Q
- Modus tollens: ¬Q, P ⟹ Q ∴ ¬P
- Affirming the consequent: Q, P ⟹ Q ∴ P (Correct answer)
- Hypothetical syllogism: P ⟹ Q, Q ⟹ R ∴ P ⟹ R
Correct answer: Affirming the consequent: Q, P ⟹ Q ∴ P
Affirming the consequent is a formal fallacy; knowing Q is true and P ⟹ Q does not allow us to conclude P.
Question 5: The Well-Ordering Principle and Mathematical Induction over ℕ are:
- Contradictory to each other
- Logically equivalent (Correct answer)
- Independent axioms requiring different assumptions
- Only equivalent when restricted to finite sets
Correct answer: Logically equivalent
The Well-Ordering Principle (every non-empty subset of ℕ has a minimum) and the Principle of Mathematical Induction are logically equivalent; each can be derived from the other.
Question 6: A proposition that can be neither proved nor disproved within a given formal system is called:
- A paradox
- An undecidable proposition (Correct answer)
- A tautology
- A lemma
Correct answer: An undecidable proposition
An undecidable (or independent) proposition is one for which the system can prove neither it nor its negation, as illustrated by the Continuum Hypothesis relative to ZFC.
Question 7: Which of the following best describes a constructive proof?
- A proof that shows existence by contradiction
- A proof that explicitly constructs or exhibits the object claimed to exist (Correct answer)
- A proof that uses exhaustive case analysis
- A proof valid only in classical logic
Correct answer: A proof that explicitly constructs or exhibits the object claimed to exist
A constructive proof provides an explicit example or algorithm that witnesses the existence claim, rather than merely ruling out non-existence.
BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 5
Which of the following correctly expresses the negation of 'P if and only if Q'?