Lesson 02: Boolean Algebra and Logic Gates
2.1 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 the complex Boolean expression. Boolean algebra is also called Binary Algebra or Logical Algebra.
Rules in Boolean Algebra
 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 complement.
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 (exclusiveNOR)  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 
Complementary  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 is 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, 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 2^{n} is the number of rows in the truth table. The n defines the number of input variables. So the possible input combinations are 2^{3} = 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 
The
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 2^{n}, 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.,) 2^{3} = 8.
2.2 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 CurrentBoostUp element, which is used to increase the capability of the output of one gate to drive a number of 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 2input 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 2input 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 

TriState Gates
A TriState gate outputs three possible logic states:
 Logic 0
 Logic 1
 Logic Z
TriState 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 tristate gates: buffer and not gates.
Threestate 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 highimpedance state acts as a selector which blocks out circuits that are not being used. As mentioned, the whole concept of the highimpedance 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.
TriState Buffer Gates
Tristate buffer works as a signalcontrolled 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 highimpedance state (logic Z).
Boolean Expression  Gate Symbol  Truth Table  TriState Buffer Switch Equivalent  
E = 0 ⇒ F = Z E = 1 ⇒ F = A 

Boolean Expression  Gate Symbol  Truth Table  TriState Buffer Switch Equivalent  
E = 0 ⇒ F = A E = 1 ⇒ F = Z 

TriState Not gates
Boolean Expression  Gate Symbol  Truth Table  TriState Buffer Switch Equivalent  
E = 0 ⇒ F = Z E = 1 ⇒ F = A 

Boolean Expression  Gate Symbol  Truth Table  TriState Buffer Switch Equivalent  
E = 0 ⇒ F = A E = 1 ⇒ F = Z 

2.3 Universal Logic Gates
A universal gate is a logic gate that can implement any Boolean function without using any other type of logic gate. The NAND and NOR are universal gates. This means you can create any logical Boolean expression using only NOR or NAND gates.
A NOR gate is equivalent to an invertedinput AND gate. 
A NAND gate is equivalent to an invertedinput OR gate. 
Gate Type  NOR Construction  NAND Construction 

OR  
AND  
NOT  
NOR  
NAND  
XOR  
XNOR 