Version 1 of Mahoney Map

Updated 2009-01-28 12:48:12 by lars_h

AMG: A Mahoney Map is like a Karnaugh Map [L1 ] except with a more regular structure. 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:

0 1

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.

10 11
00 01

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.

010 011 111 110
000 001 101 100

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.

1000 1001 1101 1100
1010 1011 1111 1110
0010 0011 0111 0110
0000 0001 0101 0100

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 preceding "/" 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.

01000 01001 01101 01100 11100 11101 11001 11000
01010 01011 01111 01110 11110 11111 11011 11010
00010 00011 00111 00110 10110 10111 10011 10010
00000 00001 00101 00100 10100 10101 10001 10000

And again! Now not only are the right four columns conceptually adjacent to the left four columns, but the top four rows are conceptually 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 first bit (E). They can be grouped. But it's not visually obvious, and now it can't even be imagined in terms of folding. This is where the notation gets tough, and it makes sense to pick a different approach to simplifying your expression.

100000 100001 100101 100100 110100 110101 110001 110000
100010 100011 100111 100110 110110 110111 110011 110010
101010 101011 101111 101110 111110 111111 111011 111010
101000 101001 101101 101100 111100 111101 111001 111000
001000 001001 001101 001100 011100 011101 011001 011000
001010 001011 001111 001110 011110 011111 011011 011010
000010 000011 000111 000110 010110 010111 010011 010010
000000 000001 000101 000100 010100 010101 010001 010000

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 dimesions 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.