7. Quantifiers

Quantifiers

Quantification is another way of creating a proposition from $P(x)$, it expresses the extent to which a predicate is true over a range of entities, called the domain.

Universal quantifier, $\forall$.

Universal quantifier

The universal quantification of $P(x)$ for a particular domain, denoted by $\forall xP(x)$, is the proposition "$P(x)$ is true for all values of $x$ from the domain". $\forall$ means "For all".

• The truth value of $\forall xP(x)$ might change if domain changes.
• Domain must always be specified when universal quantifier is used.

For example, take $P(x)$ is "$x>0$":

• For the domain of positive integers, $\forall xP(x)⇝T$.
• For the domain of all integers, $\forall xP(x)⇝F$.

To say “Everyone does not like Jane”, we write that for every $x$, $x$ does not like Jane:

$$(\forall x)(\neg Likes(x,jane))$$

In general, the notation for universal quantifiers is $(\forall x)(\phi)$ where $\phi$ is a formula in which $x$ and possible other variables may appear.

Link to original

Rules of inference ($\forall$)

Universal instantiation

A universal instantiation means for each and every entity $c$ in the domain we have a correct inference rule of the form: $$\boxed {\begin{array}{c}\underline{\forall xP(x)} \\P(c)\end{array}}$$

For example,

$$\begin{array}{lc}& \underline{\text{Everyone in the class is feeling miserable today.}}\\ \therefore & \text{Agi is feeling miserable today.}\end{array}$$

By universal instantiation, given the premise $(\forall x)\varphi (x)$, we may derive the conclusion $\varphi (x/t)$, where $t$ is any object in the domain:

$$\frac{(\forall x)\varphi (x)}{\varphi (x/t)}(\text{UI})$$

If $\varphi (x)$ holds for all the elements of the domain, it holds in particular for the element $t$ as well. Universal instantiation can be seen as $\forall$-elimination.

Link to original

Universal generalisation

A universal generalisation is $$ \boxed{\begin{array}{c} \underline{P(c) \textsf{ for any arbitrary entity } c \textsf{ in the domain}} \\ \forall x P(x)\end{array}} $$

By universal generalisation, given the premise $\varphi (x/t)$ takes place for a generic object $t$ of the domain, we may derive $(\forall x)\varphi (x)$:

$$\frac{\varphi (x/t)}{(\forall x)\varphi (x)}(\text{UG})$$

The object $t$ in the premise of $(\text{UG})$ must not be specific but arbitrary, i.e. we cannot make any assumption about $t$ other than it comes from the domain. Universal generalisation can be seen as $\forall I$.

Link to original

Existential quantifier, $\exists$.

Existential quantifier

The existential quantification of $P(x)$ for a particular domain, denoted by $\exists xP(x)$, is the proposition that "there exists a value for $x$ in the domain such that $P(x)$ is true".

• The truth value of $\exists xP(x)$ might change when domain changes.
• Domain must always be specified when used.

For example, take $P(x)$ is "$x<-3$":

• If the domain is all integers, then it is true.
  • We simply need to give one example, such as $x=-5$ then $P(-5)$ is true.
• If the domain is the positive integers, then it is false.

To say “(at least one) car is yellow”, we write that for some $x$, $x$ is yellow:

$$(\exists x)(Colour(x,yellow))$$

In general, the notation for existential quantifiers is $(\exists x)(\phi)$, where $\phi$ is a formula in which $x$ and possible other variables may appear..

Link to original

Rules of inference ($\exists$)

Existential generalisation

An existential generalisation means that for every entity $c$ in the domain, we have a correct inference rule of the form $$ \boxed{ \begin{array}{c} \underline{P(c)} \\ \exists x P(x) \end{array} } $$

For example:

$$\begin{array}{lc}& \underline{\text{Marla is reading the lecture notes.}}\\ \therefore & \text{There is someone in the class reading the lecture notes.}\end{array}$$

By existential generalisation, given that $\varphi (x/t)$ is known to hold for a particular object $t$ of the domain, we may derive $(\exists x)\varphi (x)$:

$$\frac{\varphi (x/t)}{(\exists x)\varphi (x)}(\text{EG})$$

This can be seen as $\exists I$.

Link to original

There are also deMorgan laws for quantifiers.

{
	"url":"[FC1W1 Lecture Slides.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1FC1%20Foundations%20of%20Computing%201/Week%201.%20Intro%20to%20propositional%20logic%20and%20proofs/FC1W1%20Lecture%20Slides.pdf)",
	"page":[32],
	"scale":1.5,
	"rect":[40, 260, 40, 400]
}