# Using Karnaugh maps to construct and simplify Boolean expressions

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.

• So you have 3 input NAND/AND gates, but not 3 input OR/NOR gates? A K-map will give you a minimal SOP representation, but that's often not optimal for implementation.
– W5VO
Commented Feb 12, 2015 at 7:35
• Unfortunately no, we don't have three-input OR/NOR gates. Is there a way to reduce it? Commented Feb 12, 2015 at 7:38
• But you have 3 input NAND/AND gates?
– W5VO
Commented Feb 12, 2015 at 7:40
• That's correct. Why? Commented Feb 12, 2015 at 7:41
• We're using TTL logic by the way, not sure if that's relevant. Commented Feb 12, 2015 at 7:42

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.

• How do you get this? I'm looking to simplify other expressions so I'm interested in learning how to do it. Commented Feb 12, 2015 at 20:16

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.