Introduction to Boolean Logic

Objectives

  1. Be able to construct a truth table
  2. Understand the basics of boolean logic and how it relates to computer programming
  3. Understand the basics of series and parallel circuits, and be able to construct them
  4. Begin understanding the basic parts of a Java computer code

Words to Know

  • boolean logic
  • truth table
  • electric switch
  • series circuit
  • parallel circuit
  • input
  • computer code
  • computer program
  • output
  • logic gate

boolean logic
- a system of symbolic logic used in computers
truth table
- lists all possible combinations (true or false) of the variables (p, q, r, etc)
electric switch
- control consisting of a mechanical or electrical or electronic device for making or breaking or changing the connections in a circuit
series circuit
- one in which the voltage is divided among the devices
parallel circuit
- one in which the voltage is the same across each device
input
- something put into a system to achieve a desired outcome or result
computer code
- a system of symbols and rules used to represent instructions to a computer
computer program
- complied code that can run directly from a computer’s operating system
output
- data generated or produced by a computer
logic gate
- basic elements of a circuit that implement a basic boolean operation (AND, OR, NOT)

Introduction

Most of us use a computer on a daily basis. From emails to surfing the web and cars to cellphones, we increasingly rely on these devices. Most of you, however, have probably never thought about how a computer collects information (input), processes that information (code/program), and provides something that we can use (output).


Part 1: Boolean Logic

To begin understanding of how computers think, we need to only look as far away as the wall. How many of you have turned on a light today? This seemingly simple act illustrates the basis of how computers think. In one position of the switch the light is in the “on” position, and in the other position of the switch the light is “off”.

Now, think about the light being on and off as ones and zeros. Let us represent “off” as 0, and “on” as 1. When we flip the switch and electricity flows to the light and it turns on, this represented by a 1. When we flip the switch in the other direction, electricity stops flowing to the light and this is represented by a 0. So when the switch is 0, the light is 0. When the switch is 1, the light is 1. The light can either be “on” or “off”. It cannot be partially “on” or partially “off”. There are a total of 2 possible outcomes for this scenario.


//image here


Figure 1. The first picture shows a light switch in the “off” position. This is represented by a 0 in “computer speak.” The second picture shows a light switch in the “on” position. This is represented by a 1 in “computer speak.”


Now, what if we have 2 switches? Instead of 2 possible outcomes, we have 4. What are they (The first outcome has been completed for you)?

Outcomes:


  1. Both switches are on.





If we have 3 switches, how many possible combinations are there? If you thought 8, you were right. Fill in the table below with the 8 possible combinations for a set of 3 light switches.

Outcomes:

  1. All three switches are on.








  2. Are you starting to notice a pattern? The number of possible outcomes is always 2 to the power n , where n equals the number of switches.

    Number of Switches and Total Possible Combinations

    1. one switch = 2 combinations
    2. two switches = 4 combinations
    3. three switches = 8 combinations
    4. four switches = 16 combinations

    Table 1. Table showing the total possible combinations for 1, 2, 3, and 4 switches.


    Computers use the same type of logic. This involves a type of math known as boolean logic. Luckily, this type of math does not involve much math at our level. In discrete math, they represent “off” or zero as False and “on” or one as True. So, in the above example, the light switches that were on would be considered True and the switches that were off would be considered False. Have I blown your mind yet?


    In the second example with two light switches, we will represent the first switch with a p (This is a random letter. You could have just as well called it x.) and the second switch with a q. This example had 4 possible outcomes. To organize their thoughts, mathematicians construct tables known as truth tables to predict all possible outcomes. Here is the truth table for two light switches.


    p q In words... F F both off F T p off and q on T F p on and q off T T both on


    Table 2. Truth table showing the possible outcomes for two switches, p and q and what the results mean in words.


    In the example with three light switches, we will call the switches p, q, and r. We can also make a truth table for three switches. Fill in the rest of the “In words...” section of the table. The first one has been completed for you.


    p q r In words... F F F all three switches are off. F F T F T T F T F T F T T F F T T F T T T


    Table 3. Truth table showing the possible outcomes for three switches, p, q, and r and what the first result means in words.


    This is the basis of boolean logic. This is the basics of how computers and electricity work, as you will see in the next section.


    More Boolean logic

    1. Construct a truth table for a set of 4 electrical switches. You can name the 4th switch whatever letter you would like.


    2. In words, write what each possible outcome in #1 means.


    3. Look at the following truth table. Write this table in “computer language”, i.e., using 0’s and 1’s instead of “true” and “false”.

    4. p q F F F T T F T T


    Part 2: Series and Parallel Circuits


    There are many, many ways that engineers, electricians, and computer designers can set up electrical circuits. Almost every type of circuit, no matter how complicated, is based on either a series circuit or a parallel circuit.

    A series circuit is one in which the voltage is divided among the devices. As you can see in the figure below, the lights are connected in series. This means that the power from the battery must be divided to light each bulb. This also means that if one lightbulb goes out, the other will too. This is the problem that occurs in Christmas tree lights -- when one goes out, the whole strand goes out.


    Figure 2. A series circuit.


    A parallel circuit is one in which the voltage is the same across each device. As you can see in the figure below, the lights are connected in parallel. You can see how each lightbulb is getting the same amount of power and if one goes out, the other will continue to work. Most newer Christmas tree lights are constructed in parallel.


    Figure 3. A parallel circuit


    Before we continue, we also need to become familiar with some electrical symbols (Not everyone is a great artist, so engineers developed these symbols so they did not have to illustrate everything.)


    1. Component Symbol

    2. wire
    3. resistor
    4. light bulb
    5. battery
    6. open switch
    7. closed switch

    Table 4. Table representing the various components and their symbols in electrical diagrams.


    The Figure below shows a series circuit (left) and a parallel circuit (right) represented as an electrical diagram. Figure 4. Series circuit with 2 lightbulbs, one switch, and a battery (left) and a parallel circuit (right) with 2 lightbulbs, one switch, and a battery represented as electrical diagrams.


    Now that we have been introduced to circuits and we understand electrical diagrams, we can continue with our light switch examples from Part 1. We will start with the example involving two light switches. Remember, on=true=1 and off=false=0.

    Let’s say that these light switches are connected in series. Looking at the figure below, it becomes clear that for the light to turn on each of the switches needs to be in the "on" position for the current to flow and the light to come on. Any off switch creates a break in the current, and the light will not turn on.


    Figure 5. An electrical diagram illustrating a series circuit with 2 switches.


    We can use our truth tables from before to represent a series circuit: p and q. You can see by looking at Figure 5 that the only way the light will illuminate is if both p and q are on, which means we need p=1 and q=1. For the table below, the only way that the statement “p and q” will be true is if both p and q have values of 1 (true).

    p q p and q 0 0 F 0 1 F 1 0 F 1 1 T


    Table 5. Truth table representing a series circuit.


    Now let’s think about a parallel circuit. Looking at the figure below, you can see that if both switches are open, or off, the lightbulb will not illuminate. However, if switch A is closed (on) and switch B is off (open), the lightbulb will receive power from the battery and light up. Additionally, if switch A is open (off) and switch B is closed (on), the lightbulb will also receive power from the battery and light up. The last scenario, if both switches are closed (on), the lightbulb will also illuminate.


    Figure 6. An electrical diagram illustrating a parallel circuit with 2 switches.


    We can use the following statement to represent a parallel circuit: p or q. You can see by looking at Figure 6 that the light will illuminate if both p and q are closed, if p is closed and q is open, or if p is open and q is closed. If both switches are open, or turned off, the light will not illuminate.


    p q p or q 0 0 F 0 1 T 1 0 T 1 1 T


    Table 6. Truth table representing a parallel circuit.


    These switches form the basis for every computer command. Computers can be off or they can be on. They cannot be partially on or partially off. They also “think” in the language of “true” or “false”, “on” or “off”, “yes” or “no”.


    More on Circuits

    1. Draw an electrical diagram with 3 switches connected in series.

    2. Construct a truth table for the electrical circuit in #1.

    3. Draw an electrical diagram with 3 switches connected in parallel.

    4. Construct a truth table for the electrical circuit in #2.


    5. Part 3: Logic Gates and Computers

      Computer programmers often have to create very complicated codes. In fact, our robots will use codes that are very complicated. We will be able to manipulate them, but we will probably not be able to write our own, new codes. When programmers are stuck, or need more help, they often use truth tables AND Logic Gates to work through their problems. Logic gates are models of circuits. Each gate implements an operation (OR, AND, INVERTER). The three types of gates are shown below.


      Figure 7. Diagram of the three types of logic gates. A and B are known as inputs and Y is called the output.

      These logic gates give programmers a visual representation of some of the possible outcomes in a truth table. For example, the AND gate above, tells a programmer “Y equals A and B”. The OR gate above tells a programmer “Y equals A or B”. And, the inverter gate above tells a programmer to reverse the charge or to output “ Y equals not A”. A and B are known as inputs and Y is called the output. All gates except for an INVERTER gate have more than one input. All logic gates have only one output.


      Let’s try a simple circuit with two logic gates.


      Figure 8. Combination of two logic gates.


      What does the set of logic gates in Figure 8 tell a programmer?


      ____________________________________________________________________________________ If you wrote “Q equals A and not B”, then you are correct! [Note: You could have also written “Q=A and not B”]


      Now, sometimes, programmers have to combine more than two logic gates. This can sometimes get tricky and confusing, so they have to add in parenthesis, so they know what came first (similar to order of operations in math class).


      Let’s try the following set of logic gates.


      Figure 9. Combination of three logic gates.


      We will have to work through this example in steps. The first thing we want to do is find out what each individual gate is producing. Fill in the following:


      D = ________________________________________________________________________________


      E = ________________________________________________________________________________


      Q = ________________________________________ = _____________________________________


      For D, you should have written “D = not A OR not B”. We can simplify this by writing D = not (A OR B). For E, you should have written “E = B AND C”. Finally, Q = D OR E. We could also write out “Q = (NOT(A OR B)) OR (B AND C)”. As you can see, the parentheses are needed in order for the programmer to know what operation the computer will perform first. You certainly wouldn’t want to try and launch iTunes without first turning on your computer!!


      Use the problems in Part 3: Extension to help with your understanding of logic gates.


      More on Logic Gates


      1. What does the following set of logic gates tell a programmer?

      2. E = ________________________________________________________________________________



        D = ________________________________________________________________________________



        Y = ________________________________________ = _____________________________________



      3. What does the following set of logic gates tell a programmer?

      4. E = ________________________________________________________________________________



        D = ________________________________________________________________________________



        Y= ________________________________________ = ______________________________________



      5. What does the following set of logic gates tell a programmer?

      6. E = ________________________________________________________________________________



        F = ________________________________________________________________________________



        G = ________________________________________________________________________________



        Y = ________________________________________ = ______________________________________



      7. What does the following set of logic gates tell a programmer?

      8. C = ________________________________________________________________________________



        D = ________________________________________________________________________________



        E = ________________________________________________________________________________



        Y = ________________________________________ = ______________________________________



      ***************BONUS QUESTION***************

      1. What does the following set of logic gates tell a programmer?

      G = _______________________________________________________________________________



      H = ________________________________________________________________________________



      I = ________________________________________________________________________________



      J = ________________________________________________________________________________



      K = ________________________________________________________________________________



      L = ________________________________________________________________________________



      Y = ________________________________________________________________________________