Boolean Algebra

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

— Merlin, The Coder

Background

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

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.

Truth Tables

Truth tables provide us with a straightforward means to specify the required output(s) for the specified input(s), in table form. On the left-hand side of the table we enumerate the input(s) and on the right-hand side of the table we specify the output(s). Assuming that we have $n$ inputs we may label each input as $I_{1},I_{2},I_{3},...I_{n}$. The value of the inputs on any given row, may be referred to as an input tuple. Likewise, assuming that we have $m$ outputs we may label each output as $O_{1},O_{2},O_{3},...O_{n}$, and the value of these outputs on any given row may be referred to as an output tuple. The number of rows in any such table is given by the formula $2^{n}$.

Question

Why is the formula for determining the number of rows in a truth table related only to the number of inputs, and why is the formula $2^{n}$?

Note that for convenience we sometimes label inputs as A, B, C, etc. rather than $I_{1},I_{2},I_{3},$ etc. and do the same for outputs, often beginning with the letter Q.

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

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.

De Morgan's Laws

• $A\land B\Leftrightarrow \neg (\neg X\lor \neg Y)$
• $A\lor B\Leftrightarrow \neg (\neg X\land \neg Y)$

References

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