Find the truth values for each P(x, y)???

by John Baek   Last Updated January 14, 2018 13:20 PM

Here is the problem

Let $S$ denote the two-element set {0, 1}. Find truth values (i.e. True of False) for each of P(0, 0), P(0, 1), P(1, 0), P(1, 1) so that

$\forall x\in S, \exists y \in S, P(x, y)$ is true


$\exists y \in S, \forall x\in S, P(x, y)$ is false.

This exercises illustrates the fact that changing the order of your quantifiers can change the meaning of your statement.

The problem's hint:

Just to clarify, for problem 5 you are assigning the value True or False to each of P(0,0), P(0,1), P(1,0), and P(1,1). That's four choices for you to make.

For example, if you choose





you'll see that both of the given statements become true, and if you choose





you'll see that both of the given statements become false.

What set of 4 choices makes the first given statement true and the second given statement false?

I answered the question like...

There are two pairs of truth values for P(0,0), P(0,1), P(1,0), P(1,1)
which satisfy two statements. (true true false false), (false false true true). 

And the professor said "You just need to find one such assignment."

Um.. I'm totally lost here. Could anyone help me to solve this problem???

Answers 1

The idea is that, for each $x$, we pick one $y$ so that $P(x,y)$ is true (in order to keep the first statement true), but this shouldn't be the same $y$ for all values of $x$ (in order to keep the second statement false).

So, let's pick $y=0$ for $x=0$ and $y=1$ for $x=1$. (This is one possible example, there are others.) Now set:

$$P(0,0)=\top, P(1,1)=\top$$


$$P(0,1)=\bot, P(1,0)=\bot$$

You can easily check that this choice of truth values does the job.

January 14, 2018 13:14 PM

Related Questions

Permutations and COMBINATION divisibility test

Updated November 16, 2017 01:20 AM

Discretizing a formula for simulation

Updated September 19, 2017 11:20 AM