Assignment #2, Question 5

This is a tricky one...

One answer is that I would need 3^9 binary operations to represent every possible two argument function on Trinary operations. But this could be labeled a 'crappy answer'.

So, a more interesting question to answer would be what is the minimal number of binary operations needed to represent every possible two argument function on Trinary.

I immediately attempted using familiar binary operations such as {AND, OR, NOT} but soon found that the NOT operation did not make too much sense on Trinary.

That is, how would NOT 1 look like? Well NOT 1 in Trinary would be 2 or 0. The problem we run into is how to logically differentiate between the two? I abandoned this method.

Instead I made new symbols that might satifsy this question.

I believe I would need at least 4 binary operations to represent every possible two argument function on Trinary. Mind you it would have to be 'repeated' applications of one, two, three, or all four of these NEW operations...Much like how we can use compositions of {AND, OR, NOT} to represent every possible binary operation in binary.

The new symbols are:

SHIFTRIGHT= function shifts entire line to the right, last digit moves to the start of string = (100100000) = (010010000)
INSERT 1 = function replaces number in the 1st space with a 1 = (000000000) = (100000000)
INSERT 2 = function replaces number in the 1st space with a 2 = (000000000) = (200000000)
INSERT 0 = function replaces number in the 1st space with a 0 = (100000000) = (000000000)

Using these symbols you can apply them repeatedly to represent every possible binary operation on Trinary.