Simplifying 4-term Boolean Expression

Question

I am given a pretty lengthy Boolean expression:

$$(¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D)$$

which I am asked to simplify. The solution should be:

$$((¬D ∨ B) ∧ (D ∨ ¬B)) ∧ ((¬A ∨ C) ∧ (A ∨ ¬C))$$

But I'm not really sure how this reduction can be achieved. Here's my attempts:

Attempt #1

$ \begin{align} (¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D) &\text{Given}\\ (¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D) ∨ (A ∧ B ∧ C ∧ D) ∨ (A ∧ B ∧ C ∧ D) &\text{Idempotence}\\ ((¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D)) ∨ ((¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ B ∧ C ∧ D)) ∨ ((A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D)) & \text{Commutativity, Associativity}\\ ((¬A ∨ A) ∧ (¬B ∨ B) ∧ (¬C ∨ C) ∧ (¬D ∨ D)) ∨ ((¬A ∨ A) ∧ (B ∨ B) ∧ (¬C ∨ C) ∧ (D ∨ D)) ∨ ((A ∨ A) ∧ (¬B ∨ B) ∧ (C ∨ C) ∧ (¬D ∨ D)) & \text{Commutativity, Distributivity}\\ (1 ∧ 1 ∧ 1 ∧ 1) ∨ (1 ∧ B ∧ 1 ∧ D) ∨ (A ∧ 1 ∧ C ∧ 1) & \text{Boundedness}\\ (1 ∧ 1 ∧ 1 ∧ 1) ∨ (B ∧ D) ∨ (A ∧ C) & \text{Boundedness, Commutativity}\\ 1 & \text{Boundedness} \end{align} $

Attempt #2

$ \begin{align} (¬A ∧ ¬B ∧ ¬C ∧ ¬D) ∨ (¬A ∧ B ∧ ¬C ∧ D) ∨ (A ∧ ¬B ∧ C ∧ ¬D) ∨ (A ∧ B ∧ C ∧ D) &\text{Given}\\ ((¬A ∨ ¬A) ∧ (¬B ∧ B) ∧ (¬C ∨ C) ∧ (¬D ∨ D)) ∨ ((A ∨ A) ∧ (¬B ∧ B) ∧ (¬C ∨ C) ∧ (D ∨ ¬D)) &\text{Commutativity, Distributivity}\\ (¬A ∧ 1 ∧ ¬C ∧ 1) ∨ (A ∧ 1 ∧ C ∧ 1) & \text{Boundedness}\\ (¬A ∧ ¬C) ∨ (A ∧ C) & \text{}\\ \end{align} $ (Obviously incorrect because the expression has no dependence on $C$ nor $D$.)

How should I start simplifying this expression correctly? I really appreciate the help!

I think you just use Commutativity and Distributivity and then get the conjuction of a bunch of disjunctions. Once you have that, you can cancel out the expressions that are tautologies to get the simplified expression. — Noble Mushtak, Feb 07 '16 at 15:40
The solution can be further simplified to $(A\equiv C)\wedge(B\equiv D)$ — Jan Stout, Feb 08 '16 at 07:31

score 2 · Accepted Answer · answered Feb 07 '16 at 17:20

The solution is much easier if you use an algebraic notation: $+$ instead of $\vee$, product instead of $\wedge$ and $\overline{A}$ instead of $\neg A$. Then you have $$ \overline{A}\overline{B}\overline{C}\overline{D} + \overline{A}B\overline{C}D + A\overline{B}C\overline{D} + ABCD = (AC + \overline{A}\overline{C})(BD + \overline{B}\,\overline{D}) $$ Since $A\overline{A} = \overline{C}C = 0$, one gets $$ AC + \overline{A}\overline{C} = A\overline{A} + AC + \overline{A}\overline{C} + \overline{C}C = (A+\overline{C})(\overline{A}+C) $$ and similarly $BD + \overline{B}\,\overline{D} = (B + \overline{D})(D+\overline{B})$. Therefore, $$ (AC + \overline{A}\overline{C})(BD + \overline{B}\,\overline{D}) = (B + \overline{D})(\overline{B} + D)(\overline{A}+C)(A+\overline{C}) $$ which gives the expected solution.

score 1 · Answer 2 · answered Feb 07 '16 at 16:23

We have the following:

$$({\sim} A \wedge {\sim} B \wedge {\sim} C \wedge {\sim} D) \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D) \vee (A \wedge B \wedge C \wedge D)$$

Using Distributivity, we get the following: $$({\sim} A \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} B \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} C \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} D \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D))$$

In each one of these four disjunctions, there is something in the form of $X \vee (X \wedge Y)$ which we can simplify to just $X$, getting rid of one of the conjunctions in each disjunction: $$({\sim} A \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D) \vee (A \wedge B \wedge C \wedge D)) \wedge ({\sim} B \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge B \wedge C \wedge D)) \wedge ({\sim} C \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D) \vee (A \wedge B \wedge C \wedge D)) \wedge ({\sim} D \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D) \vee (A \wedge B \wedge C \wedge D))$$

We can distribute $(A \wedge B \wedge C \wedge D)$ out of each disjunction: $$(A \wedge B \wedge C \wedge D) \vee (({\sim} A \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} B \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D)) \wedge ({\sim} C \vee (A \wedge {\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} D \vee ({\sim} A \wedge B \wedge {\sim} C \wedge D)))$$

Each of the four disjunctions are now in the form of ${\sim} X \vee (X \wedge Y)$ which can be simplified to ${\sim} X \vee Y$: $$(A \wedge B \wedge C \wedge D) \vee (({\sim} A \vee ({\sim} B \wedge C \wedge {\sim} D)) \wedge ({\sim} B \vee ({\sim} A \wedge {\sim} C \wedge D)) \wedge ({\sim} C \vee (A \wedge {\sim} B \wedge {\sim} D)) \wedge ({\sim} D \vee ({\sim} A \wedge B \wedge {\sim} C)))$$

Use Distributivity in each disjunction: $$(A \wedge B \wedge C \wedge D) \vee ((({\sim} A \vee {\sim} B) \wedge ({\sim} A \vee C) \wedge ({\sim} A \vee {\sim} D)) \wedge (({\sim} B \vee {\sim} A) \wedge ({\sim} B \vee {\sim} C) \wedge ({\sim} B \vee D)) \wedge (({\sim} C \vee A) \wedge ({\sim} C \vee {\sim} B) \wedge ({\sim} C \vee {\sim} D)) \wedge (({\sim} D \vee {\sim} A) \wedge ({\sim} D \vee B) \wedge ({\sim} D \vee {\sim} C)))$$

Get rid of unnecessary parentheses: $$(A \wedge B \wedge C \wedge D) \vee (({\sim} A \vee {\sim} B) \wedge ({\sim} A \vee C) \wedge ({\sim} A \vee {\sim} D) \wedge ({\sim} B \vee {\sim} A) \wedge ({\sim} B \vee {\sim} C) \wedge ({\sim} B \vee D) \wedge ({\sim} C \vee A) \wedge ({\sim} C \vee {\sim} B) \wedge ({\sim} C \vee {\sim} D) \wedge ({\sim} D \vee {\sim} A) \wedge ({\sim} D \vee B) \wedge ({\sim} D \vee {\sim} C))$$

Use Commutativity and Idempotence to get rid of repeats: $$(A \wedge B \wedge C \wedge D) \vee (({\sim} A \vee {\sim} B) \wedge ({\sim} A \vee C) \wedge ({\sim} A \vee {\sim} D) \wedge ({\sim} B \vee {\sim} C) \wedge ({\sim} B \vee D) \wedge ({\sim} C \vee A) \wedge ({\sim} C \vee {\sim} D) \wedge ({\sim} D \vee B))$$

Use Commutativity and add parentheses to make this look more like our conclusion: $$(A \wedge B \wedge C \wedge D) \vee ((({\sim} D \vee B) \wedge (D \vee {\sim} B)) \wedge (({\sim} A \vee C) \wedge (A \vee {\sim} C)) \wedge ({\sim} A \vee {\sim} B) \wedge ({\sim} A \vee {\sim} D) \wedge ({\sim} B \vee {\sim} C) \wedge ({\sim} C \vee {\sim} D))$$

Use Distributivity on the conjunction of the last four disjunctions twice to move things around a bit: $$(A \wedge B \wedge C \wedge D) \vee ((({\sim} D \vee B) \wedge (D \vee {\sim} B)) \wedge (({\sim} A \vee C) \wedge (A \vee {\sim} C)) \wedge (({\sim A} \wedge {\sim C}) \vee ({\sim} B \wedge {\sim} D)))$$

Now, use De Morgan's Law on the last bit we just created twice: $$(A \wedge B \wedge C \wedge D) \vee ((({\sim} D \vee B) \wedge (D \vee {\sim} B)) \wedge (({\sim} A \vee C) \wedge (A \vee {\sim} C)) \wedge {\sim} (A \wedge B \wedge C \wedge D))$$

We now have the whole expression in the form of $X \vee (Y \wedge {\sim} X)$ which we can simplify down to just $Y$: $$(({\sim} D \vee B) \wedge (D \vee {\sim} B)) \wedge (({\sim} A \vee C) \wedge (A \vee {\sim} C))$$

Thus, we have reached the conclusion as desired.

Simplifying 4-term Boolean Expression

2 Answers2