Unit 2 Logic And Proof Answer Key

Logic and proof form the bedrock of mathematics, providing the framework for constructing rigorous arguments and establishing the truth of mathematical statements. Understanding these concepts is crucial for anyone venturing into higher-level mathematics or fields that rely heavily on logical reasoning.

Understanding the Building Blocks: Logic and Proof

Logic is the study of reasoning. It provides the rules and principles that govern how we draw conclusions from given information. In mathematics, logic allows us to build consistent and reliable arguments. A proof, on the other hand, is a logical argument that demonstrates the truth of a particular statement. It uses axioms (statements accepted as true without proof), definitions, and previously proven theorems to arrive at a conclusion.

Propositional Logic: The Foundation

Propositional logic deals with propositions, which are declarative statements that can be either true or false, but not both. These propositions are combined using logical connectives to form compound propositions. Key logical connectives include:

• Negation (¬): Reverses the truth value of a proposition. If p is true, then ¬p is false, and vice versa.
• Conjunction (∧): Represents "and." The proposition p ∧ q is true only if both p and q are true.
• Disjunction (∨): Represents "or." The proposition p ∨ q is true if either p or q or both are true.
• Implication (→): Represents "if...then." The proposition p → q is false only when p is true and q is false. It is true in all other cases. p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).
• Biconditional (↔): Represents "if and only if." The proposition p ↔ q is true when p and q have the same truth value (both true or both false).

Truth Tables: Visualizing Logical Connectives

Truth tables are used to systematically determine the truth value of a compound proposition for all possible combinations of truth values of its constituent propositions. For example, the truth table for implication (p → q) is:

Understanding these truth tables is crucial for evaluating the validity of logical arguments.

Logical Equivalence: Different Ways of Saying the Same Thing

Two propositions are logically equivalent if they have the same truth value under all possible circumstances. We denote logical equivalence by ≡. For instance, p → q ≡ ¬p ∨ q. This equivalence is important because it allows us to rewrite propositions in different forms, which can be helpful in constructing proofs or simplifying complex logical expressions.

Tautologies and Contradictions: Special Propositions

A tautology is a proposition that is always true, regardless of the truth values of its variables. For example, p ∨ ¬p is a tautology. A contradiction is a proposition that is always false, regardless of the truth values of its variables. For example, p ∧ ¬p is a contradiction.

Predicate Logic: Dealing with Quantifiers

Predicate logic extends propositional logic by introducing predicates and quantifiers. A predicate is a statement that contains variables. Its truth value depends on the values assigned to those variables. For example, "x > 5" is a predicate.

Quantifiers express the extent to which a predicate is true over a range of elements. The two main quantifiers are:

• Universal Quantifier (∀): Means "for all." The statement ∀x P(x) means that the predicate P(x) is true for all values of x in a specified domain.
• Existential Quantifier (∃): Means "there exists." The statement ∃x P(x) means that there is at least one value of x in a specified domain for which the predicate P(x) is true.

Negating Quantified Statements

Negating quantified statements requires careful attention to the rules:

• ¬(∀x P(x)) ≡ ∃x ¬P(x) (The negation of "for all x, P(x) is true" is "there exists an x such that P(x) is false.")
• ¬(∃x P(x)) ≡ ∀x ¬P(x) (The negation of "there exists an x such that P(x) is true" is "for all x, P(x) is false.")

Methods of Proof: Building a Convincing Argument

Several techniques can be used to construct a mathematical proof. Some common methods include:

• Direct Proof: Starts with the hypothesis and uses logical deductions to arrive at the conclusion. To prove p → q, assume p is true and show that q must also be true.
• Proof by Contraposition: Proves p → q by proving its contrapositive, ¬q → ¬p. The implication and its contrapositive are logically equivalent.
• Proof by Contradiction: Assumes the negation of the statement to be proven and shows that this assumption leads to a contradiction. This contradiction implies that the original statement must be true. To prove p, assume ¬p is true and derive a contradiction.
• Proof by Cases: Divides the problem into a finite number of cases and proves the statement for each case.
• Mathematical Induction: Used to prove statements that hold for all positive integers. It consists of two steps:
  • Base Case: Show that the statement is true for the smallest integer (usually n = 1).
  • Inductive Step: Assume that the statement is true for an arbitrary integer k (the inductive hypothesis) and show that it must also be true for k+1.

Example: Direct Proof

Theorem: 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² is 2 times an integer, which means n² is even.
5. Therefore, if n is an even integer, then n² is an even integer.

Example: Proof by Contraposition

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

Proof (by contraposition):

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² + 2*k) + 1.
5. Since 2k² + 2*k is an integer, n² is 2 times an integer plus 1, which means n² is odd.
6. Therefore, if n is not an even integer, then n² is not an even integer.
7. Since we have proven the contrapositive, we have also proven the original statement: If n² is an even integer, then n is an even integer.

Example: Proof by Contradiction

Theorem: √2 is irrational.

Proof (by contradiction):

1. Assume, for the sake of contradiction, that √2 is rational.
2. If √2 is rational, then it can be expressed as a fraction a/b, where a and b are integers and b ≠ 0, and the fraction is in its simplest form (i.e., a and b have no common factors other than 1).
3. So, √2 = a/b.
4. Squaring both sides, we get 2 = a²/b².
5. Multiplying both sides by b², we get 2b² = a².
6. This means a² is an even integer.
7. Since a² is even, then a must be even (as we proved earlier). Therefore, a = 2k for some integer k.
8. Substituting a = 2k into 2b² = a², we get 2b² = (2k)² = 4k².
9. Dividing both sides by 2, we get b² = 2k².
10. This means b² is an even integer.
11. Since b² is even, then b must be even.
12. We have now shown that both a and b are even. This contradicts our initial assumption that a/b was in its simplest form (i.e., a and b have no common factors other than 1).
13. Therefore, our initial assumption that √2 is rational must be false.
14. Hence, √2 is irrational.

Common Mistakes in Proofs: Avoiding Logical Fallacies

Constructing proofs requires careful attention to detail and a thorough understanding of logical principles. Common mistakes include:

• Affirming the Consequent: Assuming that if p → q is true and q is true, then p must be true. This is a fallacy. For example: "If it is raining, then the ground is wet. The ground is wet, therefore it is raining." The ground could be wet for other reasons (e.g., a sprinkler).
• Denying the Antecedent: Assuming that if p → q is true and p is false, then q must be false. This is also a fallacy. For example: "If it is raining, then the ground is wet. It is not raining, therefore the ground is not wet." The ground could still be wet.
• Begging the Question (Circular Reasoning): Assuming the conclusion in the premise. For example: "God exists because the Bible says so, and the Bible is the word of God."
• Hasty Generalization: Drawing a conclusion based on insufficient evidence.
• Correlation vs. Causation: Assuming that because two things are correlated, one must cause the other.

Applying Logic and Proof: Examples and Applications

Logic and proof are not confined to abstract mathematical theory; they have numerous practical applications in various fields:

• Computer Science: Logic is fundamental to computer science, especially in areas like programming languages, artificial intelligence, and database management. Programmers use logical reasoning to write code that executes correctly. AI systems use logical inference to make decisions.
• Law: Lawyers use logical arguments to present their cases in court. They analyze evidence, construct arguments, and try to convince the judge or jury of the validity of their claims.
• Engineering: Engineers use logic to design and analyze systems, ensuring that they function correctly and safely. They use logical models to predict the behavior of systems and to identify potential problems.
• Philosophy: Philosophers use logic to analyze arguments, to identify fallacies, and to construct sound philosophical theories.
• Everyday Life: We use logic every day to make decisions, solve problems, and communicate effectively. Whether we are planning a route, choosing a product, or evaluating a claim, we are using logical reasoning.

Practice Problems and Solutions (Answer Key Examples)

While a full "answer key" would require specific problems from a textbook or curriculum, here are some examples of problems and solutions that illustrate the concepts discussed:

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

Solution:

Problem 2: Prove that if x is an odd integer, then x + 1 is an even integer. (Direct Proof)

Solution:

1. Assume x is an odd integer.
2. By definition of an odd integer, x = 2k + 1 for some integer k.
3. Then, x + 1 = (2k + 1) + 1 = 2k + 2 = 2(k + 1).
4. Since k + 1 is an integer, x + 1 is 2 times an integer, which means x + 1 is even.
5. Therefore, if x is an odd integer, then x + 1 is an even integer.

Problem 3: Prove that if a and b are rational numbers, then a + b is a rational number. (Direct Proof)

Solution:

1. Assume a and b are rational numbers.
2. By definition of a rational number, a = p/q and b = r/s for some integers p, q, r, and s, where q ≠ 0 and s ≠ 0.
3. Then, a + b = p/q + r/s = (ps + qr)/qs.
4. Since p, q, r, and s are integers, ps + qr and qs are also integers.
5. Since q ≠ 0 and s ≠ 0, qs ≠ 0.
6. Therefore, a + b is the ratio of two integers, where the denominator is not zero, which means a + b is a rational number.

Problem 4: Disprove the statement: "For all positive integers n, n² + n + 41 is a prime number."

Solution:

To disprove a universally quantified statement, we only need to find one counterexample.

Let n = 41. Then, n² + n + 41 = 41² + 41 + 41 = 41(41 + 1 + 1) = 41(43) = 1763.

Since 1763 is divisible by 41 and 43, it is not a prime number.

Therefore, the statement "For all positive integers n, n² + n + 41 is a prime number" is false.

Problem 5: Use mathematical induction to prove that 1 + 2 + 3 + ... + n = n(n+1)/2 for all positive integers n.

Solution:

Base Case (n=1):

• Left-hand side: 1
• Right-hand side: 1(1+1)/2 = 1(2)/2 = 1
• The formula holds for n=1.

Inductive Step:

1. Assume the formula holds for an arbitrary positive integer k. This is the inductive hypothesis: 1 + 2 + 3 + ... + k = k(k+1)/2
2. We need to show that the formula also holds for k+1: 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2

Starting with the left-hand side:

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

Using the inductive hypothesis, we can replace (1 + 2 + 3 + ... + k) with k(k+1)/2:

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.

Therefore, if the formula holds for k, it also holds for k+1.

Conclusion:

By the principle of mathematical induction, the formula 1 + 2 + 3 + ... + n = n(n+1)/2 holds for all positive integers n.

Resources for Further Learning

Many resources are available to deepen your understanding of logic and proof:

• Textbooks: Discrete Mathematics and Its Applications by Kenneth H. Rosen, How to Prove It by Daniel J. Velleman.
• Online Courses: Coursera, edX, Khan Academy offer courses on logic and discrete mathematics.
• Websites: Wolfram MathWorld, Wikipedia (search for "Mathematical Logic," "Proof Techniques").

Conclusion: The Power of Rigorous Thinking

Logic and proof are essential tools for mathematical reasoning and problem-solving. By mastering these concepts, you can develop the ability to construct sound arguments, identify fallacies, and confidently tackle complex mathematical problems. The journey to understanding logic and proof might seem challenging at first, but the rewards in terms of analytical thinking and problem-solving skills are well worth the effort. Embrace the rigor, practice consistently, and unlock the power of logical thinking.