#### putianyi888

##### Terrarian

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).