Lawrence J. Thaden
Registered: Jan 2004
Posts: 350 |
Venn Diagrams for Signed Boolean Logic
Venn diagrams are useful in the study of cellular automata. They facilitate understanding how the individual digits (minterms) of the digit expansion of a rule number contribute to the behavior of a particular cellular automaton.
For example, in a post on this Forum I demonstrated by means of a Venn diagram why ECA rule 110 only occupies the left half of its ArrayPlot.
That was an example of the usefulness of Venn diagrams for analysis of the ECAs.
What about employing Venn diagrams when analyzing cellular automata that have more than just the two colors that ECAs have?
Why Never Before
I looked around trying to find a Venn diagram appropriate to three color rules, but all I found is Venn diagrams that increase the number of variables without increasing the number of possible states or colors.
So I decided to construct one myself. It is a Venn diagram for three colored rules with three variables. The logic behind this Venn diagram is the signed Boolean logic that I have been posting about.
First, I asked myself why nobody has ever published a Venn diagram for signed Boolean logic.
Maybe the answer to that question would set me in the right direction to discover how it might be done.
A Clue
I reasoned it might have to do with the number of digits in the digit expansion for three color rules. If you use three variables, the number of digits is 27.
Compared to two state Venn diagrams that have three variables, that is a lot of digits. The two state Venn diagrams have just 8 digits. Since each digit occupies a plot region, two state Venn diagrams for three variables have just eight plot regions. To construct a Venn diagram for signed Boolean with the same design as a two state model would mean having 27 plot regions.
It might be that others have thought that, while the ECA rules nicely represent all 256 possibilities with three intersecting circles having just 8 plot regions, to represent the 7.6 trillion possibilities with 27 plot regions would only produce a diagram more confusing than it’s worth.
Not So Different
However, since it is only the variables that are being represented by the Venn diagram circles, and since signed Boolean has three variables just as the ECAs do, it is possible to represent the 7.6 trillion rules with the same three intersecting triangles as employed by the ECAs.
Of course there are other factors than the number of variables to be accounted for. Let us consider each of these.
Factor I: Signs
In signed Boolean there are plus and minus variables, whereas the ECAs only have absolute variables. How are signs to be represented within the plot regions?
Let each plot region include all minterms that fit the definition of that plot region regardless of the variable sign. Then use a checkmark to indicate which minterms are included as indicated by the digit list. (If the digit list has a 0, the checkmark is not included.)
For example, the plot region representing the intersection of the three variables contains eight minterms. They are:
(-p) AND (-q) AND (-r)
(-p) AND (-q) AND (r)
(-p) AND (q) AND (-r)
(-p) AND (q) AND (r)
(p) AND (-q) AND (-r)
(p) AND (-q) AND (r)
(p) AND (q) AND (-r)
(p) AND (q) AND (r)
If any of these minterms is associated with a non-zero digit in the digit list, it is preceded in its plot region with a checkmark.
An Aside
Incidentally, these eight minterms, in turn, could be represented in their own three-circle Venn diagram. At this next level, the colored plot regions would represent which minterms have a checkmark. (See Figure 2.)
Also, notice that the positively signed variables in the plot regions at this next level belong to the background. This arrangement promotes the idea that signed Boolean supports a fabric of space, somehow woven, such that negatively signed variables appear in the foreground and positively signed variables in the background. Alternately, this idea could be represented by a fabric of space having two sides, a front side and back side.
I have not included this second level feature in this Venn diagram for signed Boolean logic. But to do so, all is needed is a button in each plot region that takes you to a new window showing the second level for that plot region.
Continuing with the original Venn diagram analysis, let the intersection of any two variables include four minterms. Then these plot regions will have a second level diagram with two intersecting circles and a background with the positively signed variables ANDed with the NOT-variable.
Next, let the region that exclusively represents just one variable include two minterms. The second level diagram for these will have a single circle and a background with the positively signed variable ANDed with both of the other two NOT-variables.
Finally, let the background, which contains no variables, include a single minterm. It will not have a second level diagram.
Factor II: Complements
But what is to be said about conventions for expressing the complement of a variable? Since there are two kinds of complements in signed Boolean, one might be lead to believe that it would require twice as many expressions to accommodate all of the possibilities.
However, it turns out that both complements act the same when combined with the other variables in the minterms. It is as though complements are absolute-valued. So instead of having (-1 - p) along with (-1 + p) for representing the two kinds of complements, it is only necessary to include one representation. By convention, let this be (-1 + p) and read it as Not-p.
Factor III: Coefficients
There is one final feature that needs to be addressed. In the ECAs, if a minterm is to be included it has an implied coefficient of 1. If it is to be excluded it has an implied coefficient of 0. As stated above, in signed Boolean excluded coefficients are not preceded in their plot region with a checkmark.
But minterms with coefficients (+1) and (-1) have both a checkmark and explicitly shown coefficients. This specification indicates that a modulo 3 product operation is to be performed in order to arrive at the full expression.
To represent the coefficients properly would require a pair of disjoint Venn diagrams, since (+1) and (-1) digits of the digit expansion are mutually exclusive. I have not included this as a feature in this Venn diagram for signed Boolean logic.
Example
Attached Figure 1 shows a Venn diagram for signed Boolean rule number 2970263127. The numbers in parentheses are the minterm locations counting 26 through 0, from left to right. These locations are also the powers of the base 3 that indicate the place values.
Notice that place value locations (18) and (9) both have checkmarks, but the minterm at location (18) has a positive coefficient (+1) while that at location (9) has a negative coefficient (-1). Since both are check marked, both forms of p, (+p) and (-p), are included with (Not-q And Not-r). This plot region is colored blue.
Similarly, both (1) (+r) and (2) (-r) have positive coefficients and are are included with (Not-p And Not-q). This plot region is colored yellow.
But (19) (-1) (-p) And Not-q And (r) is the only minterm for its plot region which is colored green.
And, likewise, (17) (-1) (p) And (-q) And (-r) is the only minterm for its plot region which is colored purple.
Information for the digit list and place value location numbers is repeated beneath the Venn diagram.
The rule number is located in the upper left hand corner of the diagram.
CDF File
In the reply to this post there is a CDF file attached that combines features of the notebook, MakeRule, posted previously, along with the Venn diagram presented here.
This CDF file has a TabView construct. It allows you to make any rule from the 7.6 trillion rules by selecting minterms within the tab, Make Rule. This tab also shows you the cellular automaton for the rule as run with simple initial conditions. Then you can select a second tab, View Venn Diagram, which displays the Venn diagram for that rule.
One advantage to having the two tabs in a single CDF file is that you can easily see which rule is the most efficient rule when run under simple initial conditions. A rule is more efficient if it takes fewer minterms than another rule to produce the same cellular automaton.
In the above example for rule number 2970263127, for instance, if minterm at location (8) with either a positive or negative coefficient, is included, the behavior of the cellular automaton is not changed. Of course the rule number changes to 2970269688 with the positive coefficient and to 2970276249 with the negative coefficient.
But adding these minterms and coefficients does not change the behavior of the cellular automaton, it just adds to the inefficiency of the cellular automaton since more work (computation) has to be done to generate the same result.
However, if you ran these three rule numbers with the CellularAutomaton command and the same random initial conditions, you would observe different behaviors. In this case the extra work (computation) is well spent since it generates a different result.
Note on Running the CDF File
When you start the file, you will be required to “enter dynamics”.
If on the first time you make a rule and then view the Venn diagram, the Venn diagram is still the initial default one, just return to Make Rule and one again select the View Venn Diagram tab. Then it will appear correctly.
Lawrence J. Thaden has attached this image:
__________________
L. J. Thaden
Report this post to a moderator | IP: Logged
|
06-04-2012 12:30 PM
Attachment: 
