Unit 2 Test Study Guide Logic And Proof

Logic and Proof: Your Comprehensive Study Guide to Mastering Unit 2

Logic and proof form the bedrock of mathematical understanding, providing the tools to construct valid arguments and demonstrate the truth of mathematical statements. This study guide will help you navigate the intricacies of Unit 2, equipping you with the knowledge and skills necessary to excel in your test and beyond.

What is Mathematical Logic?

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It focuses on making mathematical reasoning precise, rigorous, and capable of being analyzed formally. Logic, in this context, serves as a framework for constructing and evaluating mathematical arguments, ensuring that conclusions follow validly from given premises.

Why is logic important in math?

• Foundation for Reasoning: Logic provides the foundation for all mathematical reasoning. Every theorem, proof, and mathematical argument relies on the principles of logic to ensure its validity.
• Precision and Clarity: Logic demands precision and clarity in mathematical statements. It forces mathematicians to define terms rigorously and express ideas in a way that leaves no room for ambiguity.
• Proof Construction: Logic is essential for constructing mathematical proofs. It provides the rules and methods for deriving conclusions from axioms and previously proven theorems.
• Problem Solving: Logical thinking is crucial for solving mathematical problems. It allows mathematicians to break down complex problems into smaller, manageable parts and to develop strategies for finding solutions.

Key Concepts in Logic

Before diving into proof techniques, let's solidify your understanding of the fundamental building blocks of logic:

Statements (Propositions)

A statement is a declarative sentence that is either true or false, but not both.

• Examples:
  • "The sky is blue." (True)
  • "2 + 2 = 5." (False)
  • "x > 3." (Not a statement, as its truth value depends on the value of x)

Logical Connectives

These operators combine simple statements to form compound statements. Understanding their truth tables is crucial.

• Negation (¬): "Not P." Reverses the truth value of P.
  • If P is true, ¬P is false.
  • If P is false, ¬P is true.
• Conjunction (∧): "P and Q." True only if both P and Q are true.
  • Otherwise, it is false.
• Disjunction (∨): "P or Q." True if either P or Q (or both) are true.
  • False only if both P and Q are false.
• Conditional (→): "If P, then Q." True unless P is true and Q is false.
  • P is the hypothesis (or antecedent).
  • Q is the conclusion (or consequent).
• Biconditional (↔): "P if and only if Q." True if P and Q have the same truth value (both true or both false).
  • Also known as "P is equivalent to Q."

Truth Tables

Truth tables systematically display the truth values of compound statements for all possible combinations of truth values of their components. They are indispensable for understanding and analyzing logical connectives.

Negation (¬)

Conjunction (∧)

Disjunction (∨)

Conditional (→)

Biconditional (↔)

Quantifiers

These symbols express the scope of a statement's truth.

• Universal Quantifier (∀): "For all" or "For every." ∀x P(x) means "For all x, P(x) is true."
• Existential Quantifier (∃): "There exists" or "There is at least one." ∃x P(x) means "There exists an x such that P(x) is true."

Logical Equivalence

Two statements are logically equivalent if they have the same truth value in all possible cases. This is denoted by ≡ or ⇔.

• Example: P → Q ≡ ¬P ∨ Q

Tautology and Contradiction

• 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.

Argument Forms and Validity

An argument consists of premises (statements assumed to be true) and a conclusion. An argument is valid if the conclusion logically follows from the premises. That is, if the premises are true, the conclusion must be true.

• Important Note: Validity does not guarantee that the conclusion is true. It only guarantees that if the premises are true, then the conclusion is also true. An argument can be valid even if its premises are false.
• Invalid Argument (Fallacy): An argument where the conclusion does not logically follow from the premises.

Rules of Inference

Rules of inference are valid argument forms that allow you to deduce new statements from existing ones. Mastering these rules is essential for constructing proofs.

• Modus Ponens:
  • Premise 1: P → Q
  • Premise 2: P
  • Conclusion: Q
  • (If P, then Q. P is true. Therefore, Q is true.)
• Modus Tollens:
  • Premise 1: P → Q
  • Premise 2: ¬Q
  • Conclusion: ¬P
  • (If P, then Q. Q is false. Therefore, P is false.)
• Hypothetical Syllogism:
  • Premise 1: P → Q
  • Premise 2: Q → R
  • Conclusion: P → R
  • (If P, then Q. If Q, then R. Therefore, if P, then R.)
• Disjunctive Syllogism:
  • Premise 1: P ∨ Q
  • Premise 2: ¬P
  • Conclusion: Q
  • (P or Q is true. P is false. Therefore, Q is true.)
• Addition:
  • Premise: P
  • Conclusion: P ∨ Q
  • (P is true. Therefore, P or Q is true.)
• Simplification:
  • Premise: P ∧ Q
  • Conclusion: P
  • (P and Q are true. Therefore, P is true.)
• Conjunction:
  • Premise 1: P
  • Premise 2: Q
  • Conclusion: P ∧ Q
  • (P is true. Q is true. Therefore, P and Q are true.)
• Universal Instantiation:
  • Premise: ∀x P(x)
  • Conclusion: P(a) (where 'a' is a specific element in the domain of x)
  • (For all x, P(x) is true. Therefore, P(a) is true for any specific a.)
• Universal Generalization:
  • If P(a) is true for an arbitrary element 'a' in the domain of x, then
  • Conclusion: ∀x P(x)
  • (If P(a) is true for an arbitrary a, then P(x) is true for all x.)
• Existential Instantiation:
  • Premise: ∃x P(x)
  • Conclusion: P(c) (where 'c' is a specific element in the domain of x)
  • (There exists an x such that P(x) is true. Therefore, we can give that x a name, 'c', and say P(c) is true.)
• Existential Generalization:
  • Premise: P(a) (where 'a' is a specific element in the domain of x)
  • Conclusion: ∃x P(x)
  • (P(a) is true for a specific a. Therefore, there exists an x such that P(x) is true.)

Proof Techniques

A mathematical proof is a convincing argument that demonstrates the truth of a mathematical statement. Here are several common proof techniques:

Direct Proof

Starts with the assumption that the hypothesis (P) is true and uses logical steps and established facts to show that the conclusion (Q) is true.

• Structure:
  1. Assume P is true.
  2. Use definitions, axioms, and previously proven theorems to derive Q.
  3. Conclude that if P is true, then Q is true (P → Q).

Proof by Contraposition

Proves the statement P → Q by proving its contrapositive, ¬Q → ¬P. The contrapositive is logically equivalent to the original statement.

• Structure:
  1. Assume ¬Q is true.
  2. Use definitions, axioms, and previously proven theorems to derive ¬P.
  3. Conclude that if ¬Q is true, then ¬P is true (¬Q → ¬P). Therefore, P → Q is true.

Proof by Contradiction

Assumes that the statement to be proven is false and then demonstrates that this assumption leads to a contradiction. This contradiction shows that the initial assumption must be false, and therefore the original statement must be true.

• Structure:
  1. Assume ¬(P → Q) is true (or, more generally, assume the statement you want to prove is false).
  2. Use definitions, axioms, and previously proven theorems to derive a contradiction (a statement of the form R ∧ ¬R, or something that is known to be false).
  3. Conclude that the initial assumption ¬(P → Q) must be false. Therefore, P → Q is true.

Proof by Cases

Divides the problem into several cases and proves the statement for each case separately.

• Structure:
  1. Identify the different cases that cover all possibilities.
  2. For each case, prove the statement is true under the assumptions of that case.
  3. Conclude that the statement is true in all possible cases.

Proof by Mathematical Induction

Used to prove statements that hold for all natural numbers (or for all integers greater than or equal to some base case).

• Steps:
  1. Base Case: Show that the statement is true for the smallest value in the range (usually n = 0 or n = 1).
  2. Inductive Hypothesis: Assume that the statement is true for an arbitrary integer k (where k is greater than or equal to the base case).
  3. Inductive Step: Show that if the statement is true for k, then it must also be true for k+1. That is, prove P(k+1) assuming P(k).
  4. Conclusion: Conclude that the statement is true for all integers greater than or equal to the base case.

Vacuous Proof

If the hypothesis (P) is false, then the conditional statement (P → Q) is automatically true, regardless of the truth value of Q. This is a vacuous proof.

• When to Use: When you can show that the hypothesis is always false.
• Example: "If x is a number greater than 10 and less than 5, then x is even." Since no number can be both greater than 10 and less than 5, the hypothesis is always false, and the statement is vacuously true.

Trivial Proof

If the conclusion (Q) is true, then the conditional statement (P → Q) is automatically true, regardless of the truth value of P. This is a trivial proof.

• When to Use: When you can show that the conclusion is always true.
• Example: "If x is an even number, then 1 = 1." Since 1 = 1 is always true, the statement is trivially true.

Common Mistakes to Avoid

• Affirming the Consequent: A common fallacy.
  • Premise 1: P → Q
  • Premise 2: Q
  • Incorrect Conclusion: P
  • (If it rains, the ground is wet. The ground is wet. Therefore, it rained. This is incorrect because the ground could be wet for other reasons.)
• Denying the Antecedent: Another common fallacy.
  • Premise 1: P → Q
  • Premise 2: ¬P
  • Incorrect Conclusion: ¬Q
  • (If it rains, the ground is wet. It did not rain. Therefore, the ground is not wet. This is incorrect because the ground could be wet for other reasons.)
• Begging the Question (Circular Reasoning): Assuming the conclusion in your premises.
• Using Examples as Proof: Examples can illustrate a concept, but they do not constitute a proof.
• Incorrectly Applying Induction: Forgetting the base case, or failing to show that P(k+1) follows from P(k).

Tips for Success

• Practice, Practice, Practice: Work through numerous examples of proofs using different techniques.
• Understand the Definitions: Make sure you have a clear understanding of the definitions of all terms involved.
• Break Down Complex Problems: Decompose complex statements into simpler parts.
• Use Scratch Paper: Plan your proof before writing it formally.
• Review Your Work: Carefully check each step of your proof to ensure its validity.
• Seek Help When Needed: Don't hesitate to ask your instructor or classmates for help if you are struggling.
• Be Precise: Use precise language and avoid ambiguity.
• Be Organized: Present your proof in a clear and logical manner.
• Know Your Audience: Tailor your proof to the level of understanding of your audience.

Examples

Example 1: Direct Proof

Statement: If n is an even integer, then n² is an even integer.

Proof:

1. Assume n is an even integer.
2. By definition of an even integer, n = 2k for some integer k.
3. Then, n² = (2k)² = 4k² = 2(2k²).
4. Since 2k² is an integer, n² = 2*(an integer).
5. Therefore, n² is an even integer.

Example 2: Proof by Contraposition

Statement: If n² is an even integer, then n is an even integer.

Proof:

1. 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).
2. Assume n is an odd integer.
3. By definition of an odd integer, n = 2k + 1 for some integer k.
4. Then, n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.
5. Since 2k² + 2k is an integer, n² = 2*(an integer) + 1.
6. Therefore, n² is an odd integer.
7. Since we have proven the contrapositive, the original statement is true.

Example 3: Proof by Contradiction

Statement: There is no largest integer.

Proof:

1. Assume, for the sake of contradiction, that there is a largest integer, call it M.
2. Consider the integer M + 1.
3. Since M is the largest integer, M ≥ M + 1.
4. Subtracting M from both sides, we get 0 ≥ 1, which is a contradiction.
5. Therefore, our initial assumption that there is a largest integer must be false.
6. Hence, there is no largest integer.

Example 4: Proof by Mathematical Induction

Statement: For all positive integers n, 1 + 2 + 3 + ... + n = n(n + 1)/2

Proof:

1. Base Case: For n = 1, the statement is 1 = 1(1+1)/2 = 1, which is true.

2. Inductive Hypothesis: Assume that the statement is true for some positive integer k. That is, assume 1 + 2 + 3 + ... + k = k(k + 1)/2

3. Inductive Step: We must show that the statement is true for k + 1. That is, we must show that 1 + 2 + 3 + ... + (k + 1) = (k + 1)((k + 1) + 1)/2 = (k + 1)(k + 2)/2

   Starting with the left-hand side:

   1 + 2 + 3 + ... + (k + 1) = (1 + 2 + 3 + ... + k) + (k + 1)

   By the inductive hypothesis, we can substitute k(k + 1)/2 for (1 + 2 + 3 + ... + k):

   k(k + 1)/2 + (k + 1) = [k(k + 1) + 2(k + 1)] / 2 = (k² + k + 2k + 2) / 2 = (k² + 3k + 2) / 2 = (k + 1)(k + 2) / 2

   This is equal to the right-hand side, (k + 1)(k + 2)/2.

4. Conclusion: By the principle of mathematical induction, the statement 1 + 2 + 3 + ... + n = n(n + 1)/2 is true for all positive integers n.

FAQ

• What is the difference between a valid argument and a sound argument?
  • A valid argument has a conclusion that logically follows from its premises. A sound argument is a valid argument with true premises. Therefore, a sound argument must have a true conclusion.
• How do I negate a quantified statement?
  • ¬(∀x P(x)) ≡ ∃x ¬P(x) (It is not the case that for all x, P(x) is true, is equivalent to saying there exists an x for which P(x) is false.)
  • ¬(∃x P(x)) ≡ ∀x ¬P(x) (It is not the case that there exists an x for which P(x) is true, is equivalent to saying that for all x, P(x) is false.)
• What is the difference between P → Q and Q → P?
  • P → Q is a conditional statement ("If P, then Q"). Q → P is its converse ("If Q, then P"). These are not logically equivalent.

Conclusion

Mastering logic and proof is essential for success in mathematics. By understanding the fundamental concepts, practicing proof techniques, and avoiding common mistakes, you can build a strong foundation for your mathematical studies. Remember to practice regularly, seek help when needed, and approach each problem with a clear and logical mindset. Good luck!