[Reflections] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Reflections
(Click here to view the original thread with full colors/images)
Posted by: Lawrence J. Thaden
This post presents a way to find pairs of three color rule numbers that generate cellular automata with graphs that are left-right reflections of each other.
An inspection of the rules on page 883 of the NKS book and their expressions listed on page 884 show a definite pattern. For example, rules 2 and 16 have these expressions: 2:
And[Not[p], Not[q], r] and 16: And[p, Not[q], Not[r]. The graphs for these rules found on page 55 show opposing diagonal lines. They are left-right vertical reflections of each other. Notice that the expressions are very much alike. The only difference is where the Not operator is with reference to the operands p and r. Rule 2 has the Not operator applied to the variable p and rule 16 has it applied to variable r. It is this arrangement that makes the two rules produce cellular automaton graphs that are left-right reflections of each other.
Similar analysis of remaining rule pairs shows various arrangements of p and r complemented and not complemented in this way. Sometimes this goes on within the place occupied by one of the three operands in the model: {operation, operand p, operand q, operand r}. For example, in rules 110 and 124 operands p and r are themselves operations, and it is within these that the complementation takes place. So rule 110: Xor[And[Not[p], q, r], q, r] has an And operation for operand p. It is within this operation that complementation is applied to p so that it is Not[p]. Contrast this with rule 124: Xor[p, q, And[p, q, Not[r]] where the complementation is applied to r within operand r which is actually an And operation.
What about three color rules. How can pairs be found that generate graphs with left-right vertical reflection?
Finding pairs in traditional Boolean logic presents no difficulty because Wolfram has listed all the expressions on page 884. But the three valued rules present a dilemma since there are so many of them. Where do we go to find a list of expressions for all 7625597484987 three valued rules? Even if one were readily accessible, it would be unwieldy because of its volume.
The method proposed here is to identify certain primitive expressions that can be used to construct expressions representing likely candidates for rules that can then be tried out using the CellularAutomaton command. Then by inspecting the graphs as well as comparing the output data we can establish whether a pair of expressions and their rules generate left-right reflections.
This can be accomplished without the need to identify all the trillions of expressions in three valued Boolean logic. And this method has the added advantage that we actually know what logic expressions cause a rule to be going to the left or right. Something that obviously is not available by merely inserting some totalistic numbers in the CellularAutomaton command.
So let’s began by identifying the rule numbers for primitives in three valued Boolean logic, assigning them symbolic expressions.
As a starting point we can rely on Wolfram’s work, for this logic is an extension of two valued Boolean logic, the basis for expressions of rules listed on page 884 of the NKS book.
Prominent features of this extension are as follows. Whereas traditional Boolean values are {0, 1}, here they are {0, 1, 2} with {2} acting logically as {-1}. The {0} covers additive identity, but the multiplicative identity splits into positive and negative identity.
Also, the minterms are products of variables having three states. For example, the variable p is present as (p), (1 + p), and (- 1 - p).
The last form corresponds to Boolean Not[p] and is related to negative multiplicative identity: p + (- 1 - p) = (- 1).
The middle form is the new one, being related to the positive multiplicative identity: (- p) + (1 + p) = 1.
Although unconventional, I am avoiding the use of the Not operator so as to present a more algebraic symbolism.
When more than one minterm occurs in an expression, the minterms are summed modulo 3. This differs from traditional Boolean systems in which the minterms are ORed.
One other difference occurs when the coefficient is 2 rather than 0 or 1. The coefficient 2 acts as a (- 1) and is taken with the minterm to form a modulo 3 product.
The minterms are as they are in two valued Boolean logic, expressions composed of And together with the variables p, q, and r and their various forms. Minterm rule numbers are the list in descending order of the powers of three starting with 3^26 and ending with 3^0.
This use of And to form the minterms is characteristic of an arrangement of the list of all expressions in conjunctive normal form. An alternative arrangement which uses Or is called disjunctive normal form. We follow the conjunctive normal form arrangement. Then Or is derived from And by reflective complementation in which the digits of the And rule are reversed while zeroes and ones are interchanged.
Xor is modulo 3 sum. This is similar to two valued Boolean logic where Xor is modulo 2 sum. However the counterpart, modulo 3 product, is a unique operation. Whereas modulo 2 product is identical to And in two value Boolean logic, modulo 3 product bears no resemblance to And in this logic, other than the fact that both are commutative operations.
There is also an operation for modulo 3 difference. In two valued Boolean logic modulo 2 difference is the same as Or, and it is a commutative operation. But in three valued Boolean logic Or and modulo 3 difference are distinct operations. As expected, Or is commutative, whereas modulo 3 difference is not.
Correction: It is Xor that is equivalent to modulo 2 difference, not Or. (May 11, 2006)
Inverses:
There are three sets of inverse pairs:
(0 - p) + p = 0
(1 - Not[p]) + Not[p] = 1
(-1 - (1 + p)) + (1 + p) = (- 1)
The first is the additive inverse pair (- p) and p. It has a non-linear distribution. (See figure 1a.)
The second associates the lattice complements with positive multiplicative identity. We prefer to write it in modulo 3 form as: (1 - (- 1 - p)) + (-1 - p) = 1. The distribution of these pairs is non-linear and diagonally flipped with respect to the distribution of the additive inverses. (See figure 1b.)
The third associates the new term, used in the minterm expressions, with negative multiplicative identity. The distribution of these pairs is linear descending.
Notice that there is no division. Multiplication splits into positive and negative and each is its own multiplicative inverse. The distribution of both positive and negative inverse pairs for modulo 3 product is the same: non-linear and diagonally flipped with respect to the distribution of the additive inverses. It is also skewed to the upper left. (No figure shown.)
Relations <, =, and >:
There are no rule numbers defining these relations. However, two expressions are equal when they have the same rule number. As for the relations less than and greater than, they are defined with reference to the place held by a rule number in the canonical list of normal forms. That is, when a rule number has a greater integer value than another rule number the expression of the former is said to be greater than the latter. This is similar to traditional Boolean logic. Note, for example, the order of logic expressions listed on page 884 of the NKS book: (240: p) > (204: q) > (170: r) > (85: Not[r]) > (51: Not[q]) > (15: Not[p]).
Here is the list of primitives together with their rule numbers. All 7625597484987 logic expressions in this system can be constructed using these primitives and the mapping function. Needless to say, this notebook limits identification to a small fraction of the total.
Identities: There are three distinct identities: 1 for addition and 2 for multiplication. They correspond to the three values in the logic: 0, 1, and 2, where 2 acts algebraically as modulo 3 (-1). Additive identity has a 0 digit in every position of its base three rule number expansion. Positive multiplicative identity has a 1 digit. And negative multiplicative identity a 2 digit.
Additive identity: 0
Positive multiplicative identity (1): 3812798742493
Negative multiplicative identity (-1): 7625597484986
Addition: Addition is done modulo 3 sum. This is the operation Xor.
Modulo 3 sum with three operands (p + q + r): 2201243116917
Modulo 3 sum with two operands (p + q): 3681670999617
Modulo 3 sum with two operands (p + r): 3226154728017
Modulo 3 sum with two operands (q + r): 3188245183617
Other forms of modulo 3 sum (Xor) in three variables are:
Nxor[p, q, r] written modulo 3 as (- 1 - (p + q + r)): 5424354368069
(1 + (p + q + r)): 3188195038717
(- 1 + (p + q + r)): 6048958071845
(- (p + q + r)): 1576639413141
(1 - (p + q + r)): 4437402446269
Other forms of modulo 3 sum (Xor) in two variables are:
(p + q)
(- 1 - (p + q)): 3943926485369 (Lattice complement form of (Xor[p, q]).)
(1 + (p + q)): 7479339588409
(- 1 + (p + q)): 277385639453
(- (p + q)): 7348211845533
(1 - (p + q)): 146257896577
(p + r)
(- 1 - (p + r)): 4399442756969 (Lattice complement form of (Xor[p, r]).)
(1 + (p + r)): 6158987419273
(- 1 + (p + r)): 2053254080189
(- (p + r)): 5572343404797
(1 - (p + r)): 1466610065713
(q + r)
(- 1 - (q + r)): 4437352301369 (Lattice complement form of (Xor[q, r]).)
(1 + (q + r)): 6049103421049
(- 1 + (q + r)): 2201047622813
(- (q + r)): 5424549862173
(1 - (q + r)): 1576494063937
Difference: There is a modulo 3 difference. Since it is not commutative, there are more forms. However, many are equivalent to each other.
Modulo 3 difference with three operands (p - q - r) = (p - r - q): 4437206964645
Modulo 3 difference with three operands (q - r - p) = (q - p - r): 4296386505957
Modulo 3 difference with three operands (r - p - q) = (r - q - p): 3329409531045
Other forms of modulo 3 difference in three variables are:
(-1 - (p - q - r)): 1576689562877 (Lattice complement form of (p - q - r).)
(1 + (p - q - r)): 5424499699957
(-1 + (p - q - r)): 1576689562877 (Same as lattice complement form.)
(- (p - q - r)): 6048907922109
(1 - (p - q - r)): 2201097785029
(-1 - (q - r - p)): 1616923979645 (Lattice complement form of (q - r - p).)
(1 + (q - r - p)): 5525085741877
(-1 + (q - r - p)): 1616923979645 (Same as lattice complement form.)
(- (q - r - p)): 6008673505341
(1 - (q - r - p)): 2100511743109
(-1 - (r - p - q)): 2100375622397 (Lattice complement form of (r - p - q).)
(1 + (r - p - q)): 6008611074037
(-1 + (r - p - q)): 2100375622397 (Same as lattice complement form.)
(- (r - p - q)): 5525221862589
(1 - (r - p - q)): 1616986410949
Modulo 3 difference with two operands (p - q) = (- (q - p)): 146430861993
Modulo 3 difference with two operands (q - p) = (- (p - q)): 277192716489
Modulo 3 difference with two operands (p - r) = (- (r - p)): 1466669662809
Modulo 3 difference with two operands (r - p) = (- (p - r)): 2053105087449
Modulo 3 difference with two operands (q - r) = (- (r - q)): 1616787841929
Modulo 3 difference with two operands (r - q) = (- (q - r)): 2100313177833
Other forms of modulo 3 difference in two variables are:
(p - q) and (q - p)
(-1 - (p - q)) = (-1 + (q - p)): 7479166622993
(1 + (p - q)) = (1 - (q - p)): 3943560596989
(-1 + (p - q)) = (-1 - (q - p)): 7348404768497
(1 - (p - q)) = (1 + (q - p)): 3682036887997
(p - r) and (r - p)
(-1 - (p - r)) = (-1 + (r - p)): 6158927822177
(1 + (p - r)) = (1 - (r - p)): 4399234167133
(-1 + (p - r)) = (-1 - (r - p)): 5572492397537
(1 - (p - r)) = (1 + (r - p)): 3226363317853
(q - r) and (r - q)
(-1 - (q - r)) = (-1 + (r - q)): 6008809643057
(1 + (q - r)) = (1 - (r - q)): 4296324078397
(-1 + (q - r)) = (-1 - (r - q)): 5525284307153
(1 - (q - r)) = (1 + (r - q)): 3329273406589
Multiplication is modulo 3 product.
Modulo 3 product with three operands (p q r): 6088151958012
Modulo 3 product with two operands (p q): 3943933137846
Modulo 3 product with two operands (p r): 4399472553246
Modulo 3 product with two operands (q r): 4456336869846
Other forms for modulo 3 product in three variables are:
Not[(p q r)] written modulo 3 as (- 1 - (p q r)): 1537445526974
(1 + (p q r)): 2181066547621
(- 1 + (p q r)): 3169177721846
(- (p q r)): 4456419763140
(1 - (p q r)): 5444530937365
Other forms of modulo 3 product in two variables are:
(p q)
(-1 - (p q)): 3681664347140 (Lattice complement form of (p q).)
(1 + (p q)): 7348218498049
(-1 + (p q)): 146244591584
(- (p q)): 7479352893402
(1 - (p q)): 277378986937
(p r)
(-1 - (p r)): 3226124931740 (Lattice complement form of (p r).)
(1 + (p r)): 5572373203345
(-1 + (p r)): 1466550470888
(- (p r)): 6159047014098
(1 - (p r)): 2053224281641
(q r)
(-1 - (q r)): 3169260615140 (Lattice complement form of (q r).)
(1 + (q r)): 5444696751169
(-1 + (q r)): 1537362606464
(- (q r)): 6088234878522
(1 - (q r)): 2180900733817
And[p, q, r]: 2541865828329
And[p, q]: 3671583974253
And[p, r]: 2639495791557
And[q, r]: 2541994975053
Other forms of And in three variables are:
Nand[p, q, r] written modulo 3 as (-1 - (And[p, q, r])): 5083731656657
(1 + (And[p, q, r])): 6354664570822
(- 1 + (And[p, q, r])): 2541865828328
(- (And[p, q, r])): 5083731656658
(1 - (And[p, q, r])): 1270932914164
Other forms of And in two variables are:
And[p, q]
(-1 - (And[p, q])): 3954013510733 (Lattice complement form of (And[p, q]).)
(1 + (And[p, q])): 7484382716746
(-1 + (And[p, q])): 282429536480
(- (And[p, q])): 7343167948506
(1 - (And[p, q])): 141214768240
And[p, r]
(-1 - (And[p, r])): 4986101693429 (Lattice complement form of (And[p, r]).)
(1 + (And[p, r])): 6452294534050
(-1 + (And[p, r])): 2346605901872
(- (And[p, r])): 5278991583114
(1 - (And[p, r])): 1173302950936
And[q, r]
(-1 - (And[q, r])): 5083602509933 (Lattice complement form of (And[q, r]).)
(1 + (And[q, r])): 6354793717546
(-1 + (And[q, r])): 2541607534880
(- (And[q, r])): 5083989950106
(1 - (And[q, r])): 1270803767440
Or[p, q, r]: 7625597484985
Or[p, q]: 3812798742480
Or[p, r]: 3812798741736
Or[q, r]: 3812411302320
Other forms of Or in three variables are:
Nor[p, q, r] written modulo 3 as (-1 - (Or[p, q, r])): 1
(1 + (Or[p, q, r])): 2
(- 1 + (Or[p, q, r])): 3812798742492
(- (Or[p, q, r])): 3812798742494
(1 - (Or[p, q, r])): 7625597484984
Other forms of Or in two variables are:
Or[p, q]
(-1 - (Or[p, q])): 3812798742506 (Lattice complement form of (Or[p, q]).)
(1 + (Or[p, q])): 7625597484973
(-1 + (Or[p, q])): 26
(- (Or[p, q])): 7625597484960
(1 - (Or[p, q])): 13
Or[p, r]
(-1 - (Or[p, r]])): 3812798743250 (Lattice complement form of (Or[p, r]).)
(1 + (Or[p, r])): 7625597484229
(-1 + (Or[p, r])): 1514
(- (Or[p, r])): 7625597483472
(1 - (Or[p, r])): 757
Or[q, r]
(-1 - (Or[q, r])): 3813186182666 (Lattice complement form of (Or[q, r]).)
(1 + (Or[q, r])): 7625210044813
(-1 + (Or[q, r])): 774880346
(- (Or[q, r])): 7624822604640
(1 - (Or[q, r])): 387440173
There are six forms for each of the three variables.
The first three are the ones that occur in the minterms.
The last three are complements of these with respect to positive multiplicative identity.
p: 7625403764901
(1 + p): 387410647
Not[p] written modulo 3 as (- 1 - p): 193720085
(1 - p): 7625210074339
(- p): 3812992433055
(- 1 + p): 3812605051931
q: 7479532539765
(1 + q): 277019723695
Not[q] written modulo 3 as (- 1 - q): 146064945221
(1 - q): 7348577761291
(- q): 3943753520967
(- 1 + q): 3681843964019
r: 6159136430181
(1 + r): 2053045476727
Not[r] written modulo 3 as (- 1 - r): 1466461054805
(1 - r): 5572552008259
(- r): 4399383164415
(- 1 + r): 3226214320571
Notice the additive inverse rule number pairs:
p: 7625403764901
(- p): 3812992433055
q: 7479532539765
(- q): 3943753520967
r: 6159136430181
(- r): 4399383164415
Consistent with what was pointed out above about the order of lattice complement expressions in traditional Boolean logic, the positives are descending and the negatives are ascending.
Now pairs, the second of which is a lattice complement rule number:
(- 1 + p): 3812605051931
(- 1 - p): 193720085
(- 1 + q): 3681843964019
(- 1 - q): 146064945221
(- 1 + r): 3226214320571
(- 1 - r): 1466461054805
The lattice complements are ascending and the others are descending.
Finally, the remaining pairs:
(1 + p): 387410647
(1 - p): 7625210074339
(1 + q): 277019723695
(1 - q): 7348577761291
(1 + r): 2053045476727
(1 - r): 5572552008259
Positives are ascending and negatives descending.
By means of the substitution principle, we can partition the entire space into these three sets of selected pairs.
When graphed the first and second sets resemble a nested set of triangles, emphasizing the non-linear nature of canonical order in Boolean logic. See figures (1a) and (1b).
But the third set presents a linear descending behavior.
Here are the minterm expressions and rule numbers:
And[p, q, r]: 2541865828329
And[p, q, (r + 1)]: 847288609443
And[p, q, (- 1 - r)]: 282429536481
And[p, (q + 1), r]: 94143178827
And[p, (q +1), (r + 1)]: 31381059609
And[p, (q + 1), (- 1 - r)]: 10460353203
And[p, (- 1 - q), r]: 3486784401
And[p, (- 1 - q), (r + 1)]: 1162261467
And[p, (- 1 - q), (- 1 - r)]: 387420489
And[(p + 1), q, r]: 129140163
And[(p + 1), q, (r + 1)]: 43046721
And[(p + 1), q, (- 1 - r)]: 14348907
And[(p + 1), (q + 1), r]: 4782969
And[(p + 1), (q +1), (r + 1)]: 1594323
And[(p + 1), (q + 1), (- 1 - r)]: 531441
And[(p + 1), (- 1 - q), r]: 177147
And[(p + 1), (- 1 - q), (r + 1)]: 59049
And[(p + 1), (- 1 - q), (- 1 - r)]: 19683
And[(- 1 - p), q, r]: 6561
And[(- 1 - p), q, (r + 1)]: 2187
And[(- 1 - p), q, (- 1 - r)]: 729
And[(- 1 - p), (q + 1), r]: 243
And[(- 1 - p), (q +1), (r + 1)]: 81
And[(- 1 - p), (q + 1), (- 1 - r)]: 27
And[(- 1 - p), (- 1 - q), r]: 9
And[(- 1 - p), (- 1 - q), (r + 1)]: 3
And[(- 1 - p), (- 1 - q), (- 1 - r)]: 1
Page 884 of the NKS book gives a list of all of the expressions for two valued, three variable Boolean logic. However, it is not feasible to list all of the expressions for this system since there are 7625597484987. But an expression for a given rule number can be listed by finding the modulo 3 sum of the modulo 3 products of its coefficients and minterms.
The coefficients are the digits of the base three expansion of a rule number. Here is the Mathematica code used to generate a sum of products expression for any given rule number.
Apply[Plus, DeleteCases[IntegerDigits[anygivenrule, 3, 27] minterms, 0] /.{2 -> -1}], where minterms is a list of all the minterm expressions.
The expression is in canonical form and must then be simplified manually.
Combinations of these primitive symbolic expressions identified above can be input to a mapping function. And with certain combinations, this mapping function identifies pairs of rule numbers that generate left-right reflection cellular automata. Here is the mapping function:
map[operation_, operand1_, operand2_, operand3_] : =
FromDigits[Reverse[IntegerDigits[operation, 3, 27]] [[ Dot[MapThread[List, {IntegerDigits[operand3, 3, 27], IntegerDigits[operand2, 3, 27], IntegerDigits[operand1, 3, 27]}], {3 ^0, 3 ^1, 3 ^2}] + 1 ]], 3]
Note: When using the mapping function with any two variable operation such as (p + q), that is Xor[p, q], the unused operand is a don’t care. It can have any value. Likewise, when with any single variable operation such as (- 1 - p), that is Not[p]; the unused operands are don’t cares.
How it works:
The best way to introduce this method of arranging primitive expressions as input to the mapping function is to use an example.
Say we want to find the rule numbers to reflect these expressions:
On the left side: (p + q)[(1 + (p q)), q, (don’t care)]
On the right side: (p + q)[(1 + (q r)), q, (don’t care)]
Simply fill in the operation for both left and right hand side map expressions with the expression: (p + q).
Then fill in the operands on the left side with the three expressions: (1 + (p q)), q, and (don’t care).
Note that the first expression, (1 + (p q)), is itself a compound operation: (p + q)[1, (p q)]. However, since it was already assigned a rule number in the discussion above on modulo 3 product in two variables, there is no need to encode it at this time.
The second operand is q and the third operand is a don’t care. Don’t care because the operation only requires entries for p and q. Since r is not required we don’t care what is in the third operand.
Fill in the operands on the right side with the three expressions: (1 + (q r)), q, and (don’t care).
Note that the first expression, (1 + (q r)) is slightly different from the first expression on the left side.
Then the mapping functions look like this:
Left side: map[(p + q), (1 + (p q)), q, (don’t care)].
Right side: map[(p + q), (1 + (q r)), q, (don’t care)].
The mapping function returns rule numbers:
Left side: 3812978360425
Right side: 4356764745385
These rules are then input into the CellularAutomaton command and generate data as rendered in figure 2a. The CellularAutomaton commands for left and right sides look like this:
CellularAutomaton[3812978360425, 3, {{-1}, {0}, {1}}, {{2}, 0}, 128]
CellularAutomaton[4356764745385, 3, {{-1}, {0}, {1}}, {{2}, 0}, 128]
A slight change to the first operands generates the graphs in figure 2b.
It might appear quite daunting at first. But it really does not require much familiarity with the logic expressions. Just move the expressions around a bit like pieces of a jig saw puzzle.
Not only is it easy to discover left-right behavior. But you actually know what combinations of logic expressions generate that behavior.
Here are some clues to cut down trial and error time.
Balance the outside operands: If the left side has an expression in the first operand, put it in the third operand on the right side.
Use complementary operands: If the left side has an expression in the first operand, put a complementary expression in the third operand on the right side.
Try using complementary operations: For example, if the left side has (p - q - r), make the right side (r - p - q). I tried this with left side operands: (1 - (p q r)), q, r and right side operands: p, q, (1 - (p q r)). (See figure 3.)
A word of caution: Not every combination works. It takes some understanding and a little acquired skill to arrange a successful set of primitives.
Sometimes you might find a pair that looks similar, but on inspection is not a match. One example of this is figure 4.
In conclusion:
There is a sequel to Wolfram’s mantra that simple programs can produce complex behavior:
A very small addition to a simple program can introduce explosive complexity.
The addition of a single digit value has a huge impact on the traditional system of Boolean logic. Not only from the standpoint of sheer volume of expressions, but also with respect to the emergence of new operators.
Consider how modulo 2 product is identical to And in two valued Boolean logic and modulo 2 difference is identical to Or.
Correction: It is Xor that is equivalent to modulo 2 difference, not Or. (May 11, 2006)
Now contrast how they emerge differentiated in three valued Boolean logic and spawn a whole host of additional expressions.
Similarly, multiplicative identity differentiates, introducing another realm of behavior with its positive and negative sides.
For example, take the behavior of additive inverses distributed over the entire space. We saw in figure (1a) that the distribution forms a non-linear, yet homogeneous nested pattern of corner points for triangles. One consequence of this is the futility of expecting the negative of an expression to have a rule number less than the positive version of the expression.
Nevertheless, for all of this new and unfamiliar behavior, the huge space of three valued Boolean logic is understandable. And this method of establishing primitives and using the mapping function defined here provides a first step in that direction.
Posted by: Lawrence J. Thaden
Those familiar with traditional Boolean logic are well aware of the idempotent property for bitwise And and bitwise Or:
And[p, p] -> p
Or[p, p] -> p
The operators for And and Or on page 884 of the NKS book are bitwise operators.
The way bitwise operators work can be illustrated with minterm rule 128: And[p, q, r].
Bitwise this is a product of the base 2 representations of rule numbers for p, q, and r:
(IntegerDigits[240, 2, 8] IntegerDigits[204, 2, 8] IntegerDigits[170, 2, 8]) == IntegerDigits[128, 2, 8]
When the three operands are all the same, the idempotent result occurs.
Here is And[p, p, p], where p is rule 240:
(IntegerDigits[240, 2, 8] IntegerDigits[240, 2, 8] IntegerDigits[240, 2, 8] ) == IntegerDigits[240, 2, 8]
However, in the three valued extension to Boolean logic, the bitwise And operator is not used to form the minterms.
In three valued Boolean logic the And operator for the minterm And[p, q, r] is defined by the rule number that has a single 1 digit in the leftmost position of its base three expansion. This is rule number: 2541865828329, as noted in the post at the top of this thread.
IntegerDigits[2541865828329, 3, 27]:
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
This is consistent with the way the And operator is fixed in slot 128 of the canonical forms on page 884 of the NKS book.
IntegerDigits[128, 2, 8]:
{1,0,0,0,0,0,0,0}
What then about the bitwise operators in three valued Boolean logic? They are all there. Only they do not play the central role that they do in traditional Boolean logic. Here then is the list of bitwise rule numbers for three valued Boolean logic. Notice that Xor is not included here. It has been listed previously as modulo 3 sum, a bitwise operator.
Bitwise operators for And:
bwAnd[p, q, r]: 5083733250981
bwAnd[p, q]: 7343174857239
bwAnd[p, r]: 5279036283207
bwAnd[q, r]: 5115372604119
Other forms of bwAnd in three variables are:
bwNand[p, q, r] written modulo 3 as (-1 - (bwAnd[p, q, r])): 2541864234005
(1 + (bwAnd[p, q, r])): 1270934508487
(- 1 + (bwAnd[p, q, r])): 5083728468011
(- (bwAnd[p, q, r])): 2541869016975
(1 - (bwAnd[p, q, r])): 6354662976499
Other forms of bwAnd in two variables are:
bwAnd[p, q]
(-1 - (bwAnd[p, q])): 282422627747 (Lattice complement form of (bwAnd[p, q]).)
(1 + (bwAnd[p, q])): 141221676973
(-1 + (bwAnd[p, q])): 3953999693267
(- (bwAnd[p, q])): 3671597791719
(1 - (bwAnd[p, q])): 7484375808013
bwAnd[p, r]
(-1 - (bwAnd[p, r])): 2346561201779 (Lattice complement form of (bwAnd[p, r]).)
(1 + (bwAnd[p, r])): 1173347651029
(-1 + (bwAnd[p, r])): 4986012293243
(- (bwAnd[p, r])): 2639585191743
(1 - (bwAnd[p, r])): 6452249833957
bwAnd[q, r]
(-1 - (bwAnd[q, r])): 2510224880867 (Lattice complement form of (bwAnd[q, r]).)
(1 + (bwAnd[q, r])): 1302186421453
(-1 + (bwAnd[q, r])): 5020837201907
(- (bwAnd[q, r])): 2604760283079
(1 - (bwAnd[q, r])): 6323411063533
Bitwise operators for Or:
bwOr[p, q, r]: 7625595280377
bwOr[p, q]: 7625590319997
bwOr[p, r]: 7625537881077
bwOr[q, r]: 7581816745437
Other forms of bwOr in three variables are:
bwNor[p, q, r] written modulo 3 as (-1 - (bwOr[p, q, r])): 2204609
(1 + (bwOr[p, q, r])): 4409215
(- 1 + (bwOr[p, q, r])): 3812796537887
(- (bwOr[p, q, r])): 3812800947099
(1 - (bwOr[p, q, r])): 7625593075771
Other forms of bwOr in two variables are:
bwOr[p, q]
(-1 - (bwOr[p, q])): 7164989 (Lattice complement form of (bwOr[p, q]).)
(1 + (bwOr[p, q])): 14329939
(-1 + (bwOr[p, q])): 3812791577543
(- (bwOr[p, q])): 3812805907443
(1 - (bwOr[p, q])): 7625583155047
bwOr[p, r]
(-1 - (bwOr[p, r])): 59603909 (Lattice complement form of (bwOr[p, r]).)
(1 + (bwOr[p, r])): 119205547
(-1 + (bwOr[p, r])): 3812739140855
(- (bwOr[p, r])): 3812858344131
(1 - (bwOr[p, r])): 7625478279439
bwOr[q, r]
(-1 - (bwOr[q, r])): 43780739549 (Lattice complement form of (bwOr[q, r]).)
(1 + (bwOr[q, r])): 86399158579
(-1 + (bwOr[q, r])): 3770180323463
(- (bwOr[q, r])): 3855417161523
(1 - (bwOr[q, r])): 7539198326407
.
Attached is a graphic with examples of reflections using the bitwise operators.
Posted by: Lawrence J. Thaden
One of the fundamental properties in traditional Boolean logic is the absorptive property:
And[p, Or[p, q]] = Or[p, And[p, q]] = p
What happens to absorption when expanding to three valued Boolean logic? The expressions are no longer invariant with respect to p. This is true of bitwise And and Or as well as the more general And and Or defined in the post at the top of this thread.
Some might reason, quite understandably, that we should, therefore, a priori reject this extension to traditional Boolean logic.
I urge a more thoughtful approach.
According to traditional definitions, this system of logic does not even qualify as a poset. For, while its operations of And and Or are commutative and associative, they do not have the idempotent and absorptive properties. But all four of these properties are required of posets.
And if it does not meet the requirements of posets, how could it ever be considered Boolean? For the path from posets to Boolean goes through lattices, modular lattices, and distributive lattices, each demanding additional properties.
Apparently those who over the years have refined the understanding of posets, lattices, and Boolean logic never envisioned what we have here.
For where in the literature on Boolean logic can one find a (- 1) and (+ 1) dual multiplicative identity? And how does one fit in (- 1) as the least element in the lattice when it is the last canonical form? Or even more awkwardly, how about the greatest element (+ 1) as midway in the list of canonical forms?
However, just as previous logicians had insights after considering many examples, so it is for us to consider this as new material from which we can gain new insights.
And just as they were thus able to formulate their understanding as the definitions we now take for granted, so too we can hope to formulate definitions of properties we observe in this three valued logic.
Posted by: Lawrence J. Thaden
Figure 1a above presented a representative distribution of the additive inverses (p, (-p)).
Notice that they are nested. The way that they nest is as follows.
As p ranges from 0 through its maximum, points for the pair rotate clockwise from lower left corner of a triangle to apex and then to lower right of a triangle.
Nesting levels change as the value of p takes on the next power of 3. When they change, the previous level is used as the triangle for the lower left corner and triangle building begins at the apex of the new nested level.
When the distribution is represented by an inverted triangular structure as in figure 1b, the process is counter clockwise.
Posted by: Lawrence J. Thaden
The attached graphic further illustrates the nesting property for additive inverses as presented in the previous post (See Figure 1a 10000 Random Pairs of {p, (-p)}).
Here side by side are figures representing pairs of {p, (-p)} for three, four, and five valued logic in three variables.
Notice how the number of sets of relatively opposing images increases as the base increases from three through five.
In the left hand figure the images appear to represent two sets of triangles relatively opposed to the lower left hand corner set of triangles.
In the middle figure there are three sets relatively opposed.
In the right hand figure there are four sets relatively opposed.
If you were to continue to represent pairs for higher valued logic, the number of opposing sets would increment.
Posted by: Lawrence J. Thaden
Three color rule numbers correspond to expressions that are additive inverse pairs.
But how does one determine which expression of a pair is the positive and which is the negative?
If we posit that rule 1 corresponds to a positive expression, then we can determine all of the rule numbers corresponding to positive expressions by this code:
Table[FoldList[Plus, 3^i, Table[1, {(3^i ) - 1}]], {i, 0, 26}]
But do not try it in Mathematica. The code is intended to generate trillions of integers. If you do try to do it, Mathematica will stop with a message about $IterationLimit’s value being exceeded.
However, by changing {i, 0, 26} to {i, 0, 3}, we can display this small sample of all of the rule numbers corresponding to positive expressions:
{{1},
{3, 4, 5},
{9, 10, 11, 12, 13, 14, 15, 16, 17},
{27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53}}
What the code is saying is that:
(1) There are intervals of rule numbers that are positive.
(2) The intervals always start with a rule number that is a power of 3.
(3) The number of rules in an interval is always equal to the first rule number in the interval.
(4) Rule numbers in the interval increment by 1.
(5) There are 27 intervals.
It is possible to list any part of an interval. For example the first three rule numbers in interval 20 can be listed with this code:
Table[i, {i, 3^19, (3^19) +2}]
{1162261467, 1162261468, 1162261469}
So what about the rules corresponding to the negative expressions?
All of the rule numbers corresponding to negative expressions are generated with the code:
Table[FoldList[Plus, 2 (3^i), Table[1, {(3^i ) - 1}]], {i, 0, 26}]
Again, do not try this. Instead, to illustrate this, I change “26” to an integer representing just 3 intervals.
Table[FoldList[Plus, 2 (3^i), Table[1, {(3^i ) - 1}]], {i, 0, 2}]
{{2},
{6, 7, 8},
{18, 19, 20, 21, 22, 23, 24, 25, 26}}
Note that for negative expressions intervals always start with double the value of the power of 3. And the number of rule numbers in the interval is half of the first rule number.
Given any three color rule number, code like this will determine if it corresponds to a positive or negative expression and indicate to which interval it belongs:
signQ[rn_]:= Which[
GreaterEqual[rn, 3^0] && LessEqual[rn, (2 3^0) - 1], 1,
GreaterEqual[rn, 3^1] && LessEqual[rn, (2 3^1) - 1], 2,
GreaterEqual[rn, 3^2] && LessEqual[rn, (2 3^2) - 1], 3,
… (Here belong all the comparisons for powers of 3 between 2 and 24.)
GreaterEqual[rn, 3^24] && LessEqual[rn, (2 3^24) - 1], 25,
GreaterEqual[rn, 3^25] && LessEqual[rn, (2 3^25) - 1], 26,
GreaterEqual[rn, 3^26] && LessEqual[rn, (2 3^26) - 1], 27,
GreaterEqual[rn, (2 3^0)] && LessEqual[rn, 3^1 - 1], -1,
GreaterEqual[rn, (2 3^1)] && LessEqual[rn, 3^2 - 1], -2,
GreaterEqual[rn, (2 3^2)] && LessEqual[rn, 3^3 - 1], -3,
… (Here belong all the comparisons for powers of 3 between 2 and 24.)
GreaterEqual[rn, (2 3^24)] && LessEqual[rn, 3^25 - 1], -25,
GreaterEqual[rn, (2 3^25)] && LessEqual[rn, 3^26 - 1], -26,
GreaterEqual[rn, (2 3^26)] && LessEqual[rn, 3^27 - 1], -27]
As examples, signQ[3812798742493] returns 27 and signQ[7625597484986] returns -27.
These two rule numbers correspond to positive and negative multiplicative identity respectively.
The only surprise I found was with XOR[p, q, r]. Its rule number, 2201243116917, returns -26.
This is unexpected because XOR is modulo 3 sum.
However, an insight into this behavior is had when considering the rule number for XOR[p, q]: 3681670999617. It returns 27. Similarly, XOR[p, r]: 3226154728017 and XOR[q, r]: 3188245183617 both return 27.
Apparently with an even number of variables XOR is associated with a positive expression while with an odd number of variables it is a associated with a negative expression.
You can see then that there is an order to this extension of Boolean logic.
It should be fairly straight forward to construct a comparator for evaluating when expressions are equal, less than, or greater than, using the intervals first and then proceeding within an interval when required.
For example XOR[p, q, r] is associated with an expression that is less than XOR[p, q] because interval -26 is less than 27. And XOR[p, q] is greater than XOR[p, r] because, although both belong to interval 27, XOR[p, q]: 3681670999617 is greater than XOR[p, r]: 3226154728017.
Posted by: Lawrence J. Thaden
p = 240 (page 884 in the NKS Book)
But
FromDigits[Mod[IntegerDigits[0, 2, 8] - IntegerDigits[240, 2, 8], 2], 2] == 240
True
So in two valued Boolean logic:
p == (0 - p)
That is, p and (-p) are invariant with respect to mod 2 sum.
There is symmetry.
No signs in classical Boolean.
But look at the pattern of digits for p in two valued logic:
IntegerDigits[240, 2, 8]
{1, 1, 1, 1, 0, 0, 0, 0}
Now compare this to the pattern I selected for p in this three valued extension of Boolean:
FromDigits[{2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0}, 3]
7625403764901
So I assigned:
p = 7625403764901
And for (-p):
FromDigits[Mod[IntegerDigits[0, 3, 27] - IntegerDigits[7625403764901, 3, 27], 3], 3]
3812992433055
But look what happens when you test the signs:
signQ[p = 7625403764901]
-27
And for (-p):
signQ[3812992433055]
27
Conclusion:
In this three valued extension of Boolean logic p and (-p) are no longer symmetric.
What is p in two valued Boolean logic emerges here as (-p).
And, disquieting as it is, what I labeled as p in this three valued extension of Boolean logic is actually (-p).
Posted by: Lawrence J. Thaden
My professor in philosophy used to say that errors in consistent systems will tend to their own reversal.
Perhaps this is what has happened here. My error was to assign to p the rule number that belongs to (-p). This error did not become apparent until I developed a means to discriminate between p and (-p).
The consistency of this system of logic revealed that the rule number for p, as I had assigned it, actually belonged to (-p).
However, that is not the end of the matter.
Because the assignment of rule numbers for p and the other variables (q and r) fix the assignment of the rule number for AND, all of the minterm expressions are affected.
An inspection of the digit expansions for the correct rule numbers for p, q, and r makes this clear.
p: {1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0}
q: {1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,0,0,0}
r: {1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0}
Since the rule for AND is {{2, 2, 2} -> 1, {_, _, _} -> 0}, the digit expansion for AND must be:
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}
and not
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
as I had it before discovering my error.
So, converting the digit expansion shows the rule number for AND is 1594323, with a single digit in the middle of the coefficients for the minterms, not 2541865828329, with the single digit in the leftmost position.
However, inserting 1594323 as AND in the mapping function together with the corrected rule numbers for p, q, and r returns a rule number whose digit expansion is still:
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
the rule number with the single digit in the leftmost position.
And the expression for the rule with the single digit in the middle is AND[(-p), (-q), (-r)].
Moreover, the forms of p used in the minterms are:
{p, (1 - p), (- p)}
Not:
{p, (p + 1), (- p)}.
Here is the correct list of minterms and rule numbers.
AND[p, q, r] 2541865828329
AND[p, q, (-r)] 847288609443
AND[p, q, (1-r)] 282429536481
AND[p, (-q), r] 94143178827
AND[p, (-q), (-r)] 31381059609
AND[p, (-q), (1-r)] 10460353203
AND[p, (1 -q), r] 3486784401
AND[p, (1 -q), (-r)] 1162261467
AND[p, (1 -q), (1-r)] 387420489
AND[(-p), q, r] 129140163
AND[[(-p), q, (-r)] 43046721
AND[[(-p), q, (1-r)] 14348907
AND[[(-p), (-q), r] 4782969
AND[[(-p), (-q), (-r)] 1594323
AND[[(-p), (-q), (1-r)] 531441
AND[[(-p), (1 -q), r] 177147
AND[[(-p), (1 -q), (-r)] 59049
AND[[(-p), (1 -q), (1-r)] 19683
AND[(1 -p), q, r] 6561
AND[[(1 -p), q, (-r)] 2187
AND[[(1 -p), q, (1-r)] 729
AND[[(1 -p), (-q), r] 243
AND[[(1 -p), (-q), (-r)] 81
AND[[(1 -p), (-q), (1-r)] 27
AND[[(1 -p), (1 -q), r] 9
AND[[(1 -p), (1 -q), (-r)] 3
AND[[(1 -p), (1 -q), (1-r)] 1
The expressions (-p), (-q), and (-r) are additive inverses of p, q, and r. One might say that they are the complements with respect to additive identity and write them as (0-p), (0-q), and (0-r).
The expressions (1 -p), (1 -q), and (1 -r) are complements of p, q, and r with respect to positive multiplicative identity.
The expressions p, q, and r are the complements of NOT[p], NOT[q], and NOT[r] with respect to negative multiplicative identity.
And, curiously, AND[NOT[p], NOT[q], NOT[r]] turns out to be equivalent to AND[p, q, r].
So, AND is symmetric with respect to negative multiplicative complementation.
However, it is not symmetric with respect to the other two forms of complementation, positive multiplicative complementation and additive inverses.
This information might well be useful later when modeling certain physical processes.
Furthermore, NOT[p] can be written in modulo 3 form as (-1 -p).
This means that the minterms can be written entirely as complemented expressions:
AND[p, q, r] is equivalent to AND[(-1 -p), (-1 -q), (-1 -r)]
AND[p, q, (-r)] is equivalent to AND[[(-1 -p), (-1 -q), (0 -r)]
And so forth.
Note: In all of the above, only the expressions are being corrected. The minterm rule numbers are the same as before.
Also, none of these corrections affects the validity of the mapping function.
This corrects for the variables p, q, and r, for AND, and for the minterms.
However, there is still OR to consider.
Posted by: Lawrence J. Thaden
The assignment of rule number 7625597484985 to the expression OR is incorrect.
It was assumed that variables p, q, and r had assignments of rule numbers
7625403764901,
7479532539765, and
6159136430181.
The correct assignments for p, q, and r are rule numbers
3812992433055,
3943753520967, and
4399383164415.
To find OR, apply the rule {{1, 1, 1} -> 1, {_, _, _} -> 2} to the digit expansions of the additive inverses of the rule numbers of the variables:
Transpose[{
IntegerDigits[minusp, 3, 27],
IntegerDigits[minusq, 3, 27],
IntegerDigits[minusr, 3, 27]}] /.{{1, 1, 1} -> 1, {_, _, _} -> 2}
{2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2}
This converts to decimal integer: 7625595890663.
This is the correct rule number for OR.
To test that we have the correct rule numbers for AND and OR we refer to classical Boolean logic where:
NOT[AND[p, q, r]] == OR[Not[p], NOT[q], NOT[r]]
Since NOT[rule number] is found by subtracting a rule number from the highest rule number in the system, we use the following code for NOT:
not[expression_]: =
FromDigits[Mod[
IntegerDigits[7625597484986, 3, 27] -
IntegerDigits[expression, 3, 27], 3], 3]
So with the map function we can establish that the above classical Boolean equality holds for our choice of rule numbers for AND and OR:
andpqr = 1594323;
orpqr = 7625595890663;
not[map[andpqr, p, q, r]] == map[orpqr, not[p], not[q], not[r]]
True
Posted by: Lawrence J. Thaden
I am not at all comfortable about my last two posts to this thread.
Granted, the assignment of rule numbers to variables {p, q, r} should have been to{( -p), ( -q), ( -r)}. But that did not necessitate changing the definitions for AND and OR.
The AND and OR definitions were appropriate. Only the expressions of the minterms needed to be corrected.
So let’s do some backtracking.
We reestablish the original definition of AND using negative variables:
FromDigits[Transpose[{
IntegerDigits[minusp, 3, 27],
IntegerDigits[minusq, 3, 27],
IntegerDigits[minusr, 3, 27] }] /.{{2, 2, 2}-> 1, {_, _, _}-> 0}, 3]
2541865828329
Here it is with the map function.
map[2541865828329, minusp, minusq, minusr]
2541865828329
Also, we reestablish the OR function. As previously defined, it is the dual of AND. That is, it is the reflected complement of AND with respect to negative multiplicative identity. (Negative multiplicative identity has rule number 7625597484986.)
FromDigits[Mod[IntegerDigits[7625597484986, 3, 27] - Reverse[IntegerDigits[2541865828329, 3, 27]], 3], 3]
7625597484985
This definition is in terms of the negative forms of the variables {p, q, r}.
FromDigits[Transpose[{
IntegerDigits[minusp, 3, 27],
IntegerDigits[minusq, 3, 27],
IntegerDigits[minusr, 3, 27]}] /.{{0, 0, 0} -> 1, {_, _, _} -> 2}, 3]
7625597484985
Using the map function:
map[7625597484985, minusp, minusq, minusr]
7625597484985
So the basic operations AND and OR are defined in terms of negative forms of the variables. This system has an inherently negative character to it.
Positive values are had by the principle of substitution.
So, to get the AND of {p, q, r} we use the result of AND[(- p), (- q), (- r)]] as operation, and substitute operands {p, q, r} for operands {(- p), (- q), (- r)}.
map[2541865828329, p, q, r]
1594323
Of course, we could redefine the map function to make it work like this:
redefinedMap[1594323, p, q, r]
1594323
However, the map function was designed first to accommodate Wolfram’s two-color rule numbers and then seamlessly extended to this logic.
No, redefining the map function would be a step backwards since our goal is to maintain consistency with Wolfram’s two-valued logic.
Moreover, such a redefinition of the map function involves a change to Wolfram’s arrangement of the rule numbers and their Boolean expressions.
We would have to turn Wolfram’s list of Boolean expressions upside down, placing {p, q, r} at the top of the list, while also reversing the order of the digit expansion of the rule numbers.
For, whereas {p, q, r} are absolute, or unsigned, variables in Wolfram’s two-color system, they emerge as signed variables in this three-color system with rule numbers for {( -p), ( -q), ( -r)} at the bottom of the list, just as Wolfram’s variables are at the bottom of the list.
Let’s keep it that way. Let’s accept the fact that this three-colored system emerges from the two-colored system with a nascent negative polarity.
While it is true that the old textbooks presented {p, q, r} at the top of the list of canonical forms, Wolfram broke free from this practice in the mid 1980’s. This made possible the expanding place value mechanism for defining the minterms and their coefficients from right to left, consistent with the place value mechanism of the real number system.
So, as the real number system place values advance in powers of ten from right to left, logic place values advance in powers of the base from right to left.
Not only does the map function presented here leverage these aspects of Wolfram’s arrangement of the rules and their expressions. It also depends upon Wolfram’s arrangement.
So let’s leave the map function alone, accept the definitions of AND and OR in terms of the negative forms of {p, q, r}, and go from there.
All that we need to do to get back on track is correct the minterm expressions.
Here is a summary of some of the main features of this logic, with corrected minterm expressions.
Rule numbers for the identities, same as before:
Additive identity: 0
Positive multiplicative identity ( +1): 3812798742493
Negative multiplicative identity ( -1): 7625597484986
Rule numbers for the variables:
p: 3812992433055
q: 3943753520967
r: 4399383164415
Now the additive inverses:
(-p): 7625403764901
(-q): 7479532539765
(-r): 6159136430181
Finally, the complements of the additive inverses of the variables with respect to negative multiplicative identity:
( -1 + p): 193720085
( -1 + q): 146064945221
( -1 + r): 1466461054805
These above three forms of the variables are used to construct the minterms.
Next, common operations, each defined in terms of the negative values of the variables:
AND[(-p), (-q), (-r)]: 2541865828329
OR[(-p), (-q), (-r)]: 7625597484985
(Mod 3 Sum)[(-p), (-q), (-r)]: 2201243116917 (This is XOR.)
(Mod 3 Difference)[(-p), (-q), (-r)]: 4437206964645
(Mod 3 Product)[(-p), (-q), (-r)]: 6088151958012
AND[(- p), (- q)]: 7625597484973
AND[(- p), (- r)]: 7625597484229
AND[(- q), (- r)]: 7625210044813
OR[(- p), (- q)]: 3671583974253
OR[(- p), (- r)]: 2639495791557
OR[(- q), (- r)]: 2541994975053
XOR[(- p), (- q)]: 3681670999617
XOR[(- p), (- r)]: 3226154728017
XOR[(- q), (- r)]: 3188245183617
(Mod 3 Difference) [(- p), (- q)]: 146430861993
(Mod 3 Difference) [(- p), (- r)]: 1466669662809
(Mod 3 Difference) [(- q), (- r)]: 1616787841929
(Mod 3 Product) [(- p), (- q)]: 3943933137846
(Mod 3 Product) [(- p), (- r)]: 4399472553246
(Mod 3 Product) [(- q), (- r)]: 4456336869846
Finally, the minterms for disjunctive normal forms:
Leftmost minterm: AND[(-p), (-q), (-r)]: 2541865828329
Middle minterm: AND[p, q, r]: 1594323
Rightmost minterm: AND[( -1 + p), ( -1 + q), ( -1 + r)]: 1
All of the minterms:
AND[(- p), (- q), (- r)]: 2541865828329
AND[(- p), (- q), r]: 847288609443
AND[(- p), (- q), ( -1 + r)]: 282429536481
AND[(- p), q, (- r)]: 94143178827
AND[(- p), q, r]: 31381059609
AND[(- p), q, ( -1 + r)]: 10460353203
AND[(- p), ( -1 + q), (- r)]: 3486784401
AND[(- p), ( -1 + q), r]: 1162261467
AND[(- p), ( -1 + q), ( -1 + r)]: 387420489
AND[p, (- q), (- r)]: 129140163
AND[p, (- q), r]: 43046721
AND[p, (- q), ( -1 + r)]: 14348907
AND[p, q, (- r)]: 4782969
AND[p, q, r]: 1594323
AND[p, q, ( -1 + r)]: 531441
AND[p, ( -1 + q), (- r)]: 177147
AND[p, ( -1 + q), r]: 59049
AND[p, ( -1 + q), ( -1 + r)]: 19683
AND[( -1 + p), (- q), (- r)]: 6561
AND[( -1 + p), (- q), r]: 2187
AND[( -1 + p), (-q), ( -1 + r)]: 729
AND[( -1 + p), q, (- r)]: 243
AND[( -1 + p), q, r]: 81
AND[( -1 + p), q, ( -1 + r)]: 27
AND[( -1 + p), ( -1 + q), (-r)]: 9
AND[( -1 + p), ( -1 + q), r]: 3
AND[( -1 + p), ( -1 + q), ( -1 + r)]: 1
Laws of signs:
Note: Use signQ[ ] to determine laws of signs, especially when signs are mixed.
For AND:
There is a fundamental difference between the operation AND with two inputs and AND with three inputs. So laws governing signs of the results of AND are considered separately for each version.
With two inputs held constant but with any combination of signs AND produces the same result, and it is negative or positive but apparently never zero.
Here is an example when the sign is negative:
AND[( -p), ( -q)] ==
AND[( -p), q] ==
AND[p, ( -q)] ==
AND[p, q]
signQ[AND[( -p), ( -q)]]
-27
Here is an example when the sign is positive:
AND[(1 - p), (1 - q)] ==
AND[(1 - p), - (1 - q)] ==
AND[ - (1 - p), (1 - q)] ==
AND[ - (1 - p), - (1 - q)]
signQ[AND[(1 - p), (1 - q)]]
27
Now contrast this with AND with three inputs.
First of all, as is seen with the minterms, the result is not the same when the signs change:
NOT_EQUAL[AND[p, q, r], AND[( -p), ( -q), ( -r)]]
So, when there are three same signed inputs, the signs affect the magnitude. However, AND in this case still produces a positive sign or zero.
The identities are no exception:
AND[0, 0, 0] == 0
AND[1, 1, 1] == 0
Incidentally, the only case where AND with three of the identities is not zero is:
AND[( -1), ( -1), ( -1)] == 1
Also of interest is AND with three inputs when one input is one of the three forms of the variables {p, q, r} and the other two inputs are identities.
Recall that the three forms of the variables are: {p, (- p), ( -1 + p)}, {q, (- q), ( -1 + q)}, and {r, (- r), ( -1 + r)}. Except for three cases the result is always zero.
For example the variable p has these exceptions:
AND[p, (-1), (-1)] == AND[p, p, p]
AND[( -p), (-1), (-1)] == AND[( -p), ( -p), ( -p)]
AND[( -1 + p), (-1), (-1)] == AND[( -1 + p), ( -1 + p), ( -1 + p)]
Note also the difference between nested:
AND[AND[p, q], r] == ( -1)
which is negative, and the non-nested minterm:
AND[p, q, r]
which is positive.
Interestingly, even with mixed sign input, AND with three inputs never appears to return a negative result. With randomly selected inputs from millions of cases it is always positive or zero.
In contrast to this three input case, as we saw above, AND with two inputs but with mixed signs appears to never return zero as a result. With randomly selected inputs from millions of cases it is always either positive or negative.
For OR:
With the three inputs held constant but with any combination of signs, OR produces the same result, and it is negative or positive but apparently never zero.
Here is an example when the sign is negative:
OR[(p), (q), (r)] ==
OR[(p), (q), ( -r)] ==
OR[(p), ( -q), (r) ==
OR[(p), ( -q), ( -r)] ==
OR[( -p), (q), (r)] ==
OR[( -p), (q), ( -r)] ==
OR[( -p), ( -q), (r)] ==
OR[( -p), ( -q), ( -r)] == OR[( -p), ( -q), ( -r)]
signQ[OR[( -p), ( -q), ( -r)]]
-27
Here is an example when the sign is positive:
OR[(1 - p), (1 - q), (1 - r)] ==
OR[(1 - p), (1 - q), - (1 - r)] ==
OR[(1 - p), - (1 - q), (1 - r)] ==
OR[(1 - p), - (1 - q), - (1 - r)] ==
OR[- (1 - p), (1 - q), (1 - r)] ==
OR[- (1 - p), (1 - q), - (1 - r)] ==
OR[- (1 - p), - (1 - q), (1 - r)] ==
OR[- (1 - p), - (1 - q), - (1 - r)] == OR[- (1 - p), - (1 - q), - (1 - r)]
signQ[OR[- (1 - p), - (1 - q), - (1 - r)] ]
27
Similarly, with three inputs selected at random, and therefore having mixed signs, the resulting sign of OR is negative or positive but apparently never zero.
This also holds true even when the three inputs are the identities, where
OR[0, 0, 0] == 1
For all other possible combinations of the identities OR with three inputs results in ( -1).
Note also the difference between nested:
OR[OR[p, q], r] == 0
which has no sign, and non-nested:
OR[p, q, r] == OR[( -p), ( -q), ( -r)]
which is negative.
Based on millions of randomly constructed examples it appears that, when OR has two inputs, the sign of the result is always positive or zero. This is so whether the signs of the input are the same or mixed.
No exception to this is the case when both inputs are the identities. Then for all possible combinations except one, the result is 0.
OR[0, 0] == 0
OR[1, 1] == 0
OR[( -1), ( -1)] == 1
OR[0, 1] == 0
OR[0, ( -1)] == 0
OR[1, ( -1)] == 0
Curiously, a review of the above shows that OR with two inputs has operational characteristics similar to AND with three inputs. Conversely, AND with two inputs is comparable to OR with three inputs.
How closely related these operations are, is seen from equivalent expressions:
OR[p, 0, 0] == AND[p, 0]
AND[p, 0, 0] == OR[p, 0]
For Mod 3 Sum:
Unlike AND and OR, XOR operates the same with two or three inputs.
So, the following two expressions give the same result:
XOR[p, q, r] == XOR[XOR[p, q], r]
Use signQ[ ] to determine the result of an operation with XOR.
XOR is the operation used to sum the minterm expressions. For example, the rightmost three minterms are summed as follows:
XOR[
AND[( -1 + p), ( -1 + q), ( -r)],
AND[( -1 + p), ( -1 + q), r],
AND[( -1 + p), ( -1 + q), ( -1 + r)]] ==
NOT[AND[p, q]]
For Mod 3 Difference:
Similar to XOR, modulo 3 difference (DIFF) operates the same with two or three inputs.
However, unlike XOR, it is not commutative.
Use signQ[ ] to determine the sign of the result.
Here are sample expressions which illustrate the relation of DIFF to XOR.
First, with two inputs:
DIFF[p, q] == XOR[p, ( -q)]
DIFF[p, ( -q)] == XOR[p, q]
DIFF[( -p), q] == XOR[( -p), ( -q)]
DIFF[( -p), ( -q)] == XOR[( -p), q]
Next, with three inputs:
DIFF[p, q, r] == XOR[p, ( -q), ( -r)]
DIFF[p, q, ( -r)] == XOR[p, ( -q), r]
DIFF[p, ( -q), r] == XOR[p, q, ( -r)]
DIFF[p, ( -q), ( -r)] == XOR[p, q, r]
DIFF[( -p), q, r] == XOR[( -p), ( -q), ( -r)]
DIFF[( -p), q, ( -r)] == XOR[( -p), ( -q), r]
DIFF[( -p), ( -q), r] == XOR[( -p), q, ( -r)]
DIFF[( -p), ( -q), ( -r)] == XOR[( -p), q, r]
Because of the associative principle the left hand side of the above expressions can be nested, using two inputs at a time:
DIFF[DIFF[p, q], r] == DIFF[p, q, r]
DIFF[DIFF[p, q], ( -r)] == DIFF[p, q, ( -r)]
DIFF[DIFF[p, ( -q)], r] == DIFF[p, ( -q), r]
DIFF[DIFF[p, ( -q)], ( -r)] == DIFF[p, ( -q), ( -r)]
DIFF[DIFF[( -p), q], r] == DIFF[( -p), q, r]
DIFF[DIFF[( -p), q], ( -r)] == DIFF[( -p), q, ( -r)]
DIFF[DIFF[( -p), ( -q)], r] == DIFF[( -p), ( -q), r]
DIFF[DIFF[( -p), ( -q)], ( -r)] == DIFF[( -p), ( -q), ( -r)]
Note that wherever NOT[p] has been used in this discussion it is an abbreviation for DIFF[( -1), p] . And by the principle of substitution:
NOT[any expression] == DIFF[( -1), any expression]
For Mod 3 Product:
Mod 3 Product (PROD) operates the same whether with two inputs or three inputs.
Use signQ[ ] to determine the sign of the result.
Note that the negative of any positive expression can be had by finding the product of the expression and ( -1).
Thus:
PROD[( -1), (any positive expression)] == - (any positive expression)
Complements:
Additive inverses:
See variables and their negatives.
Positive multiplicative complements for variables: {( -p), ( -q), ( -r)}
(1 + p): 7625210074339
(1 + q): 7348577761291
(1 + r): 5572552008259
Positive multiplicative complements for variables: {p, q, r}
(1 - p): 387410647
(1 - q): 277019723695
(1 - r): 2053045476727
Negative multiplicative complements for variables: {( -p), ( -q), ( -r)}
(-1 + p): 193720085
(-1 + q): 146064945221
(-1 + r): 1466461054805
Negative multiplicative complements for variables: {p, q, r}
(-1 - p): 3812605051931
(-1 - q): 3681843964019
(-1 - r): 3226214320571
De Morgan’s duality:
( -1 -AND)[p, q, r] == OR[(-1 -p), (-1 -p), (-1 -p)] ,
which is another way to write the more familiar:
NOT[AND[p, q, r]] == OR[NOT[p], NOT[q], NOT[r]]
Involution:
In Boolean logic:
NOT[NOT[p] -> p
NOT[NOT[0] -> 0
NOT[NOT[1] -> 1
So also, in this three valued logic:
NOT[NOT[p] -> p
NOT[NOT[0] -> 0
NOT[NOT[1] -> 1
But there are additional cases for negative multiplicative identity, ( -p), and ( -1 + p)
NOT[NOT[( -1)] -> ( -1)
NOT[NOT[( -p)] -> ( -p)
NOT[NOT[( -1 + p)] -> ( -1 +p)
Idempotency:
In classical Boolean logic:
OR[p, p] -> p
and
AND[p, p] -> p.
This can also be written as a nested function:
OR[p, p] == OR[ …OR[OR[p, p], p] ], …,p] == p
and
AND[p, p] == AND[ … AND[AND[p, p], p], …,p] == p
In this three valued logic:
OR[OR[p, p, p], p, p] == OR[OR[OR[p, p, p], p, p], p, p] == ( -1)
and
AND[AND[p, p, p], p, p] == AND[AND[AND[p, p, p], p, p], p, p] == 0
These can also be nested indefinitely.
However, as can be seen, they do not equal p.
But there is an operation in this logic that strait away equals p.
Mod 3 Product[p, p, p] == Mod 3 Product[Mod 3 Product[p, p, p], p, p] == p.
The other two modulo operations have a cycle of three values as they nest. The cycles are offset by one and are the reverse of each other.
Mod 3 Sum cycles through {0, (-p), p}.
Mod 3 Difference cycles through {( -p), 0, p}.
Boundless
In Boolean logic:
OR[p, 0] -> p
AND[p, 0] -> 0
OR[p, 1] -> 1
AND[p, 1] -> p
In this logic:
There are two types of AND, two types of OR, and three identities. Therefore, there are many more statements relating the variable p to the identities.
Here are the statements for AND with three inputs:
AND[p, ( -1), ( -1)] == AND[p, p, p]
AND[p, ( -1), 1] == 0
AND[p, ( -1), 0] == 0
AND[p, 1, ( -1)] == 0
AND[p, 1, 1] == 0
AND[p, 1, 0] == 0
AND[p, 0, ( -1)] == 0
AND[p, 0, 1] == 0
AND[p, 0, 0] == 0
Next, the statements for AND with two inputs:
AND[p, ( -1)] == ( -1)
AND[p, 1] == ( -1)
AND[p, 0] == AND[p, p]
Now OR with three inputs:
OR[p, ( -1), ( -1)] == ( -1)
OR[p, ( -1), 1] == ( -1)
OR[p, ( -1), 0] == ( -1)
OR[p, 1, ( -1)] == ( -1)
OR[p, 1, 1] == ( -1)
OR[p, 1, 0] == ( -1)
OR[p, 0, ( -1)] == ( -1)
OR[p, 0, 1] == ( -1)
OR[p, 0, 0] == OR[p, p, p]
Finally, OR with two inputs:
OR[p, ( -1)] == OR[p, p]
OR[p, 1] == 0
OR[p, 0] == 0
Absorption:
In classical Boolean logic:
OR[p, AND[p, q]] == AND[p, OR[p, q]] == p
In this logic:
It appears that there is no expression for absorption.
However:
OR[p, AND[p, q] == OR[p, p] == AND[p, p, p]
And
AND[p, OR[p, q] == AND[p, p] == OR[p, p, p]
Attached is a Mathematica notebook featuring the map function. It demonstrates what has been stated here and then some.
Consider it as a replacement for the notebook attached to a previous post in another thread on this forum.
Posted by: Lawrence J. Thaden
In the previous post the notebook attachment failed to upload.
I am attaching it here.
Posted by: Lawrence J. Thaden
Implication in traditional Boolean logic has two basic forms, conditional and converse, together with their negations, non-conditional and non-converse.
In this three valued extension to traditional Boolean logic there are many more forms of implication.
Below is a list of the forms when implication is defined as a relation between two variables and the OR operation.
The list is in two parts: implications and negations.
Part 1: Implications
Rule Expression Description
13: ~ ( -p) V ~ ( -q) New expression
351: ~ p V q Traditional form for conditional implication
9477: ~ ( -p) V ( -q) Conditional implication in this system
255879: p V ~ q Traditional form for converse implication
6908733: p V q Absence of implication (traditionally called OR)
186535791: p V ( -q) New expression
5036466357: ( -p) V ~ ( -q) Converse implication in this system
135984591639: ( -p) V q New expression
3671583974253: ( -p) V ( -q) Absence of implication (OR in this system)
Part 2: Negations of Implication
Rule Expression Description
7625597484973: ~ (~ ( -p) V ~ ( -q)) New expression
7625597484635: ~ (~ p V q) Traditional form for non-conditional implication
7625597475509: ~ (~ ( -p) V ( -q)) Non-conditional implication in this system
7625597229107: ~ (p V ~ q) Traditional form for non-converse implication
7625590576253: ~ (p V q) Negation of absence of implication (traditionally called NOR)
7625410949195: ~ (p V ( -q)) New expression
7620561018629: ~ (( -p) V ~ ( -q)) Non-converse implication in this system
7489612893347: ~ (( -p) V q) New expression
3954013510733: ~ (( -p) V ( -q)) Negation of absence of implication (NOR in this system)
In traditional Boolean, implication is used to control logic processes.
Might not the above forms of implication be put to use to control many more logic processes?
Notes: ~ is the symbol for NOT.
V is the symbol for OR.
New expression means there is no corresponding form of traditional Boolean implication.
Posted by: Lawrence J. Thaden
This is a correction for the notebook: Revised Three Color Three Variable.nb.
Under the Subsection, Classical Boolean Logic, and the Subsubsection, Xor, replace:
“But let us go beyond this and use De Morgan's duality to validate the assignment.
According to De Morgan's duality:“
With:
“De Morgan’s Laws governing AND and OR relations suggests a way to validate the assignment. Complementing the variables and the operation, results in an equivalent expression for modulo operations, XOR and NXOR. However, note that the expression itself is not complemented as is done in the De Morgan procedure. Also, this mechanism only holds true for traditional Boolean logic. The introduction of signed variables in the three valued extension to traditional Boolean logic complicates things considerably.
So we have:”
Posted by: Lawrence J. Thaden
AND with two variables in this three valued extension to traditional Boolean logic is symmetric with respect to signed values of the variables. OR is not symmetric.
As a result these AND expressions all have the same rule number (7625597484973):
AND[ p, q]
AND[ - p, q]
AND[ p, - q]
AND[ - p, - q]
Notice, in the non-symmetric case, each corresponding OR expression has a unique rule number.
6908733: OR[ p, q]
135984591639: OR[ - p, q]
186535791: OR[ p, - q]
3671583974253: OR[ - p, - q]
One might be inclined to doubt that De Morgan’s Law could ever be applied to these expressions. However, De Morgan’s Law does apply. For the negations of the OR expressions have the same rule numbers as the AND expressions with negated variables.
Here are the rule numbers for the negated OR expressions:
7625590576253: NOT[OR[ p, q]]
7489612893347: NOT[OR[ - p, q]]
7625410949195: NOT[OR[ p, - q]]
3954013510733: NOT[OR[ - p, - q]]
Here are the rule numbers for the AND expressions with negated variables:
7625590576253: AND[NOT[ p], NOT[ q]]
7489612893347: AND[NOT[- p], NOT[ q]]
7625410949195: AND[NOT[ p], NOT[- q]]
3954013510733: AND[NOT[- p], NOT[- q]]
So by De Morgan’s Law:
NOT[OR[ p, q]] == AND[NOT[ p], NOT[ q]]
NOT[OR[ - p, q]] == AND[NOT[- p], NOT[ q]]
NOT[OR[ p, - q]] == AND[NOT[ p], NOT[- q]]
NOT[OR[ - p, - q]] == AND[NOT[- p], NOT[- q]]
Also by De Morgan’s Law you can start with the negation of the AND expression and find the equivalent for OR by taking the negation of the OR variables.
All of these negated AND expressions have rule 13:
NOT[AND[ p, q]]
NOT[AND[ - p, q]]
NOT[AND[ p, - q]]
NOT[AND[ - p, - q]]
Likewise all of these OR expressions with negated variables have rule 13:
OR[NOT[ p], NOT[ q]]
OR[NOT[- p], NOT[ q]]
OR[NOT[ p], NOT[- q]]
OR[NOT[- p], NOT[- q]]
So by De Morgan’s Law:
NOT[AND[ p, q]] == OR[NOT[ p], NOT[ q]]
NOT[AND[ - p, q]] == OR[NOT[- p], NOT[ q]]
NOT[AND[ p, - q]] == OR[NOT[ p], NOT[- q]]
NOT[AND[ - p, - q]] == OR[NOT[- p], NOT[- q]]
Rule numbers for the various forms of the variables:
3812992433055: p
7625403764901: - p
3812605051931: NOT[ p]
193720085: NOT[ - p]
3943753520967: q
7479532539765: - q
3681843964019: NOT[ q]
146064945221: NOT[ - q]
Rule numbers for AND and OR when there are just two variables input:
7625597484973: AND
3671583974253: OR
Posted by: Lawrence J. Thaden
Traditional Boolean Logic: De Morgan’s Laws Generalization
In traditional Boolean logic De Morgan’s Laws equate two expressions, one with the AND operator and the other with the OR operator.
Thus we have:
NOT[AND[p, q]] == OR[NOT[p], NOT[q]]
and
NOT[OR[p, q]] == AND[NOT[p], NOT[q]]
But are AND and OR the only pair of operators for which these laws hold true?
Operators AND and OR in this context are expressions for just two of the elementary rule numbers listed on page 884 of the NKS book:
Rule 192: AND[p, q]
Rule 252: OR[p, q]
(For NOT, subtract variable or expression from 255.)
However, with the following mapping function, any one of the elementary rule numbers on page 884 of the NKS book can be used as an operator:
map[operator_, operand1_, operand2_, operand3_] : =
FromDigits[
(
Reverse[IntegerDigits[operator, 2, 8]]
[[ (* begin subscripting*)
Dot[
MapThread[
List,
{
IntegerDigits[operand3, 2, 8],
IntegerDigits[operand2, 2, 8],
IntegerDigits[operand1, 2, 8]
}
], (*MapThread*)
{2^0, 2^1, 2^2}
] (*Dot*)
+ 1
]] (* end subscripting*)
), 2] (*FromDigits*)
What if we substitute other rule numbers for AND and OR?
Are there any pairs of rule numbers other than 192 and 252 for which the De Morgan duality holds true?
Yes, there are. Many pairs.
(And the relation between the pairs holds true also for any rule numbers substituted for p and q.)
In fact there are 16 OR substitutes for each AND substitute.
For example, rule 192: AND[p, q] can be paired with any one of the following 16 rule numbers:
84: XOR[OR[p, q, r], r]
86: XOR[OR[p, q], r]
92: XOR[OR[p, XOR[q, r]], r]
94: XOR[AND[p, r], OR[p, q, r]]
116: XOR[OR[p, q], AND[q, r]]
118: XOR[OR[p, q, r], AND[q, r]]
124: XOR[p, AND[p, q, NOT[r]], q]
126: OR[XOR[p, q], XOR[p, r]]
212: XOR[OR[XOR[p, q], XOR[p, r]], r]
214: OR[AND[p, q], XOR[p, q, r]]
220: OR[AND[p, NOT[r]], q]
222: OR[XOR[p, q, r], q]
244: OR[p, AND[q, NOT[r]]]
246: OR[p, XOR[q, r]]
252: OR[p, q]
254: OR[p, q, r]
As another example, rule 252: OR[p, q] can be paired with any one of the following 16 rule numbers:
64: AND[p, q, NOT[r]]
66: AND[XOR[p, r], XOR[q, r]]
72: XOR[AND[p, q], AND[q, r]]
74: XOR[AND[p, OR[q, r]], r]
96: AND[p, XOR[q, r]]
98: XOR[AND[OR[p, r], q], r]
104: XOR[p, OR[p, q, r], q, r]
106: XOR[AND[p, q], r]
192: AND[p, q]
194: XOR[p, OR[p, q, r], q]
200: AND[OR[p, r], q]
202: XOR[AND[p, XOR[q, r], r]
224: AND[p, OR[q, r]]
226: XOR[AND[p, q], AND[q, r], r]
232: OR[AND[p, q], AND[OR[p, q], r]]
234: OR[AND[p, q], r]
Attached is a graphic depicting the AND-OR substitution pairs.
Over the horizontal axis are the rule numbers for 16 OR substitutions.
The 256 AND substitutions are displayed on the vertical axis.
An analysis of all possible pairings shows that certain sets of OR substitutes are common to more than one AND substitute.
The following sets of AND substitution rule numbers have the same set of 16 OR substitutes:
(1) AND: {0, 2, 8, 10, 32, 34, 40, 42, 128, 130, 136, 138, 160, 162, 168, 170}
OR: {85, 87, 93, 95, 117, 119, 125, 127, 213, 215, 221, 223, 245, 247, 253, 255}
(2) AND: {1, 3, 9, 11, 33, 35, 41, 43, 129, 131, 137, 139, 161, 163, 169, 171}
OR: {21, 23, 29, 31, 53, 55, 61, 63, 149, 151, 157, 159, 181, 183, 189, 191}
(3) AND: {4, 6, 12, 14, 36, 38, 44, 46, 132, 134, 140, 142, 164, 166, 172, 174}
OR: {69, 71, 77, 79, 101, 103, 109, 111, 197, 199, 205, 207, 229, 231, 237, 239}
(4) AND: {5, 7, 13, 15, 37, 39, 45, 47, 133, 135, 141, 143, 165, 167, 173, 175}
OR: {5, 7, 13, 15, 37, 39, 45, 47, 133, 135, 141, 143, 165, 167, 173, 175}
(5) AND: {16, 18, 24, 26, 48, 50, 56, 58, 144, 146, 152, 154, 176, 178, 184, 186}
OR: {81, 83, 89, 91, 113, 115, 121, 123, 209, 211, 217, 219, 241, 243, 249, 251}
(6) AND: {17, 19, 25, 27, 49, 51, 57, 59, 145, 147, 153, 155, 177, 179, 185, 187}
OR: {17, 19, 25, 27, 49, 51, 57, 59, 145, 147, 153, 155, 177, 179, 185, 187}
(7) AND: {20, 22, 28, 30, 52, 54, 60, 62, 148, 150, 156, 158, 180, 182, 188, 190}
OR: {65, 67, 73, 75, 97, 99, 105, 107, 193, 195, 201, 203, 225, 227, 233, 235}
(8) AND: {21, 23, 29, 31, 53, 55, 61, 63, 149, 151, 157, 159, 181, 183, 189, 191}
OR: {1, 3, 9, 11, 33, 35, 41, 43, 129, 131, 137, 139, 161, 163, 169, 171}
(9) AND: {64, 66, 72, 74, 96, 98, 104, 106, 192, 194, 200, 202, 224, 226, 232, 234}
OR: {84, 86, 92, 94, 116, 118, 124, 126, 212, 214, 220, 222, 244, 246, 252, 254}
(10) AND: {65, 67, 73, 75, 97, 99, 105, 107, 193, 195, 201, 203, 225, 227, 233, 235}
OR: {20, 22, 28, 30, 52, 54, 60, 62, 148, 150, 156, 158, 180, 182, 188, 190}
(11) AND: {68, 70, 76, 78, 100, 102, 108, 110, 196, 198, 204, 206, 228, 230, 236, 238}
OR: {68, 70, 76, 78, 100, 102, 108, 110, 196, 198, 204, 206, 228, 230, 236, 238}
(12) AND: {69, 71, 77, 79, 101, 103, 109, 111, 197, 199, 205, 207, 229, 231, 237, 239}
OR: {4, 6, 12, 14, 36, 38, 44, 46, 132, 134, 140, 142, 164, 166, 172, 174}
(13) AND: {80, 82, 88, 90, 112, 114, 120, 122, 208, 210, 216, 218, 240, 242, 248, 250}
OR: {80, 82, 88, 90, 112, 114, 120, 122, 208, 210, 216, 218, 240, 242, 248, 250}
(14) AND: {81, 83, 89, 91, 113, 115, 121, 123, 209, 211, 217, 219, 241, 243, 249, 251}
OR: {16, 18, 24, 26, 48, 50, 56, 58, 144, 146, 152, 154, 176, 178, 184, 186}
(15) AND: {84, 86, 92, 94, 116, 118, 124, 126, 212, 214, 220, 222, 244, 246, 252, 254}
OR: {64, 66, 72, 74, 96, 98, 104, 106, 192, 194, 200, 202, 224, 226, 232, 234}
(16) AND: {85, 87, 93, 95, 117, 119, 125, 127, 213, 215, 221, 223, 245, 247, 253, 255}
OR: {0, 2, 8, 10, 32, 34, 40, 42, 128, 130, 136, 138, 160, 162, 168, 170}
Observations:
(1) Sets of rule numbers for AND and OR substitutes are always all even or all odd.
(2) The sets beginning with rule number 5, 17, 68, and 80 have same rules for AND and OR substitutes.
(3) Of the remaining 12 sets half switch ANDs for ORs and ORs for ANDs.
(4) From the first to the last all AND sets alternate even and odd.
(5) The first 8 OR sets are odd and the last 8 are even.
(6) Within a set of AND-OR substitutes any AND can go with any OR.
(7) Pairs of OR substitute rule numbers all follow a pattern such that, knowing the first of the 16 rule numbers, the rest can be generated by FoldList:
FoldList[Plus, 85, {2, 6, 2, 22, 2, 6, 2, 86, 2, 6, 2, 22, 2, 6, 2}]
{85, 87, 93, 95, 117, 119, 125, 127, 213, 215, 221, 223, 245, 247, 253, 255}
(8) The first AND substitute rule numbers all follow a pattern such that, starting with 0, the rest can be generated by FoldList:
FoldList[Plus, 0, {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1}]
{0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85}
This pattern is the OR substitute rules pattern divided by 2:
{2, 6, 2, 22, 2, 6, 2, 86, 2, 6, 2, 22, 2, 6, 2} / 2
{1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1}
(9) The absolute differences between each pair of corresponding members of the AND-OR substitutes enumerated above from (1) through (16) are:
{85, 20, 65, 0, 65, 0, 45, 20, 20, 45, 0, 65, 0, 65, 20, 85}
So, in traditional Boolean logic, De Morgan’s Law has application to much more than the dual pair AND-OR. There are many dual pairs. And by implication, application of the concept of duality is also extended.
But what about this three valued logic? Does it support a general application of De Morgan’s law?
Perhaps the answer can be found by analyzing this behavior of De Morgan duality in traditional Boolean logic.
Here are some clues:
(1) There are 16 sets of AND-OR substitutes. There are 256 rule numbers. 16 is the square root of 256. Traditional Boolean logic is two valued.
So maybe there are 19683 sets of AND-OR substitutes in this three valued logic, since there are 7625597484987 rule numbers and 19683 is the cube root of 7625597484987.
(2) FoldList[Plus, 0, {1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1}] generated the list of first AND substitute rules for traditional Boolean logic.
If we could find the first half of the pattern of differences for the first AND rules for this three valued logic, we could generate the entire pattern, since the pattern is left-right symmetric.
This would give us a list of the first AND substitute rule numbers for this three valued logic.
(3) We found that four sets of the AND-OR substitute rule numbers had the same starting rule number for AND as for OR.
Since four is the square root of 16 and 27 is the cube root of 19683, perhaps there are 27 sets of AND-ORs that have the same starting rule numbers.
With the list of the first AND substitute rule numbers for this three valued logic, we could test for which ones the De Morgan duality holds true when both are the same.
That would leave 19656 sets that switch. So we would be looking for 9828 starting AND rule numbers that are also starting OR rule numbers.
(4) What we would still need is the pattern for generating the list of OR substitute rules. Traditional Boolean logic used {2, 6, 2, 22, 2, 6, 2, 86, 2, 6, 2, 22, 2, 6, 2}. Each integer in the pattern is twice what the corresponding number is in the AND pattern.
Perhaps we could discover the corresponding OR pattern for this three valued logic by finding three times the integers that are in the AND pattern for this three valued logic.
(5) Since the absolute values of corresponding pairs of each set of AND-OR substitutes is the same for traditional Boolean logic, it might be expected to be the same in this three valued logic. And since there is a symmetric pattern to the set of 16 absolute values in traditional Boolean logic, we might detect a pattern in the 19683 absolute values. In particular, the placement of the 0 members, since these represent positions where the AND rules are the same as the OR rules.
Posted by: Lawrence J. Thaden
In traditional Boolean logic substitution rules for AND and OR, in this De Morgan context, partition the system of ECA rule numbers. That is, each rule number is used once for the AND substitute and each is used once for the OR substitute.
And the results for each AND substitute taken with its particular set of 16 OR substitutes is always the same. Also the results for each OR substitute taken with its particular set of 16 AND substitutes is always the same.
Moreover, all of 256 rule numbers in the system are used for the AND and the OR substitutes. Not one is missing.
However, the results do not account for all of the rule numbers. Rather when the AND substitute is taken with its 16 OR substitutes results are confined to the set:
{255, 252, 243, 240, 207, 204, 195, 192, 63, 60, 51, 48, 15, 12, 3, 0}.
And when the OR substitute is taken with its 16 AND substitutes they are confined to the same set with the results in a different order:
{0, 192, 48, 240, 12, 204, 60, 252, 3, 195, 51, 243, 15, 207, 63, 255}.
So, although there are (256 * 16) = 4096 ways to express the De Morgan Law using substitutes for AND and OR, there are only 16 possible results:
{0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255}.
For example, when rule 192: AND[p, q] is paired with each of the following ORs the result is always rule 63: NOT[AND[p, q]]
OR: {84, 86, 92, 94, 116, 118, 124, 126, 212, 214, 220, 222, 244, 246, 252, 254}
And when rule 252: OR[p, q] is paired with each of the following ANDs the result is always rule 3: NOT[OR[p, q]]
{64, 66, 72, 74, 96, 98, 104, 106, 192, 194, 200, 202, 224, 226, 232, 234}
Here are the expressions for the 16 possible results:
0: NOT[1] (or as in NKS book on p. 884: 0)
3: AND[NOT[p], NOT[q]] (or as in NKS book on p. 884: NOT[OR[p, q]])
12: AND[NOT[p], q] (or as in NKS book on p. 884: XOR[AND[p, q], q])
15: NOT[p]
48: AND[p, NOT[q]]
51: NOT[q]
60: AND[OR[NOT[p], NOT[q]], OR[p, q]] (or as in NKS book on p. 884: XOR[p, q])
63: OR[NOT[p], NOT[q]] (or as in NKS book on p. 884: NOT[AND[p, q]])
192: AND[p, q]
195: OR[AND[NOT[p], NOT[q]], AND[p, q]] (or as in NKS book on p. 884: XOR[p, NOT[q]])
204: q
207: OR[NOT[p], q] (or as in NKS book on p. 884: NOT[AND[p, NOT[q]])
240: p
243: OR[p, NOT[q]]
252: OR[p, q]
255: 1
Notice how nicely they pair up.
When there is only one operand, the complement of the first expresssion becomes the second expression in the pair.
Otherwise, in the first expression change ANDs to ORs and ORs to ANDs to get the second expression in the pair.
16 Possible Results from 4096 Ways to Express the De Morgan Law Using Substitutes for AND and OR
0: NOT[1]
255: 1
3: AND[NOT[p], NOT[q]]
63: OR[NOT[p], NOT[q]]
12: AND[NOT[p], q]
207: OR[NOT[p], q]
15: NOT[p]
240: p
48: AND[p, NOT[q]]
243: OR[p, NOT[q]]
51: NOT[q]
204: q
60: AND[OR[NOT[p], NOT[q]], OR[p, q]]
195: OR[AND[NOT[p], NOT[q]], AND[p, q]]
192: AND[p, q]
252: OR[p, q]
Corrected the figure for number of possible pairs from
(256 * 256) = 65536 to
(256 * 16) = 4096
Posted by: Lawrence J. Thaden
Substitution Rules
In the previous post on De Morgan’s Laws we looked at rule numbers:
192: AND[p, q]
252: OR[p, q]
together with operator substitutions.
Moreover, it was observed that, by the means of algebraic substitution, any rule numbers can be used in place of variables p and q.
So, one might conclude: That's the end of that!
However, on page 884 of the NKS book we also find:
160: AND[p, r]
250: OR[p, r]
as well as:
136: AND[q, r]
238: OR[q, r]
These two pairs of rules behave similarly with respect to De Morgan’s Laws.
However, they have characteristics peculiar to themselves.
In this post we look at rules for AND[p, r] and OR[p, r].
The following sets of AND[p, r] substitution rule numbers have the same set of 16 OR[p, r] substitutes:
(1) AND: {0, 4, 8, 12, 64, 68, 72, 76, 128, 132, 136, 140, 192, 196, 200, 204}
OR: {51, 55, 59, 63, 115, 119, 123, 127, 179, 183, 187, 191, 243, 247, 251, 255}
(2) AND: {1, 5, 9, 13, 65, 69, 73, 77, 129, 133, 137, 141, 193, 197, 201, 205}
OR: {19, 23, 27, 31, 83, 87, 91, 95, 147, 151, 155, 159, 211, 215, 219, 223}
(3) AND: {2, 6, 10, 14, 66, 70, 74, 78, 130, 134, 138, 142, 194, 198, 202, 206}
OR: {35, 39, 43, 47, 99, 103, 107, 111, 163, 167, 171, 175, 227, 231, 235, 239}
(4) AND: {3, 7, 11, 15, 67, 71, 75, 79, 131, 135, 139, 143, 195, 199, 203, 207}
OR: {3, 7, 11, 15, 67, 71, 75, 79, 131, 135, 139, 143, 195, 199, 203, 207}
(5) AND: {16, 20, 24, 28, 80, 84, 88, 92, 144, 148, 152, 156, 208, 212, 216, 220}
OR: {49, 53, 57, 61, 113, 117, 121, 125, 177, 181, 185, 189, 241, 245, 249, 253}
(6) AND: {17, 21, 25, 29, 81, 85, 89, 93, 145, 149, 153, 157, 209, 213, 217, 221}
OR: {17, 21, 25, 29, 81, 85, 89, 93, 145, 149, 153, 157, 209, 213, 217, 221}
(7) AND: {18, 22, 26, 30, 82, 86, 90, 94, 146, 150, 154, 158, 210, 214, 218, 222}
OR: {33, 37, 41, 45, 97, 101, 105, 109, 161, 165, 169, 173, 225, 229, 233, 237}
(8) AND: {19, 23, 27, 31, 83, 87, 91, 95, 147, 151, 155, 159, 211, 215, 219, 223}
OR: {1, 5, 9, 13, 65, 69, 73, 77, 129, 133, 137, 141, 193, 197, 201, 205}
(9) AND: {32, 36, 40, 44, 96, 100, 104, 108, 160, 164, 168, 172, 224, 228, 232, 236}
OR: {50, 54, 58, 62, 114, 118, 122, 126, 178, 182, 186, 190, 242, 246, 250, 254}
(10) AND: {33, 37, 41, 45, 97, 101, 105, 109, 161, 165, 169, 173, 225, 229, 233, 237}
OR: {18, 22, 26, 30, 82, 86, 90, 94, 146, 150, 154, 158, 210, 214, 218, 222}
(11) AND: {34, 38, 42, 46, 98, 102, 106, 110, 162, 166, 170, 174, 226, 230, 234, 238}
OR: {34, 38, 42, 46, 98, 102, 106, 110, 162, 166, 170, 174, 226, 230, 234, 238}
(12) AND: {35, 39, 43, 47, 99, 103, 107, 111, 163, 167, 171, 175, 227, 231, 235, 239}
OR: {2, 6, 10, 14, 66, 70, 74, 78, 130, 134, 138, 142, 194, 198, 202, 206}
(13) AND: {48, 52, 56, 60, 112, 116, 120, 124, 176, 180, 184, 188, 240, 244, 248, 252}
OR: {48, 52, 56, 60, 112, 116, 120, 124, 176, 180, 184, 188, 240, 244, 248, 252}
(14) AND: {49, 53, 57, 61, 113, 117, 121, 125, 177, 181, 185, 189, 241, 245, 249, 253}
OR: {16, 20, 24, 28, 80, 84, 88, 92, 144, 148, 152, 156, 208, 212, 216, 220}
(15) AND: {50, 54, 58, 62, 114, 118, 122, 126, 178, 182, 186, 190, 242, 246, 250, 254}
OR: {32, 36, 40, 44, 96, 100, 104, 108, 160, 164, 168, 172, 224, 228, 232, 236}
(16) AND: {51, 55, 59, 63, 115, 119, 123, 127, 179, 183, 187, 191, 243, 247, 251, 255}
OR: {0, 4, 8, 12, 64, 68, 72, 76, 128, 132, 136, 140, 192, 196, 200, 204}
Observations:
(1) Sets of rule numbers for AND[p, r] and OR[p, r] substitutes are always all even or all odd.
(2) The sets beginning with rule number 3, 17, 34, and 48 have same rules for AND[p, r] and OR[p, r] substitutes.
(3) Of the remaining 12 sets half switch AND[p, r]s for OR[p, r]s and OR[p, r]s for AND[p, r]s.
(4) From the first to the last all AND[p, r] sets alternate even and odd.
(5) The first 8 OR sets are odd and the last 8 are even.
(6) Within a set of AND[p, r] - OR[p, r] substitutes any AND[p, r] can go with any OR[p, r].
(7) Pairs of OR[p, r] substitute rule numbers all follow a pattern such that, knowing the first of the 16 rule numbers, the rest can be generated by FoldList:
FoldList[Plus, 51, {4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4}
51, 55, 59, 63, 115, 119, 123, 127, 179, 183, 187, 191, 243, 247, 251, 255}
(This is in contrast with the case for OR[p, q]:
FoldList[Plus, 85, {2, 6, 2, 22, 2, 6, 2, 86, 2, 6, 2, 22, 2, 6, 2}]
{85, 87, 93, 95, 117, 119, 125, 127, 213, 215, 221, 223, 245, 247, 253, 255})
(8) AND[p, r] substitute rule numbers all follow the same pattern such that, starting with 0, the rest can be generated by FoldList:
FoldList[Plus, 0, {4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4}]
{0, 4, 8, 12, 64, 68, 72, 76, 128, 132, 136, 140, 192, 196, 200, 204}
(This is in contrast with the case for AND[p, q] which had its own pattern.)
(9) The absolute differences between each pair of corresponding members of the AND[p, r] - OR[p, r] substitutes enumerated above from (1) through (16) are:
{51, 18, 33, 0, 33, 0, 15, 18, 18, 15, 0, 33, 0, 33, 18, 51}
(For comparison here are the absolute differences for AND[p, q] - OR[p, q]:
{85, 20, 65, 0, 65, 0, 45, 20, 20, 45, 0, 65, 0, 65, 20, 85}
It is curious that rule number 51: NOT[q] signals its absence from AND[p, r] - OR[p, r].
Likewise rule number 85: NOT[r] signals its absence from AND[p, q] - OR[p, q].)
(10) The attached graphic illustrates the distribution of AND[p, r] - OR[p, r] substitution rule numbers over the system of traditional Boolean logic.
The pattern of this distribution is closely related to the difference pattern used to generate OR[p, r] substitution rules: {4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4}.
Here are all of the OR[p, r] substitution rules blocked out to highlight the pattern.
In addition to the difference pattern in the rows, notice that rule numbers are dealt out four rows of four columns at a time by incrementing by 1. This block of OR[p, r] distribution rules is repeated to complete the graphic input .
{0, 4, 8, 12,........64, 68, 72, 76,...........128, 132, 136, 140,...192, 196, 200, 204},
{1, 5, 9, 13,........65, 69, 73, 77,...........129, 133, 137, 141,...193, 197, 201, 205},
{2, 6, 10, 14,.......66, 70, 74, 78,...........130, 134, 138, 142,...194, 198, 202, 206},
{3, 7, 11, 15,.......67, 71, 75, 79,...........131, 135, 139, 143,...195, 199, 203, 207},
{16, 20, 24, 28,...80, 84, 88, 92,...........144, 148, 152, 156,...208, 212, 216, 220},
{17, 21, 25, 29,...81, 85, 89, 93,...........145, 149, 153, 157,...209, 213, 217, 221},
{18, 22, 26, 30,...82, 86, 90, 94,...........146, 150, 154, 158,...210, 214, 218, 222},
{19, 23, 27, 31,...83, 87, 91, 95,...........147, 151, 155, 159,...211, 215, 219, 223},
{32, 36, 40, 44,...96, 100, 104, 108,.....160, 164, 168, 172,...224, 228, 232, 236},
{33, 37, 41, 45,...97, 101, 105, 109,.....161, 165, 169, 173,...225, 229, 233, 237},
{34, 38, 42, 46,...98, 102, 106, 110,.....162, 166, 170, 174,...226, 230, 234, 238},
{35, 39, 43, 47,...99, 103, 107, 111,.....163, 167, 171, 175,...227, 231, 235, 239},
{48, 52, 56, 60,...112, 116, 120, 124,...176, 180, 184, 188,...240, 244, 248, 252},
{49, 53, 57, 61,...113, 117, 121, 125,...177, 181, 185, 189,...241, 245, 249, 253},
{50, 54, 58, 62,...114, 118, 122, 126,...178, 182, 186, 190,...242, 246, 250, 254},
{51, 55, 59, 63,...115, 119, 123, 127,...179, 183, 187, 191,...243, 247, 251, 255}
Unique Results
Substitution rules for AND[p, r] - OR[p, r] partition the ECA rule numbers just as AND[p, q] - OR[p, q] substitution rules were seen to do.
And the results for each AND[p, r] substitute taken with its particular set of 16 OR[p, r] substitutes is always the same. Also the results for each OR[p, r] substitute taken with its particular set of 16 AND[p, r] substitutes is always the same.
Moreover, all of 256 rule numbers in the system are used for the AND[p, r] and the OR[p, r] substitutes. Not one is missing.
However, the results do not account for all of the rule numbers. Rather when the AND[p, r] substitute is taken with its 16 OR[p, r] substitutes results are confined to the set:
{255, 250, 245, 240, 175, 170, 165, 160, 95, 90, 85, 80, 15, 10, 5, 0}.
(Compare this to the set for OR[p, q]:
{255, 252, 243, 240, 207, 204, 195, 192, 63, 60, 51, 48, 15, 12, 3, 0}.)
And when the OR[p, r] substitute is taken with its 16 AND[p, r] substitutes they are confined to the same set with the results in a different order:
{0, 160, 80, 240, 10, 170, 90, 250, 5, 165, 85, 245, 15, 175, 95, 255}.
(Compare this to the set for AND[p, q]:
{0, 192, 48, 240, 12, 204, 60, 252, 3, 195, 51, 243, 15, 207, 63, 255}.)
So, although there are (256 * 16) = 4096 ways to express the De Morgan Law using substitutes for AND[p, r] and OR[p, r], there are only 16 possible results:
{0, 5, 10, 15, 80, 85, 90, 95, 160, 165, 170, 175, 240, 245, 250, 255}.
Here are the expressions for the 16 possible results for AND[p, r] and OR[p, r]:
0: NOT[1] (or as in NKS book on p. 884: 0)
5: AND[NOT[p], NOT[r]] (or as in NKS book on p. 884: NOT[OR[p, r]])
10: AND[NOT[p], r]
15: NOT[p]
80: AND[p, NOT[r]]
85: NOT[r]
90: AND[OR[NOT[p], NOT[r]], OR[p, r]] (or as in NKS book on p. 884: XOR[p, r])
95: OR[NOT[p], NOT[r]] (or as in NKS book on p. 884: NOT[AND[p, r]])
160: AND[p, r]
165: OR[AND[NOT[p], NOT[r]], AND[p, r]] (or as in NKS book on p. 884: XOR[p, NOT[r]])
170: r
175: OR[NOT[p], r]
240: p
245: OR[p, NOT[r]]
250: OR[p, r]
255: 1
If you compare this list with the one in the previous post for AND[p, q] and OR[p, q], you will see that they are the same expressions except for here, wherever there is a letter r, in the previous list it is a letter q. Of course, the rule numbers have changed.
Corrected 238: OR[p, r] to read 238: OR[q, r] on 2/11/2007
Posted by: Lawrence J. Thaden
Unique Results
In the previous post on De Morgan’s Laws we looked at rule numbers:
160: AND[p, r]
250: OR[p, r]
together with operator substitutions.
We observed that this pair of rules behaves similarly with respect to De Morgan’s Laws, but noted that they have characteristics peculiar to themselves.
We also noted that there is a third pair of rules to be considered:
136: AND[q, r]
238: OR[q, r]
Let’s now look at these rules.
First off, it is no surprise that the unique results generated from these two rules follow the same pattern as the results from the other pairs of rules.
So, in the list of 16 unique results below, wherever you find a letter q, there was a letter p for rules for AND[p, r] and OR[p, r].
Here then are the expressions for the 16 possible results for AND[q, r] and OR[q, r]:
0: NOT[1] (or as in NKS book on p. 884: 0)
17: AND[NOT[q], NOT[r]] (or as in NKS book on p. 884: NOT[OR[q, r]])
34: AND[NOT[q], r]
51: NOT[q]
68: AND[q, NOT[r]]
85: NOT[r]
102: AND[OR[NOT[q], NOT[r]], OR[q, r]] (or as in NKS book on p. 884: XOR[q, r])
119: OR[NOT[q], NOT[r]] (or as in NKS book on p. 884: NOT[AND[q, r]])
136: AND[q, r]
153: OR[AND[NOT[q], NOT[r]], AND[q, r]] (or as in NKS book on p. 884: XOR[q, NOT[r]])
170: r
187: OR[NOT[q], r]
204: q
221: OR[q, NOT[r]]
238: OR[q, r]
255: 1
Substitution Rules
Recall that the substitution rules for {p, r} has the same difference pattern for AND as for OR. It is:
{4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4, 52, 4, 4, 4}.
For reference, OR[p, q] has
{2, 6, 2, 22, 2, 6, 2, 86, 2, 6, 2, 22, 2, 6, 2}.
And half of that for AND[p, q].
What about this case, {q, r}?
It follows {p, r} in that there is only one difference pattern, not a separate one for OR and for AND. But, somewhat unexpectedly, the {q, r} difference pattern never varies. It is always 16:
{16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16}.
This has a remarkable effect. It is seen in the pattern of all of the OR[q, r] substitution rules:
{0,...16, 32, 48, 64, 80,...96, 112, 128, 144, 160, 176, 192, 208, 224, 240},
{1,...17, 33, 49, 65, 81,...97, 113, 129, 145, 161, 177, 193, 209, 225, 241},
{2,...18, 34, 50, 66, 82,...98, 114, 130, 146, 162, 178, 194, 210, 226, 242},
{3,...19, 35, 51, 67, 83,...99, 115, 131, 147, 163, 179, 195, 211, 227, 243},
{4,...20, 36, 52, 68, 84, 100, 116, 132, 148, 164, 180, 196, 212, 228, 244},
{5,...21, 37, 53, 69, 85, 101, 117, 133, 149, 165, 181, 197, 213, 229, 245},
{6,...22, 38, 54, 70, 86, 102, 118, 134, 150, 166, 182, 198, 214, 230, 246},
{7,...23, 39, 55, 71, 87, 103, 119, 135, 151, 167, 183, 199, 215, 231, 247},
{8,...24, 40, 56, 72, 88, 104, 120, 136, 152, 168, 184, 200, 216, 232, 248},
{9,...25, 41, 57, 73, 89, 105, 121, 137, 153, 169, 185, 201, 217, 233, 249},
{10, 26, 42, 58, 74, 90, 106, 122, 138, 154, 170, 186, 202, 218, 234, 250},
{11, 27, 43, 59, 75, 91, 107, 123, 139, 155, 171, 187, 203, 219, 235, 251},
{12, 28, 44, 60, 76, 92, 108, 124, 140, 156, 172, 188, 204, 220, 236, 252},
{13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173, 189, 205, 221, 237, 253},
{14, 30, 46, 62, 78, 94, 110, 126, 142, 158, 174, 190, 206, 222, 238, 254},
{15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255}
It counts out down the rows 1 by 1 as the rules are dealt out column by column, such that the columns are exactly 16 apart. The effect is a uniform distribution.
This is in contrast with the clustered distribution for OR[p, r].
This block of substitution rules is repeated 16 times to complete the OR[q, r] input of 4096 pairs expressing the De Morgan Laws using substitutes for AND[q, r] and OR[q, r].
See the attached graphic.
Here then are sets of AND[q, r] substitution rule numbers that have the same set of 16 OR[q, r] substitutes:
(1) AND: {0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240}
OR: {15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255}
(2) AND: {1, 17, 33, 49, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241}
OR: {7, 23, 39, 55, 71, 87, 103, 119, 135, 151, 167, 183, 199, 215, 231, 247}
(3) AND: {2, 18, 34, 50, 66, 82, 98, 114, 130, 146, 162, 178, 194, 210, 226, 242}
OR: {11, 27, 43, 59, 75, 91, 107, 123, 139, 155, 171, 187, 203, 219, 235, 251}
(4) AND: {3, 19, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 195, 211, 227, 243}
OR: {3, 19, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 195, 211, 227, 243}
(5) AND: {4, 20, 36, 52, 68, 84, 100, 116, 132, 148, 164, 180, 196, 212, 228, 244}
OR: {13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173, 189, 205, 221, 237, 253}
(6) AND: {5, 21, 37, 53, 69, 85, 101, 117, 133, 149, 165, 181, 197, 213, 229, 245}
OR: {5, 21, 37, 53, 69, 85, 101, 117, 133, 149, 165, 181, 197, 213, 229, 245}
(7) AND: {6, 22, 38, 54, 70, 86, 102, 118, 134, 150, 166, 182, 198, 214, 230, 246}
OR: {9, 25, 41, 57, 73, 89, 105, 121, 137, 153, 169, 185, 201, 217, 233, 249}
(8) AND: {7, 23, 39, 55, 71, 87, 103, 119, 135, 151, 167, 183, 199, 215, 231, 247}
OR: {1, 17, 33, 49, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241}
(9) AND: {8, 24, 40, 56, 72, 88, 104, 120, 136, 152, 168, 184, 200, 216, 232, 248}
OR: {14, 30, 46, 62, 78, 94, 110, 126, 142, 158, 174, 190, 206, 222, 238, 254}
(10) AND: {9, 25, 41, 57, 73, 89, 105, 121, 137, 153, 169, 185, 201, 217, 233, 249}
OR: {6, 22, 38, 54, 70, 86, 102, 118, 134, 150, 166, 182, 198, 214, 230, 246}
(11) AND: {10, 26, 42, 58, 74, 90, 106, 122, 138, 154, 170, 186, 202, 218, 234, 250}
OR: {10, 26, 42, 58, 74, 90, 106, 122, 138, 154, 170, 186, 202, 218, 234, 250}
(12) AND: {11,27,43,59,75,91,107,123,139,155,171,187,203,219,235,251}
OR: {2, 18, 34, 50, 66, 82, 98, 114, 130, 146, 162, 178, 194, 210, 226, 242}
(13) AND: {12, 28, 44, 60, 76, 92, 108, 124, 140, 156, 172, 188, 204, 220, 236, 252}
OR: {12, 28, 44, 60, 76, 92, 108, 124, 140, 156, 172, 188, 204, 220, 236, 252}
(14) AND: {13, 29, 45, 61, 77, 93, 109, 125, 141, 157, 173, 189, 205, 221, 237, 253}
OR: {4, 20, 36, 52, 68, 84, 100, 116, 132, 148, 164, 180, 196, 212, 228, 244}
(15) AND: {14, 30, 46, 62, 78, 94, 110, 126, 142, 158, 174, 190, 206, 222, 238, 254}
OR: {8, 24, 40, 56, 72, 88, 104, 120, 136, 152, 168, 184, 200, 216, 232, 248}
(16) AND: {15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255}
OR: {0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240}
Posted by: Lawrence J. Thaden
A generalization of De Morgan's Laws reveals that, for traditional Boolean logic in three variables, there are 4096 combinations of AND and OR substitutions with variables p and q for which the laws hold true.
But these 4096 combinations produce just 16 possible results.
Rule numbers: {0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255}.
Also, when the AND and OR substitution rules are for variables {p, r} or {q, r}, the results are:
{p, r}: {0, 5, 10, 15, 80, 85, 90, 95, 160, 165, 170, 175, 240, 245, 250, 255}
{q, r}: {0, 17, 34, 51, 68, 85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255}
All three sets have rule numbers {0, 255} in common.
These are rule numbers for the identities, 0 and 1.
Sets {p, q} and {p, r} have rules {0, 15, 240, 255} in common.
These are rule numbers for the identities {0, 1} and variables Not[p] and p.
Sets {p, q} and {q, r} have rules {0, 51, 204, 255} in common.
These are rule numbers for the identities {0, 1} and variables Not[q] and q.
Sets {p, r} and {q, r} have rules {0, 85, 170, 255} in common.
These are rule numbers for the identities {0, 1} and variables Not[r] and r.
These three sets are closed under the map function introduced earlier. That is, when the members of a set are taken as operator and operands in the map function, the results are always a member of the set.
However, this is not the case for the union of the three sets.
The union of the three sets is not closed under the map function.
It introduces another 194 rule numbers.
In fact this union of all three sets has products for all but these 24 rule numbers:
{22, 23, 41, 43, 73, 77, 97, 104, 107, 109, 113, 121, 134, 142, 146, 148, 151, 158, 178, 182, 212, 214, 232, 233}.
These are out of reach even when closure is broken.
On page 231 in the NKS book, Wolfram categorizes rules and their CA behavior into four classes of increasing complexity. There he describes as “quite remarkable” the fact that different rules could generate similar patterns. I am sure that many, including myself, have shared this sense of wonder.
But in this context of De Morgan generalization I find “quite remarkable” a different categorization of the ECA rules, one based on the increasing complexity of their structure rather than on their behavior.
And where Wolfram’s sense of wonder arose out of the discovery of many rules having similar patterns of behavior, here one is surprised that rules with similar expressions manifest such different structure.
To see what I mean, recall that the expressions for the three sets of 16 rules have similar syntax such that to change from one set of expressions to another all that is necessary is to drop in the correct variables, be they {p, q}, {p, r}, or {q, r}.
But when these are used to generate plots of 4096 pairs of rules expressing the De Morgan Laws, we unexpectedly see different structures of increasing complexity.
The graphic for set {q, r} is the most uniform of the three. Followed by {p, r} with its clustered structure, and finally {p, q}.
Quite frankly, based on the discussion at the top of this thread, I expected to find left-right symmetry between {p, q} and {q, r}. To quote myself:
“An inspection of the rules on page 883 of the NKS book and their expressions listed on page 884 show a definite pattern. For example, rules 2 and 16 have these expressions: 2:
And[Not[p], Not[q], r] and 16: And[p, Not[q], Not[r]. The graphs for these rules found on page 55 show opposing diagonal lines. They are left-right vertical reflections of each other. Notice that the expressions are very much alike. The only difference is where the Not operator is with reference to the operands p and r. Rule 2 has the Not operator applied to the variable p and rule 16 has it applied to variable r. It is this arrangement that makes the two rules produce cellular automaton graphs that are left-right reflections of each other.”
In an effort to amplify this distinction of structures, we will examine the different characteristics of plots for the three sets of 16 outer products of {p, q}, {p, r}, and {q, r} using the map function.
In the next post we begin with an analysis of the map functions for 16 outer products of the set for {p, q}:
{0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255}.
Posted by: Lawrence J. Thaden
Assign to the symbol pqset the rule numbers for the unique set of results from applying De Morgan’s Laws to AND[p, q] and OR[p, q].
pqset = {0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255};
Next generate outer products for this set:
pqouterproducts = Outer[List, pqset, pqset, pqset];
Dimensions[pqouterproducts]
{16, 16, 16, 3}
We will take these triples as input to the map function and generate 16 projections one for each member of pqouterproduct. This will be input to a cube shaped plot as layers along the z-axis. Each layer will have (16 by 16) = 256 rule numbers, the results of the map function.
Prior to this we make sure there will be no surprises by checking for closure.
This affirms that every execution of the map function takes its operation and two operands from the set {p, q} and then returns a result also from the set {p, q}.
Union[Flatten[Table[map[pqouterproducts[[i, j, k, 1]], pqouterproducts[[i, j, k, 2]], pqouterproducts[[i, j, k, 3]], dontcare], {i, Length[pqouterproducts]}, {j, Length[pqouterproducts[[i]]]}, {k, Length[pqouterproducts[[i, j]]]}]]] = = pqset
True
Now to generate the projections from the triples:
pqprojections = Table[(map[pqouterproducts[[i, j, k, 1]], pqouterproducts[[i, j, k, 2]], pqouterproducts[[i, j, k, 3]], dontcare]), {i, Length[pqouterproducts]}, {j, Length[pqouterproducts[[i]]]}, {k, Length[pqouterproducts[[i, j]]]}];
Dimensions[pqprojections]
{16, 16, 16}
Replacing the triples with the projections we generate values for the plot points’ coordinates:
pqplotpoints = Table[{pqouterproducts[[i, j, k, 2]], pqouterproducts[[i, j, k, 3]], pqprojections[[i, j, k]]},{i, Length[pqouterproducts]}, {j, Length[pqouterproducts[[i]]]}, {k, Length[pqouterproducts[[i, j]]]}];
These coordinates are now graphed as little red cubes in a composite plot. See Figure 1a.
pqcompositeplot = Show[Graphics3D[Table[{RGBColor[1, 0, 0], Point[pqplotpoints[[i, j, k]] ]}, {i, Length[pqplotpoints]}, {j, Length[pqplotpoints[[i]] ]}, {k, Length[pqplotpoints[[i, j]] ]} ]]] /. Point[pt_] :> Cuboid[pt + {0.1, 0.1, 0.1}];
Figure 1a shows us how De Morgan values for {p, q} are distributed in the rule space.
The values are, for the most part, found in the corners of a cube.
Taking subsets of the pqplotpoints coordinates we can generate plots for the 16 components that make up the composite plot in Figure 1a. See Figure 1b.
pqcomponents = Table[Graphics3D[Take[pqcompositeplot[[1, i]], 16]], {i, 16}];
Show[GraphicsArray[{Partition[pqlayers, 4] [[#]]}], DisplayFunction -> $DisplayFunction]&/@Range[4];
Figure 1b helps in identifying detail features of composite plot Figure 1a.
As one example of this, the third cube in the first row of figure 1b plots a set of 4 clusters in each of 3 corners of the floor of the cube together with another set of 4 clusters found in the corresponding 4th corner of the ceiling.
Eight of the 16 cubes in Figure 1b have this configuration.
In the same figure, in the third cube in the second row, there are a pair of 4-set clusters in opposite corners on the ceiling and also on the floor. But the corners on the ceiling and the floor are also opposite one another.
Two of the 16 cubes in Figure 1b have this configuration.
In Figure 1b there are also cubes with the sets of clusters confined to the diagonal planes.
Four of the 16 cubes in Figure 1b have this configuration.
Finally, the ceiling and the floor each have a configuration of 4-set clusters in the corners.
In summary: This structure manifests a variety of clusters, complex and highly ordered, sometimes confined to a plane, but other times traversing planes. As such it is not anchored to any one axis window of the cube.
Posted by: Lawrence J. Thaden
Set {p, r} has 4 sets of 16 distinct clusters of rules within the cube.
One set is on the ceiling. Another is on the floor. Then there is one set on each diagonal plane as viewed through the x-axis window of the cube. See Figure 2a. Mappings are repetitious as can be seen in Figure 2b.
In summary: This structure manifests no variety in the clusters. They are very ordered and simple. They are uniformly spaced within the planes to which they are confined. There is repetitious mapping. The structure itself is anchored in the x-axis window of the cube.
Posted by: Lawrence J. Thaden
In set {q, r} there is a uniform distribution of rules on the ceiling and floor of the cube.
This same uniform distribution is seen in the diagonal planes as viewed through the y-axis of the cube. See Figure 3a. Mappings are repetitious as can be seen in Figure 3b.
One curious observation: There are four repetitions of the map for one of the diagonals while only two for the other cross diagonal.
In summary: This is the simplest of the three structures. No clusters. Everything confined to the planes. Uniform distribution of rules. Repetitious. Anchored in the y-axis window of the cube.
Posted by: Lawrence J. Thaden
Figure 4a, 4b, and 4c show combinations of the plots for the three sets: {p, q}, {p, r}, and {q, r}. There are three views. Each intended to highlight the presence of one of the three sets.
This inquiry into De Morgan’s Laws and their generalization led to the discovery of three sets of ECA rules based on AND[p, q] and OR[p, q], AND[p, r] and OR[p, r], and AND[q, r] and OR[q, r].
We found that each of these sets of ECA rules has distinct structural characteristics when viewed in the context of their outer products and projections in three-space using the map function.
This leads to the conclusion that the ECA rules submit to a categorization according to structural properties just as much as they do to the NKS class categorization according to behavioral properties of cellular automata.
The question now arises: What effect, if any, do structural characteristics have on the behavior of ECA rules at each step of a CA run?
Will rules dominated by the influence of AND[p, q] and OR[p, q] manifest their structural characteristics in some regular and detectable way?
For example, we saw that one of the structural characteristics of the {p, q} set is that it is not confined to a plane. Will this manifest itself in some consistent behavioral way during the execution of cellular automata with rules dominated by an influence of the {p, q} set?
Whatever the answer, it is not an obvious one. Perhaps this is due to a major difference between the dynamics in projections of outer products using the map function and the operation of the CellularAutomaton command.
The CellularAutomaton command cycles its output back in as input. The map function in this context does not.
Certainly the parallels between NKS class characteristics and structural characteristics of the ECAs that we have examined are intriguing.
CA classes of behavior:
Class (1): Very simple behavior; uniform final state.
Class (2): Same or repeating simple structures.
Class (3): More complicated random behavior.
Class (4): Localized structures interacting in complicated ways. In some ways ordered and in others manifesting randomness.
Unique De Morgan set structure:
{p, q}: Variety of clusters; complex and highly ordered; sometimes confined to a plane, but other times traversing planes; non-repetitious; not anchored to any one axis window of the cube.
{p, r}: No variety in the clusters; very ordered and simple; uniformly spaced; confined to planes; repetitious; anchored in the x-axis window of the cube.
{q, r}: No clusters; very ordered and simple; confined to the planes; uniformly distributed.; repetitious; anchored in the y-axis window of the cube.
Posted by: Lawrence J. Thaden
Those five clues listed at the end of the 12-21-2006 http://forum.wolframscience.com/sho...15&pagenumber=1post, De Morgan Generalization, were actually misleading.
For instance, to suggest that there would only be 19683 sets of AND[p, q] and OR[p, q] substitution rules in a system with 7.6 trillion rules is unimaginable.
The confusion arose from failing to realize that De Morgan’s laws are characteristic of traditional Boolean logic, not logic in general. So, if we expect to see similar characteristics in three valued logic, it will have to be the way we see ECA behavior in three and higher valued logics. That is, we should expect to find it emulated in clusters all along three space.
Indeed, if you start executing a test for De Morgan’s laws in three space starting with 0 as the AND substitution rule and 7625597484986 as the OR substitution rule, you will find that there are billions of pairs of substitution rules that pass De Morgan’s laws tests.
These rule numbers have a difference pattern, the union of which includes at least:
{3, 57, 1515, 40881, 1103763, 29801577, 804642555, 21725348961, 586584421923}.
And just as the ECAs for AND and OR have emulated cellular automaton behavior billions of times in three space, so expect to see similar emulations of the results of combining AND and OR substitution rules in the De Morgan formulations.
If there is an analog to De Morgan’s laws native to three valued logic, anticipate that it will be limited to 19683 sets of triples of operations instead of pairs. Two of the operations will be AND and OR. But the third operation will be an, as yet, unidentified operation.
One clue behind this conjecture is the parallel between traditional Boolean logic’s