Let's Say: A Child's First Calculus

out to Contents
summary of algebraic identities

Topic 8. Boolean in Pancake

8.1 The Boolean values and operators
8.2 Translating between Boolean and Pancake
8.3 DeMorgan's Law
8.4 The "Boolean Duals"
8.5 AND understood
8.6 Operator precedence
8.40 Examples
8.50 Expose an irrelevant variable

"Boolean," from George Boole's name, is pronounced in three syllables, not two, to the rhythm of "chromium" or "Narnian". Don't rhyme it with "too lean."

8.0 "Watchit" Note

The standard view pancake operator we have been using in pancake calculus is a pair of parentheses. In boolean calculus, paired parentheses are used purely for grouping, without any further operation meant.

8.1 The Boolean Values and Operators

The boolean B2 calculus defines two values: TRUE, FALSE, and three operators: AND, OR, and NOT. They are symbolized for calculation thus:

TRUE : 1
FALSE : 0
NOT : ~
AND : * (Don't say "times"--say "and.")
OR : + (Don't say "plus"--say "or.")

Boolean calculus is usually notated in "infix" style, the two-operand (binary) operators *, + appearing between their operands, and the single-operand (unary) operator ~ preceding what it negates (inverts, complements). Parentheses are used only to group parts of expressions; they have no further operator character in boolean. For example, to negate (invert) a large expression such as

g + ~( q * p ),

a new outer pair of parentheses is supplied and the ~ operator is prefixed to the new expression:

~ ( g + ~( q * p )).

However, in digital circuits documentation the ~(  ...  ) syntax is usually replaced by an overbar serving the combined roles of grouping and negation. Thus the overbar is a grouping-inverting operator somewhat similar to the pancake:
    ________
   _____
g + q * p

In digital documentation also, the boolean AND operator is often omitted, just as is the "multiply" or "times" operator in number arithmetic:
_______
____
g + q p

What the boolean operators do is best defined in truth-tables: input values listed on the left, output values listed on the right:

a | ~a
0 | 1
1 | 0

boolean NOT

a b | a * b
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1

boolean AND

a b | a + b
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

boolean OR

From the truth-table for ~a the boolean algebraic consequence ~( ~a) = a ought to be quickly obvious, the counterpart to pancake's doubleflip.

8.2 Translating Between Boolean and Pancake

We now lay out how these all can be modeled in pancake. There are obviously two ways to map value between the two calculi: vizzo=TRUE, and vizzo=FALSE. For Boolean investigations it does not matter at all which translation we use. I find it more convenient to use the vizzo=TRUE translation.

Let's look at a package of Neapolitan ice cream: vanilla in the middle, flanked by chocolate and strawberry. Pancake is the vanilla in the middle. vizzo=TRUE is strawberry, and vizzo=FALSE is chocolate. Or maybe it's the other way 'round -- I sometimes forget.

vizzo=TRUE pancake vizzo=FALSE

1 vizzo 0
0 invizzo 1
~a (a) ~a
a + b a b a * b

Neapolitan ice cream translation rules, incomplete

The alert and suspicious reader will note there's an incomplete issue here: How do we express boolean AND-- a*b --in pancake when using vizzo=TRUE? and how do we express boolean OR-- a+b --in pancake when using vizzo=FALSE translation?

8.3 DeMorgan's Law

DeMorgan's Law (DeMorgan's Rule) gives the answer. It makes a two-faceted claim which we can state verbally like this:

an expression of "terms" coordinated with + may be negated by negating each "term" and changing the coordinating + operators to *

similarly,

an expression of "factors" coordinated with * may be negated by negating each "factor" and changing the coordinating * operators to +

In boolean notation we might write DeMorgan's Law thus:

~( a + b + c + d + ...) = ~a * ~b * ~c * ~d * ...

~( a * b * c * d * ...) = ~a + ~b + ~c + ~d + ...

To obtain our missing translation recipe, restate this slightly by negating both sides:

a + b + c + d + ... = ~( ~a * ~b * ~c * ~d * ... )

a * b * c * d * ... = ~( ~a + ~b + ~c + ~d + ...)

Now consider the 2-variable form of DeMorgan's Law:

a + b = ~( ~a * ~b )

a * b = ~( ~a + ~b )

With these observations in hand we should now be able to complete a set of Neapolitan translation rules, noting carefully how negation is expressed in pancake:

vizzo=TRUE pancake vizzo=FALSE

1 vizzo 0
0 invizzo 1
~a (a) ~a
a + b a b a * b
a * b ((a)(b)) a + b

Neapolitan ice cream translation rules, complete

Let's call the construct, (( ) ( ) ( ) ...) the DeMorgan shell.
Note we may easily build a DeMorgan shell for any number of terms we might have:

((m) (o) (r) (g) (a) (n) ... )

8.4 The "Boolean Duals"

For local purposes it is useful to give an aggregate name to those boolean operators which are inter-transformed in deMorgan's Law: AND, OR. We call them the boolean duals.

8.5 Convention: AND understood

Keep in mind that the modern convention in boolean notation is to let *, AND be the "understood" operator when two boolean expressions -- groupings under parentheses or variables -- appear next to each other with no explicit operator between.

8.6 Convention: Operator precedence (binding)

We must also note an operator precedence convention:

~, NOT binds tightest,
then *, AND,
then +, OR most loosely.

That is, for NOT, ~ to apply to a composite expression, parentheses are required to override precedence: ~(K+L+M).

In "~W+B", then, we are to evaluate "~W" first, getting its result before evaluating with "+B".

In "~WB+G", we are to evaluate "~W" first, getting its result before evaluating "*B". This all before evaluating with "+G". Note that this differs from the comparable convention in numerical algebra, where multiplication binds tighter than negation, as in "-ab+c".

When we want to express the complement of WB, we override the binding with parentheses: ~(WB), meaning ~(W*B).

8.40 Translation Examples

We are now equipped to investigate any boolean expression whatsoever in pancake. The algebra of pancake is easier to learn and is more powerful than boolean calculus, especially on the issue of detecting irrelevant variables.

The irrelevant variables problem is a pesky one when a boolean expression involves more than eight variables, for which inelegant tabular (Karnaugh mapping) and computerized techniques have been developed. You may confidently prefer pancake for any irrelevant variables problem in boolean calculus.

8.40.6 Example

Consider the boolean expression

(r+ ~s)(t * ~(s r)+(u * ~(s+r))), given boolean expression

We let the shallowest-nested Boolean dual guide the modeling choice; this happens to be *, AND. The model in which AND is "understood" is ( )=FALSE; we synthesize OR at need.

Let A*(B+C) = the given expression, where
C= u* ~D,
D= s+r
Then

D --> ((s)(r))
C --> (s)(r)
B= t* ~(s*r) --> t (s r)
B+C = ((t(s r))((s)(r)))
A= r+ ~s --> ((r)s)
A*(B+C) --> ((r)s) ((t(s r))((s)(r)))

((r)s) ((t(s r))((s)(r))), model: ( )=FALSE.

Three appearances each of r, s make us suspect a simplification is available.

There is a trade-off always to be made, however, between expression depth on the one hand, and multiplicity of appearances of a variable on the other. A chip architecture will typically favor one or the other optimization.

Laws of Form presents a "dual" of theorems which say that in any finite expression we may either reduce all variables to a maximum appearance count of two each, or we may reduce the expression to a maximum depth of two, these two properties not necessarily achievable in one and the same reduced form.

The max depth of our expression as it stands is three, and so neither optimization is present.

((r)s) ((t(s r))((s)(r))), model: ( )=FALSE.
=
((r)s) ((t(s r))((s)(r)) ((r)s)), infect
=
((r)s) ((t(s r)) ((((s)(r)) ((r)s)))), doubleflip
=
((r)s) ((t(s r)) ((r)(((s)) (s)))), secret passage
=
((r)s) ((t(s r)) ((r)(s(s)))), doubleflip
=
((r)s) ((t(s r)) ((r))), self-inviz
=
((r)s) ((t(s r)) r), doubleflip
=
((r)s) ((t(s)) r), outfect

The transformed expression now shows two appearances max of any variable.

From an inspection of the algebraic identities, apparently depth reduction is available only by using echelon, a.k.a tower/topple, or XNOR.

8.40.7 Example

The documentation for a section of a semiconductor chip might give the following specification, in boolean:

~(G+ ~M7 J + (A R H)) (M2+M7+R), given boolean expression

Let's see what pancake reveals. Making the AND explicit everywhere, this becomes

~(G+ ~M7*J +(A*R*H)) * (M2+M7+R), AND-explicit boolean

Model choice: We notice that in this expression, the shallowest operator among the "boolean duals" -- AND, OR -- is *. This suggests a ( )=FALSE model, where AND is "understood" and OR will be synthetic:

Let the given boolean = ~x * y, where
x= G+u+v,
y= M2+M7+R.

Then
y= M2+M7+R --> ((M2)(M7)(R))

v= A*R*H --> A R H

u= ~M7*J --> (M7)J

x= G+u+v --> ((G)(u)(v))
~x= --> (G)(u)(v)

~x*y --> (G)(u)(v) ((M2)(M7)(R))

~x*y --> (G) ((M7)J) (A R H) ((M2)(M7)(R)), substituting u, v

We notice variables that appear multiple times: M7, and R. The occurrences are at depths 2, 2 for M7, and depths 1, 2 for R.

Let's abstract the essential formal situation of R:

(f R) (g(R)). No algebraic reduction is obvious here.

Now let's analyze M7's situation:

((M7) h) ((M7) j)
=
((((M7) h) ((M7) j))), doubleflip
=
(((h) (j))(M7)), secret passage

The M7 analysis may be showing an opportunity to avoid routing a signal to two places on the chip at the small cost of a NOT gate.

We discover nothing egregious, anyway.

8.50 Expose an Irrelevant Boolean Variable

Draft 4.0 16Jun2003