putianyi888
Terrarian
The idea came from this thread. The full adder by @ekinator surprised me quite a bit because I had always thought that the complexity of a single logic gate is too small to express the logic in a full adder. Then I began to think of the complexity of a single logic gate. I came up with some methods with which I made a key part of a binary-to-BCD decoder much smaller than that within this thread.
You don't need to know the wiring because I will show the logical expression later.
Note that the Terrarian XOR gate does not perform the XOR operation in reality. Because terrarian XOR doesn't satisfy the associative law, I would consider it as a function ^() rather than an operator.
But Terraria does have a real XOR operation which is to simply connect two or more inputs to one lamp. According to how it seems like in game, we simply denote a XOR b by ab. This free operation significantly raises the complexity of logic gates.
Any combinational logic is associated with a unique truth table. The size of a truth table is (n+1)x2^n where n denotes the number of inputs. The first step is to reduce the size of the truth table.
Let F denote the combinational logic with inputs a_1,...,a_n.
Define size(F) as the 1's in the (n+1)-th column of the truth table of F.
In terraria, F is basically the same as ~F, so we can assume that size(F) is at most 2^(n-1).
Let M be a matrix whose rows are all possible inputs (a_1,...,a_n) with F=1. For example, if F=^(a,b,c), then F=1 if and only if (a,b,c)=(1,0,0), (0,1,0) or (0,0,1). Thus M should be:
It's clear that switching rows of M doesn't matter. Switching rows doesn't make any sense as well.
From now on, we regard M as the truth table of F. The approach is to transform M to some specific truth tables which can be achieved by a single logic gate.
Truth Tables of Single Logic Gates
There are two distinct combinational logic gates in Terraria: the AND gate and the XOR gate.
A single AND gate has a logical expression of s_1&s_2&...&s_r where s_i's denote strings of {~,a_1,...,a_n}. The number of &'s is one less than that of lamps on the gate. For example, consider F with three inputs a,b and c, then a&b&c, a&~b&~c, a&b, ab&c and abc can all be achieved with a single AND gate:
The truth tables of these logics are:
A single XOR gate has a logical expression of ^(s_1,s_2,...,s_r) where s_i's are the same as above. XOR gates only make sense with more than 2 inputs. The examples here are ^(a,b,c) and ^(ab,b,c):
As there are many candidates of those strings, a single logic gate can play quite a few logics. The problem is, given the truth table of ^(ab,b,c), how can we find the logical expression?
before:
after:
This still doesn't make much sense. Now we add column b to column a. The addition is actually XOR operation: 0+0=1+1=0, 0+1=1+0=1. Also we have to add the column titles. When two column titles add, simply put the letters together and cancel letters which appear twice.
before:
after:
This truth table is the same as the truth table of a&b (see above), so we conclude that the original truth table is associated with expression ab&c.
There is another transformation that I didn't use in the example. We can switch 1's and 0's of a column and add '~' to the column title. The addtion also follows the string addition rule.
Given any truth table, we implement three operations: switching columns, adding a column to another and, switching 1's and 0's of a column. The truth table may become our known truth table and we obtain a simplified logic.
As I have promised, I'm going to put the logical expression of the part of binary to BCD decoder. It has 4 inputs denoted by a,b,c,d and 4 outputs denoted by A,B,C,D, all from higher digit to lower digit. The truth tables of A,B,C and D are shown below:
The truth table of B can be transformed to below, which tells that B=ab&~c&~ad.
The truth table of C can be transformed to below, which tells that C=^(a,b,cd,bd).
The truth table of D can be transformed to below, which tells that D=^(a,b,bc,bcd).
The truth table of A cannot be transformed to a good enough table, so we have to take "undefined" inputs into consideration. The inputs can only be 0 to 9, so given 10 to 15, the output can be arbitrary. So we add another 6 rows marked with 'x' to note that these rows can be freely deleted.
Add column b to column a, then the column ab has 7 1's. If it had 8 1's, we could have A=ab. The exception is 0100, so we can add a gate to exclude the exception: A=ab(~a&b&~c&~d).
You don't need to know the wiring because I will show the logical expression later.
NOTATIONS
'&' denotes the operator AND. '~' denotes the operator NOT. Note that the Terrarian XOR gate does not perform the XOR operation in reality. Because terrarian XOR doesn't satisfy the associative law, I would consider it as a function ^() rather than an operator.
But Terraria does have a real XOR operation which is to simply connect two or more inputs to one lamp. According to how it seems like in game, we simply denote a XOR b by ab. This free operation significantly raises the complexity of logic gates.
THE TRUTH TABLE
DefinitionsAny combinational logic is associated with a unique truth table. The size of a truth table is (n+1)x2^n where n denotes the number of inputs. The first step is to reduce the size of the truth table.
Let F denote the combinational logic with inputs a_1,...,a_n.
Define size(F) as the 1's in the (n+1)-th column of the truth table of F.
In terraria, F is basically the same as ~F, so we can assume that size(F) is at most 2^(n-1).
Let M be a matrix whose rows are all possible inputs (a_1,...,a_n) with F=1. For example, if F=^(a,b,c), then F=1 if and only if (a,b,c)=(1,0,0), (0,1,0) or (0,0,1). Thus M should be:
It's clear that switching rows of M doesn't matter. Switching rows doesn't make any sense as well.
From now on, we regard M as the truth table of F. The approach is to transform M to some specific truth tables which can be achieved by a single logic gate.
Truth Tables of Single Logic Gates
There are two distinct combinational logic gates in Terraria: the AND gate and the XOR gate.
A single AND gate has a logical expression of s_1&s_2&...&s_r where s_i's denote strings of {~,a_1,...,a_n}. The number of &'s is one less than that of lamps on the gate. For example, consider F with three inputs a,b and c, then a&b&c, a&~b&~c, a&b, ab&c and abc can all be achieved with a single AND gate:
The truth tables of these logics are:
A single XOR gate has a logical expression of ^(s_1,s_2,...,s_r) where s_i's are the same as above. XOR gates only make sense with more than 2 inputs. The examples here are ^(a,b,c) and ^(ab,b,c):
As there are many candidates of those strings, a single logic gate can play quite a few logics. The problem is, given the truth table of ^(ab,b,c), how can we find the logical expression?
TRANSFORMATION OF TRUTH TABLES
I have talked about switching of rows, which is a useless way to transform M. There are ways to change M as well. Similarly, we can switch columns with there titles as well. For example, we switch column b and column c of M of ab&c:before:
This still doesn't make much sense. Now we add column b to column a. The addition is actually XOR operation: 0+0=1+1=0, 0+1=1+0=1. Also we have to add the column titles. When two column titles add, simply put the letters together and cancel letters which appear twice.
before:
This truth table is the same as the truth table of a&b (see above), so we conclude that the original truth table is associated with expression ab&c.
There is another transformation that I didn't use in the example. We can switch 1's and 0's of a column and add '~' to the column title. The addtion also follows the string addition rule.
Given any truth table, we implement three operations: switching columns, adding a column to another and, switching 1's and 0's of a column. The truth table may become our known truth table and we obtain a simplified logic.
As I have promised, I'm going to put the logical expression of the part of binary to BCD decoder. It has 4 inputs denoted by a,b,c,d and 4 outputs denoted by A,B,C,D, all from higher digit to lower digit. The truth tables of A,B,C and D are shown below:
The truth table of B can be transformed to below, which tells that B=ab&~c&~ad.
The truth table of C can be transformed to below, which tells that C=^(a,b,cd,bd).
The truth table of D can be transformed to below, which tells that D=^(a,b,bc,bcd).
The truth table of A cannot be transformed to a good enough table, so we have to take "undefined" inputs into consideration. The inputs can only be 0 to 9, so given 10 to 15, the output can be arbitrary. So we add another 6 rows marked with 'x' to note that these rows can be freely deleted.
Add column b to column a, then the column ab has 7 1's. If it had 8 1's, we could have A=ab. The exception is 0100, so we can add a gate to exclude the exception: A=ab(~a&b&~c&~d).