Null Quantification Complete Lecture: Null Quantification Rules in Predicate Logic
Null Quantification mean when a quantified variable does not appear in part of a statement.
For e.g. Consider this : $\forall x (P(x) \wedge A)$ .. where x does not occur as a free variable in $A$ Or informally(not precisely correct But for simplicity purpose..) we could say There is No $x$ in $A$ (See Note 1 below).
Rules for Null Quantification can be used when a quantified variable does not appear in part of a statement.
Following are some rules :
$\forall x (P(x) \wedge A) \equiv \forall x P(x) \wedge A$
$\forall x (P(x) \vee A) \equiv \forall x P(x) \vee A$
$\exists x (P(x) \vee A) \equiv \exists x P(x) \vee A$
$\exists x (P(x) \wedge A) \equiv \exists x P(x) \wedge A$
$\exists x (A \rightarrow P(x) ) \equiv A \rightarrow \exists x P(x)$
$\forall x (A \rightarrow P(x) ) \equiv A \rightarrow \forall x P(x)$
NOTE the following :
$\forall x (P(x) \rightarrow A ) \rightarrow ( \forall x P(x) \rightarrow A)$ ...Is True
$\forall x (P(x) \rightarrow A ) \leftarrow ( \forall x P(x) \rightarrow A)$...Is False.
$\exists x (P(x) \rightarrow A ) \leftarrow (\exists x P(x) \rightarrow A)$....Is True.
$\exists x (P(x) \rightarrow A ) \rightarrow (\exists x P(x) \rightarrow A)$....Is False.
NOTE the following as well :
$\forall x (P(x) \rightarrow A ) \equiv \exists x P(x) \rightarrow A$
$\exists x (P(x) \rightarrow A ) \equiv \forall x P(x) \rightarrow A$
HINT for Proving Rules of Null Quantification : Take two cases for each rule : When $A$ is True and When $A$ is False.
Let me show proof for any one of the above (All others can be proven in similar way) :
Consider this : $F : \forall x (P(x) \rightarrow A ) \rightarrow ( \forall x P(x) \rightarrow A)$
Let me call the LHS $P $ and RHS $Q$ i.e. $P = \forall x (P(x) \rightarrow A )$ and $Q = ( \forall x P(x) \rightarrow A)$
So, $F$ is $P \rightarrow Q$, which is implication which is Always True except when $P$ is True and $Q$ is False simultaneously.
Now, There could be Two cases :
Case 1 : $A$ is True.
In this case, Always, $P$ is True(See Note 2 below) and $Q$ is True. So, $P \rightarrow Q $ i.e. $F$ is True in this case.
Case 2 : $A$ is False.
In this case, $P$ will become $\forall x (\sim P(x))$ and $Q$ will become $\sim \forall x P(x)$ which means $Q$ is $\exists x \sim P(x)$, And by definition of $\forall \,\,and\,\, \exists,$ $\forall x (\sim P(x)) \rightarrow \exists x \sim P(x) ,$ Hence, $F$ is True in this case as well.
Hence, we have shown that $F$ is Always True i.e. Valid Formula.
Now, Let's consider this formula : $S : \forall x (P(x) \rightarrow A ) \leftarrow ( \forall x P(x) \rightarrow A)$
Let me call the LHS $P $ and RHS $Q$ i.e. $P = \forall x (P(x) \rightarrow A )$ and $Q = ( \forall x P(x) \rightarrow A)$
So, $S$ is $P \leftarrow Q$, which is implication which is Always True except when $P$ is False and $Q$ is True simultaneously.
Now, There could be Two cases :
Case 1 : $A$ is True.
In this case, Always, $P$ is True(See Note 2 below) and $Q$ is True. So, $P \leftarrow Q $ i.e. $S$ is True in this case.
Case 2 : $A$ is False.
In this case, $P$ will become $\forall x (\sim P(x))$ and $Q$ will become $\sim \forall x P(x)$ which means $Q$ is $\exists x \sim P(x)$, And we know that $\forall x (\sim P(x)) \leftarrow \exists x \sim P(x) ,$ is False. Hence, $S$ is False in this case.
Hence, we have shown that $S$ is Not Always True i.e. It is Not Valid Formula.
NOTE 1 : In the above answer, I wrote this :
"Consider this : $\forall x (P(x) \wedge A)$ .. where $x$ does not occur as a free variable in $A$ Or informally(not precisely correct But for simplicity purpose..) we could say There is No $x$ in $A$ "
Let's see this little bit more :
If $x$ does not, at all, appear in $A$ then we can easily also say that $x$ does not occur as a free variable in $A$
But If $x$ does not occur as a free variable in $A$ then we, technically, cannot say that $x$ does not, at all, appear in $A.$
For instance, consider this : Let $A = \forall x Q(x)$, here, $x$ does not occur as a free variable in $A$ But $x$ appears in $A$ (Here $x$ is called Bounded Variable or Quantified Variable )
So, In Null Quantification rules, the Condition is that $x$ does not occur as a free variable in $A.$
NOTE 2 : $\forall x P(x) \rightarrow \exists x P(x) $ is said to be True in logic But it is actually False for Empty Domain.
But we, anyway, say that $\forall x P(x) \rightarrow \exists x P(x) $ is True because in First Order Logic, by default, Non-empty domains are considered.
Null Quantification Complete Lecture: Null Quantification Rules in Predicate Logic
GATE 2020 question on Null Quantification: https://gateoverflow.in/333192/gate-cse-2020-question-39
See here for more : https://gateoverflow.in/132789/free-variable-and-validity-related-problem
https://gateoverflow.in/132788/%23-free-variable-null-quantification-related-problem
