Quantificational logic is an extension of propositional logic. It is logic of expressions such as “for any”, “for all”, “there is some”, and “there is exactly one”. Quantificational logic is also called first-order logic, predicate logic, or predicate calculus. The universal quantifier $\forall$ means “for all”, “for each”, “for any”, or “for every”. The existential quantifier $\exists$ means “there exists”.
Example. $\forall x\exists y P(x,y)$
Quantificational formulae such as the one in the above example are merely strings of symbols which do not mean anything (i.e. being true or false) as logical statements until they are accompanied by proper interpretations. An interpretation of a quantificational formula has to specify the following.
- The universe $U$, the nonempty set from which the values of the variables ($x$, $y$, $z$, etc.) are drawn.
- For each, say $k$-ary, predicate symbol $P$, which $k$-tuples of members of $U$ the predicate is true of, and
- What elements of the universe correspond to any constant symbols, and what functions from the universe to itself correspond to function symbols mentioned in the formula.
Example. Let $U=\{0,1\}$ and $P$ be the less-than relation i.e. $P(x,y)$ is “$x$ is less than $y$.” Then
- $P(0,0)$ is false
- $P(0,1)$ is true
- $P(1,0)$ is false
- $P(1,1)$ is false
The quantificational formula $\forall x\exists y P(x,y)$ is false because there is no value of $y$ in the universe for which $P(x,y)$ is true when $x=1$.
Example. Let $U=\{0,1\}$ and $P$ be the not-equal relation i.e. $P(x,y)$ is “$x$ is not equal to $y$.” Then
- $P(0,0)$ is false
- $P(0,1)$ is true
- $P(1,0)$ is true
- $P(1,1)$ is false
Hence $\forall x\exists y P(x,y)$ is true.
In general, the universe of an interpretation is an infinite set, so it is impossible to specify the values of the predicate for every combination of elements. For a remedy, we restate the definition in terms of relations by saying an interpretation of a quantificational formula consists of
- a nonempty set called the universe
- for each $k$-place predicate symbol, a $k$-ary relation on the universe
- for each $k$-place function symbol, a $k$-ary function from the universe to itself.
Example. Let $U=\mathbb{N}$, the set of natural numbers and $P$ be the less-than relation. Then the formula $\forall x\exists y P(x,y)$ is true.
Example. Let $U=\mathbb{N}$ and $P$ be the greater-than relation. Then the formula $\forall x\exists y P(x,y)$ is false.
Example. An example of a formula involving a function. Let $U=\mathbb{N}$ and $P(x,y)$ be $\forall x\exists y(x+y=0)$. The constant symbol 0 is interpreted as zero and the binary function symbol $+$ represents addition. The formula is false. For example, when $x=1$, there is no value of $y$ in the universe such that $x+y=0$. If $U=\mathbb{Z}$, the set of integers, however, the formula is true.
Two formulae are equivalent if they are true under the same interpretation.
Example. $\forall x\exists y P(x,y)$ and $\forall y\exists x P(y,x)$ are equivalent.
If two formulae $F$ and $G$ are equivalent, we write $F\equiv G$.
A model of a formula is an interpretation in which it is true. A satisfiable formula of quantificational logic is one that has a model. A valid formula, also called theorem, is a formula that is true under every interpretation. Valid formulae are the quantificational analogs of tautologies in propositional logic.
Example. $\forall x(P(x)\wedge Q(x))\Longrightarrow\forall y P(y)$ is a valid formula. $\forall x P(x)\wedge\exists y\neg P(y)$ is unsatisfiable.
Note. $\exists x (H(x)\wedge B(x))\not\equiv\exists xH(x)\wedge\exists x B(x)$. $\exists x (H(x)\wedge B(x))\not\equiv\exists x H(x)\wedge B(x)$. $x$ in $B(x)$ in the second formula is a free variable i.e. $\exists x H(x)\wedge B(x)\equiv(\exists x H(x))\wedge B(x)$$
The laws we learned in propositional logic are carried over. For example, Distributive Laws \begin{align}\forall x(P(x)\wedge(Q(x)\vee R(x)))&\equiv\forall x((P(x)\wedge Q(x))\vee(P(x)\wedge R(x)))\label{eq:distlaw1}\\\forall x(P(x)\vee(Q(x)\wedge R(x)))&\equiv\forall x((P(x)\vee Q(x))\wedge(P(x)\vee R(x)))\label{eq:distlaw2}\end{align}
Quantificational Equivalence Rule 1 (Proposition Substitutions)
Suppose $F$ and $G$ are quantificational formulae and $F’$ and $G’$ are propositional formulae that result from $F$ and $G$, respectively, by replacing each subformula by a corresponding propositional variable at all of its occurrences in both $F$ and $G$. Suppose $F’\equiv G’$ as formulae of propositional logic. Then replacing $F$ by $G$ in any formula results n an equivalent formula.
Example. $\forall x\neg\neg P(x)\equiv\forall x P(x)$ since $p\equiv\neg\neg p$ and so $\neg\neg P(x)$ can be replaced by $P(x)$.
Example. Replacing $P(x)$, $Q(x)$ and $R(x)$ by $p$, $q$ and $r$, respectively, turns $P(x)\wedge(Q(x)\vee R(x))$ into $p\wedge(q\vee r)$ and $(P(x)\wedge Q(x))\vee(P(x)\wedge R(x))$ into $(p\wedge q)\vee(p\wedge r)$. Since $p\wedge(q\vee r)\equiv (p\wedge q)\vee(p\wedge r)$, $P(x)\wedge(Q(x)\vee R(x))$ can be replaced by $(P(x)\wedge Q(x))\vee(P(x)\wedge R(x))$. Hence we have the equivalence in \eqref{eq:distlaw1}.
Quantificational Equivalence Rule 2 (Change of Variables)
Let $F$ be a formula containing a subformula $\Box x G$, where $\Box$ is either $\forall$ or $\exists$. Assume $G$ has no bound occurrence of $x$ and let $G’$ be the result of replacing $x$ by $y$ everywhere in $G$. Then replacing $\Box x G$ by $\Box y G’$ within the formula results in an equivalent formula.
Example. $\exists x (H(x)\wedge B(x))\equiv\exists y (H(y)\wedge B(y))$
Quantificational Equivalence Rule 3 (Quantifier negation)
\begin{align*}\neg\forall x F&\equiv\exists x\neg F\\\neg\exists x F&\equiv\forall x\neg F\end{align*}
Quantificational Equivalence Rule 4 (Scope change)
Suppose the variable $x$ does not appear in $G$. Let $\Box$ denote either $\forall$ or $\exists$. Let $\diamond$ denote either $\vee$ or $\wedge$. Then \begin{align*}(\Box x F\diamond G)&\equiv\Box x(F\diamond G)\\(G\diamond\Box x F)&\equiv\Box x(G\diamond F)\end{align*}
Example. Let $r$ be “it rains”, $\mathrm{outside(x)}$ “$x$ is outside” and $\mathrm{wet}(x)$ “$x$ gets wet”. Then “If it is raining, then anything that is outside will get wet” is written as the quantificational formula $$r\Longrightarrow\forall x(\mathrm{ouside}(x)\Longrightarrow\mathrm{wet}(x))$$ This is equivalent to $$\forall x(r\Longrightarrow(\mathrm{ouside}(x)\Longrightarrow\mathrm{wet}(x)))$$ as a consequence of scope change. The transformed formula says, in plain English, “Any object, if it is raining, will get wet if it is outside” which sounds less natural than the original statement.
Example. As a consequence of scope change we obtain \begin{align*}(\forall x P(x)\vee\exists y Q(y))&\equiv\forall x\exists y (P(x)\vee Q(x))\\&\equiv\exists y\forall x(P(x)\vee Q(y))\end{align*}
Example. For $(\forall x P(x)\vee\exists x Q(x))$, neither quantifiers can be moved out because the quantified variable $x$ appears in both subformulae. However, instead of scope change one can use change of variable rule to turn it into $(\forall x P(x)\vee\exists y Q(y))$ which is shown in the previous example.
Through repeated application of the quantificational equivalence rules, all quantifiers can be pulled out to the beginning of the formula. Such a formula is said to be in prenex normal form.
Example. Let $L(x,y)$ be “$x$ loves $y$”. Then the statement “everyone has a unique beloved” can be written as the quantificational formula $$\forall x\exists y (L(x,y)\wedge\forall z (L(x,z)\Longrightarrow y=z)$$ It can be transformed to the formula in prenex form $$\forall x\exists y\forall z(L(x,y)\wedge(L(x,z)\Longrightarrow y=z))$$
Example. Translate into quantificational logic and put into prenex form: “If there are any ants, then one of them is the queen.”
Solution. Let $A(x)$ be “$x$ is an ant and $Q(x)$ “$x$ is a queen.” Then the statement can be written as the quantificational formula $$\exists x A(x)\Longrightarrow\exists y (A(y)\wedge Q(y)\wedge\forall z (Q(z)\Longrightarrow z=y))$$ It’s direct translation is “If there exists an $x$ such that $x$ is an ant, then there exists a $y$ such that $y$ is an ant and $y$ is a queen and any $z$ that is a queen is equal to $y$.” The formula can be transformed to \begin{align*}\neg\exists x A(x)\vee\exists y(A(y)\wedge Q(y)\wedge\forall z (Q(z)\Longrightarrow z=y))&\equiv\forall x\neg A(x)\wedge\exists y(A(y)\wedge Q(y)\wedge\forall z (Q(z)\Longrightarrow z=y))\\&\equiv\forall x\exists y\forall z(\neg A(x)\vee(A(y)\wedge Q(y)\wedge\forall z (Q(z)\Longrightarrow z=y))\end{align*}
References.
[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019