GATE2010-30

5.8k views

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

1. Everyone can fool some person at some time
2. No one can fool everyone all the time
3. Everyone cannot fool some person all the time
4. No one can fool some person at some time

edited

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

edited by
1
after applying de morgan's law why negation sign is with only there exits and not with for all
23

Negation sign propagates like this.

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

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

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

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

0

The last line should be  ¬∃x∀y∀t(F(x,y,t)).

1
@vineet.ildm negation sign is just propagated outward by successively applying de Morgan's law.
0
this one helped me
Thanks..
0
if we don't want to bring negation outside, then is it possible to answer?

What does it mean by $\neg F(x,y,t)$  ?
0
What's wrong with option C??
0
Does the negate sign only apply with the leftmost (all values of x) or negate for the entire expression.
0

@Verma Ashish it says if there is a group of people and you call anyone from the group, for every person being called there will always exist a person who will not get fooled by him.

EDIT: I option c, a specific person is targeted by all which is not implied by the formulae. "There exist y" y need not be unique, just for each and every person there exist a person y.

0

@tusharp

@verma

Is $\mathbf{no-one}$ means $\mathbf{\exists}$?

1
No one means ~$\exists$
0
Thanks
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)))$.

edited by
0

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.

1
¬(∃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"
0

@Bhagirathi

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

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

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.

0
What would be the predicate logic for option C : "Everyone cannot fool some person all the time".
5
∀x∃y∀t(¬F(x,y,t))
0
Then what will be the meaning of this logic: ∀x∃y(¬∀t(F(x,y,t)))
I simply took negation outside the function F.
0
1. No one can fool everyone all the time = No (one can fool everyone all the time) = ¬[∃x∀y∀t(F(x,y,t))] = ∀x∃y∃t(¬F(x,y,t)) got it
2. ∀x∃y(¬∀t(F(x,y,t))) = ∀x∃y∃t(¬F(x,y,t)) same meaning of above.
0
∀x∃y(¬∀t(F(x,y,t))) should be equal to  "Everyone cannot fool some person all the time".

English tranlation of this logic (∀x∃y(¬∀t(F(x,y,t)))) could be: For all x there exist a Y such that x can not fool y all the time.
0
∀x∃y(¬∀t(F(x,y,t))) should be equal to Everyone cannot fool some person not all the time

which means Everyone cannot fool some person all the time .
0
for all t also negate na u cannot ignore it.
0
Ya ok...so
For all x there exist a Y such that x can not fool y not all the time.
What would the meaning of above statement in simple english?
And sorry of these silly doubts...
1

What would the meaning of above statement in simple english :

For all x there exist a Y such that x can[ not fool y not all the time].

= For all x there exist a Y such that x can not (fool y some time).

0
For all x there exist a Y such that x can not (fool y some time).
So my actual doubt was can it be equal to  "Everyone cannot fool some person all the time"(option c)....:P
1

No. I guess a "not" came extra in beween and you meant

For all x there exist a Y such that x can not (fool y ALL time).

Now

Everyone cannot fool some person all the time

Both are same. Both mean, a "person" exist who can not be fooled by everyone all the time- this person can be different for each person.

1
@arjun sir..... So the answer could be C also?
1
Nopes. Then "all the time" in C should be changed to "some time".
0
Thanks sir

Related questions

1
5k views
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{equivalent} (a,b)$ ...
The CORRECT formula for the sentence, "not all Rainy days are Cold" is $\forall d (\text{Rainy}(d) \wedge \text{~Cold}(d))$ $\forall d ( \text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{~Rainy}(d) \to \text{Cold}(d))$ $\exists d(\text{Rainy}(d) \wedge \text{~Cold}(d))$
What is the logical translation of the following statement? "None of my friends are perfect." $∃x(F (x)∧ ¬P(x))$ $∃ x(¬ F (x)∧ P(x))$ $∃x(¬F (x)∧¬P(x))$ $¬∃ x(F (x)∧ P(x))$
$\def\graph{\text{ Graph}} \def\connected{\text{ Connected}}$ Let $\graph(x)$ be a predicate which denotes that $x$ is a graph. Let $\connected(x)$ be a predicate which denotes that $x$ is connected. Which of the following first order logic sentences DOES NOT represent the statement: ... $\forall x \, \Bigl ( \graph(x) \implies \lnot \connected(x) \Bigr )$