Question

The proposition {[p → (q ∨ r)] ∧ (~q)} → (p → r) is

Comments

the answer given is  Tautology, but m' unable to proove?

Answer 1

[p → (q ∨ r)] ∧ (~q)} → (p → r)
= ((p' + q + r)q')' + p' + r
= (p'q' + rq')' + p' + r
= (p + q)(r' + q) + p' + r
= pr' + pq + qr' + q + p' + r
=pr' + (pq + qr' +q) + p' + r = (pr' + p') + q(p + r' +1) + r
= p' +r' + q + r
=p' + q + (r + r')
= p' + q + T
= TAUTOLOGY
 

Comments

4th '=' from top   ---- in middle it shud be q instead of qq'

Answer 2

implication is false when lhs is true and rhs is false

so rhs p->r is false if p is true and r is false (we assume RHS is false)

coming to lhs it is conjunction of two terms

-q is true  that means q is false

p->(q or r)    p is true q and r are false  so T->F is false

so lhs is false and false that gives false

F->F is true

so it is tautology(bcoz if rhs is false lhs is also false )

Comments

Good method. You have gone inside the formula- so all GATE questions on this topic will be very easy :)

---

by considering this, how can we say its true for all combinations of p q r boolean values, thus forming tautology, thus a single case enough?

---

In case of Implication(=>), When LHS is true and RHS is false is the only case that the overall result becomes false. That's why he has checked for that case only. In all the other cases its undoubtedly a Tautology.

---

thanks