1.2 Quantifiers

Quantifier

A quantifier of a proposition is a logical operator that specifies how many elements in a domain satisfy a statement which refers to a variable, known as a propositional formula. For the propositional formula $P(x)$, we can define the duals:

1. Universal Quantifier: $\forall xP(x)⟺P(x)\text{ is true for all x.}$
2. Existential Quantifier: $\exists xP(x)⟺\text{There exists at least one }x\text{ for which }P(x)\text{is true.}$

Understanding

We can translate any propositional formula from the duals back to propositional forms. For example, take a variable $x$ such that $x\in \{1,2,3\}$. Then,

1. $\forall xP(x)⟺P(1)\wedge P(2)\wedge P(3)$.
2. $\exists xP(x)⟺P(1)\vee P(2)\vee P(3)$.

Properties

(DeMorgan’s Laws) $\neg [\forall xP(x)]\equiv \exists x\neg P(x)$, and $\neg [\exists xP(x)]\equiv \forall x\neg P(x)$.