Simplifying 4-term Boolean Expression 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!
 A: 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.
A: 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.
