Unit 2 Test Study Guide Logic And Proof Answers

Embarking on a journey through logic and proofs can feel like navigating a complex maze, especially when preparing for a Unit 2 test. To conquer this challenge, understanding the fundamental concepts and practicing various proof techniques are essential. This study guide will provide a comprehensive overview of logic and proofs, complete with detailed explanations, examples, and strategies to tackle common problems, ensuring you're well-equipped to ace your test.

Understanding the Building Blocks: Logic

Logic forms the bedrock of mathematical reasoning. It provides a framework for constructing valid arguments and drawing sound conclusions. Mastering the core elements of logic is crucial before diving into the world of proofs.

Statements and Truth Values

At the heart of logic lies the statement, a declarative sentence that can be either true or false, but not both.

• For example, "The Earth is round" is a true statement, while "The Earth is flat" is a false statement.

Statements are assigned truth values, denoted by T for true and F for false. These values determine the validity of logical arguments.

Logical Connectives: Combining Statements

Logical connectives are operators that combine simple statements to form more complex ones. Understanding these connectives is paramount to constructing and interpreting logical arguments.

• Negation (~): Reverses the truth value of a statement. If p is true, then ~p is false, and vice versa.
• Conjunction (∧): Represents "and." The statement p ∧ q is true only if both p and q are true.
• Disjunction (∨): Represents "or." The statement p ∨ q is true if either p or q or both are true.
• Conditional (→): Represents "if...then..." The statement p → q is false only if p is true and q is false. Otherwise, it's true. p is called the hypothesis and q is called the conclusion.
• Biconditional (↔): Represents "if and only if" (often abbreviated as "iff"). The statement p ↔ q is true only if p and q have the same truth value (both true or both false).

Truth Tables: Mapping Truth Values

Truth tables are invaluable tools for analyzing the truth values of compound statements. They systematically display all possible combinations of truth values for the individual statements and the resulting truth value of the compound statement.

Here's a truth table for the conditional statement p → q:

Notice that the conditional statement is only false when the hypothesis (p) is true and the conclusion (q) is false. This is a crucial point to remember!

Tautologies, Contradictions, and Contingencies

Based on their truth tables, statements can be classified into three categories:

• Tautology: A statement that is always true, regardless of the truth values of its components.
• Contradiction: A statement that is always false, regardless of the truth values of its components.
• Contingency: A statement whose truth value depends on the truth values of its components.

Logical Equivalence

Two statements are logically equivalent if they have the same truth values in all possible cases. This means their truth tables are identical. Logical equivalence is denoted by ≡. Understanding logical equivalences allows you to simplify complex statements and rewrite them in more convenient forms.

• Example: p → q ≡ ~p ∨ q (This is a very important equivalence to remember!)

Quantifiers: Expressing Generality

Quantifiers are used to express the extent to which a predicate is true over a range of elements.

• Universal Quantifier (∀): Represents "for all" or "for every." ∀x, P(x) means that the predicate P(x) is true for all values of x in the domain.
• Existential Quantifier (∃): Represents "there exists" or "for some." ∃x, P(x) means that there exists at least one value of x in the domain for which the predicate P(x) is true.

Negating quantified statements involves switching the quantifier and negating the predicate:

• ~(∀x, P(x)) ≡ ∃x, ~P(x)
• ~(∃x, P(x)) ≡ ∀x, ~P(x)

Delving into Proofs: The Art of Persuasion

Proofs are rigorous arguments that demonstrate the truth of a statement based on established facts, definitions, and previously proven theorems. Mastering proof techniques is essential for success in higher-level mathematics.

Direct Proof

The direct proof is the most straightforward proof technique. You start with the given premises (hypotheses) and use logical deductions, definitions, and known theorems to arrive at the conclusion.

• Example: Prove that if n is an even integer, then n² is also an even integer.

  • Proof: Assume n is an even integer. This means n can be written as n = 2k for some integer k. Then, n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is also an even integer. Therefore, if n is an even integer, then n² is also an even integer.

Indirect Proof: Proof by Contrapositive

The proof by contrapositive relies on the logical equivalence between a conditional statement and its contrapositive. The contrapositive of p → q is ~q → ~p. To prove p → q using the contrapositive, you assume ~q and show that it implies ~p.

• Example: Prove that if n² is an even integer, then n is also an even integer. (This is the converse of the previous example!)

  • Proof: We will prove the contrapositive: if n is not an even integer (i.e., n is odd), then n² is not an even integer (i.e., n² is odd). Assume n is an odd integer. This means n can be written as n = 2k + 1 for some integer k. Then, n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. Since 2k² + 2k is an integer, n² is also an odd integer. Therefore, if n is not an even integer, then n² is not an even integer. Since we have proven the contrapositive, we have also proven the original statement: if n² is an even integer, then n is also an even integer.

Indirect Proof: Proof by Contradiction

The proof by contradiction involves assuming the negation of the statement you want to prove and then showing that this assumption leads to a contradiction. A contradiction is a statement that is both true and false at the same time, which is impossible. This contradiction demonstrates that the initial assumption was false, and therefore the original statement must be true.

• Example: Prove that √2 is irrational.

  • Proof: Assume, for the sake of contradiction, that √2 is rational. This means that √2 can be written as a fraction a/ b, where a and b are integers and a/ b is in its simplest form (i.e., a and b have no common factors other than 1). Then, √2 = a/ b. Squaring both sides, we get 2 = a²/ b², which implies a² = 2b². This means a² is an even integer. From the previous proof (or its contrapositive), we know that if a² is even, then a must also be even. So, we can write a = 2k for some integer k. Substituting this into a² = 2b², we get (2k)² = 2b², which simplifies to 4k² = 2b², and further to b² = 2k². This means b² is also an even integer, and therefore b must also be even. But this means that both a and b are even, which contradicts our initial assumption that a/ b was in its simplest form (i.e., a and b have no common factors other than 1). Since our assumption leads to a contradiction, it must be false. Therefore, √2 is irrational.

Proof by Induction

Proof by induction is a powerful technique used to prove statements about natural numbers (1, 2, 3, ...). It involves two steps:

• Base Case: Show that the statement is true for the smallest natural number (usually 1).
• Inductive Step: Assume that the statement is true for some arbitrary natural number k (called the inductive hypothesis) and then show that it must also be true for the next natural number k + 1.

If you can successfully complete both the base case and the inductive step, then the statement is true for all natural numbers.

• Example: Prove that the sum of the first n natural numbers is n(n + 1)/2. That is, prove that 1 + 2 + 3 + ... + n = n(n + 1)/2 for all natural numbers n.

  • Proof:
    • Base Case (n = 1): The sum of the first 1 natural number is simply 1. The formula gives 1(1+1)/2 = 1(2)/2 = 1. So the formula holds for n = 1.
    • Inductive Step: Assume that the formula holds for some arbitrary natural number k. That is, assume that 1 + 2 + 3 + ... + k = k(k + 1)/2. We need to show that the formula also holds for k + 1. That is, we need to show that 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2. Starting with the left-hand side of the equation, we have: 1 + 2 + 3 + ... + k + (k + 1) = (k(k + 1)/2) + (k + 1) (by the inductive hypothesis) = (k(k + 1) + 2(k + 1))/2 = (k² + k + 2k + 2)/2 = (k² + 3k + 2)/2 = (k + 1)(k + 2)/2 This is exactly the right-hand side of the equation, so we have shown that if the formula holds for k, it also holds for k + 1.
    • Conclusion: Since we have proven both the base case and the inductive step, the formula 1 + 2 + 3 + ... + n = n(n + 1)/2 holds for all natural numbers n.

Common Mistakes in Proofs

• Begging the Question (Circular Reasoning): Assuming the conclusion you are trying to prove as one of your premises.
• Affirming the Consequent: Assuming that if p → q is true and q is true, then p must be true. This is a fallacy.
• Denying the Antecedent: Assuming that if p → q is true and p is false, then q must be false. This is also a fallacy.
• Using Examples as Proof: A few examples can illustrate a concept, but they do not constitute a proof. A proof must be a general argument that applies to all cases.
• Incorrectly Applying Definitions: Make sure you understand the precise definitions of the terms you are using.
• Making Logical Leaps: Each step in your proof must follow logically from the previous steps. Don't skip steps or make unsubstantiated claims.

Practice Problems and Solutions

To solidify your understanding, let's work through some practice problems.

Problem 1: Construct a truth table for the statement (p ∧ q) → (p ∨ q).

Solution:

Notice that the statement is always true. Therefore, it is a tautology.

Problem 2: Prove that if x is an odd integer and y is an odd integer, then x + y is an even integer.

Solution (Direct Proof):

Assume x is an odd integer and y is an odd integer. This means that x can be written as x = 2m + 1 for some integer m, and y can be written as y = 2n + 1 for some integer n. Then, x + y = (2m + 1) + (2n + 1) = 2m + 2n + 2 = 2(m + n + 1). Since m + n + 1 is an integer, x + y is an even integer. Therefore, if x is an odd integer and y is an odd integer, then x + y is an even integer.

Problem 3: Prove that if x² - 4 = 0, then x = 2 or x = -2.

Solution (Direct Proof):

Assume x² - 4 = 0. Then x² = 4. Taking the square root of both sides, we get x = ±2. Therefore, x = 2 or x = -2.

Problem 4: Disprove the statement: For all real numbers x, x² > 0.

Solution (Proof by Counterexample):

To disprove a universal statement, we only need to find one counterexample. Let x = 0. Then x² = 0² = 0, which is not greater than 0. Therefore, the statement is false.

Problem 5: Prove by contradiction that there is no largest integer.

Solution (Proof by Contradiction):

Assume, for the sake of contradiction, that there is a largest integer, call it N. Then, N is an integer, and for any integer x, x ≤ N. Now, consider the integer N + 1. Since N + 1 is an integer, it must be less than or equal to N. That is, N + 1 ≤ N. Subtracting N from both sides, we get 1 ≤ 0, which is a contradiction. Therefore, our assumption that there is a largest integer must be false. Therefore, there is no largest integer.

Tips for Test Day

• Review Definitions and Theorems: Make sure you have a solid understanding of the key definitions and theorems covered in the unit.
• Practice, Practice, Practice: The more you practice solving problems, the more comfortable you will become with the concepts and techniques.
• Read Carefully: Pay close attention to the wording of the problems.
• Plan Your Proofs: Before you start writing, take a few minutes to plan your strategy. What proof technique will you use? What are the key steps?
• Show Your Work: Even if you don't arrive at the correct answer, you may receive partial credit for showing your work.
• Check Your Work: After you finish a proof, take a few minutes to check your work for errors.
• Stay Calm: Don't panic if you get stuck on a problem. Take a deep breath and try a different approach.

Conclusion

Mastering logic and proofs is a challenging but rewarding endeavor. By understanding the fundamental concepts, practicing various proof techniques, and avoiding common mistakes, you can build a solid foundation in mathematical reasoning and excel on your Unit 2 test. Remember that practice makes perfect, so dedicate time to working through various problems and seeking help when needed. Good luck!