Math Is Fun Forum

say you have a 2-boolean-variable truth table expressed with a square.
Here is the square:
tt
tf

so three outputs are true and one is false.
the inputs are the x and y axes along the edge of the square.
x and y inputs vary from 0 to 1.
Now wikipedia does a pretty bad job explaining Karnaugh maps.
I also do a bad job because they are not easy to teach without
some interaction and a good lecture hall and an occasional question.
Why should I ramble about Karnaugh maps?
The reason why is because maybe the electrical engineers could
donate valuable information to the math guys and the mathematicians
could develop their boolean algebra a little more if they are lucky.

So here is another Karnaugh map in 2-variables:

AB
CD

A,B,C,andD are just positions to talk about.
Note you can start at any location and build a tree.
A
/\
B C
The tree then closes up to D.
Basically in my mind, we are taking a 2-d object, a
square, and making it into an object that is either 2-d, a tree,
or 1-d, the same tree, depending how you view it.
If you view the tree one vertex at a time and move through
the tree like a flowchart, following paths, then it might be a
1-d object.
The reason I mentioned that is because I'm trying to take the
16 vertex graph called a hypercube, and create 3-d or 2-d trees
that I like so I can make comparisons either on paper or otherwise.
(again although this is "help me", I hope I'm not breaking rules here)
(basically I'm just thinking through my project and thought
someone might get interested and post a comment to spawn ideas
for me, thanks in advance, but I don't expect that to happen so
please just let me ramble since graph theory and boolean algebra
are important things to work on.  Never mind knot theory!

Here is how a 4-variable (hypercube) Karnaugh map is set up in 2-d
for EE majors in the 1980s:

      0   1   3   2
-------------------
0 |  Z  A   C   B
   |
1 |  D  E   G   F
   |
3 |  L   M  O   N
   |
2 |  H   I   K   J

Note that E is at (1,1) input location.  Output locations A, D, G, and M are
the four locations where the input coordinates vary by only one variable.
The reason I believe Maurice 1953 Karnaugh did this is because when
you combine terms or locations with a loop drawn around them, the
boolean expression naturally get smaller.  For example, let's label two
boolean variables x and y and make them go horizontally 0 1 3 2 with y
as the 1's place and x as the 2's place.  Now make z and w go downward
with 0 1 3 2 too(, so 00 01 11 10) for z and w making those numbers.
Now the column CGOK is when x and y make 3 and x=1 and y=1 or their
input values in the corresponding boolean truth table.
The row LMON is when z and w are both true or 1.
Location E is at (1,1), right-down or 0101/xyzw so x=0 y=1 z=0 w=1


So for GO, xy both are true (1) and on the vertical z/w are 1/3.

zwzw
0111

So for GO the variable z is both 0 and 1, so just drop it out of the equation.
And GO has w=1 in both places so use w.  So equation for GO is xyw.
A boolean truth table has an output value and likewise, the location GO
could be filled with two 1's or two 0's if you circle it together.
If two 1's, then output value is 1=xyw or OutputValue(x,y,z,w)=xyw.
The output value will be one when those three xyw variables multiply to 1,
they are all 1.  They are actually AND'd together, but multiplying does the
same thing.


A little more explanation here is needed ofcourse, actually a lot, but I'm
just trying to help so you can piece it together from various sources if
you are trying to learn it.



Below I am trying to show that z is true for half of karnaugh map grid
at LMON and HIKJ see parenthesis to the right and binary inputs z,w.
Note that w is true for the middle two horizontal rows.  From this info,
wz=LMON. w OR z = DEFG LMON HIKJ.

      0   1   3   2
-------------------                  z,w
0 |  Z  A   C   B                   0 0              
   |                                            
1 |  D  E   G   F          \        0 1                   
   |                             w                              
3 |  L   M  O   N     \    /       1 1                                 
   |                         z                                          
2 |  H   I   K   J      /            1 0                          

w XOR z = DEFG OR HIKJ.

If you don't know this stuff you kind should piece it together from many
angles since few people have time to post a comprehensive explanation,
but I'll do piecemeal at times to aid a little.