Tmua Notes On Logic And Proof

TMUA Notes on Logic and Proof: A Comprehensive Guide

The TMUA (Test of Mathematics for University Admission) assesses mathematical reasoning and problem-solving skills crucial for university-level study. A significant portion focuses on logic and proof, demanding a strong understanding of fundamental concepts and the ability to apply them rigorously. This comprehensive guide provides TMUA notes on logic and proof, covering key topics and offering strategies for tackling exam-style questions. We'll explore propositional logic, methods of proof, and common pitfalls, equipping you with the necessary tools to excel in this section.

I. Introduction to Propositional Logic

Propositional logic forms the bedrock of mathematical reasoning. It deals with propositions, which are statements that can be either true (T) or false (F), but not both. We use logical connectives to combine propositions and create more complex statements.

Key Connectives:

• Negation (¬): Reverses the truth value of a proposition. ¬P is true if P is false, and vice versa.
• Conjunction (∧): "And". P ∧ Q is true only if both P and Q are true.
• Disjunction (∨): "Or" (inclusive). P ∨ Q is true if at least one of P or Q is true.
• Implication (→): "If...then". P → Q is false only if P is true and Q is false. It's crucial to understand the nuances of implication; a false premise can imply anything.
• Equivalence (↔): "If and only if". P ↔ Q is true if P and Q have the same truth value.

Truth Tables: These systematically show the truth values of compound propositions for all possible combinations of truth values of their constituent propositions. Mastering truth tables is essential for understanding logical equivalence and implications. For instance, constructing truth tables can demonstrate the equivalence of (P → Q) and (¬P ∨ Q).

Logical Equivalences: Certain combinations of connectives always yield the same truth values. Recognizing these equivalences is critical for simplifying complex logical expressions and manipulating proofs. Some important 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

II. Methods of Proof

Mathematical proofs establish the truth of statements with rigorous logical arguments. Several methods are commonly used:

1. Direct Proof: Starts with the given premises and uses logical deductions to arrive at the conclusion. This is the most straightforward approach, often involving algebraic manipulation or applying known theorems.

Example: Prove that if x is an even integer, then x² is an even integer.

Proof: Let x be an even integer. By definition, x = 2k for some integer k. Then x² = (2k)² = 4k² = 2*(2k²). Since 2k² is an integer, x² is an even integer. ∎

2. Proof by Contradiction: Assumes the negation of the conclusion and shows that this assumption leads to a contradiction (a statement that is both true and false). This contradiction implies that the original assumption must be false, thus proving the conclusion.

Example: Prove that √2 is irrational.

Proof: Assume, for the sake of contradiction, that √2 is rational. Then √2 = a/b, where a and b are integers with no common factors (i.e., the fraction is in its simplest form). Squaring both sides, we get 2 = a²/b². This implies 2b² = a². Therefore, a² is even, and hence a must be even. We can write a = 2k for some integer k. Substituting this into 2b² = a², we get 2b² = (2k)² = 4k². This simplifies to b² = 2k*², implying that b² is even and b is even. However, this contradicts our initial assumption that a and b have no common factors, since both are even. Therefore, our assumption that √2 is rational must be false, proving that √2 is irrational. ∎

3. Proof by Induction: Used to prove statements about natural numbers. It involves two steps:

• Base Case: Prove the statement is true for the smallest natural number (usually 1).
• Inductive Step: Assume the statement is true for some arbitrary natural number k, and then prove it's also true for k + 1.

Example: Prove that the sum of the first n natural numbers is n(n+1)/2.

Proof:

• Base Case (n=1): The sum of the first natural number is 1, and 1(1+1)/2 = 1. The statement holds for n=1.
• Inductive Step: Assume the statement is true for n=k, i.e., 1 + 2 + ... + k = k(k+1)/2. We want to show it's true for n=k+1. The sum of the first k+1 natural numbers is: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2. This is the formula for n=k+1.

Therefore, by the principle of mathematical induction, the statement is true for all natural numbers n. ∎

4. Proof by Exhaustion (or Casework): This method involves examining all possible cases to prove a statement. It’s suitable when the number of cases is finite and manageable.

III. Quantifiers and Negation

Quantifiers specify the scope of a statement. Two main quantifiers are:

• Universal Quantifier (∀): "For all" or "For every." ∀x P(x) means that P(x) is true for every x in the domain.
• Existential Quantifier (∃): "There exists" or "There is at least one." ∃x P(x) means that there is at least one x in the domain for which P(x) is true.

Negating Quantified Statements: This is crucial for proof by contradiction and understanding logical implications:

• ¬(∀x P(x)) ≡ ∃x ¬P(x) (If it's not true for all x, then there exists at least one x for which it's false).
• ¬(∃x P(x)) ≡ ∀x ¬P(x) (If there doesn't exist an x for which it's true, then it's false for all x).

IV. Common Pitfalls and Strategies for Success

• Misunderstanding Implication: Remember that P → Q is only false when P is true and Q is false.
• Incorrect Negation: Carefully apply De Morgan's Laws and the rules for negating quantified statements.
• Insufficient Justification: Each step in a proof must be logically justified, referencing definitions, axioms, or previously proven theorems.
• Circular Reasoning: Avoid using the conclusion to prove the conclusion.
• Unclear Definitions: Ensure you have a precise understanding of all the terms involved.

Strategies:

• Practice Regularly: Work through numerous examples and practice questions.
• Understand the Concepts: Don't just memorize formulas; grasp the underlying logic.
• Break Down Complex Problems: Divide complex problems into smaller, manageable parts.
• Check Your Work: Carefully review your proofs to ensure logical consistency and completeness.
• Seek Feedback: Get feedback on your proofs from teachers or peers.

V. Beyond Propositional Logic: A Glimpse into Predicate Logic

While the TMUA primarily focuses on propositional logic, a brief understanding of predicate logic can be advantageous. Predicate logic extends propositional logic by considering the structure of propositions. Instead of just dealing with simple propositions (like "it is raining"), it analyzes statements with predicates and variables. For example, "x is a prime number" uses the predicate "is a prime number" and the variable x. Predicate logic allows for more nuanced and expressive statements, enabling more sophisticated reasoning. Concepts like quantifiers (∀ and ∃) become even more crucial within this framework.

VI. Conclusion

Mastering logic and proof is fundamental for success in the TMUA and future mathematical studies. This guide provides a strong foundation in propositional logic, outlines key proof techniques, and highlights common pitfalls. Consistent practice, a deep understanding of the underlying principles, and careful attention to detail are essential for achieving proficiency in this crucial area. By applying the strategies and insights provided here, you can significantly enhance your ability to tackle the logic and proof section of the TMUA with confidence and accuracy. Remember, consistent effort and a focused approach are your keys to success.