Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need some help regarding solving a logic. The question is to find an equivalent to the following logic.

$$(P \lor Q) \land (P \to R) \land (Q \to S)$$

The choices are

(a) $S \land R$
(b) $S \to R$
(c) $S \lor R$
(d) none of these

The answer given in the book is (c) $S \lor R$ . I tried many ways, but unable to bring the solution. So, kindly explain me the steps. Thanks in advance.

share|improve this question
2  
Are you familiar with truth tables? –  Gerry Myerson Aug 18 '12 at 12:06
    
yes. But that would be a very long process. It must be solved using laws. –  Gomathi Aug 18 '12 at 12:11
2  
Yes, but you might learn something on the way that would show you how to shorten it. –  Gerry Myerson Aug 18 '12 at 12:14
    
Solving this with truth tables would take maybe five to ten minutes. That's already less time than you've used asking here. –  Chris Eagle Aug 18 '12 at 12:15
2  
The terminology you are using isn't correct. The formula shown is not an equation, and certainly the formula cannot be "solved". Also, it does not make sense to find an equivalent for "a logic" - you are asking for an equivalent of a particular formula within a particular logic, namely within propositional logic. –  Carl Mummert Aug 18 '12 at 12:46

3 Answers 3

up vote 5 down vote accepted

The solution is (d)

The first formula is false if $P$ and $Q$ are false, but all other answers (a), (b) or (c) can be true if $P$ and $Q$ are false (by setting $R$ and $S$ true for example).

EDIT :

$$(P\vee Q)\wedge (P\rightarrow R) \wedge (Q\rightarrow S)$$ $$\Leftrightarrow$$ $$(P\vee Q)\wedge (\neg P\vee R) \wedge (\neg Q\vee S)$$

And you can't just eliminate $P$ and $Q$ to obtain an equivalent formula. However, you can eliminate them if you just try to find an implication...

$$((P\vee Q)\wedge (\neg P\vee R)) \wedge (\neg Q\vee S) \Rightarrow (Q\vee R) \wedge (\neg Q\vee S) \Rightarrow (R\vee S)$$

share|improve this answer
    
Can it be solved by laws? –  Gomathi Aug 18 '12 at 12:14
    
How does the first two terms become ( Q V R ) ? –  Gomathi Aug 18 '12 at 13:06
    
@Gomathi: what collection of laws is your book/course using? (There are various different sets of laws that can be given for propositional logic.) –  Peter LeFanu Lumsdaine Aug 18 '12 at 13:50
    
@PeterLeFanuLumsdaine Just the basic laws like associative, demorgan, idempotent laws, etc. Do you know how the first two terms of this answer becomes (Q V R) ? –  Gomathi Aug 18 '12 at 14:34
    
$(P\wedge Q)=(\neg Q\rightarrow P)$. $(\neg P\wedge R)=(P\rightarrow R)$. Hence $(\neg Q\rightarrow R)=(Q\wedge R)$ This is modus barbara (A implies B implies C, then A implies C). –  Xoff Aug 18 '12 at 14:47

This is not an equivalence but rather a valid argument. In symbols it looks like

a) $P\vee Q$

b) $P\rightarrow R$

c) $Q\rightarrow S$


$\rightarrow R\vee S$

To see the implication is valid argument consider the simpler statement

a) $P\vee Q$

b) $P\rightarrow R$


$\rightarrow R \vee Q$

This can be checked by a truth table.

share|improve this answer
    
yes, Sir. But, while checking with truth table, they are not equivalent sir. Can you explain by proving with laws ( with detailed steps, please) –  Gomathi Aug 18 '12 at 13:47

You can see that the implication $(P \lor Q) \land (P \to R) \land (Q \to S) \Rightarrow (R \lor S)$ is intuitively clear without resorting to truth tables.

Let $P$ be the statement: "We are in the Phillipines."

Let $Q$ be the statement: "We are in Quebec."

Let $R$ be the statement: "It is raining."

Let $S$ be the statement: "It is snowing."

The expression $(P \lor Q) \land (P \to R) \land (Q \to S)$ then becomes:

We are in the Phillipines or Quebec, and if we are in the Phillipines then it is raining and if we are in Quebec then it is snowing. Clearly then, it is either raining or snowing. $(R \lor S)$

share|improve this answer
1  
yes, Sir. But, while checking with truth table, they are not equivalent sir. –  Gomathi Aug 18 '12 at 12:26
4  
Yes, but it is possible to rain or snow without being in Quebec or Phillipines, so it's not equivalent. –  Xoff Aug 18 '12 at 12:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.