Registered: Jan 2004
Posts: 350

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

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-02-2007 at 02:32 AM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-12-2007 at 02:29 AM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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}

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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}.

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-16-2007 at 12:56 AM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 02-16-2007 at 02:28 AM

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

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 16 pairs of AND and OR rows each with 16 substitution rules and three valued logic having 19683 triples of rows each with 19683 substitution rules. Just as 16^2 accounts for all 256 rules in traditional Boolean logic, 19683^3 accounts for all 7625597484987 rules in three valued logic.

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

Registered: Jan 2004
Posts: 350

It is possible to construct a compound expression using three color rules that relates the components to each other in a way analogous to the way in Boolean logic that De Morgan’s laws relate lattice complements of two variables to expressions using the rules for AND and OR.

De Morgan’s laws state the relation for variables {p, q} this way:

NOT[AND[p, q] == OR[NOT[p], NOT[q]] &&

AND[NOT[p], NOT[q]] == NOT[OR[p, q]


The three color analog states the relation this way:

NOT[sAND][p, q, r] == POS[sOR][p, q, r] == NEG[sOP][p, q, r] &&

NEG[sAND][p, q, r] == NOT[sOR][p, q, r] == POS[sOP][p, q, r] &&

POS[sAND][p, q, r] == NEG[sOR][p, q, r] == NOT[sOP][p, q, r]

Notes:

All three variables are used. However they may be any rule number so long as the rule number chosen is the same for each occurrence of variable p, q, or r. Indeed, even if the same rule is used consistently in place of more than one variable, the relation holds true.

Lattice complements of the variables are not the subject of the relation. In fact sAND, sOR, and sOP give the same results whether the variables are {p, q, r} or {NOT[p], NOT[q], NOT[r]}.

Rules are prefaced with the letter “s”.
This seems appropriate for two reasons:

(1) Base three digits of the rule numbers are symmetric, as shown below where a single digit at the center of the list breaks the pattern of like digits on each side.

(2) Cellular automata for the analog to De Morgan's laws appear to always be simply class 1. (But see note at end of post.)

Here are the rule numbers together with their digit lists:

sAND = 1594323

{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}

sOR = 7625594296340

{2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2}

sOP = 3812800336816

{1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1}

The third rule, for lack of a name, is simple called sOP for operation.

Complements are expressed by NOT, POS, and NEG.

NOT identifies the lattice complement. It is the complement with respect to negative multiplicative identity which is rule 7625597484986.

POS identifies the complement with respect to positive multiplicative identity which is rule 3812798742493.

NEG identifies the negative. It is the complement with respect to additive identity which is rule 0.

Attached is a notebook set up to demonstrate this analog and display cellular automata associated with its component expressions.

This note added June 4, 2007:


This is not to say that only class 1 CAs result from these De Morgan analog expressions.

For example,

sAND = 5648590730114;

ArrayPlot[CellularAutomaton[{map[pos[sAND],
2490849336603, 1445703670749, 277344820106],
3, {{-1},{0}, {1}}}, {{2}, 0}, 27], ImageSize->{75, 75}];

generates a CA with rule 6640711648789, which has the same structure as class 4 ECA rule 137, but with grey wherever ECA 137 has white.

Attachment: three color de morgan analog.nb
This has been downloaded 1171 time(s).

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 06-04-2007 at 05:14 PM

Report this post to a moderator | IP: Logged