Digital Logic and Truth Tables

Information Processing Operations

We start with some fundamental operations on binary digits and work up to more complicated operations.

AND

x AND y

is a binary digit, defined by

x AND y = 1 if x = 1 and y = 1 = 0 otherwise

More explicitly, AND is defined by the table

x y x AND y 0 0 0 0 1 0 1 0 0 1 1 1

Diagrammatically:

Truth Tables

The table defining AND is usually called a truth table, and can be written out using false and true instead of 0 and 1.

x y x AND y false false false false true false true false false true true true

Yet another terminology is high and low for 1 and 0, referring to high and low voltage levels in electronics. We will use all these terms interchangeably, but we will normally stick to 0 and 1 when writing out truth tables.

OR

x OR y

is a binary digit, defined by

x OR y = 1 if x = 1 or y = 1 or both = 0 otherwise

The truth table for OR is as follows.

x y x OR y 0 0 0 0 1 1 1 0 1 1 1 1

Again, note that OR has the same meaning as in ordinary language: x OR y is true (i.e. 1) if x is true or y is true (or both).

Diagrammatically:

Example: Majority Voting

If x, y, z stand for the three votes, and r stands for the result, then we can write

r = (x AND y) OR (y AND z) OR (z AND x)

Diagrammatically:

NOT

x NOT x 0 1 1 0

A NOT gate is often called an inverter.

By using AND , OR and NOT in combination, it is possible to define any desired function on binary numbers - for example, addition or multiplication. We will see how to do this in a few lectures' time.

Perhaps surprisingly, we only need NOT and just one of AND and OR . We can check that the circuit

One Fundamental Operation

x y x NAND y 0 0 1 0 1 1 1 0 1 1 1 0

and drawn like this:

x NAND y = NOT (x AND y).

Assuming that we have NAND but not AND , OR or NOT , we can define the other operations as follows:

NOT x = x NAND x x AND y = NOT (x NAND y) x OR y = (NOT x) NAND (NOT y)

XOR

The operation with the second meaning is exclusive or, written XOR . If x and y are binary digits (either 0 or 1) then

x XOR y

is a binary digit, defined by

x XOR y = 1 if either x = 1 or y = 1 but not both = 0 otherwise

The truth table for XOR is as follows.

x y x XOR y 0 0 0 0 1 1 1 0 1 1 1 0

Diagrammatically:

Another Fundamental Operation

x NAND y = NOT (x AND y),

we can also define an operation called NOR by

x NOR y = NOT (x OR y).

Its truth table is as follows.

x y x NOR y 0 0 1 0 1 0 1 0 0 1 1 0

It is drawn like this:

NOT x = x NOR x x OR y = NOT (x NOR y) x AND y = (NOT x) NOR (NOT y)

Exercise: Check these equations.

Truth Table Exercise