[AMG]: A Mahoney Map is like a Karnaugh Map [http://en.wikipedia.org/wiki/Karnaugh_map] 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.
----
!!!!!!
%| [Category Algorithm] |%
!!!!!!