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.

1) $(P \vee Q) \Rightarrow R$
2) $(P \Rightarrow R) \wedge (Q \Rightarrow R)$

Explain why 1 and 2 are equivalent statements.

Attempt at solution:

I converted 1 and 2 to these statements which are equivalent:

1) $(P \cup Q) \subseteq R$

2) $(P \subseteq R) \cap (Q \subseteq R)$

This now seems logical but I dont know how to prove it? Any help is appreciated, thanks.

EDIT: I should have said truth tables are not necessary.

share|improve this question
    
Have you tried forming truth tables for both, and checking if the statements are respectively true? –  InterestedGuest Feb 7 '11 at 7:03
    
Are you attempting to prove that $(P\cup Q)\subseteq R$ and $(P\subseteq R)\cap(Q\subseteq R)$ are equivalent to each other? Or are you trying to prove that they are essentially the same as the first two statements you wrote? –  yunone Feb 7 '11 at 7:11
    
I don't see how they relate! What does this notation mean? Is $(P\subseteq R)\cap(Q\subseteq R)$ a set or what? –  milcak Feb 7 '11 at 7:20
    
I retagged the question, it has nothing to do with abstract algebra. –  Asaf Karagila Feb 7 '11 at 13:57
    
There is a difference between "truth tables are not necessary" and "truth tables are not allowed." Yes, the problem may be solved without truth tables, but truth tables happen to provide an easy, straightforward way of checking the equivalence. So, while you may be able to solve it without using truth tables, a question is why you would want to do that. There may be good reasons for wanting to do that, but then you have to tells us what they are so that the answers can be suitably written. –  Arturo Magidin Feb 7 '11 at 16:45
show 1 more comment

4 Answers

up vote 7 down vote accepted

If you are unwilling to use truth tables then the following are equivalent $$(P \lor Q) \rightarrow R$$ $$\lnot(P \lor Q) \lor R$$ $$(\lnot P \land \lnot Q) \lor R$$ $$(\lnot P \lor R) \land (\lnot Q \lor R)$$ $$(P \rightarrow R) \land (Q \rightarrow R)$$

share|improve this answer
    
But whats the reason behind this? Like the second line, how did you come to know you had to do this? –  1337holiday Feb 7 '11 at 16:40
    
@1337holiday: the steps in Henry's proof were (probably) not motivated by any direct foreknowledge that that particular step was the way to go, but more likely just using the strategy of simplifying (or translating out) the '$\rightarrow$' (which is a useful strategy because the identities involving '$\land$' and '$\lor$' are easier to manipulate. –  Mitch Feb 7 '11 at 17:56
    
Indeed. The question was how to translate the $\rightarrow$. An alternative approach, which would have introduced an extra step or two, might have been $\lnot ((P \lor Q) \land \lnot R).$ –  Henry Feb 7 '11 at 18:55
add comment

You should either use truth tables, or you can argue by contrapositive.

To prove $(P \vee Q) \Rightarrow R$ then $(P \Rightarrow R) \wedge (Q \Rightarrow R)$, it is equivalent to show that when $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ is false, then $(P \vee Q) \Rightarrow R$ is false as well.

When is $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ false?

Then to prove the other direction reverse the formulas above, and again;

When is$(P \vee Q) \Rightarrow R$ false?

In both of these cases you can find sufficient conditions on $P,Q,R$, then establish the other statement.

share|improve this answer
add comment

It is usually the other way around: the basic properties of propositionsal calculus and logical connectives are established from first principles, and then the corresponding properties for sets and set-theoretic operations are concluded from them. So the properties of $\cap$ are deduced from the properties of $\wedge$; the properties of $\subseteq$ are deduced from the properties of $\Rightarrow$, etc.

You seem to be trying to go the other way. Unless this is how it was done in your class or book, chances are this would not be acceptable. Moreover, the second set-theoretic statement that you write doesn't really make a lot of sense as a set-theoretic statement: $$(P\subseteq R)\cap(Q\subseteq R)$$ is not a well-formed formula of set theory: $\cap$ is an operator between sets, but $\subseteq$ is a relation; $P\subseteq R$ is not a set, but a statement about sets, and $\cap$ cannot operate on statements about sets, only on sets.

share|improve this answer
    
I agree with this and with milcak above: $(P \subseteq R) \cap (Q \subseteq R)$ is nonsensical with the usual meanings of the symbols in mathematics. You get away with it (but maybe get confused by it) in $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ because you confuse a binary connective with a binary relation. Or you confuse a proposition with its truth value. Or something. –  GEdgar Aug 13 '11 at 17:34
add comment

Instead of working with truth-tables or Venndiagrams you could just reason with these statements:

Assume (1) holds. Then R is true, whenever P or Q is true. So assume P holds, then "P or Q" holds and therefore R holds. Likewise Q implies R. We have that (2) holds.

Now assume (2) holds. Let "P or Q" be true, one can assume without loss that P is true. But from (2) we know that P implies R, therefore R holds. The means that (1) holds.

Now (1) implies (2) and (2) implies (1), this means both are indeed equivalent.

This is certainly less 'formal' than what you might be expecting (although it can be made formal). But it is this kind of reasoning one will usually make in a mathematical proof and because of that it's useful to be able to think about it this way.

share|improve this answer
add comment

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.