Proving $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$.

Question

How do I prove using boolean algebra that $\neg A\vee(A\wedge \neg B)= \neg A \vee \neg B$? I can see it in the logic table and it is logical, but I can't prove it mathematically.

Answer 1

Distribute so you get $(\neg A\vee A)\wedge(\neg A\vee \neg B)$ The first is obviously a tautology so you just get $\neg A\vee \neg B$

Answer 2

I like to do these via cases because it is a little quicker than truth tables a lot of the time. Suppose $A = T$ then

$$\begin{align}\neg A\vee (A\wedge \neg B) &= F\vee (T\wedge \neg B) \\ &= F\vee \neg B \\ &= \neg A\vee \neg B.\end{align}$$

This follows since $F = \neg A$. Then if $A=F$, we have

$$\begin{align}\neg A\vee(A\wedge \neg B) &= T\vee (F\wedge\neg B) \\ &= T \\ &= \neg A\vee \neg B. \end{align}$$

This follows since $\neg A = T.$ This holds regardless of the truth or falsity of $B$ so they are the same.

Answer 3

Here is essentially the answer from ruler501, but written down in a different notation, and with some more detail.

To prove this equivalence, the simplest approach is to start at the most complex side and try to simplify. Therefore we calculate:

\begin{align} & \lnot A \lor (A \land \lnot B) \\ \equiv & \qquad \text{"$\;\lor\;$ distributes over $\;\land\;$ -- really the only thing we can do"} \\ & (\lnot A \lor A) \land (\lnot A \lor \lnot B) \\ \equiv & \qquad \text{"left hand part: law of the excluded middle, i.e., $\;P \lor \lnot P \equiv \text{true}\;$"} \\ & \text{true} \land (\lnot A \lor \lnot B) \\ \equiv & \qquad \text{"simplify using $\;P \land \text{true} \equiv P\;$"} \\ & \lnot A \lor \lnot B \\ \end{align}

This proves the equivalence.