The Gateway to Computer Science Excellence
+1 vote
The proposition {[p → (q ∨ r)] ∧ (~q)} → (p → r) is
in Mathematical Logic by Active (2.8k points)
retagged by | 1k views
the answer given is  Tautology, but m' unable to proove?

2 Answers

+4 votes
Best answer

[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


by Veteran (60.8k points)
selected by
4th '=' from top   ---- in middle it shud be q instead of qq'
+4 votes
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 )
by Boss (31.4k points)
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.
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
50,741 questions
57,251 answers
104,680 users