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

asked in Mathematical Logic by Boss (6.2k points)   | 49 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.4k points)  
selected by
wonderfully explained..thanks..:)


Top Users Aug 2017
  1. Bikram

    5388 Points

  2. ABKUNDAN

    4730 Points

  3. manu00x

    3582 Points

  4. akash.dinkar12

    3534 Points

  5. rahul sharma 5

    3196 Points

  6. makhdoom ghaya

    2710 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2126 Points

  10. pawan kumarln

    1914 Points


25,076 questions
32,240 answers
75,170 comments
30,249 users