I want to prove that $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$, using distributions or reductions (even though I am aware that simpler proofs exist). The issue is that I keep wandering around like a fool. Here is what I'e come up with so far:

$(P \lor A) \land ( \neg P \lor B) \Leftrightarrow$

$(P \land ( \neg P \lor B)) \lor (A \land (\neg P \lor B)) \Leftrightarrow$

$((P \land \neg P) \lor (P \land B)) \lor (A \land (\neg P \lor B)) \Leftrightarrow$

$(\bot \lor (P \land B)) \lor ( A \land (\neg P \lor B)) \Leftrightarrow$

$(P \land B) \lor (A \land ( \neg P \lor B)) \Leftrightarrow$

$(P \land B) \ \lor A) \land ((P \land B) \lor ( \neg P \lor B)) \Leftrightarrow$

$((P \land B) \ \lor A) \land ((P \land B) \lor \neg P) \lor B) \Leftrightarrow$

$((P \land B) \ \lor A) \land (((P \lor \neg P) \land (\neg P \lor B)) \lor B) \Leftrightarrow$

$((P \land B) \ \lor A) \land (( \top \land (\neg P \lor B)) \lor B) \Leftrightarrow$

$((P \land B) \ \lor A) \land ( (\neg P \lor B)) \lor B) \Leftrightarrow$

$((P \land B) \ \lor A) \land (\neg P \lor B) \Leftrightarrow$

$((P \land B) \land (\neg P \lor B)) \lor ((\neg P \lor B) \land A) \Leftrightarrow $

The point where I give up

  • $\begingroup$ You want to prove that $((P \lor A) \land ( \neg P \lor B)) \rightarrow (A \lor B)$. It would be nice if you could get $((P \lor A) \land ( \neg P \lor B)) \leftrightarrow ((A\lor B)\land \text{Something})$. And it seems to be you can get exactly this from $(P \land B) \lor (A \land ( \neg P \lor B))$. I did it my head, so I might be wrong. $\endgroup$ – Git Gud May 23 '16 at 22:54

First start with turning $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$

Into this $\neg [(P \lor A) \land ( \neg P \lor B)] \lor (A \lor B)$

This is where you might have been going in circles:

$$ \neg [(P \lor A) \land ( \neg P \lor B)] \lor (A \lor B) \\ \neg(P \lor A) \lor \neg( \neg P \lor B) \lor (A \lor B) \\ (\neg P \land \neg A) \lor ( P \land \neg B) \lor (A \lor B) \\ (\neg P \land \neg A) \lor ( P \land \neg B) \lor (A \lor B) \\ (\neg P \land \neg A) \lor ( P \land \neg B) \lor A \lor B $$

Can you continue from here?


[Note that a common convention is that $\land$ has higher precedence over $\lor$, which lessens brackets.]

The systematic way is:

  1. Convert everything into using only $\neg,\land,\lor$.

  2. Use distributivity of $\land$ over $\lor$ and De Morgan's laws to expand into disjunctive normal form.

  3. Use the law of excluded middle to simplify. Another useful law is $P \lor \neg P \land Q \equiv P \lor Q$.

Following this gives: $\def\imp{\rightarrow}$

  $(P \lor A ) \land ( \neg P \lor B ) \imp A \lor B$

  $\ \equiv \neg ( (P \lor A ) \land ( \neg P \lor B ) ) \lor ( A \lor B )$

  $\ \equiv ( \neg (P \lor A ) \lor \neg ( \neg P \lor B ) ) \lor ( A \lor B )$

  $\ \equiv ( ( \neg P \land \neg A ) \lor ( P \land \neg B ) ) \lor ( A \lor B )$

  $\ \equiv ( \neg P \land \neg A \lor A ) \lor ( P \land \neg B \lor B )$

  $\ \equiv ( \neg P \lor A ) \lor ( P \lor B )$

  ... [which I'm sure you can easily finish using excluded middle].

Here is a proof of the useful law which I used above:

  $P \lor \neg P \land Q$

  $\ \equiv P \land ( Q \lor \neg Q ) \lor \neg P \land Q$

  $\ \equiv P \land Q \lor P \land \neg Q \lor \neg P \land Q$

  $\ \equiv P \land Q \lor P \land \neg Q \lor P \land Q \lor \neg P \land Q$

  $\ \equiv P \land ( Q \lor \neg Q ) \lor ( P \lor \neg P ) \land Q$

  $\ \equiv P \lor Q$.

  • $\begingroup$ @CFLAGS: Does my answer help you? $\endgroup$ – user21820 May 30 '16 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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