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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice approach. I understood what you did. But can we also move from the left to the right? $\endgroup$
    – rsonx
    Oct 7, 2019 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$
    – integrator
    Oct 7, 2019 at 10:29
1
$\begingroup$

F(x,y,t)⟹ person x can fool person y at time t.

For the sake of simplicity propagate negation sign outward by applying De Morgan's law.

∀x∃y∃t(¬F(x,y,t))≡¬∃x∀y∀t(F(x,y,t)) [By applying De Morgan's law.]

Now converting ¬∃x∀y∀t(F(x,y,t)) to English is simple.

¬∃x∀y∀t(F(x,y,t))⟹ There does not exist a person who can fool everyone all the time. Which means No one can fool everyone all the time.

So, option (B) is correct.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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