Logic Gates

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

The 7400 chip contains four logical NAND gates.

Curriculum

Coder Merlin™  Computer Science Curriculum Data

Unit: Boolean algebra Experience Name: Logic Gates (W1014) Next Experience: () Knowledge and skills: §10.325 Demonstrate understanding and proficiency in the use of logic gates Topic areas: Boolean algebra Classroom time (average): 45 minutes Study time (average): 120 minutes Successful completion requires knowledge: understand the symbology of common logic gates Successful completion requires skills: demonstrate proficiency in using the symbols of logic gates to document Boolean functionality

Introduction

A logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces one or more binary outputs.

Symbols

The table below provides the symbols that are used to represent common gates.

Formal Name	Abbreviated Name	Symbol	Gate	Truth Table
Buffer				Inputs Outputs $A$ $Q=A$ 0 0 1 1
Conjunction	AND	$A\land B$		Inputs Outputs $A$ $B$ $Q=A\land B$ 0 0 0 0 1 0 1 0 0 1 1 1
Disjunction	OR	$A\lor B$		Inputs Outputs $A$ $B$ $Q=A\lor B$ 0 0 0 0 1 1 1 0 1 1 1 1
Exclusive OR	XOR	$A\oplus B$		Inputs Outputs $A$ $B$ $Q=A\oplus B$ 0 0 0 0 1 1 1 0 1 1 1 0
Inverter	NOT	$\neg A$		Inputs Outputs $A$ $Q={\overline {A}}$ 0 1 1 0
Negated Conjunction	NAND	${\overline {A\land B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\land B}}$ 0 0 1 0 1 1 1 0 1 1 1 0
Negated Disjunction	NOR	${\overline {A\lor B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\lor B}}$ 0 0 1 0 1 0 1 0 0 1 1 0
Negated Exclusive OR	NOT XOR	${\overline {A\oplus B}}$		Inputs Outputs $A$ $B$ $Q={\overline {A\oplus B}}$ 0 0 1 0 1 0 1 0 0 1 1 1

Additionally, a multiplexer is a device which selects from $n$ digital inputs and forwards the signal to a single output line. Given $n$ inputs, there are $log_{2}n$ selector pins. Conversely, a demultiplexer forwards the signal from a single line to one of multiple outputs.

Formal Name	Abbreviated Name	Symbol	Gate	Truth Table
Multiplexer	MUX	${A\cdot {\overline {S}}}\lor {B\cdot S}$		Inputs Outputs $S$ $A$ $B$ $Q={A\cdot {\overline {S}}}\lor {B\cdot S}$ 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1
Demultiplexer	DEMUX			Inputs Outputs $S$ $A$ $Q={{\overline {S}}\cdot A}$ $R={S\cdot A}$ 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1

The Special Role of NAND and NOR Gates

Both NAND and NOR gates exhibit a property known as functional completeness. Any Boolean function can be implemented using one or more of either of these gates. This is a very powerful principal because it enables us, using only one type of logic gate, to implement systems of arbitrary complexity.

Exercises

Exercises

•  M1014-10  Complete  Merlin Mission Manager  Mission M1014-10.

References

• NAND Gate (Wikipedia)
• Schocken, Simon and Nisan, Noam. The Elements of Computing Systems. MIT Press, 2005.

Experience Metadata

Edit Experience Metadata

Experience ID	W1014
Next experience ID
Unit	Boolean algebra
Knowledge and skills	§10.325
Topic areas	Boolean algebra
Classroom time	45 minutes
Study time	2 hours120 minutes <br />
Acquired knowledge	understand the symbology of common logic gates
Acquired skill	demonstrate proficiency in using the symbols of logic gates to document Boolean functionality
Additional categories