0
$\begingroup$

this is a problem which was asked in GATE CS 2010.

This is question statement:
Q:
Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula ∀x∃y∃t(¬F(x, y, t))?

Options:
A: Everyone can fool some person at some time.
B: No one can fool everyone all the time.
C: Everyone cannot fool some person all the time.
D: No one can fool some person at some time.

According to my solution:
If F(x): person x can fool person y at time t.
Then
$\forall$x $\exists$y $\exists$t ( ¬F( x, y, t ) )
is same as "Not all person x can fool some person y at some time t. which can be rewritten as "No one can fool some person at some time".
Hence Option D must be the correct one.
However I am wrong.

How to approach these type of problems.

$\endgroup$
2
$\begingroup$

I'm not sure how general this type of problem is so I can't tell you if this will always be the best approach, but in this case you can move the negation to the top for more clarity.

$$\forall x\ \exists y\ \exists t\ [\neg F(x,y,t)]\equiv \forall x\ \exists y\ [\neg\ \forall t F(x,y,t)]\equiv \forall x\ [\neg\ \forall y\ \forall t F(x,y,t)]\equiv \neg [\exists x\ \forall y\ \forall t F(x,y,t)]$$

From this you should be able to find the correct answer, which is:

B

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice approach. I understood what you did. But can we also move from the left to the right? $\endgroup$ – rsonx Oct 7 '19 at 10:24
  • $\begingroup$ Yes, so long as you correctly invert the operators encountered (e.g. $\neg\ \exists x$ becomes $\forall x\ \neg$), and distribute when appropriate (e.g. $\neg (A \lor B)$ is $(\neg A) \land (\neg B)$) $\endgroup$ – eru-cs Oct 7 '19 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.