Logic Gates

Logic Gates and Truth Tables

Almost all of the computing in a computer is performed by logic circuits. Logic circuits also make up the fastest memory, SRAM, that is used in registers and caches. In this topic you learn about how logic circuits are built up of basic components called logic gates, and how to analyse and design logic circuits.

Skills Required in this Unit

Know the basic logic gates
Convert between logic circuits, logic notation, Boolean algebra and Logic Expressions.
Produce a truth table from one of the above logic representations
Design a logic circuit to solve a simple supplied problem
Use the universal gates, NAND or NOR, to design equivalent circuits.

Back to Topic 3 main page.

Boolean Logic

George Boole was a mathematician who invented Boolean Algebra in order to better understand the classical logical syllogisms. This logic was coopted by Claude Shannon the originator of information theory in order to describe the logic needed by digital computers. Read more here.

Google Doodle for George Boole's 200th birthday

The Basic Logic Gates

There are six gates studied in this course: NOT, AND, OR, NAND, NOR, and XOR.

Each gate has a Symbol, Logic Notation, Boolean Algebra Expression, Logic Expression, and Truth Table.

Logic Gates 0580

Truth Tables

A truth table lists the behaviour of a logic circuit for all possible input combinations. Each input has two possible states, so n inputs have 2ⁿ possible states. We list them from 00...0 to 11....1, just like the natural numbers in binary.

In order to calculate the outputs of a circuit, it is often useful to label and calculate intermediate results.

Logic Circuits

Gates can be combined into circuits to solve particular tasks.

Example 1: X = A OR (NOT B)

This circuit has two inputs (4 states) and one output. Label the intermediate state D, to get the truth table

Exercise 1 - Write the logic notation and complete the truth tables for the following two-input circuits.

In the following, the input B splits and goes to both the AND gate and the OR gate. X = (A AND B) OR B

Example 2 Draw the logic circuit and complete the truth table for X = (A OR B) AND (A NAND B)

Truth Table: Define C = A OR B and D = A NAND B so X = C AND D, then calculate:

Note, this shows that X = A XOR B is a simpler equivalent logic expression / circuit!

Logic Circuit: Draw the sub-circuits for C and D, then combine to get X

Exercise 2 - Draw the logic circuit and complete the truth table for the following:

X = (NOT A) XOR B
X = A AND (B XOR A)
X = A AND (B XOR NOT A)

Example 3:

Logic notation Hint: Use the intermediate definitions to help find the full expression.

The output is X = A OR D, where D = B AND C. Substitute in D to get X = A OR (B AND C)

Truth Table: There are 3 inputs, so 2³ = 8 possible input states.

Exercise 3: Write the logic notation and complete the truth tables for the following three-input circuits.

Logic notation and Boolean Algebra to Logic Circuits

Exercise 4 - Draw the logic circuit and complete the truth table for the following:

X = (A AND B) NOR C
X = A AND (B XOR C)
X = (A OR B) AND (B OR C)

Logic expressions and Applications

A Logic Expression is like Logic Notation, except you explicitly state the input and output values.

For example:

X = A OR B becomes X = 1 if (A = 1 OR B = 1)
X = NOT A AND B → X = 1 if (A = OFF AND B = ON)

The basic application is that you want to control or monitor a system, given a set of sensors that yield HIGH/LOW or ON/OFF signals. Design a logic circuit that combines the sensor data to provide the required output.

Exercise 5: Complete the following handout

Logic Statement Examples - Textbook

Universal gates: NAND & NOR

These are both universal logic gates - you can build any logic out of just NAND or just NOR gates.

The key step is connecting both inputs of the NAND / NOR gates to a single wire to generate a NOT gate.

Image Source: Wikipedia

We can then construct all of the other gates from the NAND / NOR gates.

Exercise 6

1. Write the Logic notation and Boolean Algebra for the above NAND construction of the OR gate. Prove it is correct by calculating its truth table.

Aside: This construction is essentially De Morgan's Theorem which applies to both Set Theory & Logic

2. Create a similar circuit to build a AND gate from only NOR gates. And check its truth table.

Possible Extension

Other "basic" gates such as XNOR, and n-input OR & AND gates, etc...
Harder applications
- Half-adder, Full-adder and Ripple-adder
- Flip-Flops & Latches & SRAM modules

Boolean circuits from Truth Tables
De Morgan's theorems
Boolean Algebra (as in actually using the algebra)
Construction of Logic Gates from Transistors

Exam Questions

2018 Oct/Nov Question Paper 1.2

Write the Boolean Algebra and Truth Table for the monitoring system.

2018 Oct/Nov Question Paper 1.3

Report abuse