Unit 2 Test Study Guide Logic And Proof

Unit 2 Test Study Guide: Logic and Proof

This comprehensive study guide covers the key concepts and skills typically included in a Unit 2 test on Logic and Proof. We'll explore various logical reasoning techniques, proof methods, and the fundamental building blocks of mathematical argumentation. This guide aims to equip you with the knowledge and confidence to excel on your upcoming test.

I. Fundamental Concepts of Logic

A. Statements and Logical Connectives

Before diving into proofs, mastering the basics of logic is crucial. A statement is a declarative sentence that is either true or false, but not both. Understanding how statements combine using logical connectives is essential. These connectives include:

• Negation (¬): The negation of a statement reverses its truth value. For example, if p is "It is raining," then ¬p is "It is not raining."
• Conjunction (∧): The conjunction of two statements p and q, denoted p ∧ q, is true only if both p and q are true. This represents an "and" relationship.
• Disjunction (∨): The disjunction of two statements p and q, denoted p ∨ q, is true if at least one of p or q is true. This represents an "or" relationship (inclusive or).
• Implication (→): The implication p → q (read as "if p, then q") is false only when p is true and q is false. p is the hypothesis (or premise), and q is the conclusion.
• Biconditional (↔): The biconditional p ↔ q (read as "p if and only if q") is true only when p and q have the same truth value (both true or both false).

Practice: Construct truth tables for each of these logical connectives. This will help solidify your understanding of how truth values propagate through compound statements.

B. Truth Tables and Logical Equivalence

Truth tables are a systematic way to analyze the truth values of compound statements. By constructing truth tables, you can determine if two statements are logically equivalent. Logical equivalence means that two statements always have the same truth value, regardless of the truth values of their individual components. Common logical equivalences include:

• Commutative Laws: p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p
• Associative Laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r); (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
• Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
• De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Implication Equivalence: p → q ≡ ¬p ∨ q

C. Tautologies and Contradictions

A tautology is a compound statement that is always true, regardless of the truth values of its components. A contradiction is a compound statement that is always false. Identifying tautologies and contradictions is crucial for evaluating the validity of arguments and proofs.

II. Methods of Proof

Mathematical proofs are rigorous arguments that establish the truth of a statement. Several common methods exist:

A. Direct Proof

A direct proof starts with the given hypothesis and uses logical deductions to arrive at the desired conclusion. Each step in the proof must be justified by a previously established fact, definition, or theorem.

B. Indirect Proof (Proof by Contradiction)

An indirect proof assumes the negation of the conclusion and then shows that this assumption leads to a contradiction. Since a contradiction cannot be true, the original assumption (the negation of the conclusion) must be false, which implies the conclusion is true.

C. Proof by Contrapositive

A proof by contrapositive uses the fact that the implication p → q is logically equivalent to its contrapositive ¬q → ¬p. By proving the contrapositive, we indirectly prove the original implication.

D. Proof by Cases

A proof by cases breaks down the problem into a finite number of cases and proves the statement for each case separately. This is useful when the hypothesis has multiple possibilities.

E. Mathematical Induction

Mathematical induction is a powerful technique for proving statements about all positive integers (or a subset thereof). It involves two steps:

1. Base Case: Prove the statement is true for the smallest integer (usually 1).
2. Inductive Step: Assume the statement is true for an arbitrary integer k, and then prove it's true for k + 1.

III. Quantifiers and Negations

Understanding quantifiers (∀ – for all, ∃ – there exists) and their negations is crucial for working with statements involving sets and mathematical structures. The negation of a universally quantified statement is an existentially quantified statement, and vice versa:

• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

IV. Set Theory and Logic

Many logical arguments involve sets. Understanding basic set operations (union, intersection, complement) and their relationship to logical connectives is important. For example:

• The union of two sets corresponds to the disjunction of statements.
• The intersection of two sets corresponds to the conjunction of statements.

V. Common Mistakes to Avoid

• Confusing implication with equivalence: Remember p → q does not mean q → p.
• Incorrectly negating quantified statements: Pay close attention to the rules for negating universal and existential quantifiers.
• Making unjustified assumptions: Every step in a proof must be logically justified.
• Ignoring edge cases: Ensure your proof covers all possible scenarios.
• Forgetting the base case in induction: The base case is essential for the validity of an induction proof.

VI. Practice Problems

To effectively prepare for your Unit 2 test, solve a variety of practice problems. These problems should cover all the topics discussed in this study guide, including:

• Constructing truth tables for compound statements.
• Determining logical equivalence.
• Identifying tautologies and contradictions.
• Writing direct, indirect, and contrapositive proofs.
• Using mathematical induction to prove statements.
• Negating quantified statements.
• Working with set theory and its connection to logic.

Example Problems:

1. Construct a truth table for the statement (p ∧ q) → (p ∨ r).
2. Prove that for all integers n, if n is even, then n² is even. (Direct Proof)
3. Prove that √2 is irrational. (Proof by Contradiction)
4. Prove that n³ + 2n is divisible by 3 for all positive integers n. (Mathematical Induction)
5. Negate the statement: ∀x ∈ R, ∃y ∈ R such that x + y = 0.

Solving numerous problems of varying difficulty is vital for developing your problem-solving skills and confidence. Focus on understanding the underlying principles rather than just memorizing solutions.

VII. Review and Self-Assessment

After completing your practice problems, review the key concepts and definitions presented in this study guide. Assess your understanding of each topic. Identify areas where you feel less confident and revisit those sections. Consider seeking help from your instructor or classmates if you are struggling with specific concepts.

By diligently studying this guide and practicing extensively, you will significantly enhance your understanding of logic and proof, boosting your performance on your Unit 2 test and laying a solid foundation for future mathematical endeavors. Remember that consistent effort and a clear grasp of fundamental principles are key to success in this area. Good luck!