Consider the box shown above; it has two inputs, x and y, and one output,
z. If x, y and z are one bit binary numbers then the box performs a **logic
function**.

Consider all combinations of the two bits, x and y. There are 4 such combinations, 00, 01,10 and 11.

Now consider all the possible logic functions with these two bits as
inputs and one bit as the output.

For each of the 4 possible inputs there will be a value for the output.
We can completely describe this function using a table:

x y | z -----|--- 0 0 | A 0 1 | B 1 0 | C 1 1 | DThis is called a truth table, the values of ABCD completely describe the logic function.

We can now look at all the possible logic function by looking at values for ABC and D.

Each row in the following table is a logic function. There are 16 possible functions of two variables.

The columns represent DCB and A.

DCBA 1100 <-x 1010 <-y ---- 0000|0 X 0001|1 X 0010|2 X 0011|3 X 0100|4 X 0101|5 X 0110|6 z 0111|7 X 1000|8 1001|9 X 1010|a X 1011|b X 1100|c X 1101|d X 1110|e 1111|f XFor example row 6 is a logic function that is 1 when either x is one or y is one but not both.

We will use the hexadecimal row number to describe these functions.

Most of these functions are not useful.

0 and f are trivial, z is always the same.

c and a are also trivial (z=x and z=y)

x|z -|- 0|1 1|0This is a function with one bit input and one bit output. If x is one then z is 0, if x is 0 then z is one. This function is call the

This is the **Logic Symbol** for NOT.

- z=NOT x

If we write the functions as n(x,y), where n is 1..f then we can see the following:

1(x,y) is equivalent to NOT e(x,y)

2(x,y) is equivalent to NOT d(x,y)

3(x,y) is equivalent to NOT x

4(x,y) is equivalent to NOT b(x,y)

5(x,y) is equivalent to NOT y

9(x,y) is equivalent to NOT 6(x,y)

7(x,y) is equivalent to NOT 8(x,y)

also

b(x,y) is equivalent to e(NOT x,y)

d(x,y) is equivalent to e(x,NOT y)

This leaves 8, e and 6 which can not easily be reduced further.

8 is AND, e is OR, 6 is XOR.

z is one, only if x is one AND y is one.

xy|z --|- 00|0 01|0 10|0 11|1Truth Table

Logic Symbol

z is one, if x is one OR y is one OR both are one.

Note that this is not the common English usage of OR. If we say:

"This lecture is tedious, lets go to the Cinema OR the Beach"

This does not include both.

xy|z --|- 00|0 01|1 10|1 11|1Truth Table

Logic Symbol

z is one, if x is one OR y is one, but not both.

xy|z --|- 00|0 01|1 10|1 11|0Truth Table

Logic Symbol

In C, the following operators perform bitwise operations on every bit in an integer or pair of integers.~ Bitwise NOT & Bitwise AND | Bitwise OR ^ Bitwise XORThese should not be confused with the logical operators (&&,|| and !). C needs two types of operators because the value used for false is 0 and any other value is true. Using bitwise AND - (2 & 4)=0 but (2 && 4)=1;