George Boole

In this module we’ve seen how logic and valid arguments can be formalized using mathematical notation and a few basic rules.  In fact when George Boole (1815-1864) first developed symbolic logic (or Boolean logic), he had the idea that his system could be used by lawyers, philosophers, and mathematicians alike to help put convoluted arguments on a firmer footing.  Little did he realize that his system of “and,” “or,” and “not” operations would one day transform the world by ushering in the Digital Revolution and modern day computing.

What is the connection between logic and computers?  Instead of truth values T and F, digital computers rely on two states, either on(1) or off(0).  This is because a computer consists of many circuits, which are electrical pathways that can either be closed to allow the current to flow, or open to break the connection.  A “1” would signify a closed circuit while a “0” represents an open circuit.

Certain components called gates allow the computer to open or close circuits based on input.  For example, an AND gate has two input wires (A, B) and one output (C).  Electricity will flow at C if and only if both A and B have current.  Traditionally, the AND operation is written like multiplication; that is, A AND B = AB.

Multiplication seems to be a natural interpretation of AND when applied to the values 0 and 1.  Just think about the truth table for the operation [latex]\wedge[/latex], replacing T by 1 and F by 0.

There is also an OR gate.  Again, two inputs A and B determine the output C, however this time C = 1 if and only if either A or B (or both) is equal to 1.  This operation, which corresponds to the logical expression [latex]A \vee B[/latex], is often interpreted as a kind of addition (A OR B = A + B), however it’s not a perfect analogy because [latex]1+1=1[/latex] in Boolean logic.

Finally, there is a gate whose output is the opposite state as its input.  So if the input (A) is 1, then the output (C) will be 0, and vice versa.  This is called the NOT gate.  You have encountered “not” as the logical expression [latex]\sim\!\textrm{A}[/latex], but  the usual notation in computer science for NOT A is [latex]\overline{\textrm{A}}[/latex].  The gate along with its truth table shown below.

Moreover, numerical values can be represented by a string of 1’s and 0’s in what we call binary notation.  Then the basic operations of addition, subtraction, multiplication, and division of binary number can actually be accomplished using the right combination of gates, in other words by Boolean logical operations.