4
$\begingroup$

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 don't know how to prove it?

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

  • 0
    venn diagrams may be used for proving it2011-08-13

4 Answers 4

7

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

  • 0
    To the proposer: Because $A\implies B$ is the same thing as $(\neg A)\lor B.$2017-09-08
4

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.

2

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.

  • 0
    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.2011-08-13
0

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.