2
$\begingroup$

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.

  • 2
    Are you familiar with truth tables?2012-08-18
  • 0
    yes. But that would be a very long process. It must be solved using laws.2012-08-18
  • 2
    Yes, but you might learn something on the way that would show you how to shorten it.2012-08-18
  • 0
    Solving this with truth tables would take maybe five to ten minutes. That's already less time than you've used asking here.2012-08-18
  • 0
    @ChrisEagle It is for competitive exam. I can't take 5 min there for a single question. I just want to clarify if the answer can be brought using laws.2012-08-18
  • 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.2012-08-18

3 Answers 3

5

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)$$

  • 0
    Can it be solved by laws?2012-08-18
  • 0
    How does the first two terms become ( Q V R ) ?2012-08-18
  • 0
    @Gomathi: what collection of laws is your book/course using? (There are various different sets of laws that can be given for propositional logic.)2012-08-18
  • 0
    @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) ?2012-08-18
  • 0
    $(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).2012-08-18
  • 0
    Alternatively, I’d argue that $(P \lor Q) \land (P \Rightarrow R) = (P \land (P \Rightarrow R)) \lor (Q \land (P \Rightarrow R))$ (by distributivity). But now $(P \land (P \Rightarrow R))$ implies $R$ (modus ponens), and $(Q \land (P \Rightarrow R))$ implies $Q$ (various different names); so by monotonicity, $(P \land (P \Rightarrow R)) \lor (Q \land (P \Rightarrow R))$ implies $R \lor Q$.2012-08-18
5

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)$

  • 1
    yes, Sir. But, while checking with truth table, they are not equivalent sir.2012-08-18
  • 4
    Yes, but it is possible to rain or snow without being in Quebec or Phillipines, so it's not equivalent.2012-08-18
0

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.

  • 0
    yes, Sir. But, while checking with truth table, they are not equivalent sir. Can you explain by proving with laws ( with detailed steps, please)2012-08-18