GATE CSE 2003 | Question: 33

Question

Consider the following formula and its two interpretations \(I_1\) and \(I_2\).

\(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\)

\(I_1\) : Domain: the set of natural numbers

\(P_x\) =  '$x$ is a prime number'

\(Q_{xy}\) = '$y$ divides $x$'

\(I_2\) : same as \(I_1\) except that \(P_x\) = '$x$ is a composite number'.

Which of the following statements is true?

• A. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
• B. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
• C. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
• D. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)

Comments

What does "satisfies" mean here?? (Does it mean "satisfiability"?)

Are the terms "satisfiability" and "valid" equivalent??

---

satisfiability means true for at least one instance, valid means always true(true for all instances).

---

Ans Option D

This problem seems confusing to many Lets make it more simple::
First what is  "satisfiability"::::Meaning can you find a case where it is true ;

So our goal should to find A condition where above expression is TRUE;

So now come to format of question.

 

IT is having A$\Rightarrow$B which means we have three way to make it true(using TT of implication)

Come To I​2 
As Px is prime no so For composite no Px will be false That means Compliment Of Px will  be TRUE for every case(As here universal quantifier) So right site of implication is true so it will be True for all case.SO VALID

 

come to I1:

(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px] 

As Px is prime no so right side .. compliment of Px will  be False now In implication If right side is false then for To be True Left also should be false. One thing we have to focus now that how can we make left For atleast one Case 

So when we come inside the Bi-implication ([Px⇔(∀y)[Qxy⇔¬Qyy]])  we have  Px at one side which will be always true As Px is prime no.So to make biconditional  false right side we have to make false . Again right side is having biconditional  [Qxy⇔¬Qyy]]

Since we know ¬Qyy will always be fase because Qyy will always True (as every no will divide with itself).

So 

Qxy::meaning that y divide x .

  as we know when Y= 1and Y=x(meaning no itself) it will divide so Qxy  True .

So for [Qxy⇔¬Qyy]] we have two case where it will evalate False.(using TT)

 for  this Px⇔(∀y)[Qxy⇔¬Qyy]] right side is false in two cases and left will always be true.overall it will be false(universal quantifier).

         (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px] 

So for above expression we shown that Left is false for two cases and Right will always be False So It give us True for 

some cases so It is also Valid>

ANS OPTION D

 

---

@a new one 

Come To I​2  
As Px is prime no so For composite no Px will be false That means Compliment Of Px will  be TRUE for every case(As here universal quantifier) So right site of implication is true so it will be True for all case.SO VALID

Check it again... For i2 also rhs is false and it will be false for all cases. it is satisfiable because false $\Rightarrow$  false

Answer 1

Given: $(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right])\\$
$Q_{yy}$ is always True, this makes  $\neg Q_{yy}$ False.

Writing $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]$ is same as writing $(\forall y)[Q_{xy} \Leftrightarrow \text{False}]]$

This is equivalent to saying that, for all y $Q_{xy}$ is false and finally we can rewrite $(\forall y)[Q_{xy} \Leftrightarrow \neg Q_{yy}]]$ as $(\forall y)[\neg Q_{xy}]$

$\alpha : (\forall \mathbf{x)[P_x \Leftrightarrow (\forall y)[ \neg Q_{xy}]] } \Rightarrow (\forall x)[\neg P_x]$

$\text{LHS}:(\forall x)[ P_x ⇔(\forall y)[\neg Q_{xy}]]$

consider only $(\forall \mathbf{y)[\neg Q_{xy}]}$ it says all values of $y$ does not divide $x$, but there will be at least one value of $y$ (when $y=x$, or when $y=1$) that divides $x$, i.e. $\mathbf{[\neg Q_{xy}]}$ is not true for all values of $y$.  $(∀ \mathbf{y)[¬Q_{xy}]}$ is false.

Now LHS becomes $(∀x)[P_x \Leftrightarrow \text{False}]$, "$P_x \Leftrightarrow \text{False}$" this means $P_x$ is False, which is same as writing "$ \neg P_x$".

Finally, we reduced LHS to $(∀x)[\neg P_x]$

$α: (∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  (which is trivial, $P(x)⇒ P(x)$ is trivially true)

Hence $(∀\mathbf{x)[¬P_x]}⇒(∀x)[¬P_x]$  is trivially true for any $P(x)$, doesn't matter if $P(x)$ is for prime number or for composite number $(I1$ or $I2)$.

$ ⇒ I1$ and $I2$ both satisfies $α$.

Option D.

Comments

Awesome @Sachin Mittal 1 You made the answer look so easy. Thank you

---

@Sachin Mittal 1   Very good explanation.

---

@Sachin Sir thanks for the detailed explanation. I have one doubt, why Qyy will always be true is considered? What I think it's because as it's given Qxy means y divides x so we have to assume same for Qyy that y divides y which will be always true. So, is this the reason why Qyy is considered to be always true initially? Anyone please help.

---

@ankit3009 Yes you are correct, Qyy means y divides y(Which is always true for Natural numbers).

Answer 2

$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$

This is can be interpreted as:

• $\alpha: \left( (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \right) \Rightarrow \left((\forall x)\left[\neg P_x\right] \right)$

See the RHS. It says $P(x)$ is false for any natural number. But there are natural numbers which are prime and hence this RHS is FALSE. Now, to make $\alpha$ TRUE, LHS must be FALSE for any $x$. Here, LHS is bit complex, so lets consider it separately. 

$ (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] $

LHS is TRUE only if the given implication is TRUE for all $x$. Here the rightmost double implication $(\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ is always FALSE, because $x$ can be equal to $y$ and hence forall can never be TRUE. So the LHS reduces to just $(\forall x) \neg P(x)$ and returns FALSE as we have prime as well as non-prime natural numbers. So, FALSE $\Rightarrow$ FALSE returns TRUE making both $I_1$ and $I_2$ satisfy $\alpha$. D choice. 

Comments

@rahul sharma 5 (∀x)[P_x<->TRUE] reduced to (∀x)[P_x] because final value depend on P_x only,expand and see yourself !

---

(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]

Now [Qxy⇔¬Qyy] becomes false as mentioned in answer.

(∀x)[Px⇔(∀y)[False]]

(∀x)[Px⇔[False]]

(∀x)[¬Px]

Please tell if i am wrong

---

@rahul sharma 5 correct !

---

Hi @Arjun sir

just one doubt
 when it says p(x): x is a prime number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of prime numbers and for all x quantifier is going to pick every prime number value from the set

when it says p(x): x is a composite number
 α:(∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px]

then, in that (∀x) does that means x itself is a set of composite  numbers and for all x quantifier is going to pick every composite number value from the set

and the domain of Y:{set of all  natural numbers}

Answer 3

all logic concept is based on $T\rightarrow F$ .

1st let's see for $I_{2}$

If we somehow make a combination such that the implication will false, then we're done.

Now we have only one way to make an implication false, which is $T\rightarrow F$ combination.

If the domain is composite(means not prime) then right side of the $\alpha$ is always T, which implies we can't make $\alpha$ false.    $P_{x} = F$   i.e    $\sim P_{x} = T$ always.

So, $I_{2}$ satisfies $\alpha$.

 

Now, let's come in $I_{1}$

In $I_{1}$,  $\sim {Q_{yy}}$ is always false because in any circumstances y divides y.

now, try to make $T\rightarrow F$ combination.

let's forget about quantifiers & treat $\alpha$ as $[P_{x} \Leftrightarrow [Q_{xy}\Leftrightarrow Q_{yy}]] \rightarrow \sim P_{x}$.

take $P_{13}$, RHS is F.  LHS is $[P_{13} \Leftrightarrow [Q_{13.1}\Leftrightarrow Q_{1.1}]]$

So, $[P_{13} \Leftrightarrow [T\Leftrightarrow F]]$

$[P_{13} \Leftrightarrow F]$  = $F$, which means $F\rightarrow F$ implies T

So, using any number(composite or prime), we can't make the implication false.

So, $I_{1}$ also satisfies $\alpha$.

Option D is the answer.

 

 

Answer 4

Counter Example for I1 case :

X={11,121 }

Y={11}

 

Counter Example for I2 case :

X={4,6,2}

Y={2}

 

option D

Comments

Can you explain your with a few more words please?

---

Can someone explain how this counter example is working?