Assignment #2, Question 1

In this question we were asked to show that every binary function (16 in total) can be expressed as a composition of binary operations {and, or, not}.

To make things easier to read, I will write each binary operation as a 4-tuple. That is, I will write x as (0011) and y as (0101).

Below I will write each of the 16 binary functions and an accompanying equivalent expression which uses a composition of {and, or, not} to explain how we can derive any given binary function using x and y.

Let:

X=(0011)

Y=(0101)

Find using {AND, OR, NOT}

0000= NOTx AND x

0001= x AND y

0010= x AND NOTy

0011= x

0100= NOTx AND y

0101= y

0110= x OR y and NOT (x AND y)

0111= NOTx OR x

1000= NOT (x OR y)

1001= Not (x OR y and NOT (xANDy))

1010= NOTy

1011= x OR NOTy

1100= NOTx

1101= NOTx OR y

1110= NOT (x AND y)

1111= y OR NOTy , x OR NOTx