The Gateway to Computer Science Excellence
+55 votes
4.3k views

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?

  1. \(I_1\) satisfies \(\alpha\), \(I_2\) does not
  2. \(I_2\) satisfies \(\alpha\), \(I_1\) does not
  3. Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\)
  4. Both \(I_1\) and \(I_2\) satisfies \(\alpha\)
in Mathematical Logic by Veteran (52.1k points)
edited by | 4.3k views
0
What does "satisfies" mean here?? (Does it mean "satisfiability"?)

Are the terms "satisfiability" and "valid" equivalent??
+2
satisfiability means true for at least one instance, valid means always true(true for all instances).
+1

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

 

0

@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

4 Answers

+135 votes
Best answer

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

$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 False]$, "$P_x \Leftrightarrow 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.

by Boss (17.6k points)
edited by
+5
Awesome explanation @sachin Mittal  (Y)
0
thnks :)
+1
Correct and clear explanation sachin..
0
Can you please explain how we can rewrite

(∀y)[Qxy⇔¬Qyy]](∀y)[Qxy⇔¬Qyy]] as (∀y)[¬Qxy]?
0

I have doubt in this solution.As mentioned 

"consider only (∀y)[¬Qxy] it says all values of y does not divide x, It is true irrespective of x being prime or composite. Even if x is composite then only its factor divides x not all values."

How is this true always? when y and x are same in case of prime/non prime  then it will divide.

 (∀y)[¬Qxy] says that there is no number that divides x and so it should be false because if there is one case which is not satisfying for all then it is not FOR ALL.Please correct me if i understood it wrong.

Please tell me if following approach will work:-

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

We know y will always divide y(assuming 0 is not a natural number as in group theory it says 0 is natural number set but some says if 0 is included then it becomes whole number.)

A Qyy is always false,means Qxy=False.

So i can reduce this to:-

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

which means 

(∀x)[Px= false]

(∀x)[false]

and false implies anything must be true?

Please tell me if i am wrong in this approach?

+1
sir u r really talented
+1

Nice explanation.Thanks,  Sachin Mittal 1.

0

Bi conditional Truth table ...

+1
Just for thanking you I created account

Whenever I encounter your answer I can be assure that it must be checked or from trusted reference.

Thanks @sachin for your great effort and indeed wonderful explanation :)
0

@Jordan Thank you so much. :)

+3

@Sachin 

(∀y)[¬Qxy] can also be interpreted as -
¬∃(y)[Qxy] - There doesn't exist a number y such that y divides x.
Which is false always as 1 divides every number - Counter-example
So LHS:(∀x)[Px⇔(∀y)[¬Qxy]] reduced to (∀x)[Px⇔False] .
I can write it as (∀x)[¬Px
(∀x)[¬Px] ⇒ (∀x)[¬Px]
F⇒F
T

Correct me if I am wrong.  :)

0

Can't we say option d is correct,by looking only at the part after implication

Help me

+1

@sudharshan only by finding that rhs is false we can't declare that formula is satisfiable.. because there may be a case if LHS is always true in that case $true\implies false$  is always false...(so not satisfiable).

So we have to check LHS also..

0

How  (∀y)[Qxy⇔False]] is written  as (∀y)[¬Qxy] ??

+46 votes

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

by Veteran (422k points)
edited by
0
option given by ,
made easy - (D) ,
GK publication - (A) ,
Ankur Gupta website - (C) ,
and happy mittal sir - (C) , http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2003.html
@ Arjun sir , I think you are right(B) , but I am still doubt , please remove my doubt , with the help of a example .
0
Sorry, my answer was wrong. I had missed the possibility of $x = y$. Also, two interpretations are possible here as shown now.
0
@Happy-Mittal These are the two cases for 'precedence'.
+1
The scope of quantified variable is determined by square brackets, which is clear from the question and hence your second interpretation is correct.
+1
Also, your first interpretation doesn't make sense, as once we are arguing about all x, then we don't write $\forall x$ inside that, we are anyway arguing about every x.
+1
That make sense. I'll change. Thanks :)
+1
@Arjun, So the LHS reduces to just ~P(X), make this change for more correctness & Readablity !
0

Can you verify best answer selected?

In that LHS: (∀x)[Px].But LHS should be reduced to LHS: (∀x)[¬Px].

0

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

+1
(∀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
0

@rahul sharma 5 correct !

0
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}
0 votes

Counter Example for I1 case :

X={11,121 }

Y={11}

 

Counter Example for I2 case :

X={4,6,2}

Y={2}

 

option D

by (361 points)
0
Can you explain your with a few more words please?
0 votes

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.

 

 

by Active (2.8k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
193,840 comments
94,039 users