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

— Merlin, The Coder

Boolean Algebra[edit]

Background[edit]

The branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. It is a formal description of logical relations. It was introduced by George Boole in his first book The Mathematical Analysis of Logic in 1847.

Logic Gates[edit]

An idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces a single binary output.

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

Composition[edit]

Logic gates can be cascaded in the same way that Boolean functions can be composed, allowing the construction of a physical model of all of Boolean logic.

References[edit]

Boolean Algebra (Wikipedia)
De Morgan's Laws (Wikipedia)
Logic Gates (Wikipedia)