Lecture 4

Basic Logic Functions

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 | D

This 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 X

For 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)

NOT

Lets look at the simplest possible logic function:

x|z
-|-
0|1
1|0

This 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 NOT function and is drawn as shown below.

This is the Logic Symbol for NOT.

z=NOT x Lets use NOT to see if we can make some of the two input logic functions redundant.

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.

AND

The AND function:

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

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

Logic Symbol

OR

The OR function:

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|1

Logic Symbol

XOR

The Exclusive OR function:

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

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

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 XOR

These 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;

#include <stdio.h>

void main() {
   int n1=0xff00; // some hex numbers
   int n2=0x1234;
   int n3=0xf00f;

   printf("%x & %x = %x\n",n1,n2,n1 & n2); // some bitwise operations 
   printf("%x | %x = %x\n",n1,n2,n1 | n2); // on these numbers
   printf("%x & ~%x = %x\n",n1,n2,n1 & ~n2);
   printf("%x ^ %x = %x\n",n2,n3,n2 ^ n3);
}