propositional logic

Question

which of the following is tautology?

• A. (¬P^(P->q))->¬q
• B. ¬(p->q)->¬q
• C. [(¬p^q)^[q->(p->q)]]->¬r
• D. 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.

 

Comments

I'm only finding B as tautology .

C is not , is it?

---

@prashant jha 1 yes! you are correct. please can you give a detailed explanation of how to check especially for option 'C'

---

For option C . it would've been tautology if left hand of the implication resulted to false in all the case.

Now you can do this in two ways , either try to prove that it is never false always , or you can simply solve the lhs of the implication only to find that it is p'q.

So the entire formula after reduction will be p'q->r' , so it is satisfiable but never completely valid.

Answer 1

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: 

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

 

Comments

good

Answer 2

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

Comments

when u answer plz try to explain every option so that every option must be clear to the reader...but good

---

@Tauhin Gangwar i think i solved in very simple manner. Students can try option C with the help of option A.

I think it's a good practice, isn't it?

---

When we should direct method and when implicatoon property method.

---

@Sona Barman with practice you'll get. Most of the time, with less of variable, we follow direct method.

Answer 3

You can go throw like this.. b is the only answer which is tautology