1,008 views
0 votes
0 votes

which of the following is tautology?

  1. (¬P^(P->q))->¬q
  2. ¬(p->q)->¬q
  3. [(¬p^q)^[q->(p->q)]]->¬r
  4. Both (B) and(C)

please explain in detail how to check for especially for condition (C) Because “r” is only in RHS but not in LHS of this implication.

 

3 Answers

3 votes
3 votes

From the GATE point of view follow few simple steps:

Solve the expression to make in simple in terms of AND , OR and Complement i.e. in terms of '+' '*'and '~'

This can be done by applying formula for all other i.e. for implication , biconditional.

In the end you just need to find A+A' which will be 1 or AA' which will be 0. If no such term is found then contingency

This will conclude you to tautology or contradiction.

example: 

  1. (¬P^(P->q))->¬q   ==   (P'(P'+Q))' + Q'   ===  (P'+P'Q)' + Q'   =====    P(P + Q') + Q'   === P+PQ' + Q' === P + Q'  which is contingency
  2. ¬(p->q)->¬q  === ((p'+q)')' + q' === p'+q + q' === 1   which is tautology
  3. [(¬p^q)^[q->(p->q)]]->¬r  ====  ((p'q)(q'+p'+q))'+ r'  ==== (p'q)'+ r' ===  p+q'+r' which is a contingency

 

1 votes
1 votes

Before solve these type of question remember few things

1. ^ is AND / .           2. v is OR / +            3. A --> B  is A'+ B  ( if A is 1 and B is 0 then only A--->B is false(0) )  

Now, Check Option B.  ¬(p->q) --> ¬q

Try to use implication property here 

take q' as false(0) and if ¬(p->q) is true(1) then we can say directly its not tautology

so check now, ¬(p->q) --> 0        // q'=0 so, q=1

¬(p->1) --> 0  // p-->1 will be 1 only ,

So, ¬(1) --> 0 

 0-->0 that will give 1 (True) : TAUTOLOGY.

-------------------------------------------------------------------------------------------------------------

Now Check Option A : (¬P^(P->q))->¬q

you can solve it either directly or use above method

here i'm solving direct

so, (P' .(P-->q))' + q'

= P+ (P'+q)' +q'

= P+ P.q' +q'

= P+q'  (NOT TAUTOLOGY)

------------------------------------------------------------------------------------------------------------------

Similarly you can solve Option C

ANSWER: OPTION B

Related questions

2 votes
2 votes
2 answers
1
kd..... asked Jul 12, 2018
511 views
I am unable to prove following equations without using truth table1) p - (q v r) = (p->q) V (p->r) 2) ~(p <- q) = p <- ~q
1 votes
1 votes
3 answers
2
Vicky rix asked Mar 7, 2017
888 views
Which of the following statements are ALWAYS TRUE ?A) ∀x [P(x)] - ∃x [P(x)]B) ∃x [P(x)] - ∀x [P(x)]C) Both A) and B) and so both are equivalent D) Neither A) no...
0 votes
0 votes
2 answers
3