Boolean Logic, Gates, and Computer Circuits

Boolean Logic, Gates, and Building Computer Circuits
(revised 02/06/2008)

Since computers are built out of bi-stable electronic circuits, the two-value system of Boolean logic is used in circuit design. Boolean logic has two values: true and false. We used 0 to represent false and 1 to represent true.

Boolean Logic:

There are two Boolean values true and false which are sometimes represented as 1 (true ) and 0 (false).
A simple Boolean expression is an expression that evaluates to true or false.

example : (a < b) or (x == 0)

Compound Boolean expressions are formed out of simple Boolean expression using Boolean operations
Common Boolean operations are AND, OR , NOT , and XOR (eXclusive OR)
In Python use and, or and not, True and False
In C++ && denotes AND, || denotes OR and ! denotes NOT.

Defining AND, OR, NOT and XOR

Although AND, OR, and NOT have the same effect on Boolean values as their common linguistic meaning (i.e. if an "and" joins two sentences, the compound sentence is true if and only if both halves are true), we formally define the effects of AND, OR, and NOT using Truth Tables.

    P | Q | P AND Q      P | Q | P OR Q        P | NOT P      P | Q | P XOR Q
   ---+---+---------    ---+---+--------      ---+-----      ---+---+---------
    0 | 0 |    0         0 | 0 |   0           0 | 1          0 | 0 |    0
    0 | 1 |    0         0 | 1 |   1           1 | 0          0 | 1 |    1
    1 | 0 |    0         1 | 0 |   1                        1 | 0 |    1
    1 | 1 |    1         1 | 1 |   1                          1 | 1 |   0

The fourth Boolean function, XOR (exclusive or) is sometimes included with the other three. The value of an eXclusive OR is true if one or the other but not both of its components are true. In English we say "either P or Q but not both".

Evaluating Compound Boolean Expressions

Example: A leap year is a year which is divisible by 4 and not a century year (i.e. NOT divisible by 100) or is divisible by 400; so 1900 was not a leap year but 2000 was! We can express this as (Year is divisible by 4) AND NOT (Year is divisible by 100) OR (Year divisible by 400)

((Year % 4 == 0) and (not (Year % 100 == 0))) or (Year % 400 == 0)

If Year = 1900 then the above evaluates to (True AND (NOT True)) OR False which equates to False. (Note the use of parentheses to enforce the implicit meaning that you NOT (Year is divisible by 100) first, AND second then OR third. Again if Year = 2000 the expression evaluates to (True AND (NOT True)) OR True which equates to True.

If P, Q, and R are arbitrary Boolean expressions, then a three "variable" expression like (P AND (NOT Q)) OR R has eight possible input configurations for its variables. The Truth Table given below is a way to crank out all possible values of the expression for all possible input values. Note that we first evaluate NOT Q, use it to evaluate (P AND (NOT Q)) which in turn we use to evaluate (P AND (NOT Q)) OR R.

P | Q | R || NOT Q |(P AND (NOT Q) | (P AND (NOT Q)) OR R
---+---+---++-------+---------------|----------------------
0 | 0 | 0 || 1    |    0          |                 0
0 | 0 | 1 || 1    |    0          |                 1
0 | 1 | 0 || 0    |    0          |                 0
0 | 1 | 1 || 0    |    0          |                 1
1 | 0 | 0 || 1    |    1          |                 1
1 | 0 | 1 || 1    |    1          |                 1
1 | 1 | 0 || 0    |    0          |                 0
1 | 1 | 1 || 0    |    0          |                 1

Challenge: Is (P AND (NOT Q)) OR R) the same as P AND ((NOT Q) OR R)? That is, do they both generate the same Truth Table?

Aside: The operator precedence rule for Boolean operation is NOT first, AND second and OR third. Thus P AND NOT Q OR R is understood to mean (P AND (NOT Q)) OR R. Parentheses are used to change this order. Thus the leap year expression below written without parentheses evaluates the same way as the one given above

(Year % 4 == 0) and not (Year % 100 == 0) or (Year % 400 == 0)

Boolean Operator Precedence Rules

anything in parenthesis
NOT
AND - left to right
OR - left to right

Boolean Expressions

Python uses and, or, and not, C++ uses &&, || and ! for AND, OR and NOT. Alternately we can used · (dot) , +, and ¬ for AND, OR and NOT. (Sometimes we place a bar over the character instead of using ¬). Thus (a + b) · ¬c is the Boolean expression for (a AND b) OR NOT c. Since AND is sometimes called Boolean multiplication and OR is called Boolean addition, using · for AND and + for OR reinforces this terminology.

Implementing Boolean Logic - The Transistor

Transistors: A transistor is a discrete electronic component that can behave like a switch. A transistor (denoted by the circle with three lines leading in) has three connections: base, collector and emitter. When high voltage is applied to the base, the transistor behaves like a switch allowing current to flow from the collector to the emitter. (In the diagram above, current flows top to bottom - from V_cc or high voltage to Ground or low voltage.) If the collector is connected to the "bottom" end of a resistor (denoted by the squiggly line), and the base is "turned" on (high voltage is applied), current flows through the transistor (collector to emitter) causing a voltage drop across the resistor. Hence, the output line (V_out) connected at the collector has low voltage. So if V_in (base) has high voltage, V_out has low voltage. On the other hand, if V_in has low voltage, the transistor is "switched" off so current does not flow. There is no voltage drop across the resistor and high voltage accumulates at V_out. So if V_in is low, V_out is high.

A transistor configured in this manner behaves like a NOT gate.

Gates - A gate is an electronic device that operates on a set of (binary) inputs to produce a binary output. Gates implement in hardware many of the standard Boolean operations like AND, OR, and NOT.

An AND Gate is implemented by transistors configured in series. The emitter of the first transistor is connected to the collector of the second. Only when both bases are high does current flow through both transistors. Connecting the output (V_out) to the base of a third transistor inverts the output to be 1 if and only if both inputs are 1.

An OR Gate is implemented by transistors configured in parallel. The emitters of both transistors are connected (in parallel) to the end of the resistor and the collectors of both are connected (in parallel) to the common ground. If either base is high, current will flow through that transistor. Connecting the output (V_out) to the base of a third transistor inverts the output to be one if one or both inputs are 1.

A NOT Gate is implemented using the transistor configured above.

An XOR (eXclusive OR) Gate outputs 1 if one or the other input is 1 BUT NOT BOTH (see Truth Tables below). It differs from OR in the last line. An XOR gate can be constructed out of 2 AND gates, 2 NOT gates and one OR gate.

Symbols & Truth Tables for AND, OR, NOT, and XOR Gates

     a | b | a AND b   a OR b   NOT b   a XOR b
    ---+---+---------+--------+-------+-----------
     0 | 0 |    0    |    0   |   1   |    0
     0 | 1 |    0    |    1   |   0   |    1
     1 | 0 |    0    |    1   |       |    1
     1 | 1 |    1    |    1   |       |    0

Combinatorial Circuits : A combinatorial circuit is a set of logic gates that transforms a set of binary inputs to a set of binary outputs where the output depend only on the values of the inputs (and not on the state of the circuit). Below are two examples

Examples of Combinatorial Circuits

One-Bit Equality Circuit: Using 2 NOT gates, 2 AND gates and 1 OR gate a One-Bit Compare-for-Equality Circuit (see the circuit diagram below) can be constructed. The output of this circuit is 1 if and only if both inputs are 0 or both inputs are 1 (sort of like an inverted XOR gate).

Truth Table: You should verify that the above 1-Bit Compare Circuit satisfied the following truth table. Note that the upper AND gate outputs 1 if and only if both a and b are 1 while the lower AND outputs 1 if and only if both a and b are 0.

     a | b | result
    ---+---+--------
     0 | 0 |   1
     0 | 1 |   0
     1 | 0 |   0
     1 | 1 |   1

Half Adder Circuit - A half adder circuit has two inputs (a and b) and two outputs sum and carry. It implements the binary addition of two bits.

                               a | b | sum | carry
                              ---+---+-----+-------
   0      0     1      1       0 | 0 | 0 |   0
+0     +1    +0     +1       0 | 1 | 1 |   0
---    ---   ---    ---      1 | 0 | 1 |   0
   0      1     1     10       1 | 1 | 0 |   1

The Half-Adder circuit below is implemented using 2 AND gates, one OR gate and one NOT gate. We see the Sum result is 1 if and only if a is 1 OR b is 1 but (AND) both are NOT 1. The Carry result is the same as a AND b. This corresponds to the Truth Table.

Constructing Circuits

There is a standard 4-step algorithm to construct a circuit

Step 1 - Truth Table Construction: Determine how the circuit should behave by constructing a truth table that lists the output(s) for all possible inputs. Note that n inputs generates a 2ⁿ row table.

Example : a three variable boolean f(a,b,c)

     a | b | c | f(a,b,c)
    ---+---+---+---------
     0 | 0 | 0 |   0
     0 | 0 | 1 |   0
     0 | 1 | 0 |   1
     0 | 1 | 1 |   0
     1 | 0 | 0 |   0
     1 | 0 | 1 |   1
     1 | 1 | 0 |   0
     1 | 1 | 1 |   0

Step 2 – Sub-expression Construction using AND and NOT gates: Choose an output column. Scan down the column for a 1 output (ignore 0 outputs). Build a sub-expression (called a min-term) that produces the output 1 for that combination of inputs and no other as follows.

Examine the inputs for that output
If the input is 1 use that input variable directly in the sub-expression (i.e. a)
If the input is 0 use the complemented input in the expression (i.e. ¬ b )
AND all input variables or complemented input variables together. (e.g. a · ¬b)

Do this for all rows with a 1 output.

Example

sub-expression 1 (row 3) ¬a · b · ¬c

sub-expression 2 (row 6) a · ¬b · c

Step 3 – Sub-expression Combination using OR gates : Take each sub-expression generated in Step 2 and OR them together.

Example

(¬a · b · ¬c) + (a · ¬b · c)

Step 4 - Circuit Diagram Production: Construct the circuit diagram using AND, OR and NOT gates. The 3-input add gates below can be implemented by cascading two 2-input and gates.

Examples of Circuits Found in a Computer

1. A 1-Bit Equality Circuit (See above): Using 2 NOT gates, 2 AND gates and 1 OR gate a One-Bit Compare-for-Equality Circuit can be constructed. The output of this circuit is 1 if and only if the inputs are both 0 or both 1 (sort of like an inverted XOR gate). N of these circuits in parallel would give you an N-bit Comparator Circuit

2. Another Half Adder Circuit - A half adder circuit has two inputs (a and b) and two outputs sum and carry.
It implements the binary addition of two bits.

The sum part of the half adder also can be constructed using the Circuit Construction Technique given above. The carry part is easily implemented using a single AND gate. This half-adder circuit constructed this way requires 3 AND gates, 2 NOT gates and 1 OR gate and is not quite as "efficient" in terms of number of gates as the circuit given above (1 AND, 2 OR and 1 NOT gate).

Alternately a Half Adder can be implemented using 1 XOR gate (for the sum) and an 1 AND gate (for the carry).

A Full Adder Circuit - A full adder has three inputs: a, b and carry in and two outputs : sum and carry out. It implements the addition of two binary digits (a and b) either with no carry from a previous addition (carry in equals 0) or with a carry from a previous addition (carry in equals 1). This version is implemented using two XOR gates, two AND gates and 1 OR gate.

An N-Bit Ripple Carry Adder - N full adder circuits can be joined in "parallel" with the carry out at the k-1^st stage becoming the carry-in at the k^th stage to create N-bit adder. Typical values of N are 8, 16 and 32.

Control Circuits: The N-Bit Ripple Carry and N-Bit Comparator circuits are examples of arithmetical and logical circuits which are used to perform calculations. Control circuits are needed to control the operation of a computer. Two low-level circuits used to implement control circuits are given below.

3. Multiplexor (MUX) : A multiplexor circuit has N selector lines, 2^N input lines and 1 output line. The N selector lines determine which of the 2^N input lines is connected to the output. A simple 2 by 4 MUX can be constructed out of two NOT gates, four 3-input AND gate and one 4-input OR gate. Here the configuration of the two control lines c0 and c1 determines which of the four input data lines (data in 0 thru data in 3) is connected to the data out line. For example of c0 = 1 and c1 = 0 then Data In 1 is connected to Data Out through the second And gate.

This circuit can be scaled upward to 3 by 8 MUX (three NOT gates, eight 4-input AND gates, one 8-input OR gate) etc. Multiplexors can be used to control the flow of "data" through the circuits of a computer.

4. Decoder: A Decoder is the opposite of a multiplexor (also called a De-multiplexor). Here N control inputs are decoded to connect the single input to one of 2^N outputs. If the single data in is set to 1, all other data outs except the one selected are 0. A simple 2 to 4 Decoder can be constructed out of two NOT and four 3-input AND gates. Observe that if c1 equals 1 and c0 equals 0 (10 forms a binary 2), Data In is connected to Data Out 2. Data Out 0, 1, and 3 are all 0. Like multiplexors, decoders can be scaled upward.

Summary

The mathematics of Boolean algebra is the theoretical foundation of computer circuit design
Gates formed out of transistors implement AND, OR, NOT and XOR functions
A Half-Adder circuit implements the binary addition of two bits. A Full Adder circuit implements the binary addition of two bits with a carry in. N Full Adders in parallel implement an N-bit addition circuit. This is a typical arithmetic circuit
A 1-Bit Comparator for Equality circuit compares two bits for equality. N such circuits cascaded together implement a standard compare for equality circuit. This is a typical logic circuit,
A Multiplexor uses N control inputs to connect one of 2^N data in inputs to the single output. These are used for control circuits.
A Decoder circuit (De-multiplexor) uses N control input to connect the single Data In input to one of 2^N Data Out outputs. These are used for control circuits.

Return to Comp 150 Home Page