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

asked in Mathematical Logic by Active (1.7k points)   | 40 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.1k points)  
selected by
wonderfully explained..thanks..:)
Top Users Jan 2017
  1. Debashish Deka

    9716 Points

  2. sudsho

    5560 Points

  3. Bikram

    5290 Points

  4. Habibkhan

    4920 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4230 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,449 questions
24,228 answers
53,959 comments
20,373 users