2 Digital Logic

Representing binary logic

Digital logic uses two values, $0$ and $1$, to represent false and true. Boolean algebra provides rules for combining these values and describing how inputs determine an output. In circuit notation, NOT may be written $\neg A$ or $A'$, AND as $A \land B$ or $AB$, and inclusive OR as $A \lor B$ or $A+B$.

Several identities make expressions easier to simplify:

• $A+0=A$ and $A\land 1=A$.

• $A+A=A$ and $A\land A=A$.

• $A+A'=1$ and $A\land A'=0$.

For example, $(A\land 1)+(A\land 0)=A+0=A$. The first term reduces to $A$, while the second reduces to $0$.

De Morgan’s laws relate complements to AND and OR:

These identities can simplify a Boolean expression before it is implemented as a circuit.

Gates and truth tables

A logic gate implements one Boolean operation. A truth table describes the gate by listing its output for every possible input combination. With $n$ binary inputs, the table has $2^n$ input combinations.

For two inputs, the rows $(A,B)=(0,0),(0,1),(1,0),(1,1)$ give these outputs, in the same order:

• AND: $0,0,0,1$. It outputs $1$ only when both inputs are $1$.

• OR: $0,1,1,1$. It outputs $1$ when at least one input is $1$.

• XOR: $0,1,1,0$. It outputs $1$ when the inputs differ.

• NAND: $1,1,1,0$. It is the complement of AND.

• NOR: $1,0,0,0$. It is the complement of OR.

• XNOR: $1,0,0,1$. It outputs $1$ when the inputs match.

A NOT gate has one input and reverses it: $0$ becomes $1$, and $1$ becomes $0$. These operations can be combined to implement more complex Boolean functions.

From behavior to a circuit

A combinational circuit connects logic gates so that its outputs depend only on the current inputs. Because it has no dependence on earlier inputs or stored state, its behavior can be specified with a Boolean expression or a truth table.

A practical design sequence is:

1. Identify the inputs and the required output or outputs.

2. List the output for each possible input combination in a truth table.

3. Derive a Boolean expression for each output.

4. Connect gates to implement the expressions.

The truth table is the bridge between a circuit’s required behavior and its Boolean equations. Gate-level design then turns those equations into an implementation.

Example: the half adder

A half adder adds two one-bit inputs, $A$ and $B$, and produces a sum bit, $S$, and a carry bit, $C$. For input pairs $(A,B)=(0,0),(0,1),(1,0),(1,1)$, the corresponding sum values are $0,1,1,0$, and the carry values are $0,0,0,1$.

The sum is $1$ precisely when the inputs differ, so $S=A\oplus B$. The carry is $1$ only when both inputs are $1$, so $C=A\land B$. Thus, a half adder can be implemented with one XOR gate and one AND gate.

The example follows the full design sequence: specify the input-output behavior, express each output with Boolean algebra, and implement the expressions using gates. The key distinction is that the sum and carry are separate outputs, each with its own Boolean expression.