Using Karnaugh maps to construct and simplify Boolean expressions

Question

I'm trying to construct a circuit based on K-maps (see picture) - and I must do so only through two-level logic (excluding inverters).

Some of the K-maps naturally came out in two-level logic, but a few of them didn't. I used AND-OR logic by taking 1's. For the ones that exceeded two logic levels I got the following:

1st column, 4th map: $$AB+ \bar{A}\bar{B}C+A\bar{B}\bar{C}$$ This would require 3 AND gates (first level), a two-input OR (second level; we don't have three-input OR gates), and another two-input OR (third level).

2nd column, 2nd map: $$ A\bar{B}\bar{C}+ABC+\bar{A}B\bar{C}$$ Again, this would be over two levels.

2nd column, 3rd map: $$\bar{A}\bar{B}\bar{C}+AC+AB\bar{C}$$ Once more, over two levels.

Is there a way to reduce these expressions further? I thought the point of using K-maps was to get Boolean expressions in their simplest form; well at least most of the time.

Answer 1

If we allow exor gates then here is a solution.

1st col 4th map: (A exor C) + AB

2nd col 2nd map: (A exor B) + ABC

2nd col 3rd map: !(A exor C) + AB, alternatively (A exnor C) + AB

Edit:

Take col 1 map 4 for example. The first two columns have a pattern I recognize as an XOR gate. First row is 01, second row is 10. Now I look at the boxes with '1', A changes when jumping between the two. Look for another variable that is also changing; in this case it is C. A and C are either 01 or 10 in the '1' boxes: that is the characteristics of an XOR gate. Only two '1' remain in the map and they are grouped into the term AB.

Now col 2 map 2: Here are two groups that will work for an XOR gate; col 1 & 4, and col 3 & 4. The first group produces an XOR gate, the second an XNOR gate. In the XNOR gate, both inputs must be equal to produce a '1' on the output.

Finally col 2 map 3. This map looks like col 1 map 4, except the XOR pattern is reversed. That means we use an XNOR gate instead of the XOR in the first map, or we add an inverter to the XOR output.

By the way, regarding your equation for col 1 map 4, notice that the two bottom corners both have '1'. You can group them to produce the term A!C, reducing your third term to two variables.

Answer 2

Assumptions:

• NOTs do not count.

• 3-input ANDs and NANDs are valid.

• 2-input ORs and NORs.

You have some errors in your equations. Edges of K-maps loop around and you can reuse terms.

The correct answer for 1st column, 4th kmap is:

$$AB + \bar A \bar B C + A\bar C$$

Take DeMorgan's: Invert expression, change signs, invert terms.

$$ \overline {\overline {AB} • \overline {\bar A \bar B C} • \overline {A\bar C)}}$$

Two 2-input NANDs + two 3-input NANDs. Two levels.

The correct answer for 2nd column, 3rd kmap is:

$$\bar A \bar B \bar C + AC + AB$$

Take DeMorgan's:

$$\overline { \overline {\bar A \bar B \bar C} • \overline {AC} • \overline {AB}}$$

Again, two 2-input NANDs + two 3-input NANDs. Two levels.

I believe this is enough for you to get concept. Your instructor is giving you a problem which cannot be done unless you think outside the AND-OR box. AND-OR becomes NAND-NAND.