Lesson 2.3: Boolean Algebra and Logic Gates

Introduction

In this lesson, we will explore the fundamental concepts of Boolean algebra and logic gates. By the end of this lesson, students will be able to understand how digital systems utilize binary logic to perform computations. We will cover the primary logic gates—AND, OR, NOT—and their derived forms: NAND, NOR, and XOR. Furthermore, we will learn to construct and interpret truth tables, simplify Boolean expressions, and design simple logic circuits based on given requirements. This knowledge is crucial for understanding how computers process information at a fundamental level.

Learning Objectives

• Identify and describe the fundamental logic gates: AND, OR, NOT, as well as derived gates: NAND, NOR, and XOR.
• Construct truth tables for single gates and combinations of gates.
• Understand Boolean expressions and apply simplification using basic Boolean identities.
• Design small logic circuits from written requirements.
• Create truth tables for logic gates and combinations thereof.

Section 1: Fundamental Logic Gates

Logic gates are the building blocks of digital circuits. They take one or more binary inputs (0 and 1) and produce a single binary output based on a specific logical operation. Let’s examine the three primary logic gates in detail.

1.1 AND Gate

The AND gate outputs a 1 only if all its inputs are 1. If any input is 0, the output will be 0.

Symbol and Truth Table

The symbol for an AND gate is shown below, and its truth table is as follows:

Input A	Input B	Output (A AND B)
0	0	0
0	1	0
1	0	0
1	1	1

Boolean Expression

The output can be expressed mathematically as:

$$ Output = A \land B $$

Example

If we input $ A = 1 $ and $ B = 1 $, then the output will be:

$$ Output = 1 \land 1 = 1 $$

If we input $ A = 1 $ and $ B = 0 $, then the output will be:

$$ Output = 1 \land 0 = 0 $$

1.2 OR Gate

The OR gate outputs a 1 if at least one of its inputs is 1. It only outputs a 0 when all its inputs are 0.

Symbol and Truth Table

The symbol for an OR gate and its truth table:

Input A	Input B	Output (A OR B)
0	0	0
0	1	1
1	0	1
1	1	1

Boolean Expression

The output can be expressed as:

$$ Output = A \lor B $$

Example

For $ A = 0 $ and $ B = 1 $, the output is:

$$ Output = 0 \lor 1 = 1 $$

For $ A = 0 $ and $ B = 0 $, the output is:

$$ Output = 0 \lor 0 = 0 $$

1.3 NOT Gate

The NOT gate, also known as an inverter, takes a single input and outputs the opposite value. If the input is 0, the output is 1; if the input is 1, the output is 0.

Symbol and Truth Table

The symbol for a NOT gate and its truth table is:

Input A	Output (NOT A)
0	1
1	0

Boolean Expression

The output can be expressed as:

$$ Output =

eg A $$

Example

For $ A = 1 $, the output is:

$$ Output =

eg 1 = 0 $$

Section 2: Derived Logic Gates

Derived gates can be constructed using the basic gates. In this section, we will look at the NAND, NOR, and XOR gates.

2.1 NAND Gate

The NAND gate is a combination of an AND gate followed by a NOT gate. It outputs a 0 only when both inputs are 1.

Symbol and Truth Table

The symbol and truth table for the NAND gate are:

Input A	Input B	Output (A NAND B)
0	0	1
0	1	1
1	0	1
1	1	0

Boolean Expression

The output can be expressed as:

$$ Output =

eg (A \land B) $$

Example

If $ A = 1 $ and $ B = 1 $, then:

$$ Output =

$eg (1 \land 1) = $

eg 1 = 0 $$

2.2 NOR Gate

The NOR gate is a combination of an OR gate followed by a NOT gate. It outputs 1 only when both inputs are 0.

Symbol and Truth Table

The symbol and truth table are:

Input A	Input B	Output (A NOR B)
0	0	1
0	1	0
1	0	0
1	1	0

Boolean Expression

The output can be expressed as:

$$ Output =

eg (A \lor B) $$

Example

For $ A = 0 $ and $ B = 0 $:

$$ Output =

$eg (0 \lor 0) = $

eg 0 = 1 $$

2.3 XOR Gate

The XOR (exclusive OR) gate outputs a 1 if exactly one of the two inputs is 1. It outputs 0 if both inputs are the same.

Symbol and Truth Table

The symbol and truth table are:

Input A	Input B	Output (A XOR B)
0	0	0
0	1	1
1	0	1
1	1	0

Boolean Expression

The output can be expressed as:

$$ Output = A \oplus B $$

Example

For $ A = 0 $ and $ B = 1 $:

$$ Output = 0 \oplus 1 = 1 $$

Section 3: Truth Tables

A truth table is a mathematical table used to determine the output of a logic gate or circuit for all possible input combinations. In this section, students will learn how to construct truth tables for various gates and combinations of gates.

3.1 Constructing a Truth Table

To construct a truth table, follow these steps:

1. Identify the number of inputs.
2. List all possible combinations of input values (0s and 1s).
3. Determine the output for each combination.

Example: Truth Table for A AND B

We will construct a truth table for the AND gate:

1. Inputs: A and B (2 inputs)
2. Possible combinations: (0,0), (0,1), (1,0), (1,1)
3. Output based on our earlier table:

Input A	Input B	Output (A AND B)
0	0	0
0	1	0
1	0	0
1	1	1

Section 4: Boolean Expressions and Simplification

Boolean algebra allows us to represent logic gates using algebraic expressions. In this section, we will learn about simplifications using basic Boolean identities.

4.1 Basic Boolean Identities

1. Identity Law:

• $ A \land 1 = A $
• $ A \lor 0 = A $

1. Null Law:

• $ A \land 0 = 0 $
• $ A \lor 1 = 1 $

1. Idempotent Law:

• $ A \land A = A $
• $ A \lor A = A $

1. Complement Law:

• A \land

eg A = 0

• A \lor

eg A = 1

Example: Simplifying a Boolean Expression

Consider the expression $ A \land (A \lor B) $:

1. Apply the Absorption Law:

$$ A \land (A \lor B) = A $$

Section 5: Designing Logic Circuits

Given a written requirement, we can design a logic circuit utilizing the gates we have discussed.

Example Requirement

Design a circuit with the output true if either input A is true, or both inputs B and C are true.

1. Analyze the requirement:

• $ Output = A \lor (B \land C) $

1. Using AND and OR gates:

• Connect A to the input of an OR gate.
• Connect B and C to an AND gate.
• Connect the output of the AND gate to the other input of the OR gate.

Conclusion

In this lesson, students has learned about Boolean algebra and logic gates, including their symbols and truth tables. We discussed the fundamental gates: AND, OR, and NOT, as well as derived gates: NAND, NOR, and XOR. We also learned about the construction of truth tables and simplification of Boolean expressions using basic identities. Finally, we examined how to design simple logic circuits based on requirements. This foundational knowledge provides a powerful tool for understanding digital systems.

Study Notes

• Logic gates are the basic building blocks of digital circuits.
• AND gate outputs 1 if all inputs are 1; OR gate outputs 1 if at least one input is 1; NOT gate flips the input.
• Derived gates: NAND (NOT AND), NOR (NOT OR), XOR (exclusive OR).
• Truth tables show output for every combination of inputs.
• Boolean expressions can be simplified using identities.
• Logic circuits can be designed based on specific logical requirements.