Unit 13: Mathematical Logic
Contents
1. Introduction to Logic and Propositions
Mathematical Logic is the study of valid reasoning. It provides the rules for determining whether a mathematical statement is true or false.
What is a Proposition?
A Proposition (or statement) is a declarative sentence that is either True (T) or False (F), but not both.
- Examples: "The sun rises in the east" (True), "10 + 5 = 20" (False).
- Non-propositions: "How are you?" (Question), "Close the door" (Command), "x + 2 = 5" (Truth depends on x).
2. Logical Connectives and Truth Tables
Compound propositions are formed by combining existing propositions using Logical Connectives.
| Operator | Name | Symbol | Condition for Truth |
|---|---|---|---|
| Negation | NOT | ¬ p | Opposite of the original truth value. |
| Conjunction | AND | p \land q | True only if both are True. |
| Disjunction | OR | p \lor q | True if at least one is True. |
3. Conditional and Biconditional Statements
Conditional Statement (p \to q)
Also known as an "If-Then" statement. It is false only when the hypothesis (p) is True and the conclusion (q) is False.
Biconditional Statement (p ≤ftrightarrow q)
Also known as "If and only if." It is true only when both p and q have the same truth values.
4. Tautologies, Contradictions, and Contingencies
By constructing a truth table for a compound proposition, we can classify it into one of three categories:
- Tautology: A statement that is always True regardless of the truth values of its components (e.g., p \lor ¬ p).
- Contradiction: A statement that is always False (e.g., p \land ¬ p).
- Contingency: A statement that is neither a tautology nor a contradiction (it can be true or false).
5. Converse, Inverse, and Contrapositive
Given a conditional statement p \to q, we can derive three related statements:
- Converse: q \to p
- Inverse: ¬ p \to ¬ q
- Contrapositive: ¬ q \to ¬ p
Exam Fact: A statement and its Contrapositive are logically equivalent (they always have the same truth value).
6. Exam Focus Enhancements
- Truth Table Rows: If there are n propositions, the truth table will have 2n rows. For two variables (p, q), use 4 rows.
- Negation of Negation: Remember that ¬(¬ p) is equivalent to p.
- Implication Shortcut: Think of p \to q as a promise. The only time the promise is broken is if p happens but q doesn't.
- Non-Statements: Trying to identify truth values for commands or questions. They are not propositions!
- OR vs XOR: In math, "OR" (\lor) is inclusive. It is true if both are true. Don't confuse it with "Either-Or" (XOR).
- Inverse vs Converse: Getting these swapped. Remember: Contrapositive is the only one that is definitely equivalent to the original statement.
Q: What is a Truth Value?
A: It is the attribute of a proposition being either True (represented as T or 1) or False (F or 0).
Q: Can a mathematical equation be a proposition?
A: Yes, if it is an equality or inequality without variables (e.g., 5 > 3 is a True proposition). Equations with variables are "Open Sentences."