edited by
3,262 views
25 votes
25 votes

Which of the following is NOT necessarily true? { Notation: The symbol ''$\neg$''notes negation; $P (x, y)$ means that for given $x$ and $y$, the property $P(x, y)$ is true }.

  1. $(∀x∀y P(x, y)) \Rightarrow (∀y∀x P(x, y))$
  2. $(∀x∃y \neg P(x, y)) \Rightarrow \neg (∃x∀y P(x, y))$
  3. $(∃x∃y P(x, y)) \Rightarrow  (∃y∃x P(x, y))$
  4. $(∃x∀y P(x, y)) \Rightarrow  (∀y∃x P(x, y))$
  5. $(∀x∃y P(x, y)) \Rightarrow  (∃y∀x P(x, y))$
edited by

4 Answers

Best answer
21 votes
21 votes
  1. is TRUE as both LHS and RHS are equivalent- English would be for every $x$, and for every $y, P(x,y)$ is TRUE. Changing $y$ and $x$ wouldn't change the meaning.
     
  2. is TRUE as both LHS and RHS are equivalent- RHS is obtained by double negation of LHS.
     
  3. Similar to (a), both are equivalent.
     
  4. LHS: For some $x$, for all $y, P(x,y)$ is TRUE.
    RHS: For all $y$ and for some $x, P(x,y)$ is TRUE.
    Both are not equivalent. LHS is stronger and implies RHS. For example, on the natural number set, we have $x = 1$ such that for every $y, P(x \leq y)$ is TRUE. Clearly, this implies for all $y$ there exists some $x$ (here $x$ could be different for different $y$ but on LHS, it must be the same).
     
  5. LHS: For all $x$ and for some $y, P(x, y)$ is TRUE.
    RHS: For some $y$ and for all $x, P(x, y)$ is TRUE.

    As explained in d, these are not equivalent and here RHS is stronger than LHS, making the implication false. For example, consider the "<=" relation on the integer set. LHS is true here as for every integer we have another integer which is greater. But RHS is false as there is no single integer (infinity is not an integer) which is greater than all other integers. 

Hence, (E) is not necessarily TRUE.

edited by
12 votes
12 votes

The order of the quantifier does not matter if all the quantifiers in the expression are same. 
Using this rule, we eliminate options (a) and (c).

Option (b)

(∀x∃y¬P(x,y))⇒¬(∃x∀yP(x,y))

Take RHS

¬(∃x∀yP(x,y))

Apply de-morgan law

~∀x(P(X)) ≡ ∃x(~P(X))

~∃x(P(X)) ≡ ∀x(~P(X))

So, RHS aso becomes 

(∀x∃y¬P(x,y)). So. option (b) is also true.

For options (D) and (E), consider P(x,y) to be x+y=0 and domain of x,y to be set of all real numbers.

option (D)

(∃x∀yP(x,y))⇒(∀y∃xP(x,y))

L.H.S : For some x, there exist all y such that x+y=0. This is clearly false as there can be no single real number for which every other real number value would result in x+y=0.

So, L.H.S. becomes false.

Since, L.H.S. is false, implication becomes true.

Hence, option (D) is also True.

Now coming to option (E)

(∀x∃yP(x,y))⇒(∃y∀xP(x,y))

L.H.S. : For all x, there exist a y such that x+y=0. Yes this is true. For all real number x, we can have y such that y=-x and x+y=0.

R.H.S : For some y,(see here now you fix y), there is all x(means all values of x) such that x+y=0. This is false.

Hence, implication becomes false.

Ans-(E)

4 votes
4 votes

option e is false

since

(∀x∃y P{x, y}) for all x there is some y for which p is true 

 (∃y∀x P{x, y}) but for some y there is not all x may be some y are left out this make it false

now p ⇒ q is false when p is true and q is false therefore whole statement is false.

0 votes
0 votes

Let us Understand this by taking a Simple Example...

let x∈{Set of students}

y∈{Set of courses offered by a University to their students},

and, Predicate P(x, y)="x takes course y".

Now, Let's see the options for this question.


(A) If we translate this FOL into the equivalent English statement it becomes 

LHS= "All students take all courses"

RHS= "All courses are taken by all students"

so we see there are same thing (LHS=RHS).

so, A is TRUE.


(B) Here LHS and RHS are equivalent FOL expressions, just move ~ sign inside the braces and get LHS.


(C) Similarly, If we translate this FOL into the equivalent English statement 

LHS= "Some student take some course".

RHS= "Some course is taken by Some student"

Both LHS and RHS Meaning is same ('you eat fruit' or 'fruit is eaten by you' is same meaning),so we see there are equivalent(LHS=RHS).

so, C is also TRUE.


(D) Similarly, for this option,

LHS= "Some student takes all courses".

RHS= "All courses are taken by Some student"

here LHS and RHS look similar but understand this with an another example...

Consider, x and y both ∈ {Set of real Numbers}

and, P(x, y)= x + y=2

now, LHS says " There exist a value of x, for all value of y such that, x + y=2 is true"  (FALSE statement)

so LHS is FALSE, and FALSE → (anything)== always TRUE

so, D is also TRUE.


(E) BUT now, for this option,

LHS= "All students takes some course".

RHS= "Some course is taken by All students"

here also, LHS and RHS look similar 

Consider, x and y both ∈ {Set of real Numbers}

and, P(x, y)= x + y = 2

LHS= "For all values of x, there exist a value of y such that , x + y=2 is true". (ALWAYS TRUE).

but........

RHS= "There exist a value of y, for all value of x such that, x + y =2 is  true"  (FLASE statement)

and TRUE(LHS) → FALSE(RHS) == FALSE

so, E is FALSE.

SO, ANSWER -- E 

Answer:

Related questions