Sheet 5 - ternary binary operators

Question

Hello,

I have a question concerning sheet 05, Task 1b). Since the number of different binary operators is 16, calculated by 2^(2x2) = 16, the same calculation should work as well for ternary operators: 3^(3x3) = 19683.

But since this is a wrong solution, I don't see my fallacy and I couldn't find any other attempts on the internet as well.

Best regards

Jonas

Answer 1

The number of Boolean functions with n arguments is 2^{2^n} which you can see as follows: Imagine the truth table of the Boolean function. It has n argument variables and therefore 2^n many rows. For each row, you may choose as result value either 0 or 1, thus for row, there are two choices, and since these are all independent of each other, you have 2^rows = 2^{2^n} many Boolean functions with n arguments.

For n=3, you have 2^{2^3} = 2^8 = 256 such Boolean functions. So, when looking at 2^{2^2} not all 2s in that formula have the same role. Better remember the general case with 2^{2^n}.

Answer 2

Just to add to that: Note that the questions refers to binary and ternary boolean operators. Binary boolean operator has two inputs and ternary boolean operator has three inputs. Refer to slide 22/146 in propositional logic. For a n-ary boolean operator, there are 2^n possible input assignments (since input is a boolean variable). For each input assignment, the output value could be either 0 or 1 (since operator is a boolean operator). So we will have 2^(2^n) many n-ary boolean operators.

Your solution 3^(3^3) would have been correct if we would be considering operators in three-valued logic and not boolean (which is a two-valued) logic.

Comments

Two great minds think alike.

Answer 3

The question is: Why should it be 3^(3*3)?

To understand this, we try to understand where 2^(2*2) came from. We want to count the number of boolen functions with two and three operands. When are two boolean functions the same? They are the same, when they agree on the output for every given inputs. Since we are in binary logic, we have to possible output for every combination of inputs. That explains the base 2. Now we just need to know many possible combinations of inputs we have. That is the number of rows in a truth table. If we had just one input, then a truth table in binary logic has two rows. That explains a 2 in the exponent. If we now add one input variable, we duplicate the rows of the truth table for each possible input value. In boolean logic, that's two inputs. Hence, the other 2 in the exponent. If we now add a third input variable, we again double the number of rows.

Our truth table (for three input variables) has
2*2*2
rows.
That yields
2^(2*2*2)
unique truth tables.

What you answered isn't totally off! You computed the number of functions with two inputs in ternary logic.

Answer 4

Trank you very much vor all the detailed answers. My main fault was especially not to distinguish between boolean and three-valued Logic!