# 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) 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.