edited by
609 views
3 votes
3 votes

Given that 

LHS :  [(∃x,α(x))→β]
RHS :  [∃x,α(x)→β]

Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.

than which one is valid ?

a)    LHS → RHS

b)     RHS → LHS

edited by

2 Answers

2 votes
2 votes

Null Quantification Complete Lecture: Null Quantification Rules in Predicate Logic 

Let me first put proper parentheses to remove any ambiguity in reading the given expressions i.e. 

 LHS :   $[(∃x,α(x))→β]$, let's call it $Q$

RHS :   $[∃x,(α(x)→β)]$, let's call it $P$

And we have the following : "Here α(x) is a first order formula with $x$ as a free variable, and β is a first order formula with no free variable (more precisely, β does not have $x$ as a free variable)."(See Note 1 below)

then $P \leftarrow Q$ is True But $P \rightarrow Q $ is False.

Proof :

For simplicity of Typing, I am replacing $α(x)$ with $P(x)$ and $β$ with $A.$

So, Let : $P : \exists x (P(x) \rightarrow A ) \,\, and\,\, Q : ( \exists x P(x) \rightarrow A)$

First consider this : $F : \exists x (P(x) \rightarrow A ) \rightarrow (\exists 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 $\exists x (\sim P(x))$ and $Q$ will become $\sim \exists x P(x)$ which means $Q$ is $\forall x \sim P(x)$, And we know that  $\exists x \sim P(x) \rightarrow \forall x (\sim P(x))  ,$ is False. Hence, $F$ is False in this case.

Hence, we have shown that $F$ is Not Always True i.e. It is Not Valid Formula.


Now, Consider the other direction i.e. $S : \exists x (P(x) \rightarrow A ) \leftarrow (\exists 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 $\exists x (\sim P(x))$ and $Q$ will become $\sim \exists x P(x)$ which means $Q$ is $\forall x \sim P(x)$, And we know that  $\exists x \sim P(x) \leftarrow \forall x (\sim P(x))  ,$ is True(See Note 2 below). Hence, $S$ is True in this case as well.

Hence, we have shown that $S$ is Always True i.e. Valid Formula.


So, in the Question, $a$ is True But $b$ is False.


NOTE 1 : In the above answer, we have this condition :

"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 

Refer here for more : https://gateoverflow.in/130504/null-qunatification-rule?show=219958#a219958

edited by

Related questions

1 votes
1 votes
2 answers
1
0 votes
0 votes
1 answer
2
3 votes
3 votes
3 answers
3