BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 2 — Questions and Answers
Question 1: Which proof technique assumes the negation of the conclusion and derives a contradiction?
- Proof by induction
- Proof by contrapositive
- Proof by contradiction (Correct answer)
- Direct proof
Correct answer: Proof by contradiction
Proof by contradiction (reductio ad absurdum) assumes ¬P and derives a contradiction, thereby establishing P.
Question 2: In predicate logic, what does the statement ∀x∃y P(x,y) mean?
- There exists an x such that for all y, P(x,y) holds
- For all x, there exists a y such that P(x,y) holds (Correct answer)
- For all x and y, P(x,y) holds
- There exist x and y such that P(x,y) holds
Correct answer: For all x, there exists a y such that P(x,y) holds
∀x∃y P(x,y) reads 'for every x, there is some y (possibly depending on x) for which P(x,y) is true.'
Question 3: A relation R on a set A is an equivalence relation if it is:
- Reflexive, symmetric, and transitive (Correct answer)
- Reflexive, antisymmetric, and transitive
- Symmetric and transitive only
- Reflexive and antisymmetric only
Correct answer: Reflexive, symmetric, and transitive
An equivalence relation must satisfy reflexivity (aRa), symmetry (aRb ⟹ bRa), and transitivity (aRb ∧ bRc ⟹ aRc).
Question 4: Which of the following is the contrapositive of 'If P then Q'?
- If Q then P
- If ¬P then ¬Q
- If ¬Q then ¬P (Correct answer)
- If ¬Q then P
Correct answer: If ¬Q then ¬P
The contrapositive of P ⟹ Q is ¬Q ⟹ ¬P, which is logically equivalent to the original.
Question 5: In a well-ordered set, every non-empty subset has:
- A maximum element
- A least upper bound
- A minimum element (Correct answer)
- An infimum
Correct answer: A minimum element
A well-ordered set is one in which every non-empty subset has a least (minimum) element under the given ordering.
Question 6: Which logical connective makes 'P ⟹ Q' false only when P is true and Q is false?
- Biconditional
- Disjunction
- Conditional (implication) (Correct answer)
- Conjunction
Correct answer: Conditional (implication)
The conditional P ⟹ Q is false exactly when the hypothesis P is true but the conclusion Q is false.
Question 7: What is the cardinality of the power set of a finite set with n elements?
- n²
- 2n
- n!
- 2ⁿ (Correct answer)
Correct answer: 2ⁿ
The power set of an n-element set contains exactly 2ⁿ subsets, one for each binary choice of including or excluding each element.
BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 2
Which proof technique assumes the negation of the conclusion and derives a contradiction?