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

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

• 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. – 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$.