The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

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

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

28,831 questions
36,676 answers
34,638 users