GATE CSE
First time here? Checkout the FAQ!
x
0 votes
83 views

asked in Mathematical Logic by Boss (6.1k points)   | 83 views
is it option C ?
i am not able to use any identity for statement 1.

p V q--{1}

(-p . q)-> r   --(ii)

from ii,i can only write p v -q  v r

which propertty to use now??
Just convert A->B to ~AVB. Then  used kmap method for 'pqrs' where above statements are in POS form.
by k-map mehtod,i am getting (p+r).(p+q)

so,from simplification, we can get (p V r) which means ~r -> p

is this correct?

btw,i did nt know this kmap method for this thing.
If the term is pVq then put 0 for p=0, q=0.

Now, Fill the k-map for all such terms.

Now, see the meaning of A->B . If A is true, B must be necessarily true. You needn't check for B seperately.

Use this definition for kmap.

 

Now, for 1st example, fill the kmap using the premises.

Now, test the places in kmap for the terms of the conclusion. If they have 0's filled in, then the statement is valid.
Should I show the kmap for 1st example?
please if you can..i will have much clear idea then..:-)

1st example.

 

1st premise:   Vx  ( p(x) V q(x) )   (terms in kmap shown by blue color)

2nd premise: Vx (  (~p(x) ^  q(x) ) -> r(x) )

                   = Vx (  ( p(x) V  ~q(x) ) V r(x) )    (terms in kmap shown by green color)

Conclusion: Vx  ( ~r(x) -> p(x) )

                  = Vx  ( r(x) V p(x) )    (terms in kmap shown by red color)

Now, when the premises are true (i.e the terms are 0 in kmap), is the conclusion always true(i.e. terms for conclusion also 0)?

Yes, always, right?

yea...got that..very nice approach..thanks a lot ..:-)

one more thing like,here there were only universal quantifiers,but in second option,there are existential also..caan we adopt same way for them also?
Yes, its just slightly different. Try out.
in second option

,we can write (i) p -> Q ^ R (universal instatiation)

can we write (ii) as P ^ S?

because then from  (ii),we will get P (iii)& S (iv) through simplification.

from (iii) and (i), P -> Q ^ R

                            P

we get Q^ R(modes ponens) (v)

from (v),we can get Q (vi) & R (vii)(simplification)

with  (vii) and (iv) i.e R and S,we get R^ S(conjunction)

correct me if i am wrong
For 2nd premise, its given existential quantifier.  So, P^S is true only for some instances.

alright,so how will we know that for which intances we need to mark 0 in our k-map..??

so,surely this k-map is wrong cuz here,i have marked 0 for every P and evry S.caan you tell at which one to mark 0..?

P^S is SOP term, right? But there is existential quantifier.

So, when p=1 and S=1, the entries would be 1 only sometimes.

Now, Lets ignore P^S. So, remaining entries ( excluding the 2 premises)would be 1 or dont care, right?

 

Now, lets look at the conclusion.

$\exists$x { r(x) ^ s(x) }   which corresponds to third column from left.

So, you want 3rd column to be all 1's atleast once or for some instances.

 

Lets go back to $\exists$x { P(x) ^ S(x) }

So, now mark all 1's for this function because there exists atleast one instance where both P(x) and S(x) is true.

Now,  for this instance, just combine the 1's with dont care.

 

So, 2nd statement is also valid. I think I gave wrong answer initially :)

yes..i got that..thankyou so much..:-)

Please log in or register to answer this question.



Top Users Sep 2017
  1. Habibkhan

    8796 Points

  2. rishu_darkshadow

    3572 Points

  3. Warrior

    2914 Points

  4. Arjun

    2840 Points

  5. A_i_$_h

    2550 Points

  6. manu00x

    2268 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points


26,346 questions
33,927 answers
80,524 comments
31,231 users