This web page consists of a series of content units centered around interactive learning games formed from java applets. Our approach to interactive learning is described in the section on Interactive Game Theory. All the games and material may be accessed from the Window GUI, currently a JAVA applet. This GUI provides visual access, while individual games and their associated interactive learning units may be accessed either by tool selection in the applet window or by the traditional browsing of the following HTML pages.
For example, there is Logic Minimization game, in which the user tries to discover a minimum sum of products representation of a Boolean function. This is a theoretically difficult problem, and is technologically significant in a Logic Synthesis Context. Thus, it is closely related to the problem of designing a microchip to have minimum size. In its present form, the K-map game is played in a 6-dimensional boolean space, projected onto the plane. To play the game, click on K-map game.
A 6-dimensional Boolean cube is given, which is mapped onto 4 4x4 matrices in the plane (Karnaugh Map). A 6-variable Boolean function has been mapped onto this cube, as indicated by colored dots. Each dot represents a primitive boolean function called a minterm, for which the function evaluates to 1. A Boolean function F is completely characterized by such a set of minterms.
Minterms are in the class of Boolean function called Boolean cubes. If the 6 logic variables are a,b,c,d,e,f, the possible minterms are a'b'c'd'e'f',a'b'c'd'e'f,...,abcdef, where the prime denotes complement. The literals (logic symbols) a and a' are shorthands for a=1 and a=0. Thus minterms are conjunctions of any 6 literals and cubes are either single literals or conjunctions of k literals, where 1< k< 7. In an n-dimensional space, a k-literal cube contains 2**(n-k) minterms.
An implicant of F is a k-cube, k< n, for which F evaluates to 1 on all 2**k of its minterms. A set of S of implicants is said to cover the set of minterms where F=1 if and only if each dot is contained in one of the implicants of S. The object of the game is to find the smallest set of cubes which has the property that every minterm is contained in at least one of the cubes. To do this, the player tries expand the cubes where possible, trying to make some of the cubes redundant. Redundant cubes are to be deleted. The cost of the covering set decreases with the number of its cubes, and decreases with the size of each cube (fewer literals means larger cubes)
To avoid local minima, it is sometimes necessary to reduce cubes instead of expanding them. This is an "uphill move", which temporarily increases the cost of the solution, but ultimately can lead past a global minimum.
Here the variables of the 6-variable logic function $F$ are $t,u,v,w,x,y$. The
Boolean 6-cube is projected onto 4 4-variable K-maps. The map on the upper left
corresponds to $u=0, t=0$, and so on. Initially the cubes of $F$ are all minterms,
represented by the dots.
A cube with more than 1 minterm is "selected" by clicking one of its minterms
and dragging in one of the 6 coordinate directions. Direction is
defined by :drag and drop" mouse movements as follows.
Left/Right: +/- in $x$ or $y$, depending on position;
Up/Down: +/- in $v$ or $w$, depending on position;
Shift-Up/Down: +/- in $u$, depending on position;
Each of the 4 4-dimensional K-maps has a periphery of "virtual" cells, so that
a mouse movement to the left (up) from a left-edge cell indicates a "wrap-around"
movement to the corresponding cell on the right (bottom) of the K-map. For example,
if the (t=0,u=0,v=0,w=0,x=0,y=0) vertex is selected a rightward mouse drag adds
the (t=0,u=0,v=0,w=0,x=0,y=1) to the selection, whereas a downward movement would
add (t=0,u=0,v=0,w=1,x=0,y=0). A leftward movement, however, would add
(t=0,u=0,v=0,w=0,x=1,y=0) and an upward movement would add (t=0,u=0,v=1,w=0,x=0,y=0).
Finally, a shift-left movement would add (t=1,u=0,v=0,w=0,x=0,y=0) and a
shift-down movement would add (t=0,u=1,v=0,w=0,x=0,y=0).
Each cube is surrounded by an oval on the K-map. has an associated
integer index. If there are not too many cubes, all the indices are
shown. In all cases, the index of the selected cube is shown.
Solving the Optimization Problem is equivalent to finding the "smallest" (in the sense defined below) logic circuit which represents the specified logic function.
A Boolean n-cube is a unit n-dimensional equilateral parallelopiped with exactly 2**n vertices. The n-cube may be considered to be a non-planar graph with 2**n vertices and (n/2)2**n edges. Each vertex is connected to exactly n other vertices by a path of length 1 (a path of 1 edge).
n-cubes may be effectively visualized by isometric projection for n=0,1,2,3,4 (although drawing a 4-cube without line overlap is somewhat difficult). The 4-variable function represented by F=a'c'+b'c'+ac+bc is illustrated by the following figure. Here a=0 on the inner cube and a=1 on the outer cube. The upper right hand vertex has coordinates (1,1,1,1), and corresponds to the minterm abcd. F has 12 minterms, and the function evaluates to 1 for all minterms except those at vertices (1,1,0,0), (1,1,0,1), (0,0,1,0), and (0,0,1,1).
Note that the function F is independent of variable d, so that each minterm has a matching minterm with the opposite value of d.
Unfortunately the optimization problem tends to be trivial in 4 or fewer dimensions. This is because local minima, which are the rule in problems of practical importance (typically n> 32 in real logic circuits). This makes learning effective optimization strategies difficult to learn visually. This difficulty has led to widespread use of Karnaugh Maps or K-maps for short, which yields effective visualization for n=5 or n=6. In a K-map of size 4, the 16 vertices of the 4-cube are projected onto the plane as the elements, or "cells" of a 4x4 matrix.
Each edge has length 1, and each coordinate of any vertex is either 0> or 1. Along each edge, exactly one coordinate variable changes its logic value value from 0 to 1 or conversely.
Examples:
Consider a Boolean function F^k, which has exactly 2**k minterms. F^k may be viewed as a subgraph of G_k with 2**k vertices. Then F_k is a k-cube if and only if each of its vertices are connected to exactly k other vertices in the subgraph by a path of length 1. Under these conditions we similarly say that G_k is a k-cube
Thus the graph of the 1-cube has 2 distinct subgraphs which are 0-cubes, the 2-cube has 4 distinct subgraphs which are 1-cubes, and the 3-cube has 6 distinct subgraphs which are 2-cubes. In general, the n-cube has 2n distinct subgraphs which are (n-1)-cubes.
Let v_i be the ith of the 2^k vertices of a k-cube C. Exactly k of the n coordinates of v_i have the same value in all the other vertices v_j, i!=j. Thus a k-cube C can be denoted as the conjunction
The state of this applet window is controlled by the selection highlighted in the tools list (lower left). "Get Started" instructions for the selected tool appear in the message window (upper right). For the selected tool, lists of pertinent data items appear in the drop down choice list (middle left). The degree of learning interactivity is entered under the name field. Depending on the tools selection, additional text boxes may appear in the drawing window (lower right). Depending on the tool selection, "special action" buttons appear on the bottom of the window. selected contains 2 input text fields at the bottom, the upper being for specifying the SOP, and the lower for specifying a cube for display. The applet window shall also contain an output field at the top in which the cost function for the specified SOP will be displayed. The specified cube and SOP are painted onto the applet screen.
The applet window whall also have 5 "state toggle control" buttons, EXPAND, REDUCE, REDUNDANT CUBE, REMOVE REDUNDANT, and ESSENTIAL PRIMES. These buttons are stacked vertically on the right of the screen, in the indicated order.
In addition to typing a cube in the text window, Cube selection is done by the usual mouse manipulation. The selected cube is displayed by formula in the ouput text window. Selected cubes may be expanded, or reduced by similar mouse manipulation.
When the mouse is down, an orange highlight is put on the closest (Euclidian distance on the applet screen) minterm. The orange remains when the mouse goes up. At this point a minterm cube is "quasi-permanently" selected.
When a function is already displayed, only minterms of the given SOP may be thus selected
Once a cube has been quasi-permanently selected, a larger cube can be thus selected by similarly clicking on adjacent minterms. Minterms which are both in the cover and adjacent to one of minterms of the already quasi-permanently selected cube will be highlighted by mouse proximity (and ONLY such minterms). Not just the newly selected minterm, but all minterms of the cube or subcube of the given SOP which contains the new minterm as well as the already temporarily selected cube are thus highlighted. This new cube stays temporarily selected while the mouse is down. This selection may be changed by moving the mouse back to a minterm of the previously selected cube and then to a different minterm.
When the mouse goes up on a new minterm, the highlighted, larger cube, which has twice as many minterms as the previously selected cube, is now quasi-permanently selected. However, pressing the BACKSPACE key returns the quasi-permanent selection to its previous state.
For a non-trivial n-variable Boolean function, this process can be repeated up to n-1 times. Thus for n<7, at most 5 clicks are possible. Typically, however, on or two clicks should be sufficient.
Ultimately, a cube of the existing SOP will thus be selected. Then, the user should press the ENTER key, and the cube becomes permanently selected. If ENTER is depressed prior to full selection of an existing SOP cube, the message "Select another minterm" will be displayed.
This selection mechanism is restricted to cubes of the existing SOP.
The applet screen will contain EXPAND, REDUCE, and IRREDUNDANT toggle
buttons. Cube expansion is accomplished by the
above cube selection mechanism in concert with the
EXPAND button. When the EXPAND button is in its ON state, this
selection mechanism will be automatically extended to select any cube
which has the property that each of its minterms are in
If a temporarily selected minterm corresponds to an illegal selection, an alarm will sound, and the OFF-set minterm preventing expansion will be highlighted with a large red dot.
A legally expanded cube will be highlighted in black until the ENTER key is pressed. After this keyboard event, the highlight changes to orange, signifying that the permanently selected cube has been added to the existing cover.
When the EXPAND button is toggled to its ON state, the REDUCE and IRREDUNDANT buttons are toggled to their OFF state (only one of the three buttons may be in the ON state at any given time).
When the REDUCE button is in its ON state, the cube selection mechanism works in a manner opposite to that for expansion. A cube of the existing SOP is selected as described in section on cube selection. That is, when the mouse comes up and the ENTER key depressed, a cube of the existing cover is highlighted orange. Internally, the ifSelected switch is set to true.
In this state, any pair (m1,m2) of minterms of the selected cube may be selected by drag and drop (in the indicated order) for reduction. Minterms m1 and m2 will be highlighted in black.
The selected cube will be reduced "from m1 to m2". This means that if the mouse is lifted, the selected cube will be reduced to the unique subcube of the previously selected cube which contains m2 but not m1. Note this reduced cube will contain exactly half the number of minterms of the originally selected cube. Thus for non-trivial original cubes, at most (n-1) reductions are possible.
This process may be repeated as in expansion until the ENTER key is pressed. At this point the originally selected cube will be replaced in the current SOP by the reduced cube, and all highlighting will be removed. Thus the original cube is replaced by the chosen reduced cube.
A special case arises when a cube has been reduced to a single minterm In this case two minterms can not be selected, so the ENTER key may be depressed with just this one minterm highlighted in black. If this minterm is contained in any cube of the SOP except the currently selected one (orange highlight), then no minterms will be highlighted in black.
Thus it is possible for the reduced cube to be empty. That is, if the cube selected for reduction has no minterms which are not contained in some other cube of the cover, the ENTER keyboard event deletes it. In this case, the selected cube is replaced by the empty cube
Suppose a cube of the existing SOP is selected as described in section on cube selection. That is, when the mouse comes up and the ENTER key depressed, a cube of the existing cover is highlighted orange. If the IRREDUNDANT button is clicked ON in this state, the highlight will change to red if the cube is redundant, and if the ENTER key is then presses, the selected cube is removed from the cover.
If the REMOVE REDUNDANT button is pressed in any state, the redundant cubes will be removed from the current SOP, and the cost function updated in the output window. See Redundant Cube Removal.
If the ESSENTIAL PRIMES button is pressed in any state, the Essential Primes will be highlighted with pink centers as follows. First, the least (in ascending lexicographical order) is highlighted. Hitting the PAGEUP key selects the next largest lexicographically for highlighting. Similarly, PAGEDOWN selects the next largest lexicographically for highlighting. Wraparound is used for continuous scrolling of the essential primes, if any.