Lesson 02: Boolean Algebra and Logic Gates
2.1 Truth Tables
Truth Tables
Truth tables are fundamental tools in digital logic design, used to represent the relationship between the inputs and outputs of a digital circuit. They provide a systematic way to understand how the circuit behaves under different input conditions. Here's a detailed breakdown with examples and explanations:
What are Truth Tables?
- A truth table is a tabular representation of all possible input combinations to a digital circuit and their corresponding outputs.
- Each row represents one unique combination of input values (0s and 1s).
- Each column represents an input variable or the output of the circuit.
- The table shows how the output changes based on the different input combinations.
Constructing Truth Tables:
To construct a truth table:
- Identify Inputs and Outputs: Determine the number of inputs and outputs for the circuit or gate.
- List Input Combinations: List all possible combinations of input values. For n inputs, there will be 2n combinations.
- Determine Output for Each Combination: Apply the logic function of the circuit or gate to each input combination to find the output.
Applications of Truth Tables:
- Analyzing logic circuits: Understand how a circuit responds to different inputs.
- Designing logic circuits: Create a truth table first, then build the circuit to achieve the desired output.
- Simplifying Boolean expressions: Reduce complex expressions using truth tables.
- Troubleshooting circuits: Identify potential issues by tracing input-output behavior.
For more complex circuits, break down the circuit into simpler components, analyze each component with its truth table, and then combine the results to derive the overall truth table for the circuit.
Truth tables are not only theoretical tools; they are used practically in the design and analysis of digital circuits, allowing engineers to predict circuit behavior before physical implementation. They are essential in designing algorithms for digital devices, debugging circuits, and implementing logical operations in software.
2.2 Logic Gates
Logic Gates
Logic gates are electronic circuits that implement the functions of Boolean Algebra. A Boolean function can be transformed from an algebraic expression into a circuit diagram composed of logic gates connected to a particular structure. There are eight basic logic gates: OR, AND, NOT, BUFFER, NOR, NAND, XOR, and XNOR.
All the logic gates have one output signal; only NOT and BUFFER gates have one input, and all other gates have multiple inputs (at least two inputs).
OR
For an OR gate, the output F is true if one of the inputs is true. In other words, output F is false if all inputs are false.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A + B |  |
|
 |
||||||||||||||||||
AND
For an AND gate, the output F is true if all inputs are true. In other words, output F is false if one of the inputs is false.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A • B |  |
|
 |
||||||||||||||||||
NOT
For a single input NOT (Inverter) gate, the output F is ONLY true when the input is “NOT” true.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||
| F = A = A' |  |
|
 |
BUFFER
A BUFFER gate has only one Input, and its output follows the same logic state as the Input. A buffer gate is used in the following circuit:
- Used as a delay element in Digital Electronics.
- Used as a Current-Boost-Up element, which is used to increase the capability of the output of one gate to drive several other gates.
- Used to convert the signal to different voltage circuits. For example, send the signal from 3.3V to 5V circuits.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||
| F = A |  |
|
 |
NOR
For a NOR gate, the output F is true if all inputs are false. In other words, the output F is false if one of the inputs is true.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A + B |  |
|
 |
||||||||||||||||||
NAND
For a NAND gate, the output F is false if all inputs are true. In other words, the output F is true if one of the inputs is false.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A • B |  |
|
 |
||||||||||||||||||
XOR
For an XOR gate, the output F is true if the number of "true" states of inputs is odd. For a 2-input XOR gate, output F is false if input A is equal to input B.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A ⊕ B = A B + A B |
 |
|
 |
||||||||||||||||||
XNOR
For an XNOR gate, the output F is true if the number of "true" states of inputs is even. For a 2-input XNOR gate, output F is true if input A is equal to input B.
| Boolean Expression | Gate Symbol | Truth Table | Equivalent Switching Circuit | ||||||||||||||||||
| F = A ⊙ B = A ⊕ B = A B + A B |
 |
|
 |
||||||||||||||||||
Tri-State Gates
A Tri-State gate outputs three possible logic states:
- Logic 0
- Logic 1
- Logic Z
Tri-State gates have one "Control" (or "Enable") signal input. The control signal is used to activate or deactivate the gate output; if the gate is inactive, the output will be a logic Z; otherwise, the output depends on the input and the type of the logic gate. There are two types of control signals: Active high and active low control signals, and two types of tri-state gates: buffer and not gates.
Three-state logic is used to allow multiple circuits to share the same output or bus lines which may not be capable of listening to more than one device or circuit at a time. In this way, the high-impedance state acts as a selector which blocks out circuits that are not being used. As mentioned, the whole concept of the high-impedance state is to effectively remove the circuit or device's influence from the rest of the circuit as if it were not connected at all. Putting one device on high impedance is normally used to prevent a short circuit with the other device directly connected in the same way to the same leads, this also prevents both devices from being driven at once since this may lead to unintended output or input and cause the whole circuit to malfunction.
Tri-State Buffer Gates
Tri-state buffer works as a signal-controlled switch. An enable signal is used to control whether the input signal is transferred toward the output or isolated from the output, which is then held in a high-impedance state (logic Z).
| Boolean Expression | Gate Symbol | Truth Table | Tri-State Buffer Switch Equivalent | ||||||||||||||||||
| E = 0 ⇒ F = Z E = 1 ⇒ F = A |
 |
|
 |
||||||||||||||||||
| Boolean Expression | Gate Symbol | Truth Table | Tri-State Buffer Switch Equivalent | ||||||||||||||||||
| E = 0 ⇒ F = A E = 1 ⇒ F = Z |
 |
|
 |
||||||||||||||||||
Tri-State Not gates
| Boolean Expression | Gate Symbol | Truth Table | Tri-State Buffer Switch Equivalent | ||||||||||||||||||
| E = 0 ⇒ F = Z E = 1 ⇒ F = A |
 |
|
 |
||||||||||||||||||
| Boolean Expression | Gate Symbol | Truth Table | Tri-State Buffer Switch Equivalent | ||||||||||||||||||
| E = 0 ⇒ F = A E = 1 ⇒ F = Z |
 |
|
 |
||||||||||||||||||
2.3 Boolean Algebra and Boolean Equations
Boolean Algebra is a division of mathematics that deals with operations on logical values and incorporates binary variables. Boolean algebra traces its origins to an 1854 book by mathematician George Boole. It is mainly used for simplifying and analyzing complex Boolean expressions. Boolean algebra is also called Binary Algebra or Logical Algebra.
Rules in Boolean Algebra
- The name of the variable in Boolean algebra usually uses a single letter, for example, variables A, B, and X.
- The boolean variables are represented as binary numbers to represent truths: 1 = true and 0 = false.
- There are three basic logic operations: AND, OR, and NOT.
- Both AND and OR connect two variables, while NOT is applied to a single variable.
- The AND operator is called the product operator or the conjunction operator.
- The OR operator is called the sum operator or the disjunction operator.
- The NOT operator is called negation or inverter.
Below is the table defining the symbols for the Boolean algebra operations.
Table 1: The common Boolean algebra symbols and operations
| Symbol | Logic Operation | Example |
|---|---|---|
| + | Logic or | A + B |
| • | Logic and (the symbol sometimes can be ignored) | A • B = A B |
| ' or ‾ | Logic not (negation) | A' = A |
| ⊕ | Logic xor (exclusive OR) | A ⊕ B |
| ⊙ or ⊗ | Logic xnor (exclusive-NOR) | A ⊙ B |
The Laws of Boolean Algebra
The laws of Boolean Algebra are used to simplify Boolean expressions. The following are the laws of Boolean algebra.
Table 2: The Laws of Boolean Algebra
| Laws of Boolean Algebra | SOP Form | POS Form | ||
|---|---|---|---|---|
| 0 + 0 = 0 | 0 • 0 = 0 | |||
| 1 + 1 = 1 | 1 • 1 = 1 | |||
| 1 + 0 = 1 | 1 • 0 = 0 | |||
| 0 = 1 | 1 = 0 | |||
| Involution (Double Negative) | A = A | A double complement of a variable is always equal to the variable | ||
| Identity | A + 0 = A | A variable OR'ed with 0 is always equal to the variable | A • 1 = A | A variable AND'ed with 1 is always equal to the variable |
| Null | A + 1 = 1 | A variable OR'ed with 1 is always equal to 1 | A • 0 = 0 | A variable AND'ed with 0 is always equal to 0 |
| Idempotent | A + A = A | A variable OR’ed with itself is always equal to the variable | A • A = A | A variable AND’ed with itself is always equal to the variable |
| Inverse | A + A = 1 | A variable OR’ed with its complement is always equal to 1 | A • A = 0 | A variable AND’ed with its complement is always equal to 0 |
| Commutative | A + B = B + A | The order in which two variables are OR’ed makes no difference | A • B = B • A | The order in which two variables are AND’ed makes no difference |
| Associative | A + (B + C) = (A + B) + C | A • (B • C) = (A • B) • C | ||
| Distributive | A • (B + C) = A • B + A • C | A + B • C = (A + B) • (A + C) | ||
| Absorption | A + A • B = A | A • (A + B) = A | ||
| Consensus | A • B + A • C + B • C = A • B + A • C | (A + B) • (A + C) • (B + C) = (A + B) • (A + C) | ||
| DeMorgan | A + B = A • B | A • B = A + B | ||
XOR and XNOR Functions
The XOR function of two variables is defined by:
A ⊕ B = A B + A B
Furthermore, the XOR can be rewritten:
A ⊕ B = A ⊕ B
The definition of the XNOR (AND inclusive) function with two variables is given:
A ⊙ B = A B + A B
It must be noted that:
A ⊙ B = A ⊙ B = A ⊕ B = A ⊕ B = A ⊕ B
The basic properties for the XOR and XNOR operations are given in the following table:
| Laws of Boolean Algebra | XOR | XNOR |
|---|---|---|
| 0 ⊕ A = A | 0 ⊙ A = A | |
| 1 ⊕ A = A | 1 ⊙ A = A | |
| A ⊕ A = 0 | A ⊙ A = 1 | |
| A ⊕ A = 1 | A ⊙ A = 0 | |
| Commutativity | A ⊕ B = B ⊕ A | A ⊙ B = B ⊙ A |
| Associativity: | A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C = A ⊕ B ⊕ C | A ⊙ (B ⊙ C) = (A ⊙ B) ⊙ C = A ⊙ B ⊙ C |
| Factorization and Distributivity | (A B) ⊕ (A C) = A (B ⊕ C) | (A + B) ⊙ (A + C) = A + (B ⊙ C) |
| Absorption | A (A ⊕ B) = A B | A + (A ⊙ B) = A + B |
| Consensus | (A B) ⊕ (A C) + B C = (A B) ⊕ (A C) | (A + B) ⊙ (A + C)(B + C) = (A + B) ⊙ (A + C) |
| if A B = 0, then A + B = A ⊕ B | if A + B = 1, then A B = X ⊙ Y |
Q1: A ⊕ (B C) = (A ⊕ B)(A ⊕ C)?
The following truth table shows the functions A ⊕ (B C) and (A ⊕ B)(A ⊕ C). We can thus observe that A ⊕ (B C) is different from (A ⊕ B)(A ⊕ C).
| A | B | C | B C | A ⊕ B | A ⊕ C | A ⊕ (B C) | (A ⊕ B)(A ⊕ C) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Q2: A ⊕ B ⊕ (A + B) = A ⊕ B ⊕ A + A ⊕ B ⊕ B ?
The following truth table has represented the function A ⊕ B ⊕ (A + B) and A ⊕ B ⊕ A + A ⊕ B ⊕ B.
| A | B | A + B | A ⊕ B | A ⊕ B ⊕ (A + B) | A ⊕ B ⊕ A + A ⊕ B ⊕ B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Or we can expand the XOR into a standard Boolean expression, and then simplify the functions, we have:
A ⊕ B ⊕ (A + B) = (A B + A B) ⊕ (A + B)
= (A B + A B) (A + B) + (A B + A B) (A + B)
= (A + B)(A + B)(A + B)+(A B + A B)(A B)
= (A B + A B)(A + B) + 0
= AAB + A A B + A B B + A B B
= A B
and
A ⊕ B ⊕ A + A ⊕ B ⊕ B = A B + A B + A B
= A B + A (B + B)
= A B + A ...... (Distributive Law)
= A + B
From the truth table or the final Boolean expression of each function, you can observe that the functions A ⊕ B ⊕ (A + B) and A ⊕ B ⊕ A + A ⊕ B ⊕ B are not equal.
Boolean Functions (Equations)
Boolean algebra is an algebra that deals with binary variables and logic operations. The algebraic expression, known as Boolean Expression, is used to describe the Boolean Function. The Boolean expression consists of binary variables, the constants 0 and 1, and the logic operation symbols. For a given value of the binary variables, the function can be equal to either 1 or 0. As an example, consider the Boolean function below:
\(\underbrace {F(A,B,C)}_{Boolean Function} = \underbrace {A\,\overline B + C}_{Boolean Expression}\)
We defined the Boolean function F(A,B,C) = A B + C in terms of three binary variables A, B, and C. This function will equal 1 when A = 1, B = 0, or C = 1; otherwise, the F is equal to 0. Boolean function expresses the logical relationship between binary variables and is evaluated by determining the binary value of the expression for all possible values of the variables.
In addition to a Boolean expression, truth tables can also describe the Boolean function. We can represent a function using multiple algebraic expressions. They are their logical equivalents. But for each function, we have only one unique truth table.
In truth table representation, we represent all the possible combinations of inputs and their result. We can convert the switching equations into truth tables.
The truth table of the above example is given below. The 2n is the number of rows in the truth table. The n defines the number of input variables. So the possible input combinations are 23 = 8.
Table 3: Truth Table for Boolean Function: \({F(A,B,C)} = {A\,\overline B + C}\)
| Inputs | Output | ||
|---|---|---|---|
| A | B | C | F |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Boolean Algebra Terminologies
Now, let us discuss the essential terminologies covered in Boolean algebra.
- Boolean Algebra: Boolean algebra is the branch of algebra that deals with logical operations and binary variables.
- Boolean Variables: A Boolean variable is defined as a variable or a symbol defined as a variable or a character, generally an alphabet representing logical quantities such as 0 or 1.
- Boolean Function (Equation): A Boolean function consists of binary variables, logical operators, constants such as 0 and 1, equal to the operator, and the parenthesis symbols.
- Literal: A literal may be a variable or a complement of a variable.
- Complement: The complement is defined as the inverse of a variable, which is represented by a bar over the variable.
- Truth Table: The table gives all the possible values of logical variables and the combination of the variables. It is possible to convert the Boolean equation into a truth table. The number of rows in the truth table should equal 2n, where “n” is the number of variables in the equation. For example, if a Boolean equation consists of 3 variables, then the number of rows in the truth table is 8. (i.e.,) 23 = 8.
2.4 Duality Principle and Complementary Theorem
Duality Principle
The duality Principle states that if a Boolean expression is true, then its dual is also true. The duality principle does not say that a Boolean expression is equivalent to its dual. To apply the duality principle, follow these steps:
- Change each AND (+) operation to an OR (·) operation.
- Change each OR (·) operation to an AND (+) operation.
- Replace 0 with 1.
- Replace 1 with 0.
Example: Let’s take a simple example to illustrate the duality principle. Consider the expression:
a + (b · c) = (a + b)·(a + c)
The dual of this expression is obtained by:
- Changing OR (+) to AND (·)
- Changing AND (·) to OR (+)
then its dual expression is
a · (b + c) = (a · b)+(a · c)
More Examples: Here are some additional examples of applying the duality principle:
| Expression | Dual Expression |
|---|---|
| 1 + 0 = 1 | 0 · 1 = 0 |
| A + 0 = A | A · 1 = A |
| A + 1 = 1 | A · 0 = 0 |
| A · (B · C) = (A · B) · C | A + (B + C) = (A + B) + C |
| A · (A + B) = A | A + (A · B) = A |
Self-Dual Functions:
A function is considered self-dual if its dual is equivalent to the given function. For example, if a given function is:
F(x, y, z) = x y + y z + z x
Its dual is:
Fdual(x y, z) = (x + y) · (y + z) · (z + x)
Complementary Theorem
The theorem essentially states that a complement F exists for any Boolean function F.
How to Apply the Complementary Theorem:
- Identify the Original Expression: Start with the Boolean expression or function you wish to complement.
- Apply De Morgan's Theorems: De Morgan's Theorems are often used to find the complement of a Boolean expression. These theorems state that:
- Replace each OR (+) operation with an AND (·) operation and vice versa.
- Complement any 0 or 1 appearing in the expression.
- Complement each individual variable separately.
Example: Let us consider a simple example:
Given expression: A·(B + C). To find the complement, apply the following transformations:
- Change OR (+) to AND (·) ⇒ A + (B·C)
- Complement each individual literal ⇒ A + (B·C)
Self-Complementary Functions:
- A function is considered self-complementary if its complement is equivalent to the given function.
- For example, if a given function is: F(A, B, C) = A B + B C + A C
- Its complement is: F(A, B, C) = A B + B C + A C = (A + B) (B + C) (A + C)
Inverted Dual:
- Find the Dual of F
- Invert all variables
- Complementary F = F = Inverted Dual of F
F = A · (B + A)
Dual: Fdual = A + (B · A)
Inverted Dual: = A + (B · A) = F
Example 1: Complement and Duality of F(x, y, z) = x + y z
Finding the Complement
To find the complement of F, denoted as F, you invert the output of F. Use De Morgan's Laws and Boolean algebra simplification rules.
- Original Function: F(x, y, z) = x + y z
- Complement F:
- Apply the complement: F = x + y z
- Use De Morgan’s Law: F = x · (y + z)
Finding the Duality
The duality of a function is found by swapping ANDs with ORs and vice versa and swapping 0s with 1s (if present as constants in the expression).
- Original Function: F(x, y, z) = x + y z (There are no explicit 0s or 1s to swap.)
- Dual of F: Swap the operations: The dual would swap + with ⋅ and vice versa. ⇒ Fd = x · (y + z)
Example 2: Complement and Duality of F = x y z + x y z
F = x y z + x y z
Dual ⇒ Fdual = (x + y + z) (x + y + z)
Complement ⇒ F = (x + y + z) (x + y + z)
Example 3: Complement and Duality of F = x (y z + y z)
F = x (y z + y z)
Dual ⇒ Fdual = x + (y + z ) (y + z)
Complement ⇒ F = x + (y + z) (y + z)
2.5 Universal Logic Gates
In digital logic design, universal gates are special types of logic gates that can be used to implement any Boolean function. This means you can build any complex digital circuit using only one type of universal gate! The two most common universal gates are the NOR gate and the NAND gate.
|
A NOR gate is equivalent to an inverted-input AND gate.
|
A NAND gate is equivalent to an inverted-input OR gate.
|
| Gate Type | NOR Construction | NAND Construction |
|---|---|---|
| OR |  |
 |
| AND |  |
 |
| NOT |  |
 |
| NOR |  |
 |
| NAND |  |
 |
| XOR |  |
 |
| XNOR |  |
 |
Advantages of Universal Gates:
- Flexibility: Build complex circuits with just one type of gate.
- Efficiency: Reduce chip size and cost by using fewer different types of gates.
- Standardization: Simplify design and manufacturing processes.
NAND and NOR gates are incredibly powerful in digital logic design, allowing for the construction of any logic circuit. Their universal property means that with just one type of gate, it's possible to implement any digital logic function, which can simplify the manufacturing process and reduce costs. Understanding how to use these gates to construct basic logic functions is fundamental for designing efficient and effective digital circuits.