Logic and Proofs Notes

Implications and Logical Equivalence

Example of Lying

• Scenario: Someone promises to buy a new car if you graduate from Oberlin with honors in mathematics.
• Lying occurs: Only if you graduate from Oberlin with honors in mathematics, and they don't buy you a new car.

Logical Equivalence

• Claim: $P \Rightarrow Q$ is logically equivalent to $(P \Rightarrow Q) \land (Q \Rightarrow P)$
• Verification: Use a truth table to confirm their equivalence.

Knights and Knaves Worksheet

• Reference to a worksheet on Knights and Knaves.

Implication

• Truth Table for Implication ($P \Rightarrow Q$):
  • T T: T
  • T F: F
  • F T: T
  • F F: T
• Key Point: When the hypothesis (P) is false, the implication ($P \Rightarrow Q$) is true, regardless of the conclusion (Q).
• Vacuous Truth: Some say when the hypothesis (P) is false, the implication ($P \Rightarrow Q$) is vacuously true.

Alternate Ways of Expressing $P \Rightarrow Q$

1. If P then Q.
2. P implies Q.
3. Q if P.
4. P is a sufficient condition for Q.
5. Q is a necessary condition for P.
6. P only if Q.

• Example with P = "x > 5" and Q = "x > 3"
  1. If x > 5 then x > 3.
  2. x > 5 implies that x > 3.
  3. x > 3 if x > 5.
  4. x > 5 is a sufficient condition for x > 3.
  5. x > 3 is a necessary condition for x > 5.
  6. x > 5 only if x > 3.
• Note: Rephrasing example 4: To show that x > 3 holds, it suffices to show that x > 5.

Contrapositive

• $P \Rightarrow Q$ is logically equivalent to $\lnot Q \Rightarrow \lnot P$


• The implication $\lnot Q \Rightarrow \lnot P$ is called the contrapositive of $P \Rightarrow Q$


• Truth Table:
  

• $\lnot (P \land Q) \equiv \lnot P \lor \lnot Q$
• $\lnot (P \lor Q) \equiv \lnot P \land \lnot Q$

Example: Showing Equivalence

• $\lnot (P \Rightarrow Q) \equiv P \land \lnot Q$
  

• $P \Leftrightarrow Q$ (P if and only if Q)


• Equivalent to $(P \Rightarrow Q) \land (Q \Rightarrow P)$


• Truth Table:
  

• Existential Quantifier: $\exists$ (There exists)
• Example: $\exists x : x^2 - 2x + 1 = 0$ (There exists a number x such that $x^2 - 2x + 1 = 0$)
• Specifying the domain: $\exists x \in \mathbb{R} : x^2 - 2x + 1 = 0$ (There exists a real number x such that $x^2 - 2x + 1 = 0$)