Mahoney Map

AMG: A Mahoney map is like a Karnaugh map [L1 ] with a more straightforward generation process. Either can be used for simplifying logical expressions, particularly for making a simplified logical expression given a truth table.

Someday I will put code here, but for now I will just demonstrate the process of constructing a Mahoney map.

Let's start with the simple single-variable case. I will call this variable A. Make a table like this:

The numbers 0 and 1 represent /A and A, respectively, where /A is pronounced "not-A". (Man, I wish I could type an overbar!)

Now let's add a second variable B. Mirror the table vertically and add a new digit to the left-hand side, which will represent /B and B. Put 0 on the bottom row and 1 on the top row. 00: /A/B, 01: /AB, 10: A/B, 11: AB.

A third variable C can be added by mirroring horizontally and adding a third digit to the left-hand side. Put 0 on the left two columns and 1 on the right two columns.

Now a fourth variable D! Mirror vertically and add a fourth digit on the left-hand side. Put 0 on the bottom two rows and 1 on the top two rows.

Now that things are out of the realm of the trivial, let's just grab a cell at random and explain its meaning. Take 1011. What that really means is "D and (not C) and B and A", which can also be written "D/CBA". To actually use this to convert a truth table to a logical expression, circle every cell that corresponds to a "true" entry in the truth table. If the function of variables A, B, C, and D is true when "(D and (not C) and B and A)" is true, circle 1011. Depending on the truth table, there will hopefully be several adjacent circled entries, forming rows, columns, or rectangles of width and/or height 2 or 4 (but not 3; it's not a power of two). Circle these. The table wraps around the edges, so the grouping circles can wrap too. Just like how each individual cell corresponds to a single expression (such as D/CBA = 1011), the larger grouping circles correspond to expressions, also known as minterms. For example, if 1000, 1001, 1010, and 1011 are circled, that corresponds to D/C = 10xx, where "x" means "I don't care". Let's say there are large circles: 1000+1001+1010+1011 and 0111+0101. This corresponds to the expression "((D and (not C)) or ((not D) and C and A))", also written "D/C+/DCA". In order of decreasing precedence, a prefixed "/" is "not", juxtaposition is "and", and "+" is "or".

We can keep going. Just alternate between mirroring horizontally and vertically. However, after four variables things start to get tricky. Why is that? First let me explain why the above stuff isn't tricky. :^) Since the tables wrap*, each cell is adjacent to N other cells, where N is the number of variables. Adjacent cells differ in only one variable, which in my notation is one digit (or bit). But since this Wiki only allows me to create two-dimensional tables (lousy stupid wiki!), I can't actually draw a table where a cell visibly has five neighbors. So you will have to use your imagination. Pretend that the right four columns in this next table are stacked on top of the left four columns. Pretend that you have this page printed out and folded with a vertical crease down the middle, so that the rightmost column is touching the leftmost column.

* Actually they don't wrap, but the effect is same. Cells on opposite edges are adjacent because the table is "folded" so that they touch. The problem with thinking in terms of wrapping is that it may cause you to fail to notice some adjacencies when working with five or more variables.

And again!

Now not only are the right four columns adjacent to the left four columns, but the top four rows are adjacent to the bottom four rows. The consequence of this is that not only are you grouping adjacent cells into rows and columns, but also into stacks. For example, the second and seventh cells on the top row are adjacent; they differ only in the second bit (E). They can be grouped. But it's not visually obvious, and now that there are six variables, it's getting hard to imagine in terms of folding. This is where the notation stops being usable, and it makes sense to pick a different approach to simplifying your expression.

But! With a nifty Tk program I could make the table highlight adjacent cells to help overcome the limitations of the notation. Maybe someday I will write one!

Lars H: The natural domain for an n-variable function is an n-dimensional hypercube, but working directly with that is difficult already for n=3. Karnaugh maps compresses two dimensions of the hypercube into one dimension of the table by using the observation that a 2-dimensional hypercube — a square — is also a cycle of length 4, so by changing

  1-2
  | |      to    -1-2-3-4-
  4-3

in the drawing, one can depict an n-dimensional hypercube in n/2 dimensions. That way, things work well all the way up to 4 variables. In order to get further, one needs to employ an additional trick.

AMG: In a Mahoney map, this kind of compression happens with every other pair of variables. Take the third table:

Replace the second variable (B) with don't-care:

The two rows are now the same, so drop one. Also drop the don't-care term and understand that the bit assignment is now CA:

Now compare with the second table, mentally substituting C for B as the first bit and flipping vertically to match your top-to-bottom convention:

See the resemblance? In the above two tables, replace 00 with 1, 01 with 2, 11 with 3, and 10 with 4 to get your two tables.

Why the vertical flip? I used bottom-to-top so that all-bits-zero would be in the lower-left corner, similar to the origin in the first quadrant of the Cartesian plane. But you used top-to-bottom, presumably to match conventional reading order. It doesn't matter which is used.