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

But

$\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

P(0,0)=True

P(0,1)=True

P(1,0)=True

P(1,1)=True

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

P(0,0)=False

P(0,1)=False

P(1,0)=False

P(1,1)=False

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???

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$$

but:

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

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

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger