Lecture Notes: Predicate Logic and Quantifiers

Introduction

• Final video in the section on Boolean algebra transitioning to predicate logic.
• Focus on adding rules to propositional logic to include predicate logic.
• Importance of these rules in methods of proof:
  • Proof by contradiction
  • Proof by the contrapositive

Propositional Logic Recap

• Compound propositions simplified using rules.
• Outcomes:
  • Tautology: Proposition is always true.
  • Contradiction: Proposition is always false.

Transition to Predicate Logic

• Connect predicates similarly to propositions.
• Key challenge: Interaction with quantifiers (e.g., "there exists", "for all") when negated.

Rules for Quantifiers and Negation

• Example:
  • Statement: "For all x, P(x)"
  • True for all integers (e.g., all primes have a bigger prime)
  • Negating the statement: Identify occasions when false.

Rule Derivation

• Not of "for all x, P(x)" is equivalent to "there exists x such that not P(x)"
• Similar to logic rules for negation with "and" and "or":
  • Swap "and" for "or" and vice versa when negating.
• Alternative expression:
  • Not "there exists x such that P(x)" is equivalent to "for all x, not P(x)"

Example Problems

• Predicate Example:
  • Predicates: P(x) and Q(x,y)
  • Statement: For all x, either P(x) is true or there exists y such that Q(x,y) is true.

Specific Example

• Real Numbers:
  • P(x): x = 0
  • Q(x,y): x * y = 1 (find inverse)
  • True for real numbers, false for integers.*

Transforming Statements

• Negation Example:
  • Not R(x) = Not (for all x, P and there exists y, Q)
  • Transform to: Exists x such that not P(x) and for all y, not Q(x,y)

Integer Example

• Apply logic to integers:
  • If P(x) = x ≠ 0 and Q(x,y) = x * y ≠ 1
  • Example: x = 2, since 2 * any integer ≠ 1.

Conclusion

• Predicate logic and quantifiers provide a robust framework for proof strategies.
• End of the section on predicate logic.