ASSIGNMENT # 2 Q 2(g)

Problem:
Which (if any) of the possible binary functions can not be represented using only compositions of {XOR, IMPL}

Solution:

0000=x XOR x

0001=x XOR ((x IMPL y) XOR ((x XOR x) IMPL (x XOR y)))

0010=(x IMPL y) XOR ((x XOR x) IMPL (x XOR y))

0011=x

0100=x XOR(y XOR ((x IMPL y) XOR ((x XOR x) IMPL(x XOR y))))

0101=y

0110=x XOR y

0111=y XOR ((x IMPL y) XOR ((x XOR x) IMPL(x XOR y)))

1000=x XOR(y IMPL x)

1001=(x XOR y) IMPL(x XOR x)

1010=y IMPL(x XOR x)

1011=y IMPL x

1100=x IMPL(x XOR x)

1101=x IMPL y

1110=x IMPL(x XOR y)

1111=(x XOR x) IMPL(x XOR y)

Therefore all 16 functions can be written using only compositions of XOR and IMPL.