Boolean Expression Simplification - Issue

Question

I don't understand where to even begin with this problem. Any helpful tips would be nice.

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

Answer 1

The expression is in Conjunctive Normal Form (CNF), a product of sums.

Probably the easiest way is to create a truth table which lists the expression values for all $2^4=16$ input combinations. Calculate the truth values for the three parts of the expression. The overall expression can only be true, if all conjunctive sub-expressions are also true.

The analytic way to calculate the minterms of the expression is to resolve/eliminate the parentheses:

Step 1:

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

Terms with contradictory literals like $B \lnot B$ result in false and are omitted.

Applying the Absorption Law, this can be simplified to:

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

Step 2:

$$ABC \lor ABD \lor BC \lnot D \lor A \lnot CD \lor \lnot B \lnot C \lor AC \lnot D \lor \lnot B \lnot D \lor C \lnot D$$

Absorbing again:

$$ABC \lor ABD \lor BC \lnot D \lor A \lnot CD \lor \lnot B \lnot C \lor \lnot B \lnot D \lor C \lnot D$$

To simplify this sum of products, a Karnaugh map helps for expressions with a handful of input variables:

             cd
       00  01  11  10
      +---+---+---+---+
   00 | 1 | 1 | 0 | 1 |
      +---+---+---+---+
   01 | 0 | 0 | 0 | 1 |
ab    +---+---+---+---+
   11 | 0 | 1 | 1 | 1 |
      +---+---+---+---+
   10 | 1 | 1 | 0 | 1 |
      +---+---+---+---+

A minimized form is

$$C \lnot D \lor \lnot B \lnot C \lor ABD$$

---

To draw the Karnaugh map right a way without involved reasoning, one can negate the literals of the conjunctive clauses to find out which cells of the Karnaugh map are false/0. The remaining cells are then true/1.

Example: $(A \lor \lnot B \lor \lnot D)$ is false for $\lnot A B D$.

Try this method to convince yourself that it directly arrives at the Karnaugh map depicted above.