How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

Question

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help.

If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$.

Here's how I've been going about solving it:

$\neg b = a \land d$

$a \land \neg b = a \land (a \wedge d)$

$a \land \neg b = a \land d$

$a \land \neg b = \neg b$

This proves the first expression (I think?).

Then for the second expression we start with the first one.

$a \land \neg b = \neg b$

$\neg (a \land \neg b) = b$

$\neg a \lor b = b$

... and here I get stuck?

How do I get from $\neg a \lor b = b$ to $b \land \neg a = \neg a$ ?

Now if we think of this in terms of sets, you can see how $A^{c} \cup B = B$ can only hold true if $A^{c} \subseteq B$ and hence it can be seen how $b \land \neg a = \neg a$ may hold. But I'm not sure how to prove this.

Answer 1

The first part works fine.

For the second, the following will work, but I don't know what your axiom set and rules of inference say.

assumption           1 ¬b=(a∧d) 
introduce "V" in 1   2 (a V ¬b)=(aV(a∧d)).
2 (xV(x^y))=x        3 (a V ¬b)=a
3 ¬¬a=a              4 ¬¬(a V ¬b)=¬¬a
4 ¬(aVb)=(¬a^¬b)     5 ¬(¬a∧¬¬b)=¬¬a
canceling ¬'s in 5   6 (¬a∧¬¬b)=¬a
6 ¬¬a=a              7 (¬a∧b)=¬a
7 (x^y)=(y^x)        8 (b∧¬a)=¬a

Answer 2

Here is how I would do this: by calculation.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} $We are given that $$ \tag 0 \lnot b \;\equiv\; a \land d $$ For the first part, we start at the most complex side, and try to simplify $\;a \land \lnot b\;$: $$\calc a \land \lnot b \calcop\equiv{using $\ref 0$ -- the only thing we know} a \land a \land d \calcop\equiv{logic: simplify} a \land d \calcop\equiv{using $\ref 0$ -- to get us to our goal} \lnot b \endcalc$$ This proves the first part.

Now the second part can be done in a similar fashion, but you will also need to use DeMorgan and absorption.

Answer 3

The thing about Boolean algebra is that there isn't always a shortcut (unless some very monumental mathematical results manifest to surprise us all).

In your first question, you found a nice shortcut by applying $a \land \dots$ to both sides. But sometimes you just have to write out the truth tables and nothing is faster. It's more important to know how to do this the slow systematic way than it is to memorize the shortcuts.

So to do the second question in the most direct fashion, just check all 8 cases of $a$, $b$, and $d$:

$$ \DeclareMathOperator{T}{\color{blue}{\text{T}}} \DeclareMathOperator{F}{\color{red}{\text{F}}} \begin{array} {ccc|c|c|c} a & b & d & \lnot b = a \land d & b \land \lnot a = \lnot a & (\lnot b = a \land d) \rightarrow (b \land \lnot a = \lnot a) \\ \T & \T & \T & \F & \T & \T\\ \T & \T & \F & \F & \T & \T\\ \T & \F & \T & \T & \T & \T\\ \T & \F & \F & \F & \T & \T\\ \F & \T & \T & \T & \T & \T\\ \F & \T & \F & \T & \T & \T\\ \F & \F & \T & \F & \F & \T\\ \F & \F & \F & \F & \F & \T\\ \end{array} $$

So you can see that the implication always holds.