De Morgan's law (kind of) but extended...

$$\lnot$$ $$\forall$$ x P(x) $$\equiv$$ $$\exists$$ x $$\lnot$$ P(x)
- There is an x for which P(x) is false

$$\lnot$$ $$\exists$$ x  P(x) $$\equiv$$ $$\forall$$ x $$\lnot$$ P(x)
- For every x, P(x) is false

University of Michigan - Ann Arbor

 $$\exists$$ : "there exists", "at least one", "some"

"someone will buy an umbrella"
$$\exists$$ x B(x, umbrella)

Existential qualifier

$$\forall$$: "for all", "every", "any"
- all includes the universe of discourse or domain of discourse

"everyone will buy an umbrella"
- $$\forall$$ x B(x, umbrella)

Universal quantifier

University of Michigan EECS 203 Lecture Notes

"Truth table" for quantifiers

"For every x (in the domain), there is at least one y (in the domain) that can depend on x and may be equal to x such that L(x, y) is true"
- $$\forall$$ x $$\exists$$ y L(x, y)
- Everyone loves someone (e.g. their family)

"There is at least one y such that for every x (including the case y=x), L(x, y) is true"
- $$\exists$$ y $$\forall$$ x L(x, y) 
- There is someone everyone loves (e.g. santa)

Nested Quantifiers

Negating quantifiers

Proof with quantifiers

Defines the universe of all possible things. It is the x in $$\forall$$ x P(x).
- technically x could be anything
- after specifying the domain, x can mean students, numbers, people, integers, etc.
- keep the domain as clear and general as possible

Learn Before

Related