Boolean Algebra For All (college Students)!

BOOLEAN ALGEBRA FOR ALL (COLLEGE STUDENTS)! OWEN THOMAS

Presented at some conference I think. To the usual deafening indifference I think. ”Algebra for all!” was a catchphrase that year. NCTM? I. Introduction. Consider the college Liberal Arts Mathematics class. The typical population of such a class is extremely diverse—at least, in terms of mathematical (and specifically, algebraical) maturity. Though very few will have actually mastered “high school” algebra, most will have had some exposure to it. Many will have understood a fair amount of the material; many will have understood almost none of it. This is the wrong kind of diversity, of course. Much of the material covered in many versions of the liberal arts course is essentially high school algebra (this conclusion is based on a survey of the available textbooks). The wide range in student preparedness makes it very difficult to pace the presentation in such a course. The result is frustration for the well-prepared, the not-so-well-prepared, and the instructor alike. One method I’ve found very useful in dealing with this “diversity problem” is the use of symbolic logic (also known as Boolean Algebra). This subject gives the instructor an opportunity to present a collection of algebraic ideas—variables, operations, commutativity, associativity, and distributive laws, for example—in a context that’s new to (almost) all of the students. Of course, some will catch on faster than others. In my experience, this will usually include some of the “not-so-well-prepared”—many students who have come to believe that they aren’t “good at math” find logic very natural, and understand the material more readily than their classmates. The experience of being “ahead” in a mathematics class is a richly rewarding confidence builder for such students. Meanwhile, all of the students are getting plenty of practice with the algebraic ideas. The unfamiliarity of the material allows for a fair amount of time to be devoted to routine calculations. (I am assuming here without apology that this is a good thing. After all, algebra simply is manipulation of abstract symbols. This is certainly not to say that Standards-based methods are inappropriate; for example, students working in small groups can benefit by explaining their interpretations of the various symbols to each other.) The methods I intend to describe below are mostly my own, arrived at by trialand-error over a period of a few years. There’s obviously much more to be learned about teaching this material to this population II. Preliminaries. In the beginning is the statement. The crucial idea here is of course, that statements are true or false. A certain amount of time should be devoted 1

2

OWEN THOMAS

to examples of verbal statements and non-statements. However, in my opinion, one should not dwell on reasoning at the level of the sentence for long. Philosophy departments typically devote entire semesters to logic and can afford such luxury; we want to get right into the algebra. Thus, statements will usually be represented by logical variables—typically p, q, r, and so on. Next up are compound statements. This means we’re introducing the logical operations of negation, conjunction, and disjunction (implication can wait). The likeness of these operations to numerical operations should be mentioned frequently: just as “+”, “×”, and so on combine two numbers to produce a number, “∧” and “∨” combine statements to produce a statement. (The logical operations can be related to the more familiar numerical operations using the correspondences: t ↔ positive numbers f ↔ zero ∧ ↔ multiplication ∨ ↔ addition . Thus, for example, t∧f ≡ f “because” positive times zero is positive. I like to mention this correspondence since it tends to demystify the logical operations somewhat and helps students understand what we mean by “operations”. I mention it only in passing, though. This idea isn’t formally part of the course material in that I never ask students to use it on quizzes or exams.) Once the students can evaluate expressions (for example, by calculating that (f ∨ ∼f) ∧ ∼(t ∧ ∼f) evaluates to f), they’re ready to begin working with truth tables. This is a crucial step. It will be necessary to return to this repeatedly. Some of the students will resist learning how to perform these calculations. Others will catch on immediately. Patience is called for. While we’re waiting for everybody to master truth tables, we have an opportunity to explore certain identities like ∼∼p ≡ p and p∧t ≡ p. (The high-tech vocabulary—t is an identity element for the operation ∧ and an absorbing element for the operation ∨; f is absorbing for ∧ and an identity for ∨—might be mentioned in passing, with reference to the similar rˆ oles played by 0 and 1 in the number system. It might be harmful to put much stress on these facts, however. There’s always the danger that some of the students will try to memorize such facts rather than understand what’s going on.) When much of the class is proficient with truth tables, more complicated identities like DeMorgan’s laws ∼(p ∧ q) ≡ ∼p ∨ ∼q

and ∼(p ∨ q) ≡ ∼p ∧ ∼q ,

the associative laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

and

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) ,

BOOLEAN ALGEBRA FOR ALL (COLLEGE STUDENTS)!

and the distributive laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

make very good in-class exercises. I like to write one of each pair on the board and assign the other as seatwork; this gives students a good chance to explain the calculations to each other. III. Algebraic manipulations. Most of the class are comfortable with truth tables by now, but some are still struggling. The next idea doesn’t depend on truth tables, but allows opportunities for practicing with them anyway. Consider identities like (p ∧ q) ∧ (r ∧ s) ≡ (p ∧ (q ∧ r)) ∧ s . The truth table for this identity is inconveniently large. Far better to prove it by algebra as follows: (p ∧ q) ∧ (r ∧ s) ≡ ((p ∧ q) ∧ r) ∧ s ≡ (p ∧ (q ∧ r)) ∧ s . This is harder than it looks. A considerable amount of time can profitably be devoted to grouping symbols and associativity. My presentation is along the following lines: every associative law has the structure: hF ∗ Mi ∗ L = F ∗ hM ∗ Li or F ∗ hM ∗ Li = hF ∗ Mi ∗ L (the operation “∗” might be +, ×, ∧, or ∨, for example). There’s a First, Middle, and Last “thing” (a formula or a single symbol). Before the law is applied, the Middle is “associated” either with the First or the Last; applying the law changes this “association”. Having introduced this machinery, expressions like ((p ∨ q) ∨ (r ∨ s)) ∨ t can, first, be “parsed” as {(p ∨ q) ∨ [r ∨ s]} ∨ t (for example; make the pairs of grouping symbols easier to see by using different shapes). We can then ask, for each pair of grouping symbols, what are “F”, “M”, and “L”, and what happens when we apply the associative law using that particular pair of grouping symbols. With sufficient coaching, students will eventually be able to prove identities like (v(wx))(yz) = v(w((xy)z)) by repeated application of the associative law. This is a good time to throw the commutative law into the mix and assign problems like (p ∧ q) ∧ (r ∧ s) ≡ (r ∧ (p ∧ s)) ∧ q . It probably shouldn’t go without saying that all of these facts are in some sense “obvious”—for instance, that both expressions in the previous equivalence are true if

3

4

OWEN THOMAS

and only if all of p, q, r, and s are true. This obviousness should not detract from the interest in solving the problem as a sort of puzzle; it certainly does not detract from the value of the exercise in understanding the very important algebraic ideas. This is a good time to introduce the implication operation “⇒”. One can define this by its truth table or by p ⇒ q :≡ q ∨ ∼p (I like to avoid using “∼p ∨ q” since this is ambiguous when read aloud). Both the truth table and the identity should be mentioned frequently. Note that “⇒” is neither associative nor commutative. Exercises like p ⇒ (q ∨ ∼s) ≡ s ⇒ (∼p ∨ q) , or (the law of contraposition) p ⇒ q ≡ ∼q ⇒ ∼p , should now be worked out both by truth tables and by algebra. One must take care in choosing such exercises to keep the algebraic solutions fairly simple; it may be wise to avoid requiring the use of distributive, absorbing, identity, or DeMorgan laws at first. IV. Further Developments. Any treatment of symbolic logic should proceed at least this far, in my opinion. Once the class is familiar with implications, there are a number of different directions to go in. For example, one might return to the verbal level and explore argument forms (syllogisms, modus ponens, and so on). This is also a good time to begin study of set theory—the set operations of intersection, union, and complementation are easily explained in terms of conjunction, disjunction, and negation. In particular, I’ve found truth tables to be very useful in explaining Venn diagrams (and am surprised not to have found this idea in the standard texts). Here are a few more ideas for further developments in symbolic logic: The Sixteen Boolean Functions. One of the nice things about logical variables (as opposed to numerical) is that there are only finitely many values that the logical variables can take (to wit, two of them: t and f). It follows that there are only a finite number of operations—i.e., logical valued functions of two logical variables. Students can be asked to find all (sixteen) of them. Or given the various functions, one might ask: which are commutative? which are associative? how can each be expressed in terms of ∧, ∨, and ∼? and such like questions. If the class has already done some set theory, students can match these functions up with the sixteen two-set Venn diagrams. A connection can also be made with binary numbers for classes familiar with those (the sixteen numbers from 00002 to 11112 ). f f f f f

p ↓ q q − p ∼p p − q ∼q p4q p ↑ q p ∧ q p ⇔ q f f f f f f f t t f f f t t t t f f f t t f f t t f f t f t f t f t f t

q p⇒q t t f f t t f t

The Sixteen Boolean Functions

p q ⇒ pp ∨ q t t t t t t f f t f t f

t t t t t

BOOLEAN ALGEBRA FOR ALL (COLLEGE STUDENTS)!

Advanced Calculations. Consider the distributive laws algebraically. Show that one of them can be derived from the other (by repeated application of DeMorgan’s laws). Create a table of identities to be used in deriving other identities. Define the biconditional ⇔ and the symmetric difference 4 by p ⇔ q :≡ (p ∧ q) ∨ (∼p ∧ ∼q)

and p4q :≡ (p ∨ q) ∧ ∼(p ∧ q)

(say), and show using truth tables (easy) and by algebra (hard) that these are associative operations. Show that p4q ≡ (p ∧ ∼q) ∨ (∼p ∧ q) . Or consider the “nand” (or “Sheffer stroke”) operator ↑: p ↑ q :≡ ∼(p ∧ q) . Show how all of the standard logical operations can be described in terms of nand alone. And so on. The possiblilities for interesting calculations are limited only by time and patience. V. Conclusion. No one will have failed to notice that my title is overly ambitious. I haven’t made a case for “Boolean Algebra For All College Students”. I believe such a case could and should be made; but this is not the time or place. I mention here only that the perrenial question “When will I ever use this in real life?” can be realistically answered by “Probably sooner than you think” in our increasingly computer-dominated environment. For example, symbolic logic is useful in using the catalogues of most libraries. I hope I have persuaded some readers of the usefulness of logic as a supplement to, or a replacement for, the standard “high school algebra” material often presented in the college liberal arts course. This has been one of the major projects of my brief professional life; I’d very much appreciate hearing from other teachers about these ideas.

5