Replacement Rules

Overview

There are lists of what Professor Epp calls "laws."  I suggest you think of these "laws" as replacement rules. This is something a programmer can understand. We hope thinking about replacement strategies  might help towards clearer understanding of the profoundly formal nature of algebraic, logical, set-theoretic, or number theoretic manipulations.  We hope the unity of what is being done here becomes more manifest and makes learning easier.  We have rules for three fundamental structures we study here, two of which, set theory and the propositional calculus of chapter 1, are embraced by the grander status of the "Boolean algebra."  These are all RULES for handling expressions which are nothing but strings, strings, just strings of symbols.  But, not all strings can be, for example, algebraic expressions.  As you know, algebra manipulation programs like Maple or Mathematica do not read meaning into the expressions you ask these programs to manipulate.  

I. Rules for the Real Numbers

The first list,  which Ms Epp says is "our starting point," is  Appendix A.  The title of Appendix A is "Properties of the Real Numbers."  It is possible to give proofs for all of these rules from a much more fundamental starting point, such having only the arithmetic of natural numbers and some rules for good logical conduct, which is the subject of Chapter 1.

II. Rules for the Propositional Calculus

The second list is on page 14. It is called Theorem 1.1.1,  Logical Equivalences.  She has given proofs for each of these 11 items.  She also (2nd paragraph below the table on page 14)  calls them "general laws of thought that occur in all areas of human endeavor."  If this is so, then there seems something circular here, for don't we need the general laws of thought if we are to "prove" each of these items giving us  "the general laws of thought?"  So, if something in this text or anything I or anyone else says is not clear to you, it may in fact be a kind of loose speaking that does help either you or me to see what is going on. So, I would ask what exactly what does she mean by "logical equivalences."  Perhaps what she says in the last sentence before Example 1.1.15 helps:
  "They can also be used in a formal way to rewrite complicated statement forms more simply."
  It may help to think of the equal sign as a replacement rule.  
  As usual an example can help.  Look at Example 1.1.15.  Ah!  You start with a certain complicated expression, and use these rules as rules for replacement until our expression is simpler.  Note:  these replacement operations are entirely formal since I am not once thinking about the meaning of the symbols. In peforming such formal calculations, we need not think of p a simply a variable that can be assigned some statement, but more simply as just a Boolean variable which can take only the two values True or False.  It is all so formal, in fact,  it can be programmed to do all of this without human intervention!  We will soon see  how easily this can be done. You will be amazed!  The computer has no concern for the meanings of our statements.

III.  Set Identities (page 272).

Uh,oh . . . deja vu . . . the list of set indentities on page 272 under Theorem 5.2.2 is very similar to the list of logical equivalences on page 14.  If you replace "set" by say some Boolean variable, union by ∨ = "or", intersection by  ∧ = "and", complement by ~ = "negation",  and so forth.  Note also, there are the old De Morgan's Laws, number 9!  This is no coincidence!

IV.  Boolean Algebras (page 288-289)

We are now looking at Theorem 5.3.2, Properties of a Boolean Algebra.  Note the word "a".  Notice that Theorem 5.3.2 follows from a definition, the definition of a Boolean algebra.  But more importantly, notice the similarity of the replacement rules for set identities and the propositional calculus.  The rules for manipulations of expressions for ANY Boolean algebra are formally the same!  Boolean calculations are at the heart of chip design, since they are made up of pieces that are either on or off, or True or False. And they also govern the flow of any program.  Notice also that just from the rules alone, you can prove things which will be true for ANY Boolean algebra.  For a sample, see the proof on page 289 which proves for any Boolean algebra, a statement like the union of a set and its complement is the universal set, or (for propositions) p v ~p = t, a tautology.
Ms. Epp makes note  near the bottom of page 289 of the distributive rules for Boolean algebras, and she writes:
a)  a + (b*c) = (a+b)*(a +c), and b) a*(b+c) = a*b + a*c.  
Please also make note that the plus (+) and the times (*) having nothing (no, nothing at all) to do with arithmetic!  They could be the binary operators  for sets or propositions.  Now rule a) is incorrect for arithmetic, although  rule b) is correct.   BIG DIFFERENCE!
The use  of rule a) is a very common mistake in algebra of the ordinary kind  and arithmetic.  So, I ask, do those students that make that mistake think that arithmetic has the same rules as does a Boolean algebra? (Just a little joke, perhaps, but I think in the back of their minds is the sense that the plus operation and the times operation should have some symmetry.)  It is does not.  Arithmetic is NOT a kind of Boolean algebra. In the City of ARITHMETIC, visitors trying to use rule a) are immediately arrested and jailed.   Every city his its own laws you know!

Where does algebra live?

Algebra lives in the cloud covered peaks  looking upwards  into  the high heavens.   Descartes in the 17th century was the first to use algebraic methods to solve geometric problems.  Geometry is of the earth, for the prefix "geo" still speaks of the earth.  Those of us who took geometry classes in high school know the difference between geometry and algebra. Descartes meditations on the meaning of this difference is now nearly inseprable from our thinking.  For this is thought to be the one to divide our world into two quite different parts, the world of the mind and the world of things, and the first to develop methods of simply manipulating symbols without knowing anything of the meaning of those symbols.  The first he called res cogitans, things that are products of  thought, and the second he called res extensa, things that are products of this our  touchable, seeable and hearable world--in short, the sensible world.  

What do we do when we do calculations, as Ms. Epp says, "in a formal way?"  What do you do when you solve a word problem?  You first work to frame the problem in a symbolic way. This is our most creative moment.  In doing so, it is as if you have climbed from the earth into the sky.  The clouds you see are now symbols with no connection to the earth.  They are mere strings stored in a computer. You move them to and fro by certain rules.  This is called string manipulation.  And only as a final step, you take those strings, interpret them as statements about numbers (this is called evaluation of an algebraic expression by substituting actual values in the variables) and climb down to the earth below and see what these calculations revealed about our sensible world. So it is thus written by Descartes.  Here is a typical (so called word) problem that seems to show up on IQ tests (but don't be concerned you did not see the answer, it seems many miss it):   

A Little Example

A 10 mile race track is run by two runners, Charles who maintains a steady 10 mile/hour pace, but Mike runs the first five miles at a steady 9 miles/hour and the second at a steady 11 miles/hour.
Question:  Do they arrive at the same time? And if not, who wins the race and by how much is the win?  Is the average speed for both  the same,  10 miles/hour?
We climb the ladder and actually calculate the time for Charles, call it tc, and the time for Mike, call it tm.  We have an algebraic formula for the relation between a constant speed, time and distance: d = s * t.  Up here, in the clouds, we allow some computer program to do the calculation, but we could do it by hand.  We must be careful to use the right rules of arithmetic, that is, we must know how to add fractions (outputs are in the light yellow boxes):

tc = 10/10
tm = 5/9 + 5/11

Perhaps this was a surprise.  Or maybe it was obvious to you without this little calculation. We could conclude that in general a steady consistent pace yields better results than an erratic pace that appears as if it had apparently the same average speed (the average speed is, in fact, NOT the same--see below).   The difference between Mike's time and Charles' time in minutes and returned as a real number (rather than rational) is (I forced the return value to be real by writing 60 as 60. making 60 a  real number) :

(60.)*(tm -tc)  

The answer to the third question about the speed  is delicate.  Maybe you just thought the average speed was just the average of the speeds.  No, no, if you thought this, you are not thinking critically, you are not thinking carefully enough.  It requires clear and critical thinking about exactly what you mean by average speed.   Some have said to me that  if you take a trip and your speed is 40 miles per hour for half the distance and then 60 miles per hour for the next half, then the average speed is 50 miles/hour. (Did you think the average speeds of Make and Charles were both 10 miles/hour?) This is incorrect.  Is it intuitively obvious that it is incorrect or is it easier to see with a calculation?  A calculation has a kind of decisiveness about it. You can show it to anyone who knows a little arithmetic and what the average speed means; it leaves little doubt for those who follow the argument, step by step.  Here is a little calculation for our problem:
Average speed is the distance divided by the time you took for the trip.  Why?  Is not this the "formula"  you use when someone asks you for your average speed?    So, for Mike, this is:  d/t = 10/(100/99) = 9.9, slightly under the average speed of Charles which is a constant 10 miles/hour.   Hence, the averages speeds of the two runners are NOT equal.

Question for thought:  Had someone said to you that their speed was 40 miles/hour for the first hour and then 60 miles/hour for the second hour for an entire trip, would their average speed then be 50 miles/hour for the whole trip?  Whatever your answer, can you clearly explain it to someone else?  Are you convinced it is correct?  If your job depends on the correctness your answer, would you stand by it as being correct?

Algebra, the art of using Replacement Rules

You have heard,  for a long time now, about the law of substitution.  Are we clear what this means? I have seen confusion.  Let me try (not original to me) calling a law of substitution simly the application of replacement rules.  Clearer now? (Maybe not.)  True, I have changed a familiar phrase you probably used since high school or college algebra, but I think it might be clearer and closer to our computer language  when you use certain rules for replacing parts of a string by some other given string.  All of us are familiar with  search and replace operations such as those commonly found in word processors.   Programming actual examples will help, but before we do this, let us let Mathematica do some of this kind of thing with its already built in functions such as Simplify or Exand which essentially apply the algebra rules you find in Appendix A to strings.  The input for the expression will be in ASCII, but I have arranged the output to be in the formal mathematical notation you find in textbooks.  Let us start with an expression which we will even name, and call it poly.  Please again recall that the equal sign is NOT equals, but this is an ASSIGNMENT statement that assigns to poly a certain string, so that when you CALL poly, the computer will return the expression.  For example:

poly = (1 + 2x)(3x + 4x)^2 (1 - (2x +3)^2)^2

Notice that it already did a little elementary simplification for us, by replacing (3x + 4x)^2 with 49 x^2.  Mathematica also has a standard order for algebraic expressions, writing them in descending powers, so 1 + 2x gets replaced by 2x +1 by the commutative rule for addition. Now please note the clean traditional textbook formatting of "poly."  The program does nothing (except some very elementary rewriting) to poly unless I tell it to do something.  But  I can apply the string function "Expand" which will apply all the relevant rules from algebra  (in this case it is the distributive law) over and over again until all parentheses are gone.    Notice that "Expand" is a function whose domain and co-domain is the set of polynomials.  Let us apply Expand with the argument poly defined above:

Expand[poly]

Behold!  No parentheses.  How did you do that! And can it be undone?  Yes, by a function called Simplify again acting on some algebraic expression, a kind of string if you like.  What does Simplify do?  The manual says: " Simplify[expr] performs a sequence of algebraic and other transformations on expr, and returns the simplest form it finds."   Of course you the programmer must define what you mean by "simplest."  Again, the list of basic transformations  or rules you find in Appendix A. And to do that, we  must think carefully what we do when we simplify "by hand" such expressions.  Let us take the above expression and perform the string manipulator function "Simplify" on it.   We write it first in ASCII format, use the expression above as an argument for Simplify:

Simplify[1568*x^7 + 10192*x^6 + 25088*x^5 + 29008*x^4 + 15680*x^3 + 3136*x^2]

Notice that this string is not identical to the original string, but algebraically they are equivalent in the sense that 16 *(x^2 + 3x +2)^2 =  (1 - (2x +3)^2)^2.  Remember the equal sign means that you are just looking at a replacement rule, ultimately derived from those given in Appendix A, that says the expression on the right of the equal sign can be replaced by the expression on the left and vice versa.   

Behind the scenes, as it were

Yes, you as a programmer could do this easily in Java, since it has plenty of  string manipulation routines. There are exponents in expressions of the form: (a + b)^n , so we need a rule for expanding powers,  and there is the distributive rule (or law if you prefer) that tells you how to expand products like (a + b)*(c + d), where the b may or may not be there.  If you like, try it by hand, and just observe what you do.  Take something like x*(x + xy)^2  and expand it, observing which replacement rules you used.  You will find you will be using rules like the ones I will write out explicitly below.  I must first  specify that the datatype for the kind of string admissible in the domain of our function must be a polynomial string (see "poly" above for an example of a polynomial string) and second that n must be a positive integer.   Computers cannot read my mind if suddenly the function goes on and on, finally crashing my machine,  just because I forgot to specify that n is a positive integer!  The compiler will not find that error.  This error will  be a run-time error.   You might consider this a teaching lesson for the compiler.  So, let us do it.  
This is an example of actual programming with rules.  It is a bit complicated to swallow at first, but the point is that I can write a routine to apply our rules without the intervention of any human thought. You too can simply very complicated expressions by simply applying the rules as you learned in your algebra courses.
I will write a routine that takes an expression which will be of type polynomial and expands everything in sight, removing all parentheses.  Its name will be "myExpand" and it will be called by executing the commond on an argument named "expression_" where the underscore indicates this is just a place-holder, a blank, a dummy variable that allocates no storage in the computer.  The underscore with a dot, like _. means the dummy variable may or may not be there.   Before this function starts its work, it will check the argument to make sure it is a polynomial datatype, which it does by the query function PolynomialQ.  The notation //. is  POSTFIX  for the command to apply repeatedly the following rules on the actual expression until there are no longer any parentheses.   The notation c_Integer?(# > 1&) tests that the data type for the variable c is, in fact,  an integer and  this integer has a value greater than 1.   The arrow is the key.  It says anything we find here of this type will BE REPLACED BY THE EXPRESSION THAT THE ARROW POINTS TO.  Notice that we have two rules, so we must form a list of rules, hence we place  brackets around the two rules, each rule separated by a comma (oh, the programming languages are so fussy!!). Here is the definition of the function with its two accompanying rules:

myExpand[expression_?PolynomialQ] := expression //.
{(a_ + b_)^c_Integer?(# > 1&) -> a (a + b)^(c -1) + b (a + b)^(c-1),
(a_ + b_.) (c_ + d_) -> a c + b c + a d + b d }

Now let us apply this to our expression whose name is "poly" but which is called by invoking poly.

myExpand[poly]

As we see, it is the same result as we obtained in using the built in Mathematica function. This will work on most anything that is a polynomial (if you try it on something not a polynomial, nothing will happen because of our insistence that the domain be the set of polynomials), even in many variables:

myExpand[(2 +3r + u^2)(11x + 6y)]

Amazing, no?  The point of this exercise is that the application of the rules for manipulating algebraic expressions, propositions,  and set-theoretic identities are all of a very formal nature where you climb up into the realm of res cogitans and simply manipulate strings by certain rules of replacement, transforming one expression into another.  Moral:  KNOW THE RULES AND APPLY THEM CORRECTLY.  DO NOT MAKE UP YOUR OWN RULES AS YOU GO ALONG. Common mistakes along this line are mistakes using the distributive law and not observing the rules of precedence in the ordinary algebra of arithmetic (Appendix A).  
Now can this work on logical expressions?  Of course.  Some functions are already built in.  But we can write all we want for the datatype Boolean.  Things like the calculations in Example 1.1.15  on page 14 can be done  by the application of the rules at the top of page 14. How about sets?  Yes, that too.  Glance at Example 5.3.2 where replacement rules are used to derive a set difference property;  this, too, can be programmed to work on very very complicated expressions and perform the simplifications as fast as it does on much simpler expressions.   

Replacement Rules for Logical expressions

Again, think of Theorem 1.1.1 as a set of rules.  Mathematica already has built in a function which removes all the parentheses in a logical expression.  It is called by invoking LogicalExpand. It will work only if the datatype is of type Boolean.  Here is the simple example of DeMorgan's Law (the sign  ! in most programming languages is the sign for the monary operator  "negation"):

LogicalExpand[!(p || q)]

Here is another example from your text.  Example 1.4.6 on page 53 (which does yield the same answer as in your book).  

LogicalExpand[((P && !Q) || (P && Q)) && Q]

How does Logical Expand work?  The same way as the algebra "expands" works, but using a different set of rules, the rules  listed in Theorem 1.1.1.  

NAND and NOR Gates

This is on page 54 of your text.  Look over the definition and the last paragraph under the table.  The claim is that EVERY logical expression can be written as an expression using ONLY the Sheffer stroke or the Peirce arrow.  The proof for that starts in Example 1.4.7 and ends in the exercises 33 and 34 on pages 56-57.  The replacement rules derived show that any logical operator that we have met so far can be replaced by an expression involving only the Sheffer stroke.  Notice that no one would understand your logical constructions in ordinary speech should you use only the Sheffer stroke.  Looking at 1.4.7 b, try out on yourself what the replacement rule to Sheffer strokes  of "It is raining OR It is hot." to   This is computer-speak, NOT human-speak.  
Why the fuss?   Because this MATHEMATICAL result shows that ANY Boolean circuit can be constructed using ONLY NAND gates which is an implementation of the Sheffer stroke in silicone.  This is exactly how it is done.  See, for example, http://www.doctronics.co.uk/4011.htm.  But there are a lot more references on the net even from Intel concerning circuit design.  This is now the standard way to construct as complicated a Boolean circuit as is your processor on your computer board.  Here is an example with two statements, one of which is true and the other false (check the truth table for Nand on page 54):

Nand[(x==x), (y≠y)]

Visualizing the Structure of All Expressions

Your text gives you a method of visualizing Boolean expressions.  These "circuit diagrams" work not only for Boolean expressions, but for any expression at all!  
All expressions have a structure.  And we can make pictures for them all.  When your compiler parses some statement you have made, it looks very carefully at that structure, and a single misplaced comma or semi-colon or parentheses will result in a compiler error.  You obviously do not have to understand a statement to see its structure or its syntax.   The sections in your text starting around page 47 speak of Input/Output tables for a circuit and their corresponding Boolean expressions.  This is a pervasive theme in all that we do.  If you rotate the pictures  in Example 1.4.3 so that the input is on the bottom, you have a TREE-LIKE figure. In fact, ALL expressions, whether algebraic, logical, set-theoretic or even any English sentence has such a tree structure.  We talk about it here, because this is what you are looking at when you look at the circuit diagrams for a given Boolean expression.  Mathematica can give you the tree form for any expression.  Let us look at the tree structure of Example 1.4.1 , part a).

TreeForm[(!P && Q) || !Q]

Now compare this to the diagram in your text on page 50.  If you like, turn the tree on it's side.  You will notice the only thing missing is the initial inputs of P and Q which wuld be a line from the bottom Not[P] and Not[Q] down to a P and Q as the inputs.  Then the tree above turned on its side would be identical to tree in the diagram on page 50.  Incidentally, this also shows how these circuit diagrams can be drawn just using ASCII code.  Here is what it might look like in vertical position:
Or[|             , |     ]
   And[|     , q]  Not[q]
       Not[p]          |            
     |           q
     p
I have added the symbols p and q at the bottom.  You start at the bottom and work upwards.

Of course algebraic expressions also have their tree representation.  The principles here that use circuit diagrams are the same representation that your author gives for the representation of algebraic expressions, such as Example 11.5.10 on page 716.  I will ask Mathematica to give us the tree form for her expression on page 717:

TreeForm[((a-b)*c) + (d/e)]

Notice that it is more complex than her expression she gives on page 716.  The reason is that there is no separate operation like substraction.   -x is defined as (-1)*x, so subtraction of a from b, a - b is  a + (-b).  And in prefix notation, this is Plus[a, Times[-1,b]].  Notice that -1 is the NAME for the negative number -1, so that the minus sign should not be thought of as an operator.  It is true, however, that -1 = Times[-1,1] = (-1)*1, but the left side, a negative number, is a WHOLLY DIFFERENT IDEA from the right side, which is a negative number (-1)  times a positive number (1).   Let me repeat:  -x is not necessarily a negative number, but is the product of x times the negative number -1. In prefix notation, this is Times[-1, x].  If x = -5, then -x = 5.  
Fractions are handled in a similar way.  The fraction d/e is thought here as d *(1/e), and 1/e is thought to be e raised to the power -1, that is Power[e,-1].  This is usual programming practice, as  in Java for x raised to any power r you would write:  pow(x, r).  So,  d/e = Times[d, Power[e,-1]] in prefix notation.  
Do you see a, b, c, d, and e as inputs at the bottom, and as you read up the various levels of the tree, your calculations are moving from the inner most parentheses to the outermost?

Summary

We entertain here that set theory, algebra, and the propositional calculus are all languages each  having a grammar (see Chomsky's parse tree for an English sentence on page 707)  and rules for correct syntax. We have seen that these expressions can be  represented  as circuit diagrams or trees, which is what a circuit diagram really is. Furthermore, there are  rules such as distributive laws that can transform expressions in each of these languages into other expressions.    These rules we have called replacement rules.  We have looked at some examples of this process in action.  We have shown how a function which acts on expressions can be programmed to  expand expressions in accordance with certain explicit replacement rules.  Expansion simply means removing all the parentheses by the use of replacement rules. All of this takes place high in the realm of res cogitans, the realm where symbols with no connection to the earth are manipulated according to explicitly defined rules.

LEARN THE REPLACEMENT RULES.  PRACTICE USING THEM.

Created by Mathematica  (November 12, 2006)