Air Supply Lab - EE2440-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 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
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ⁿ is the number of rows in the truth table. The n defines the number of input variables. So the possible input combinations are 2³ = 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ⁿ, 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³ = 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

Inputs		Output
A	B	F
0	0	0
0	1	1
1	0	1
1	1	1

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

Inputs		Output
A	B	F
0	0	0
0	1	0
1	0	0
1	1	1

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'

Inputs	Output
A	F
0	1
1	0

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 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

Inputs	Output
A	F
0	0
1	1

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

Inputs		Output
A	B	F
0	0	1
0	1	0
1	0	0
1	1	0

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

Inputs		Output
A	B	F
0	0	1
0	1	1
1	0	1
1	1	0

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

Inputs		Output
A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

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

Inputs		Output
A	B	F
0	0	1
0	1	0
1	0	0
1	1	1

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 Not gates

Tri-State Buffer Gates
Tri-State Not gates

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

Inputs		Output
E	A	F
0	0	Z
0	1	Z
1	0	0
1	1	1

Boolean Expression

Gate Symbol

Truth Table

Tri-State Buffer Switch Equivalent

E = 0 ⇒ F = A
E = 1 ⇒ F = Z

Inputs		Output
E	A	F
0	0	0
0	1	1
1	0	Z
1	1	Z

Tri-State Not gates

Boolean Expression

Gate Symbol

Truth Table

Tri-State Buffer Switch Equivalent

E = 0 ⇒ F = Z
E = 1 ⇒ F = A

Inputs		Output
E	A	F
0	0	Z
0	1	Z
1	0	1
1	1	0

Boolean Expression

Gate Symbol

Truth Table

Tri-State Buffer Switch Equivalent

E = 0 ⇒ F = A
E = 1 ⇒ F = Z

Inputs		Output
E	A	F
0	0	1
0	1	0
1	0	Z
1	1	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 inverted-input AND gate.

NOR InvAND