source file

Printer-friendly version

Unit 12.3: Boolean Logic for Intro Robotics

Objectives for Unit 12.3

  1. What is Boolean Logic?
    The student will be able to:
    1. explain how boolean logic applies to computers
    2. use a boolean expression as a loop condition
    3. use a boolean expression in an if-statement
    4. use the four basic operators( and, or, xor, not) in a boolean expression
    5. calculate a truth table for a simple boolean expression (might be too advanced)
  2. Differentiated instruction: using MultiMedia Logic simulator (tutorial by James Larson). The student will be able to:
    1. wire together gates to form complex boolean expressions and test them.
    2. use De Morgan's laws, create equivalent circuits, calculate using De Morgan
    3. use the Distributive laws, create equivalent circuits, calculate using the distributive laws.
  3. view demo of tic-tac-toe
  4. How Boolean Logic relates to set theory.

Student/Teacher Resources

student:

  • look at flow charts: decisions and processes. A decsion involves a boolean condition
  • What do True/False look like inside the computer?

what is a bit? A bit is a unit of information which can only have 2 values 0, 1
graphics -- a picture of a light bulb/LED which is on or off.
how do computers do complex tasks using 0's and 1s'?
**need graphics**

teacher: One question that comes up frequently is how computers can do complex tasks such as play chess, search the web, and drive automobiles when all they can represent is 0's and 1's? In order to answer that question, we must understand logic, and in particular, Boolean logic which operates on 0's and 1's. Note that we could use other symbols for these two values, for example, F and T or False and True. Inside a digital computer, they are represented by different voltages, one high and one low. It can be represented by a switch with only two positions. It can be represented by a valve which is on or off. Daniel Hillis built a computer out of Tinker Toys. It is now in the Boston Museum of Science. You can also look at his book The Pattern on the Stone

student: Powerpoint slides showing the NXT-G interface for creating a loop

Slide showing a diamond decision with a condition that is a boolean expression, e.g. ultra sonic sensor value greater than threshold, less than or equal to threshold, 2 line sensors (boolean), touch sensor (boolean)

Sentence linking line-finding using IR sensor with Boolean Logic

Slide showing standard operations: and, or, and not with symbols
show a picture of two doors (gates or switches) in series, in order to pass through, they both need to be open

teacher: With numbers, the standard operations are +, -, *, /, i.e. addition, subtraction, multiplication and division. However, with Boolean values, there are three primary operations called and, or, and not, which are often written as ∧, ∨, and ¬

student: The way that we describe these operators is with something called a truth table. The simplest of the three is not and it has the property that

¬0 = 1

¬1 = 0

In other words, it just flips the values. Just as with numbers, a double negative is equal to the original value. The table for ¬ looks like this (we often use letters like p and q to represent variables in Boolean logic): what pictures would help? Doors, gates?

p | ¬p

-----------

0 | 1

1 | 0

student: The truth tables for and (∧) and or (∨) are (with pictures of doors)

p | q | p∧q

-----------

0 | 0 | 0

0 | 1 | 0

1 | 0 | 0

1 | 1 | 1

p | q | p∨q

-----------

0 | 0 | 0

0 | 1 | 1

1 | 0 | 1

1 | 1 | 1

teacher: In order to understand a truth table, the students must understand what a boolean variable is. Since p and q can each have two possible values, the total number of combined values is four. So the table has four rows. It helps to write them in a systematic order, starting with p=0, q=0. The order here is the same as counting in binary: 00, 01, 10, 11. Sometimes in symbolic logic, T and F are used as the values and the table may start with p=T, q=T which would normally be 11.

Computer hardware

teacher: Modern digital computers are built out of transistors and wires, but it is possible to use other materials. For example, Danny Hilles built a computer with Tinkertoys, and it is now in the Museum of Science, Boston.

Boolean Logic and Set Theory

student: Here are some pictures of sets.
A set of triangles, a set of faces, a set of words

teacher: Most of the sets we deal with in this book are finite, which makes them easier to visualize. Often we can use Venn diagrams to draw them.
Here is a Venn diagram which has the set U = { Hellen, Sam, Annie, Jordan, Jonah, Jeremy, Zoe}, and two subsets A = {Hellen, Sam, Annie}, B = {Annie, Jordan, Jeremy} A and B are colored red and blue.

U={1,2,3,4,5} and two subsets A={1,2,3} and B={2,3,4}, When we talk about relations between sets, we often require that they be subsets of the same universal set U. Define subset, proper subset.

 

Union and Intersection

Two operations that we can perform on sets are union ∪ and intersection ∩. You can remember the symbol for union because it looks like a U. Look at the Venn diagram with A and B. The union of A and B, A∪B, is the set of all elements either in A or B, so it is exactly the set shown in the next figure as magenta (purple). The intersection of A and B = A∩B is the yellow set of elements simultaneously in both sets.
Add more figures to illustrate this (3)

Note that union corresponds to the or operation on boolean values true and false. That is, x is in A∪B means that x is in A or x is in B. Also the symbol for or ∨ is similar to the symbol for union ∪
The symbol for and is ∧ which is similar to the symbol for intersection ∩
The symbol for or is ∨ which is similar to the symbol for union ∪ because they are connected.

Complement

The complement of a set A is everything that is in the universal set which is not in the set A. The next Venn diagram shows the complement of A. There are several possible symbols for complement. Some writers put a bar over the variable (usually a letter) A others us a minus sign or ¬ in front, -A, ¬A

Exclusive Or (XOR)

There is an exclusive or in boolean logic, so there must be a similar operation for sets. This is sometimes called the symmetric difference. We know what it should look like, see the Venn diagram. We could write this as (A - B) ∪ (B - A), but we need to define A - B, the set difference.

Assessments

  1. calculate the truth table for ¬(p ∨ q)
  2. calculate the truth table for ¬(p ∧ q)
  3. calculate the truth table for (p ∨ q) ∧ r

Boolean Challenge or Advanced Labyright Challenge

The robot must find its way through the maze: when it comes to an intersection, it must turn right, go straight or turn left, depending on which path does not have a black line across it, i.e. it cannot cross any lines. It does not know the map beforehand.

Addtional Teacher Resources