# Logic Gates

The 7400 chip contains four logical NAND gates.

## Curriculum

 Coder Merlin™  Computer Science Curriculum Data Unit: Boolean algebra Experience Name: Logic Gates (W1014) 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
${\displaystyle A}$ ${\displaystyle Q=A}$
0 0
1 1
Conjunction AND ${\displaystyle A\land B}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q=A\land B}$
0 0 0
0 1 0
1 0 0
1 1 1
Disjunction OR ${\displaystyle A\lor B}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q=A\lor B}$
0 0 0
0 1 1
1 0 1
1 1 1
Exclusive OR XOR ${\displaystyle A\oplus B}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q=A\oplus B}$
0 0 0
0 1 1
1 0 1
1 1 0
Inverter NOT ${\displaystyle \neg A}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle Q={\overline {A}}}$
0 1
1 0
Negated Conjunction NAND ${\displaystyle {\overline {A\land B}}}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q={\overline {A\land B}}}$
0 0 1
0 1 1
1 0 1
1 1 0
Negated Disjunction NOR ${\displaystyle {\overline {A\lor B}}}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q={\overline {A\lor B}}}$
0 0 1
0 1 0
1 0 0
1 1 0
Negated Exclusive OR NOT XOR ${\displaystyle {\overline {A\oplus B}}}$
Inputs Outputs
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 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 ${\displaystyle n}$ digital inputs and forwards the signal to a single output line. Given ${\displaystyle n}$ inputs, there are ${\displaystyle 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 ${\displaystyle {A\cdot {\overline {S}}}\lor {B\cdot S}}$
Inputs Outputs
${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 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
${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle Q={{\overline {S}}\cdot A}}$ ${\displaystyle 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.