1
$\begingroup$

(p ∨ q) → r ≡ (p → q) ∨ (p → r) could be valid or invalid

I need to prove it using logical equivalences (can't use truth table)

This is how far I've gotten by working with the right side:

<-> p→(q v r)

<-> ¬p v (q v r)

then commutative law

<-> (q v r) v ¬p

then commutative law

<-> (r v q) v ¬p

then associative law

<-> r v ( q v ¬p )

then commutative law

<-> (q v ¬p) v r

then commutative law

<-> (¬p v q) v r

<-> ¬(¬p v q) → r

What do I do next? Or did I do this wrong? Thanks for the assistance

$\endgroup$

2 Answers 2

2
$\begingroup$

When you get to $\neg p\lor(q\lor r)$, I would apply associativity:

$$\begin{align*} (p\to q)\lor(p\to r)&\equiv p\to(q\lor r)\\ &\equiv\neg p\lor(q\lor r)\\ &\equiv(\neg p\lor q)\lor r\;. \end{align*}$$

Your target, after all, is $(p\lor q)\to r$, which you know is equivalent to $\neg(p\lor q)\lor r$, with $r$ hanging out there on the end, so it makes sense to go for something with the same general form. However, $\neg(p\lor q)\equiv\neg p\land\neg q$, and it should be pretty clear intuitively that $(\neg p\lor q)\lor r$ is not equivalent to $(\neg p\land\neg q)\lor r$: they’re both true if $r$ is true, but if $r$ is false and $p$ and $q$ are both true, $(\neg p\land\neg q)\lor r$ is false, but $(\neg p\lor q)\lor r$ is still true.

$\endgroup$
0
$\begingroup$

Well the proposition is invalid.

The systematic way to show this is to bring it to conjunctive normal form (this can be more easily done with carnaugh tables, but that would probably count as a truth table). We start with the statement:

$((p\lor q)\rightarrow r) \leftrightarrow ((p\rightarrow q)\lor (p\rightarrow r))$

My strategy here is to rewrite the equivalence as a conjunctive form with factors in disjunctive form. Which means that the LHS and RHS of the equivalence will need to be transformed into disjunctive normal form.

The LHS:

$(p\lor q) \rightarrow r$

$\neg(p\lor q) \lor r$

$(\neg p \land \neg q) \lor r $

And the RHS:

$(p \rightarrow q) \lor (p \rightarrow r)$

$(\neg p \lor q) \lor (\neg p \lor r)$

$\neg p \lor q \lor r$

Putting them back in the original, and using that $\phi\leftrightarrow\psi$ is the same as $(\neg\phi\lor\psi)\land(\phi\lor\neg\psi)$:

$((\neg p \land \neg q) \lor r) \leftrightarrow (\neg p \lor q \lor r)$

$(\neg((\neg p \land \neg q) \lor r) \lor (\neg p \lor q \lor r)) \land (((\neg p \land \neg q) \lor r) \lor \neg(\neg p \lor q \lor r))$

De Morgan:

$((\neg(\neg p \land \neg q) \land \neg r) \lor (\neg p \lor q \lor r)) \land (((\neg p \land \neg q) \lor r) \lor (\neg\neg p \land \neg q \land \neg r))$

And again (and removing the double negation):

$(((\neg\neg p \lor \neg\neg q) \land \neg r) \lor (\neg p \lor q \lor r)) \land (((\neg p \land \neg q) \lor r) \lor (p \land \neg q \land \neg r))$

Some clean up, and removing double negations:

$(((p \lor q) \land \neg r) \lor \neg p \lor q \lor r) \land ((\neg p \land \neg q) \lor r \lor (p \land \neg q \land \neg r))$

Now we've brought it to a form of conjunctions of disjunctions of conjunctions of disjunctions. We now bring it to conjunctive normal form by using distributive laws, starting at the inner levels and working our way outwards:

$((p \land \neg r) \lor (q \land \neg r) \lor \neg p \lor q \lor r) \land ((\neg p \land \neg q) \lor r \lor (p \land \neg q \land \neg r))$

$(p \lor q \lor \neg p \lor q \lor r) \land (p \lor \neg r \lor \neg p \lor q \lor r) \land (\neg r \lor q \lor \neg p \lor q \lor r) \land (\neg r \lor \neg r \lor \neg p \lor q \lor r) \land (\neg p \lor r \lor p) \land (\neg p \lor r \lor \neg q) \land (\neg p \lor r \lor \neg r) \land (\neg q \lor r \lor p) \land (\neg q \lor r \lor \neg q) \land (\neg q \lor r \lor \neg r)$

Now bring som sanity to that mess by removing redundant terms and replacing $\phi\lor\neg\phi\lor...$ with $T$ (true):

$T \land T \land T \land T \land T \land (\neg p \lor r \lor \neg q) \land T \land (\neg q \lor r \lor p) \land (\neg q \lor r) \land T$

And removing redundant truths:

$(\neg p \lor r \lor \neg q) \land (\neg q \lor r \lor p) \land (\neg q \lor r)$

Already now we can see that this isn't universally true since the factors are disjunction of independent statements, but we can tidy it up a little bit by using absorbtion:

$(\neg p \lor r \lor \neg q) \land (\neg q \lor r \lor p)$

Since they are not equivalent I think the requirement not to utilize truth tables is partially wrong, basically because disproof by truth table only needs one line to mismatch which in turn means that we have a concrete counter-example. Creating a truth table shows that $q$ being true and $r$ being false yields a mismatch and then you can use any of these as a counter-example:

$(p \lor T) \rightarrow F$ is false

while:

$(p \rightarrow T) \lor (p \rightarrow F)$ is true

$\endgroup$
3
  • $\begingroup$ After ¬(¬p∨q)∨r i used DeMorgan's law to get (p^¬q) v r. Can i prove they're not equivalent by simply saying (p v q) is not equal to (p^¬q)? Since they're both implying r. It doesnt say anywhere on my table of equivalences that they're equal, so could that be a valid reason? $\endgroup$
    – Andrew Kor
    Sep 30, 2015 at 18:50
  • $\begingroup$ thx for ur help. i have another one now: ((p ∨ q) ∧ (¬p ∨ r)) ≡ (q ∨ r) no idea what to do.. i cant use distributive law because the p's are different and nothing else seems to work $\endgroup$
    – Andrew Kor
    Sep 30, 2015 at 19:21
  • $\begingroup$ @AjeetKljh As I wrote towards the end, the requirement not to use truth tables should be motivated. If it's a exercise that states it it's still perfectly valid to use them as a tool for your investigation, you can always exclude it in the final solution. For the statements you've written the truth table will show that it's not equivalent and it will give you the counter-examples (fx p and q false while r is true). $\endgroup$
    – skyking
    Sep 30, 2015 at 19:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .