I need help in simplifying a Boolean expression.

49 Views Asked by At

My starting point was (A+D)*(A+B+C)*(~A+C+~D)

And I should end at ~A*B*D +A*~D +C*D (according to online solvers.)

But when I do it by hand on a paper I end up with this: ~A*B*D +A*~D +C*D +A*C

And for the life of me I can't figure out how to simplify and get rid of the extra +A*C

1

There are 1 best solutions below

0
On BEST ANSWER

By applying the distributive law you get that $(A \lor D) \land (A \lor B \lor C)\land ( \sim A \lor C \, \lor \sim D)$ is equivalent to

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

We now delete all the disjuncts that are equivalent to $0$ and we get rid of all the redundant terms. We get that the original expression is equivalent to

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

We now erase the disjuncts that are smaller than another disjunct.

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

Which, by commutativity of $\land$, is equivalent to the expression you got. Therefore your solution was right.

Note that your solution is equivalent to $ (\sim A \land B \land D) \lor (A \land \sim D) \lor (C \land D)$. Indeed, by the distributive law and the fact that $D \, \lor \sim D$ is equivalent to $1$, your solution is equivalent to $$ (\sim A \land B \land D) \lor (A \land \sim D) \lor (C \land D) \lor (A \land C \land D) \lor (A \land C \land \sim D). $$

Since the two last disjuncts are smaller than the third and second ones, it is equivalent to

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