1,223 views
1 votes
1 votes

If we  think about nested quantifiers as nested loops ∀x((F (x) ∧ P(x)) → ∃yM(x, y)) for this then when we are iterating for outer loop x and we find the LHS to be true then only iterate in internal loop of y whether she is a mother. But ∀x∃y((F (x) ∧ P(x)) → M(x, y)) says

for (x){

for(y){

y((F (x) ∧ P(x)) → M(x, y)

}

}

We are making unnecessary comparisons here. So how could we move that existential quantifier in beginning? What is null quantification?

1 Answer

Best answer
1 votes
1 votes

It will be like -  

$for (x)$
{
      $if (F(x) \ and \ P(x))$
      { 
         $for(y)$
                {
                       $ if(M(x,y)) $
                           $break;$
                }
     }
}

 

In $\forall x((F(x) \wedge P(x)) \rightarrow \exists y M(x, y)), y$ does not occur as a free variable at LHS of implication so you can move it to left side of whole predicate. 
$\forall x((F(x) \wedge P(x)) \rightarrow \exists y M(x, y)) \equiv  \forall x \exists y((F(x) \wedge P(x)) \rightarrow M(x, y))$

For Null Quantification - Refer this

selected by

Related questions

0 votes
0 votes
0 answers
3
ykrishnay asked Mar 25, 2022
152 views
0 votes
0 votes
0 answers
4