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

    5388 Points

  2. ABKUNDAN

    4730 Points

  3. manu00x

    3582 Points

  4. akash.dinkar12

    3534 Points

  5. rahul sharma 5

    3196 Points

  6. makhdoom ghaya

    2710 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2126 Points

  10. pawan kumarln

    1914 Points


25,076 questions
32,240 answers
75,170 comments
30,249 users