Converting $\neg(A\land B)\land(B\lor\neg C)\Leftrightarrow(\neg A\land B)\lor(\neg B\land\neg C)$

Question

$$\neg(A\land B)\land(B\lor\neg C)\Leftrightarrow(\neg A\land B)\lor(\neg B\land\neg C)$$ Checked their truth tables are the same, but can you show the steps how to transform one to the other?

Answer 1

We have: $$\overline{AB} (B \vee \bar{C}) \Leftrightarrow (\bar{A} \vee \bar{B})(B \vee \bar{C}) \Leftrightarrow \bar{A}B \vee \bar{A} \bar{C} \vee \bar{B} B \vee \bar{B} \bar{C} \Leftrightarrow \bar{A}B \vee \bar{A} \bar{C} \vee \bar{B} \bar{C}$$ Now if $\bar{A} \bar{C}$ turns out to be true, either $\bar{A} B$ or $\bar{B} \bar{C}$ must be true, because $B$ is either true or false. That's why you can leave $\bar{A} \bar{C}$ out and you get your result: $$ \overline{AB} (B \vee \bar{C}) \Leftrightarrow \bar{A} B \vee \bar{B} \bar{C}$$

You can also use some boolean algebra to eliminate $\bar{A} \bar{C}$:

$$ \bar{A}B \vee \bar{A} \bar{C} \vee \bar{B} \bar{C} \Leftrightarrow \bar{A}B \vee \bar{A} \bar{C} (B \vee \bar{B}) \vee \bar{B} \bar{C} \Leftrightarrow \bar{A} B \vee \bar{A} \bar{C} B \vee \bar{A} \bar{C} \bar{B} \vee \bar{B}\bar{C} \\ \Leftrightarrow \bar{A} B (1 \vee \bar{C}) \vee \bar{B} \bar{C}(\bar{A} \vee 1) \Leftrightarrow \bar{A} B \vee \bar{B} \bar{C}$$

Answer 2

As an addendum to @Koepi's Answer:

To go from $(\neg A \land B) \lor (\neg A \land \neg C) \lor (\neg B \land \neg C)$ to $(\neg A \land B) \lor (\neg B \land \neg C)$ is an immediate application of the Consensus theorem:

Consensus

$$(P \land Q) \lor (\neg Q \land R) \lor (P \land R) = (P \land Q) \lor (\neg Q \land R)$$

Proof:

$$(P \land Q) \lor (\neg Q \land R) \lor (P \land R) = \text{ (Adjacency)} $$

$$(P \land Q) \lor (\neg Q \land R) \lor (P \land Q \land R) \lor (P \land \neg Q \land R) = \text{ (Absorption)} $$

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

And if you are unfamiliar with Adjacency and Absorption:

Adjacency

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

Proof:

$$P = \text{ (Identity)}$$

$$P \land \top = \text{ (Complement)}$$

$$P \land (Q \lor \neg Q) = \text{ (Distribuition)}$$

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

Absorption

$$P \lor (P \land Q) = P$$

Proof:

$$P \lor (P \land Q) = \text{ (Identity)}$$

$$(P \land \top) \lor (P \land Q) = \text{ (Distribution)}$$

$$P \land (\top \lor Q) = \text{ (Annihilation)}$$

$$P \land \top = \text{ (Identity)}$$

$$P$$