# Converting karnaugh maps to Boolean expressions

My professor briefly mentioned that there are ways of "taking 0's" and "taking 1's" from a K-map that allow you to form the logical expressions differently (e.g. NAND-NAND, AND-OR, NOR-NOR, etc.). Can anyone explain this, or direct me towards a discussion on this topic? The only method I can seem to find is minterm vs maxterm solutions.

Here is my current understanding:

For minterm solutions, we make groups of 1's in powers of 2. For each grouping, invert if the unchanged variable is a 0, and do nothing if it's 1. Each variable in the group is ANDed together, and this forms a product of sum of products with the other groupings (if any)- the result is AND-OR logic.

For maxterm solutions, we make groups of 0's in powers of 2. For each grouping, invert if the unchanged variable is a 1, and do nothing if it's 0. Each variable in the group is ORed together, and this forms a product of sums with the other groupings (if any)- the result is also AND-OR logic.

I'm not sure what I'm missing.

• NAND-NAND and AND-OR are the same. You can directly implement a SOP using this. Similarly NOR-NOR can be used to implement a POS easily. – nidhin Feb 12 '15 at 14:06
• Can this be done using DeMorgan's theorem? – Lefty Feb 12 '15 at 14:08
• Using DeMorgan's theorem, it can be proved that NANAD-NAND is equivalent to AND-OR (SOP) and NOR-NOR is equivalent to OR-AND (POS). – nidhin Feb 12 '15 at 14:10
• I'm not sure what textbooks you're using but this is fairly standard material, e.g. books.google.com/books?id=xqLl9_YwYn4C&pg=SA2-PA27 – Fizz Feb 12 '15 at 20:36

## 1 Answer

What you understood is correct. Grouping mintems results in sum of product (SOP) form or the AND-OR form as shown in (1) $$Y = a_1a_2a_3 + b_1b_2b_3 + \cdots + \omega_1\omega_2\omega_3\tag1$$ Calculating $\overline{Y}$ using De-Morgan's theorem, $$\overline{Y} = (\overline{a_1a_2a_3} )\ (\overline{b_1b_2b_3}) \cdots (\overline{\omega_1\omega_2\omega_3})$$ From this Y can be written as $$Y = \overline{(\overline{a_1a_2a_3} )\ (\overline{b_1b_2b_3}) \cdots (\overline{\omega_1\omega_2\omega_3})}\tag2$$

Which is the NAND-NAND form since variables in a group are NANDed together and NANDed again to obtain Y. So the AND-OR form and NAND-NAND form are equivalent.

Point to be noted (from(1) and (2) )is that a AND-OR circuit can be converted to NAND-NAND circuit just by replacing the AND and OR gates with NAND gates without changing any interconnections.

So grouping "1"s from K-map allow us to form AND-OR and NAND-NAND easily.

Similarly, grouping maxterms produces POS or OR-AND form: $${Y} = ({a_1+a_2+a_3} )\ ({b_1+b_2+b_3}) \cdots ({\omega_1+\omega_2+\omega_3})\tag3$$

Using De-Morgan's theorem it can be proved that OR-AND is equivalent to NOR-NOR form.

So grouping "0"s from K-map allow us to form OR-AND and NOR-NOR easily.

UPDATE:

From K-map you have to find SOP or POS then you can directly implement using NAND-NAND or NOR-NOR circuit.

For example, assume that from K-map you obtained the following SOP from K-Map $$Y = abc + ab\overline{c} + \overline{a}bc$$

You can implement this using AND-OR logic as:

Same way it can be implemented using NAND-NAND as,

So If you can directly draw AND-OR circuit from K-map (SOP) then you can draw NAND-NAND just by replacing the gates with NAND. Similarly, given POS, NOR-NOR circuit can be drawn directly.

• I appreciate the in-depth response. Thanks! This really clears things up. I think what my professor was doing was using NAND-NAND and NOR-NOR logic directly from the K-map, which might be why it was a bit confusing. – Lefty Feb 12 '15 at 19:39
• How do you get the NAND-NAND and NOR-NOR directly from the K-map without grouping "1"s and applying DeMorgan's theorem? – Lefty Feb 12 '15 at 19:46
• @Lefty I have edited the answer. I think the update can explain it for you. – nidhin Feb 12 '15 at 20:06
• Thanks a ton! I don't know why my professor is over-complicating things. The update helps a lot. – Lefty Feb 12 '15 at 20:14