Unit 2 Logic And Proof

Unit 2: Logic and Proof: A Comprehensive Guide

This unit delves into the fascinating world of logic and proof, fundamental concepts in mathematics and computer science. Understanding logic allows us to reason precisely and construct rigorous arguments, while proof provides the mechanism to establish the truth of mathematical statements. This comprehensive guide will explore various aspects of logic and proof, from basic propositional logic to more advanced techniques like mathematical induction. We'll cover key concepts, provide illustrative examples, and equip you with the tools to confidently approach logical reasoning and proof construction.

I. Introduction to Propositional Logic

At the heart of logic lies the concept of a proposition. A proposition is a declarative statement that is either true or false, but not both. For example, "The sky is blue" is a proposition (it's generally true, although the truth can depend on context), while "Close the door!" is not (it's a command). We use symbols, typically lowercase letters like p, q, r, to represent propositions.

We can combine propositions using logical connectives to create more complex statements. The primary connectives are:

• Negation (¬): The negation of a proposition p, denoted ¬p, is true when p is false, and false when p is true. Example: If p = "It is raining," then ¬p = "It is not raining."

• Conjunction (∧): The conjunction of propositions p and q, denoted p ∧ q, is true only when both p and q are true. Example: If p = "It is raining" and q = "The ground is wet," then p ∧ q = "It is raining and the ground is wet."

• Disjunction (∨): The disjunction of propositions p and q, denoted p ∨ q, is true when at least one of p or q is true. Example: If p = "It is raining" and q = "The sun is shining," then p ∨ q = "It is raining or the sun is shining." (Note: This is an inclusive "or," meaning it's true even if both are true).

• Implication (→): The implication p → q (read as "if p, then q") is false only when p is true and q is false. If p is false, the implication is true regardless of the truth value of q. This can seem counterintuitive at first, but consider it a promise: if the condition (p) is met, the consequence (q) must follow. Example: If p = "It is raining" and q = "The ground is wet," then p → q = "If it is raining, then the ground is wet."

• 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). Example: If p = "It is raining" and q = "The ground is wet," then p ↔ q might be approximately true in a particular context, but not universally (it's possible for the ground to be wet for other reasons).

II. Truth Tables and Logical Equivalence

Truth tables are a powerful tool for analyzing the truth values of compound propositions. A truth table lists all possible combinations of truth values for the individual propositions and the resulting truth value of the compound proposition.

Two compound propositions are logically equivalent if they have the same truth values for all possible combinations of truth values of their constituent propositions. We denote logical equivalence using the symbol ≡. For example, ¬(p ∧ q) ≡ (¬p) ∨ (¬q) (De Morgan's Law). Truth tables can be used to verify logical equivalences.

III. Predicate Logic

Propositional logic deals with simple propositions. Predicate logic extends this by allowing us to make statements about individuals within a domain. A predicate is a property or relationship. For example, "x is even" is a predicate, where x represents an individual from the domain of integers. We often use quantifiers to make statements about all or some elements in the domain:

• Universal Quantifier (∀): ∀x P(x) means "For all x, P(x) is true." Example: ∀x (x is an even number → x is divisible by 2).

• Existential Quantifier (∃): ∃x P(x) means "There exists an x such that P(x) is true." Example: ∃x (x is a prime number greater than 10).

IV. Methods of Proof

Mathematical proof is the process of establishing the truth of a statement (theorem) using logical reasoning and previously proven statements (axioms, definitions, theorems). Several methods exist:

• Direct Proof: We start with the hypothesis (what we assume to be true) and use logical steps to arrive at the conclusion.

• Proof by Contradiction: We assume the negation of the conclusion is true and show that this leads to a contradiction (a statement that is both true and false). This contradiction proves the original statement must be true.

• Proof by Contrapositive: This method is based on the logical equivalence p → q ≡ ¬q → ¬p. Instead of proving p → q directly, we prove its contrapositive, ¬q → ¬p.

• Proof by Cases: If a statement can be broken down into several cases, we prove the statement for each case individually.

V. Mathematical Induction

Mathematical induction is a powerful technique for proving statements about all natural numbers (or a subset starting from a base case). It consists of two steps:

1. Base Case: Prove the statement is true for the smallest natural number (usually 0 or 1).

2. Inductive Step: Assume the statement is true for some arbitrary natural number k (the inductive hypothesis), and then prove it is also true for k + 1.

If both steps are successful, the principle of mathematical induction guarantees the statement is true for all natural numbers greater than or equal to the base case.

VI. Illustrative Examples

Let's solidify our understanding with some examples:

Example 1 (Direct Proof): Prove that the sum of two even numbers is even.

• Hypothesis: Let a and b be two even numbers. This means there exist integers m and n such that a = 2m and b = 2n.

• Conclusion: We want to show that a + b is even.

• Proof: a + b = 2m + 2n = 2(m + n). Since (m + n) is an integer, a + b is of the form 2 times an integer, hence it's even.

Example 2 (Proof by Contradiction): Prove that √2 is irrational.

• Hypothesis: Assume √2 is rational. This means √2 can be expressed as a fraction a/ b where a and b are integers, b ≠ 0, and a and b are coprime (have no common factors other than 1).

• Conclusion: We want to show that our assumption leads to a contradiction.

• Proof: If √2 = a/ b, then 2 = a² / b², which implies 2b² = a². This means a² is even, and therefore a must be even. We can write a = 2k for some integer k. Substituting this into 2b² = a², we get 2b² = (2k)² = 4k², which simplifies to b² = 2k*². This shows b² is even, and therefore b must be even. But this contradicts our initial assumption that a and b are coprime (both are even, so they share a common factor of 2). Therefore, our initial assumption that √2 is rational must be false, and √2 is irrational.

Example 3 (Mathematical Induction): Prove that the sum of the first n positive integers is n(n+1)/2.

1. Base Case (n=1): The sum of the first 1 positive integer is 1, and 1(1+1)/2 = 1. The statement holds for n=1.

2. Inductive Step: Assume the statement is true for n=k: 1 + 2 + ... + k = k(k+1)/2. We need to prove it's true for n=k+1: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

   Starting with the left-hand side:

   1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) (using the inductive hypothesis) = (k(k+1) + 2(k+1))/2 = ((k+1)(k+2))/2

This is the right-hand side, so the statement holds for n=k+1. By the principle of mathematical induction, the statement is true for all positive integers n.

VII. Frequently Asked Questions (FAQ)

• Q: What's the difference between a proposition and a predicate? A proposition is a complete declarative statement that's either true or false. A predicate is a property or relationship that can be applied to individuals within a domain.

• Q: Why is proof by contradiction useful? It's a powerful indirect proof technique. Sometimes, directly proving a statement is difficult, but showing that its negation leads to a contradiction is easier.

• Q: How do I choose the right proof method? The best method depends on the specific statement you're trying to prove. Consider the structure of the statement and what seems like a more straightforward approach. Practice with different methods will improve your intuition.

• Q: Is mathematical induction only for natural numbers? While commonly used for natural numbers, it can be adapted to other well-ordered sets.

VIII. Conclusion

This comprehensive guide provides a solid foundation in logic and proof. Mastering these concepts is crucial for success in mathematics, computer science, and other fields that require rigorous reasoning. Remember that consistent practice and exposure to various proof techniques are key to developing your problem-solving skills and confidently constructing sound logical arguments. By understanding propositional logic, predicate logic, different proof methods, and mathematical induction, you are equipped to tackle a wide range of logical problems and demonstrate the validity of mathematical statements. This knowledge forms a bedrock for more advanced studies in mathematics and related disciplines. Continue to explore further resources and challenges to deepen your understanding of this fascinating and essential subject.