Problems assigned to me in Assign #2

First 4 digits of my student # = 2070

2070 = 6 (mod 8) => Problem # 2 (g)

2070 = 5(mod7) => Problem # 6 (f)

2070 = 0(mod 3) => Problem # 3(a)

BIT STRING and LOGIC

Problem (1)

Show that every binary function(there are 16) can be expressed as a composition of the binary operations AND/OR and NOT

Solution:

Let

X = [0, 0, 1, 1] and

Y = [0, 1, 0, 1]

Then

NOT X = [1, 1, 0, 0]

NOT Y = [1, 0, 1, 0]

By successive division by 2 of 0 to 15 decimal digits we get 16 Binary Functions as:

00 = [0, 0, 0, 0]
01 = [0, 0, 0, 1]
02 = [0, 0, 1, 0]
03 = [0, 0, 1, 1]
04 = [0, 1, 0, 0]
05 = [0, 1, 0, 1]
06 = [0, 1, 1, 0]
07 = [0, 1, 1, 1]
08 = [1, 0, 0, 0]
09 = [1, 0, 0, 1]
10 = [1, 0, 1, 0]
11 = [1, 0, 1, 1]
12 = [1, 1, 0, 0]
13 = [1, 1, 0, 1]
14 = [1, 1, 1, 0]
15 = [1, 1, 1, 1]

By using AND, OR and NOT we can write these Binary Functions as:

[0, 0, 0, 0] = (X) AND (NOT X)
[0, 0, 0, 1] = (X) AND (Y)
[0, 0, 1, 0] = (X) AND (NOT Y)
[0, 0, 1, 1] = (X) AND (X)
[0, 1, 0, 0] = (NOT X) AND (Y)
[0, 1, 0, 1] = (Y) AND (Y)
[0, 1, 1, 0] = {(X) AND (NOT Y)} OR {(Y) AND (NOT X)}
[0, 1, 1, 1] = (X) OR (Y)
[1, 0, 0, 0] = (NOT X) AND (NOT Y)
[1, 0, 0, 1] = NOT{(X) AND (NOT Y)} OR {(Y) AND (NOT X)}
[1, 0 ,1, 0] = NOT Y
[1, 0, 1, 1] = (X) OR (NOT Y)
[1, 1, 0, 0] = NOT X
[1, 1, 0, 1] = (NOT X) OR (Y)
[1, 1, 1, 0] = NOT{(X) AND (Y)}
[1, 1, 1, 1] = (X) OR (NOT X)