Lesson 4: Boolean Logic
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt. This lesson and supporting materials may be copied for nonprofit educational use only.

Motivation:

We have examined the way in which 0s and 1s can be used to represent values in a computer. The next thing we need to talk about is the manner in which we can use 0s and 1s, together with simple operators, to accomplish various computing tasks. It is useful to think of the value 1 as "TRUE", and the value 0 as "FALSE". Used in this way the 0s and 1s are called Boolean values (after the mathematician George Boole).

Materials:

  1. Five dice per small group of students.
  2. "Dotsy" scorecards.
  3. Overhead showing the behavior of boolean logic gates.
  4. An example circuit overhead.
  5. Elwood circuit exercise and solution, one per student.
  6. Voting circuit exercise and solution, one per student. (optional)
  7. Mystery circuit handouts, one per student, and solution handout.

Lesson Plan:

  1. Introduce the lesson by explaining the Motivation (above).
  2. Game #1: George Boole Says. This is played exactly like the game "Simon Says", except that the instructions use the special words AND, NOT, and OR. For example you may say something like, "George Boole says put your left hand on your head OR put your big toe in your mouth", or "George Boole says put your right elbow on your right knee AND do NOT lift your right foot off the ground".
  3. Discussion: The fundamental elements in the game are "AND", "OR", and "NOT". They're not just words! The key to correctly following George's instructions is to understand the use of these operators.
  4. Note that the operators can be put together to form more complex expressions: "8 items OR less, AND NOT a check OR credit card".
  5. Discussion: notice that the meaning of the sentence can be changed depending on where you put the parentheses. Demonstrate this: You can ride the roller coaster if you are NOT under 12 yrs old AND under 48" tall. What does this mean? There are two interpretations: the condition "NOT (under 12 yrs old AND under 48" tall)" is satisfied by a 49" 11-year old, or a 47" 13-year old, whereas the condition "(NOT under 12 yrs old) AND (under 48" tall)" is only satisfied by short (under 48") people who are at least 12 years old.



  6. Game #2: Dotsy. "It takes some practice to read complex phrases. To help us, we'll play a game". Demonstrate one turn of the game. Play alternates between players. The goal is to satisfy the expressions on the score card and thereby earn points. On each turn, a player rolls the 5 dice, decides whether or not to set aside any of the values showing, and then rerolls the unwanted dice twice, setting aside any dice that he/she wants to keep. At the end of these 3 rolls, the player is awarded points if the 5 dice satisfy any of the expressions on the score card. If no expression can be satisfied, then the player earns zero points for one of the expressions. The game is over after 10 turns by each player.



  7. The behavior of the AND, OR, and NOT operators can be modeled using mechanical devices. We usually refer to such devices as "gates". The AND and OR gates receive two inputs and create one output, and the NOT gate receives one input and produces one output. The gates are designed to operate on binary values. These values can be thought of as 1s and 0s, Trues and Falses, Ons and Offs, or Ups and Downs.
  8. If you've borrowed them, or made your own, use the wooden gates to explain how the operators work first, and then use the gates overhead to introduce the symbols for AND, NOT, and OR, and to show the behavior: If both inputs to the AND gate are 1s, the output is a 1, otherwise the output is a 0. If 1 or more inputs to the OR gate are 1s, the output is 1, otherwise the output is 0. (Another way of saying this is that the OR gate outputs a 0 if both inputs are 0, and outputs a 1 otherwise.) Finally, if the input to the NOT gate is 0 then the output is 1, otherwise the output is 0. It is worthwhile to mention the "exclusive or" or the XOR gate. The XOR gate outputs 1 if exactly one of its inputs is 1, otherwise it outputs 0. Put another way: XOR outputs 1 only when the inputs are different. Make sure the students understand how each type of gate works in all circumstances.

    For younger children, you might draw some gates on the floor with chalk or masking tape. Two children act as input bits, each holding either a "0" or "1" sign. They walk to the gate, and the class must decide whether a third child waiting at the gate should continue on as output of 0 or 1. You can chain several gates together (for example, use the car buzzer), where the output of one gate becomes the input to a next gate. For this to work without complication, the circuit should not have any gates whose output is split and channeled as input to more than one other gate (which happens with the mystery circuit.) We've used reversible black/white vests for larger circuit simulations.

    In a computer, the AND, OR, and NOT gates are electronic circuits. One or two input lines will have voltages of either "high" or "low", corresponding to 1 or 0, (true or false); the circuit is then configured so that the voltage on the output line is "high" or "low" as desired. For example, if the two input voltages to an AND gate are both "high", then the voltage on its output line will be "high". Example 2: If at least 1 of the input line voltages to an OR gate is "high", then the output line's voltage will be "high".


  9. Refer to the rollercoaster example again, but this time state that a person can ride if they: "are wearing shoes AND have a strong stomach." This condition for riding can be enforced using an AND gate at the entrance to the rollercoaster! (You may want to draw a picture of this scenario.) The inputs to the AND gate are determined by the two conditions. If you are wearing shoes, then the first input is a 1; otherwise it's 0. If you have a strong stomach the input is a 1; otherwise it's a 0. The output of the AND gate is 1 if you are allowed to ride; 0 otherwise.
  10. Put up the overhead of the simple Boolean circuit of a car buzzer. Ask the students what it does. Show them how to test the buzzer by writing input values, and having them flow through the gates, writing the correct output value on the wiring coming out of each gate. These in turn become input values to later gates, and so on, until the values have propagated to the final output.
  11. Explain: In a computer this type of circuit exists, but they're too small to see, and getting smaller all the time. Circuits of this sort are usually designed by electrical engineers.
  12. Have the students divide up into groups of size 2 and distribute the description of Elwood. The students should design and draw the Elwood circuit. You might tell them that it is not too different than the car buzzer circuit. Make sure that each gate has just two inputs, and just one output. For younger children, these circuit design activities may be too difficult; In such cases, modify the activity to one of appreciation and understanding, rather than design. Have them trace through the Elwood solution, or as a class, have the children do a walk-through simulation as described above.
  13. You may want to explain the construction of the more complicated Voting Booth solution with the students, if you have time. More advanced students may enjoy solving it themselves.



  14. Game #3: Distribute the mystery circuit and explain that it takes a pair of 2 bit numbers as input. The first input has bits A1 and B1, and the second input has bits A2 and B2. Thus, to input the binary numbers 3 (11 in binary) and 2 (10 in binary), the students should write 1 next to the boxes A1 and B1, then write 1 next to A2 and 0 next to B2. As described above, the 1 and 0 values flow down through the circuit. If a dot is reached, this is a branch point, where the value can go both directions. Ask the students to try different sets of input numbers, and find out what the corresponding output CDE is. (Tell them CDE should be viewed as a binary number.) Answer: the circuit computes the sum of the input numbers, so in the example above, the output would be C=1, D=0, E=1, since 101=5=2+3.
  15. Explain that this is a more realistic example of the way in which Boolean circuits are used in computers. If some students finish this quickly, challenge them to create a 3 bit adder.

Conclusion:

Earlier we looked at wooden versions of AND, OR, and NOT gates. Theoretically we could build the central processing unit of any computer out of wood! Keep in mind though, that the Pentium chip has over a million gates. If each wooden gate is a cubic foot, how big would our wooden CPU be? (Answer: Ignoring the problem of making it work and getting different gates to connect with each other, just the space needed alone would require at least a medium sized building!)

Evaluation:

If you want to assess understanding of the first part of the lesson, have each student come up with a couple of their own dotsy-type expressions to be satisfied by 5 dice. Then ask them to give 2 examples of dice rolls which satisfy each of their expressions (they can even draw the pictures of the dice).

To check understanding of circuits, collect and read the Elwood, Voting, or Mystery exercises, depending on the grade level.

Extensions:

  • Look up George Boole's biography.
  • There are many discrete math books containing lots of fun stuff dealing with propositional logic. See in particular books of Raymond Smullyan.
  • Do the "Just a Usual Day At Unusual School" activity from the MegaMath website.

Standards:

  • NCTM K-4: 1, 2, 3, 4, 13.
  • NCTM 5-8: 1, 2, 3, 4, 8.
  • NCTM 9-12: 1, 2, 3, 4, 12.

Skills:

  • Problem solving / reasoning / communication / connections
  • Sequential and logical thinking
  • Counting
  • Odd/even number recognition
  • Event modeling
  • Understanding compound logical expressions

Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt. This lesson and supporting materials may be copied for nonprofit educational use only.