Unit 2 Logic And Proof Answer Key

Unit 2: Logic and Proof – Comprehensive Answer Key

Understanding logic and proof is the cornerstone of any mathematics curriculum, especially in secondary and early‑college courses. Which means this answer key walks you through the typical problems found in Unit 2, explains the reasoning behind each solution, and highlights common pitfalls to avoid. Use it as a study guide, a self‑check, or a reference when preparing for exams.

Introduction: Why Logic and Proof Matter

Logic provides the language for rigorous mathematical thinking, while proof is the method that turns intuition into accepted truth. Mastering these skills enables you to:

• Translate everyday statements into formal logical notation.
• Identify valid arguments and spot logical fallacies.
• Construct clear, step‑by‑step proofs (direct, indirect, and by contradiction).
• Apply proof techniques to diverse topics such as number theory, geometry, and functions.

The following sections are organized by the most frequently assigned problem types in Unit 2. Each problem is presented with its solution, a brief explanation, and a key takeaway But it adds up..

1. Translating English Statements into Logical Form

Problem 1

Translate the sentence “If a number is divisible by 4, then it is even” into propositional logic using the symbols
(p:) “(n) is divisible by 4” , (q:) “(n) is even”.

Answer: (p \rightarrow q)

Explanation: The word “if…then” corresponds to the conditional connective (\rightarrow). No additional parentheses are needed because there are only two atomic propositions.

Key Takeaway: Identify the antecedent (the “if” part) and the consequent (the “then” part); place them in the order antecedent (\rightarrow) consequent.

Problem 2

Express “Either the function is injective or it is not surjective, but not both” using symbols
(I:) “(f) is injective”, (S:) “(f) is surjective” Not complicated — just consistent..

Answer: ((I \lor \neg S) \land \neg (I \land \neg S))

Explanation:

• “Either … or …” → inclusive disjunction (\lor).
• “Not both” → conjunction with the negation of the simultaneous occurrence.

Key Takeaway: When a statement combines “or” with “but not both,” treat it as an exclusive or: ((A \lor B) \land \neg(A \land B)) The details matter here..

2. Truth Tables and Logical Equivalences

Problem 3

Construct the truth table for ((p \land q) \rightarrow \neg r).

Explanation: A conditional (A \rightarrow B) is false only when (A) is true and (B) is false; all other rows evaluate to true.

Key Takeaway: Remember the only‑false rule for conditionals; it simplifies many truth‑table constructions.

Problem 4

Show that (\neg(p \lor q)) is logically equivalent to (\neg p \land \neg q).

Answer: By De Morgan’s Law, (\neg(p \lor q) \equiv \neg p \land \neg q) Simple, but easy to overlook..

Proof via truth table (summary):

Both columns match, confirming equivalence.

Key Takeaway: De Morgan’s Laws are indispensable for simplifying negations of compound statements.

3. Quantifiers – Translating and Negating

Problem 5

Translate “Every prime number greater than 2 is odd” into symbolic form.

Answer: (\forall x \bigl[(P(x) \land x>2) \rightarrow O(x)\bigr])

where (P(x)): “(x) is prime”, (O(x)): “(x) is odd”.

Explanation: The universal quantifier (\forall) captures “every”. The antecedent combines two properties with (\land); the consequent is the oddness claim That alone is useful..

Key Takeaway: When a statement contains multiple conditions before the conclusion, group them with (\land) inside the antecedent.

Problem 6

Negate the statement (\exists y \forall x (x < y \rightarrow P(x))).

Answer: (\forall y \exists x \bigl(x < y \land \neg P(x)\bigr))

Step‑by‑step:

1. Apply negation to the outer quantifier: (\neg \exists y \equiv \forall y).
2. Negate the inner statement: (\neg \forall x \equiv \exists x).
3. Negate the conditional: (\neg (A \rightarrow B) \equiv A \land \neg B).

Thus we obtain the final form.

Key Takeaway: Negating quantified statements flips each quantifier and transforms conditionals using the equivalence (\neg(A \rightarrow B) \equiv A \land \neg B).

4. Direct Proofs

Problem 7

Prove that the sum of two even integers is even.

Proof:

1. Let (a) and (b) be arbitrary even integers.
2. By definition of evenness, there exist integers (k) and (m) such that (a = 2k) and (b = 2m).
3. Consider the sum: (a + b = 2k + 2m = 2(k + m)).
4. Since (k + m) is an integer, the sum (a + b) is of the form (2) times an integer, i.e., even. ∎

Key Takeaway: Direct proofs often start with the definitions of the concepts involved (here, “even”).

Problem 8

Prove that for all real numbers (x), if (x > 0) then (x^2 > 0).

Proof:

1. Assume (x > 0).
2. Multiplying both sides of the inequality by the positive number (x) preserves the direction: (x \cdot x > 0 \cdot x).
3. Simplify: (x^2 > 0). ∎

Key Takeaway: When the hypothesis guarantees positivity, you may multiply or divide inequalities without flipping the sign.

5. Proof by Contrapositive

Problem 9

Show that if (n^2) is odd, then (n) is odd.

Proof (contrapositive):

1. The contrapositive of “(n^2) odd (\rightarrow) (n) odd” is “(n) even (\rightarrow) (n^2) even”.
2. Assume (n) is even; then (n = 2k) for some integer (k).
3. Square: (n^2 = (2k)^2 = 4k^2 = 2(2k^2)), which is divisible by 2, hence even.
4. Since the contrapositive is true, the original implication holds. ∎

Key Takeaway: Proving the contrapositive is often easier because it lets you work with a direct statement about the hypothesis.

6. Proof by Contradiction

Problem 10

Prove that (\sqrt{2}) is irrational.

Proof (by contradiction):

1. Suppose (\sqrt{2}) is rational. Then there exist coprime integers (a, b) (with (b \neq 0)) such that (\sqrt{2}=a/b).
2. Square both sides: (2 = a^2 / b^2) → (a^2 = 2b^2).
3. Hence (a^2) is even, implying (a) is even (because the square of an odd number is odd). Write (a = 2k).
4. Substitute back: ((2k)^2 = 2b^2) → (4k^2 = 2b^2) → (b^2 = 2k^2).
5. Thus (b^2) is even, so (b) is even.
6. Both (a) and (b) are even, contradicting the assumption that they are coprime.
7. Therefore the original assumption is false; (\sqrt{2}) is irrational. ∎

Key Takeaway: In a contradiction proof, the goal is to derive an impossibility—often a violation of a definition (here, “coprime”) Practical, not theoretical..

7. Induction

Problem 11

Prove by mathematical induction that for all (n \ge 1), (\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}).

Proof:

Base case (n = 1):
(\sum_{k=1}^{1} k = 1) and (\frac{1(1+1)}{2}=1). True.

Inductive hypothesis: Assume the formula holds for some (n = m):
(\displaystyle\sum_{k=1}^{m} k = \frac{m(m+1)}{2}).

Inductive step: Consider (n = m+1).
[ \sum_{k=1}^{m+1} k = \left(\sum_{k=1}^{m} k\right) + (m+1) = \frac{m(m+1)}{2} + (m+1) = \frac{m(m+1) + 2(m+1)}{2} = \frac{(m+1)(m+2)}{2}. ] The right‑hand side is exactly the formula with (n = m+1). Hence the statement holds for (m+1).

By the principle of mathematical induction, the formula is true for all integers (n \ge 1). ∎

Key Takeaway: Induction requires a clear base case and a clean algebraic manipulation that yields the same expression with (n) replaced by (n+1).

8. Set Theory – Proofs Involving Subsets

Problem 12

Prove that (A \subseteq B) and (B \subseteq C) imply (A \subseteq C).

Proof:

1. Let (x) be an arbitrary element of (A).
2. Since (A \subseteq B), (x \in B).
3. Because (B \subseteq C), every element of (B) (including (x)) belongs to (C).
4. Therefore (x \in C).
5. As the choice of (x) was arbitrary, every element of (A) lies in (C); thus (A \subseteq C). ∎

Key Takeaway: Subset transitivity follows directly from the definition of “subset” and does not require additional properties.

9. Common Mistakes and How to Avoid Them

FAQ

Q1: When should I use a proof by contrapositive instead of a direct proof?
A: Choose the contrapositive when the negation of the conclusion is easier to work with than the conclusion itself. For statements of the form “If (P) then (Q)”, examine whether “If not (Q) then not (P)” leads to a straightforward chain of definitions Not complicated — just consistent..

Q2: How do I decide whether a proof requires a contradiction?
A: Contradiction is powerful when the statement asserts non‑existence or uniqueness, or when assuming the opposite immediately violates a known property (e.g., parity, coprimality). If a direct construction feels forced, try contradiction.

Q3: What is the difference between a valid argument and a sound argument?
A: Validity concerns form—the conclusion follows logically from the premises. Soundness adds the requirement that the premises are actually true. An argument can be valid but unsound if any premise is false.

Q4: Are De Morgan’s Laws applicable to quantified statements?
A: Yes. They extend to quantifiers:
(\neg\forall x,P(x) \equiv \exists x,\neg P(x)) and
(\neg\exists x,P(x) \equiv \forall x,\neg P(x)).
These are the quantifier versions of De Morgan’s transformations Nothing fancy..

Q5: How can I improve my proof-writing speed for exams?
A: Practice the following routine:

1. Restate the problem in your own words.
2. Identify the proof technique that matches the statement’s structure.
3. Write a one‑sentence plan (e.g., “Assume (n) is even, write (n=2k)…”).
4. Execute the plan, keeping each step justified by a definition or previously proven theorem.
5. Conclude with a clear “∎” or “QED”.

Conclusion

Unit 2’s focus on logic and proof equips you with the analytical tools required for all higher‑level mathematics. On the flip side, by mastering translation between English and symbolic forms, constructing truth tables, handling quantifiers, and applying diverse proof strategies, you develop a disciplined mindset that transcends any single topic. Use this answer key not merely as a checklist, but as a learning companion: read each solution, internalize the reasoning, and then attempt similar problems without looking. Consistent practice will transform the abstract symbols into intuitive language, enabling you to tackle even the most involved mathematical arguments with confidence Not complicated — just consistent..