W1014 Logic Gates

From Coder Merlin
The 7400 chip contains four logical NAND gates.

Introduction[edit]

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[edit]

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

Formal Name Abbreviated Name Symbol Gate Truth Table
Buffer Gate Buffer.png
Inputs Outputs
0 0
1 1
Conjunction AND Gate AND.png
Inputs Outputs
0 0 0
0 1 0
1 0 0
1 1 1
Disjunction OR Gate OR.png
Inputs Outputs
0 0 0
0 1 1
1 0 1
1 1 1
Exclusive OR XOR Gate XOR.png
Inputs Outputs
0 0 0
0 1 1
1 0 1
1 1 0
Inverter NOT Gate Inverter.png
Inputs Outputs
0 1
1 0
Negated Conjunction NAND Gate NAND.png
Inputs Outputs
0 0 1
0 1 1
1 0 1
1 1 0
Negated Disjunction NOR Gate NOR.png
Inputs Outputs
0 0 1
0 1 0
1 0 0
1 1 0
Negated Exclusive OR NOT XOR Gate NOT XOR.png
Inputs Outputs
0 0 1
0 1 0
1 0 0
1 1 1

Additionally, a multiplexer is a device which selects from digital inputs and forwards the signal to a single output line. Given inputs, there are 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 Multiplexer-ABSQ.png
Inputs Outputs
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 Demultiplexer-ABSQ.png
Inputs Outputs
0 0 0 0
0 1 1 0
1 0 0 0
1 1 0 1

The Special Role of NAND and NOR Gates[edit]

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[edit]

ExercisesIcon.png
Exercises
  •  M1014-10  Complete  Merlin Mission Manager  Mission M1014-10

References[edit]

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