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

asked in Mathematical Logic by Boss (9.1k points) 4 64 210 | 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.9k points) 2 8 27
selected by


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
Top Users Oct 2017
  1. Arjun

    23462 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8560 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5038 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4416 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3868 Points


Recent Badges

Notable Question Sanjay Sharma
Notable Question Warrior
Notable Question sid1221
Nice Answer 2018
Good Question Arjun
Nice Question mitalitak
Great Question Arjun
Popular Question Tesla!
Nice Question makhdoom ghaya
Popular Question Sankaranarayanan P.N
27,349 questions
35,204 answers
84,249 comments
33,328 users