The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes

Can someone please check if my solution is correct?

asked in Mathematical Logic by Boss (40.2k points) | 178 views
seems correct.

1 Answer

+3 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 (99.2k 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..

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

39,825 questions
46,802 answers
58,918 users