Help with simplifying boolean expression

Question

How would I simplify

$$X = (A\land B\land \neg C\land \neg D)\lor (A\land B\land C\land \neg D)\lor (A\land B\land \neg C\land D)\lor (\neg A\land B\land C\land D)\lor (A\land B\land C\land D)$$

into

$X = (A\land B)\lor (B\land C\land D)$

using logical equivalence

Answer 1

Here is one possible strategy:

$$ \begin{align} A \wedge B &= A \wedge B \wedge (C \vee \neg C) && \text{(identity)} \\ =& (A \wedge B \wedge C) \vee (A \wedge B \wedge \neg C) && \text{(distribution)} \\ =& ((A \wedge B \wedge C) \vee (A \wedge B \wedge \neg C)) \wedge (D \vee \neg D) && \text{(identity)} \\ =& (A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge \neg C \wedge D) \\ & \vee (A \wedge B \wedge C \wedge \neg D) \vee (A \wedge B \wedge \neg C \wedge \neg D) && \text{(distribution)} \end{align} $$

We can make the 'identity' steps because, for any $P$ and $Q$, $P \wedge (Q \vee \neg Q) = P$. We can make the 'distribution' steps because, for any $P$, $Q$ and $R$, $P \wedge (Q \vee R) = (P \wedge Q) \vee (P \wedge R)$.

$$ \begin{align} B \wedge C \wedge D &= (B \wedge C \wedge D) \wedge (A \vee \neg A) && \text{(identity)} \\ &= (B \wedge C \wedge D \wedge A) \vee (B \wedge C \wedge D \wedge \neg A) && \text{(distribution)} \\ &= (A \wedge B \wedge C \wedge D) \vee (\neg A \wedge B \wedge C \wedge D) && \text{(commutative, associative)} \end{align} $$

Hence:

$$ \begin{align} (A \wedge B) \vee (B \wedge C \wedge D) =& (A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \neg D) \\& \vee (A \wedge B \wedge \neg C \wedge \neg D) \vee (A \wedge B \wedge C \wedge D) \vee (\neg A \wedge B \wedge C \wedge D) && \text{(by above)} \\ =& (A \wedge B \wedge \neg C \wedge \neg D) \vee (A \wedge B \wedge C \wedge \neg D) \vee (A \wedge B \wedge \neg C \wedge D) \\ &\vee (\neg A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge C \wedge D) && \text{(commutative, associative)} \\ =& (A \wedge B \wedge \neg C \wedge \neg D) \vee (A \wedge B \wedge C \wedge \neg D) \vee (A \wedge B \wedge \neg C \wedge D) \\ &\vee (\neg A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge C \wedge D) && \text{(idempotence)} \end{align} $$

Because $\vee$ is commutative and associative, we can rearrange the bracketed clauses how we like. We can make the 'idempotence' step because:

$$(A \wedge B \wedge C \wedge D) \vee (A \wedge B \wedge C \wedge D) = (A \wedge B \wedge C \wedge D)$$

Answer 2

Use:

Adjacency

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

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

Applied to your statement:

$$(A\land B\land \neg C\land \neg D)\lor (A\land B\land C\land \neg D)\lor (A\land B\land \neg C\land D)\lor (\neg A\land B\land C\land D)\lor (A\land B\land C\land D) \Leftrightarrow \text{ (Adjacency x 3: terms 1 + 2, 3 + 5, and 4 + 5)}$$

$$(A\land B\land \neg D)\lor (A\land B\land D)\lor (B\land C\land D)\Leftrightarrow \text{ (Adjacency)}$$

$$(A\land B)\lor (B\land C\land D)$$