Lawrence J. Thaden
Registered: Jan 2004
Posts: 355 
De Morgan Generalization for AND[p, r] and OR[p, r]
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 02122007 at 02:29 AM
Report this post to a moderator  IP: Logged
