Predicates and Variables
A predicate is a statement containing variables that becomes a proposition when specific values are substituted. For example, P(x): "x > 5" is a predicate. P(7) is true, P(3) is false.
Predicates allow us to express properties and relationships in a general way.
Quantifiers
Quantifiers turn predicates into propositions by specifying how many values satisfy the predicate.
Universal Quantifier (∀): "For all"
∀x P(x) means P(x) is true for every x in the domain.
Existential Quantifier (∃): "There exists"
∃x P(x) means there is at least one x for which P(x) is true.Negating Quantified Statements
¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)The negation of "all students are smart" is "there exists a student who is not smart" — not "no students are smart".
Nested Quantifiers
∀x ∃y (x + y = 0) "For every x, there exists y such that x + y = 0"
∃y ∀x (x + y = 0) "There exists y such that for all x, x + y = 0"The order of quantifiers matters! The first statement is true (y = -x), while the second is false (no single y works for all x).