GATE CSE 2010 | Question: 30

Question

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,

  $\qquad∀x∃y∃t(¬F(x,y,t))$ 

• 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

Comments

Yeah

---

b
good question done

---

Easy - Write FOL of All the options 

https://gateoverflow.in/1156/gate-cse-2010-question-30?show=537670#a537670

Answer 1

$F(x, y, t) \implies$ 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)) \equiv ¬∃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.

$\color{blue}{¬∃}x\color{green}{∀}y\color{red}{∀}t(F(x, y, t))\implies \color{blue}{\text{ There does not exist }}$$ \text{a person who can fool }$$\color{green}{\text{everyone}} $$\color{red}{\text{ all}} \text{ the time.}$

Which means No one can fool everyone all the time.

So, option (B) is correct.

Comments

i am confused with option D, can someone help me with that why it is wrong?
∀x∃y∃t
it means : everyone someone some
so, how come in the option B, we are taking : no one, everyone, all

---

convert what option D says to logic.

option D - No one can fool some person at some time

it may be simplified to say that, there does NOT exist anyone who can fool SOMEONE at SOME time.

in logic - ¬∃x∃y∃t(F(x,y,t))

this clearly doesnt match with the given logic statement in the question.

 

coming to your second question, dont just look at the quantifiers, look at the predicate function too, its negated (look inside the bracket) so when you propogate its negation outside the bracket, the quantifiers will also change.

 

---

i also solved like this

Answer 2

B is the correct answer. The trick is to bring the negate sign to the extreme left. Form a sentence without using negate and just negate that.

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

Comments

I'm not getting this: by your logic: ! ∃x∀y∀z(F(x,y,z) without negation: some person can fool everyone all the time.  
If you negate the sentence: some person can't fool everyone all the time.  so I'm not able to arrive at option b. pls help. 

---

¬(∃x∀y∀t(F(x,y,t)))≡¬(∃x∀y∀t(F(x,y,t))). means that "it is false that there exists at least some x,which can fool all persons (y's) at all times". That means no 'x' exists which do it i.e "No one can fool everyone all the time"

---

@Bhagirathi

Can you please check your $\mathbf{3^{rd}}$ step.

Where is the inner $\mathbf{Negation}$.

Answer 3

Without negation the statement is like: Everyone can fool Someone at some time. 

So symply, with negation it will be like: No one can fool everyone all the time.

Comments

@arjun sir..... So the answer could be C also?

---

Nopes. Then "all the time" in C should be changed to "some time".

---

Thanks sir

Answer 4

∀x∃y∃t(¬F(x,y,t))∀x∃y∃t(¬F(x,y,t)) 

Everyone cannot fool  someone at some time

   (∀x)             (¬F)           (∃y)              (∃t)

to translate in hindi in other words

har koyi kisi na kisi  ko bewakoof banane mein  asafal rahy ga kisi na kisi time pe

so

no one can fool everyone all the time

Answer(B)

Answer 5

The given FOL expression is as $\forall x \, \exists y \, \exists t \, (\neg \, F(x, y, t))$ which means 

"For every person x, there exists a person y who cannot be fooled at some time t."

 

By using De-Morgan's law, we could bring the NOT operator to the left,

$\neg \, \exists x \, \forall y\, \forall t\, (F(x, y, t)) \equiv$ "It is false that someone can fool everyone at all time." $\equiv$ "There is no person x that can fool every person y at all time t."

which also means "No one can fool everyone all the time." (Answer : Option B)

 

Analysing Option A

A) "Everyone can fool some person at some time." (which is straigh-forward)

$\forall x\, \exists y\, \exists t \, (F(x, y, t))$

 

Analysing Option C

C) "Everyone cannot fool some person all the time." which can be meant as "For every person x, there exists some person y who cannot be fooled at any time t."

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

Using De-Morgan's law, the above expression can be written as 

$\neg \, \exists x\, \forall y\, \exists t\, (F(x, y, t)) \equiv$ "It is false that someone can fool everyone at some time."

 

Analysing Option D

D) "No one can fool some person at some time." which is equivalent to "It is false that someone can fool some person at some time" and it can be written as

$\neg \, \exists x\, \exists y\, \exists t \, (F(x, y, t))$

Using De-Morgan's law, the above expression can be written as

$\forall x\, \forall y\, \forall t\, (\neg \, F(x, y, t)) \equiv$ "No one can fool any one at any time."

 

Answer 6

 

😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊😊