Assignment #2, Question 2f

Using compositions of {OR, IMPL}, and x=(0011) y=(0101), can all 16 binary functions be represented?

I worked systematically using Prof. Zabrocki's suggestion during Monday's class.

I found that I could only represent 6 of the 16 binary functions; namely: (0011), (0101), (0111), (1101), (1011), (1111).

Notice that because I am only using compositions of {OR, IMPL}, the likelihood of (***0) happening is impossible.

So I will not be able to represent:

(0000), (0010), (0100), (0110), (1000), (1010), (1100), (1110).

Also note that {OR, IMPL} = {OR, x OR NOT(y)}. I can therefore not reproduce or represent binary operations that utilize {AND, NOT} directly.

So I will also not be able to represent:

(1001), (0001).