GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
69 views

asked in Mathematical Logic by Boss (8.7k points)   | 69 views
Is S1 equivalent to S2?

1 Answer

+3 votes
Best answer
P(x) : x is politician

Q(x) : x is crooked

Stmt : if everyone is politician then somebody is crooked

s2 can be directly inferred from stmt

∀(x) P(x) --> ∃(x) Q(x)

So s2 is true.

s2 :
= ∀(x) P(x) --> ∃(x) Q(x)
= ~( ∀(x)P(x) ) V ( ∃(x)Q(x) ) [Applied P->Q == ~P V Q]...equation 1
= ( ∃(x)~P(x)) V ( ∃(x)Q(x) ) [Applied ~[∀(x)P(x)] == ∃(x)~P(x) ]
= ∃(x) [ ~P(x) V Q(x) ]
= ∃(x) [ P(x) --> Q(x) ] ....this is S1

Now from equation 1 back
s2 :
= ~( ∀(x)P(x) ) V ( ∃(x)Q(x) )
= ~( ∀(x)P(x) ) V ( ~~∃(x)Q(x) ) [Applied ~~P(x) == P(x) ]
= ~( ∀(x)P(x) ) V ( ~∀(x)~Q(x) ) [Applied ~[∃(x)P(x)] == ∀(x)~P(x) ]
= ~ [ ( ∀(x)P(x) ) ^ ∀(x)~Q(x) ] [Applied ~ (P ^ Q) == ~P V ~Q]
= ~∀(x) [ P(x) ^ ~Q(x) ] ---> this is s3

Hence all options s1,s2 and s3 are equivalent.
answered by Loyal (3.5k points)  
selected by


Top Users Aug 2017
  1. Bikram

    5034 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3296 Points

  5. rahul sharma 5

    3178 Points

  6. makhdoom ghaya

    2530 Points

  7. just_bhavana

    2428 Points

  8. stblue

    2240 Points

  9. Tesla!

    2076 Points

  10. joshi_nitish

    1830 Points


25,032 questions
32,178 answers
74,991 comments
30,218 users