Boolean Operators

Dr. Todd Rowland
todd_rowland@wolfram.com
Wolfram Science Group
http://www.wolframscience.com/reference/education/

Description

This lesson introduces rules with descriptions slightly more complicated than those we met in the Lesson on Unary Functions. These rules change a bit depending on its color and that of its right neighbor. Some of these exhibit behavior we saw in the last lesson, but do new things and they correspond to the boolean operators.

Pre - requisites:

Introduction to Digital Information

Unary Functions

Objectives

Materials:

Graph Sheet

Computers

Further Notes:

From NCTM  http://www.nctm.org/standards/

Note:  By counting the right neighbor dependent rules, we set up the counting problem of the elementary cellular automaton later.

Note:  Consider the function being the growth of "Or" (polynomial, actually linear).  Consider the growth of the other rules.  Consider the number of black cells on row t.  For Xor, consider the function f[n]==nth value t such that on row t all black's are consecutive.

Note:  For the functions above, determine why they are in that class.  Cyclic behavior implies cyclic functions.  Rule's behavior implies the properties of the functions in  question.

Note:  Understand behavior of Or operator.  Understand Shift operator.

Note:  From graphics, determine the function types in above notes.

Note:  Use of {x,t} to talk about locations of the xth bit in row t.

Note:  Identify Shift operator as a translation.

Note:  Possible statistics.  How many white cells?  How many black cells?  What is the percentage?  How does it change?

Note:  Conjecture which operators are finite or cyclic.  N.B.:  Xor is neither, making it a nice case for a discovery teaching method.

Note:  Proofs for cyclic and finite behavior are reasonable tasks.  Proofs of comparisons to neighbor independent rules from last lesson are reasonable.

Note:  Given observations of growth or other patterns, express it in terms of known functions.  Or, And, Mod 2 (the even or odd function), can all be used to predict behavior at {x,t}.   Linear functions, (2^t), Log[2,t] can be used to describe functions in the notes above.

Note:  A graphical array of these rules makes a nice summary, as well as a good reference.

Background:

In this lesson we begin to explore rules which depend on their neighbors.  The next simplest case is when a bit changes depending on its value and the value of its right neighbor.

When one represents the bits by saying 0 is False and 1 is True, these operators correspond to boolean operators.  Some of these correspond to words in the English language.  For instance,"And" is the rule that gives True only when both inputs are True.  In our graphical representation, black is the result only when both inputs are black.

The "Or" operator gives True when at least one of its inputs is True.  It gives False only when both of its inputs are False.In our graphical representation, black result when either of its inputs are black.  Note that the English usage of "or" is ambiguous when both inputs are True.  We arbitrarily use the convention that when both inputs are True the result is True.  This convention is commonly used in computer science and mathematics.

We are using these operators as rules,as we continue our survey of the simplest rules.  So we apply them repeatedly to strings and see what behaviors result.  Some do the same things we saw in the last lesson (neighbor independent rules).  Others are the same as before except there is a shift going on.

Whenever one rule can do what another one does, that is called emulation.  Emulation is one of the fundamental concepts in a New Kind of Science, as well as part of the foundations of computer science.  Because these rules are so simple, we will be able to understand exactly why emulation happens.  In later lessons, we may see evidence of emulation, but it will be more difficult to show exactly why it is happening.

We will also see a couple examples of new behaviors which we will analyze.  Other new behaviors will be left to analyze in future lessons (or group projects, homework, etc.).

Procedure:

Left Shift Operator

If both inputs are white we will we get a white output value.

If the right neighbor of the white input is black , we receive a black output.

If the right neighbor of a black input is white, we get a white output.

If both inputs  are black we will we get a black output value.

[[Comment: You should have observed that the output (or output value) of each particular case depends only on its right neighbor.]]

Comment: This 2 by 2 matrix summarizes the four different Cases. Inputs are designated by the little squares - we have 2 row and 2 column inputs- whereas the outputs are represented by the inner "big" squares. Something worth pointing out is : regardless what the row inputs are, the column inputs prescribe the color of the outputs. This is why the first column of outputs is black and the second column of outputs is white.

Let us apply this operator to the following initial condition for 5 steps.

Comment: If there are no black cells in a row at step 1 , we end up with a "white only" evolution.

Let us start with 2 black cells in a row.

Questions:

Hint: One needs a left neighbor dependent rules....

Realize the answer depends on the initial condition, so there are two separate cases.  (The same question can be asked for any of the rules).

Assessment:

Assessment questions are embedded in the procedure section for this lesson.