GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
38 views

Can someone please check if my solution is correct?

asked in Mathematical Logic by Veteran (11.1k points)   | 38 views
seems correct.

1 Answer

+2 votes
Best answer

As per my analysis they are not equivalent..

For this claim , we need to assign truth values in such a way that first 1st order logic is made false and 2nd order logic is made true or vice versa..

Let we take 3 pairs   :   (T , F)  , (F , T) , (T , T).. the first in each pair being the truth values for x and the second one being for y..

Now  ∀x  P(x) will be false as well as   ∀x  Q(x)...

Hence the second 1st order logic :   ∀x  P(x)  <==>   ∀x  ​​​​​​​Q(x)   will evaluate to be true as both LHS and RHS are true and we know equivalence (biconditional) returns true when the truth values of LHS and RHS are same..

 

Now coming to the first of the given 1st order logic..We can clearly see 1st 2 tuples out of the three which I have taken invalidates the equivalence  :  P(x)  <==>  Q(x)  as truth values dont match..

Hence   ∀x  ( P(x)  <==>  Q(x) )  automatically becomes false as one invalidation of 1st order logic means "for all" will return false..

 

So we have seen that for same tuples , first 1st order logic returns false and second one returns true ..Hence the given two 1st order logic statements are not equivalent..

answered by Veteran (76.9k points)  
selected by
yes, correct! same as i explained. can you check the relation which i have shown in the last part of my solution? is it correct?
To prove whether two statements are equivalent they should hold both way ..I mean both forward implication and backward implication should evaluate to true which is not the case here..

As we have seen one of the two statements can become true and other one false..Hence they are not equivalent..


Top Users Sep 2017
  1. Habibkhan

    6960 Points

  2. Warrior

    2416 Points

  3. Arjun

    2358 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. makhdoom ghaya

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,059 questions
33,664 answers
79,738 comments
31,078 users