GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
48 views

asked in Mathematical Logic by Boss (5.9k points)   | 48 views

1 Answer

+2 votes
Best answer

1. $( (p \implies q) \wedge (r \implies s) \wedge (p \vee q) ) \implies (q \vee s)$

This implication is false if LHS is true and RHS is false and true otherwise.

Let's assume RHS to be false. i.e. $ (q \vee s) $ is False. So, q = False and s = False. Put these values of False for q and s in LHS.

So LHS becomes: $( (p \implies False ) \wedge (r \implies False) \wedge (p \vee False) ) = (\neg p \vee False) \wedge ( \neg r \vee False) \wedge (p \vee False) = \neg p \wedge \neg r \wedge p = False$

So we've proven that when RHS is false then LHS is also false. So the whole implication is always true and hence valid.

Similarly for 2nd if we assume RHS to be false, then it means p = true and r = true. Now substitute these values in LHS:

$( (p \implies q ) \wedge (r \implies s) \wedge ( \neg q \vee \neg s) ) = (\neg p \vee q) \wedge ( \neg r \vee s) \wedge (\neg q \vee \neg s) = ( false \vee q) \wedge (false \vee s) \wedge ( \neg q \vee \neg s) = q \wedge s \wedge (\neg q \vee \neg s) = ( q \wedge s) \wedge \neg(q \wedge s) = false$

In 2nd case also we've proved that if RHS is False then LHS has to be false. So the implication holds and is valid.

3rd one is true by Hypothetical Syllogism (also known as "the principle of transitivity of implication")

So 1, 2, 3 are all valid.

answered by Loyal (3.3k points)  
selected by
wonderfully explained..thanks..:)


Top Users May 2017
  1. akash.dinkar12

    3292 Points

  2. pawan kumarln

    1652 Points

  3. sh!va

    1650 Points

  4. Arjun

    1424 Points

  5. Bikram

    1372 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1142 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    904 Points

  10. srestha

    718 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    458 Points

  2. Arnab Bhadra

    402 Points

  3. pawan kumarln

    278 Points

  4. Ahwan

    236 Points

  5. bharti

    194 Points


22,786 questions
29,121 answers
65,184 comments
27,661 users