Comparing Statements and predicates using Truth Tables Consider the four statements:


*

*$∃x$ $∀y$ $p(x, y)$

*$∃y$ $∀x$ $p(x, y)$

*$∀x$ $∃y$ $p(x, y)$

*$∀y$ $∃x$ $p(x, y)$


which we call S1, S2, S3 and S4 respectively.  


*

*Does there exist a predicate p such that S1 and s4 are true, but S2 and s3 are false? 

*Does there exist a predicate p such that S2 and s3 are true, but S1 and s4 are false? 

*Does there exist a predicate p such that S3 and s4 are true, but S1 and s2 are false? 

*Does there exist a predicate p such that S4 is true, but s1, S2 and s3 are false? 



Solution:
Consider the four predicates:

One can verify that:
  
  
*
  
*if we take p to be p1, then S1 and S4 are true, but S2 and S3 are false
  
*if we take p to be p2, then S2 and S3 are true, but S1 and S4 are false 
  
*if we take p to be p3, then S3 and S4 are true, but S1 and S2 are false 
  
*if we take p to be p4, then S4 is true, but S1, S2 and S3 are false
  

Here are my questions:


*

*Is my diagram correct (I highlighted the different sections)? 





*What is the structure of p1? How do you READ this table? Where is the INPUT? Where is the OUTPUT?

*How does p1 get fed into $∃x$ $∀y$ $p(x, y)$?

*How can I come up with p1?

*What is the significance of the row with #2 (highlighted in blue)?

 A: You have to read the "matrix" : $p_1, p_2, p_3, p_4$ as interpretations for the predicate letter $p$ that is $T/F$ according to the values assigned to the variables $x$ and $y$ respectively, where the values of $x$ must be read on the left and the values of $y$ on top.
Consider e.g. $S_1 : ∃x ∀y p(x,y)$, and consider the matrix $p_1$. 
Is it true that there is a value for $x$ such that $p(x,y)$ is $T$ for all values for $y$ ?

YES. Consider $p_1(0,y)$: it is $T$ for both values : $0,1$ for $y$.

Thus the predicate $p_1$ satisfy the formula $S_1$.
The same for $S_4$, and these results are consistent with the solution 1: "if we take $p$ to be $p_1$, then $S_1$ and $S_4$ are true, but $S_2$ and $S_3$ are false".

Note
In principle, the approach is the same IF we have to read the "matrix" in the other "direction" (as suggested by you : with the values for $x$ on top and the values for $y$ on the left) : but in that case, you can see that now the predicate $p_1$ does not satisfy the formula $S_1$.
But in the same way, you can verify that $p_2$ satisfy $S_1$.
