Surely you have heard about logic gates, such as AND, NOT, XOR, and many others. A logic gate is a tiny device with some inputs and outputs that implements a Boolean function. That is, the inputs and outputs are boolean values (0 or 1), and for each particular gate each output is uniquely determined by its inputs.
For example, the traditional NAND gate has two inputs (let’s call them x and y) and one output (z). All possible outputs of this gate are given in the truth table shown below. This gate computes the “not and” function: the output is true if and only if the logical “and” of both inputs is false.
It is a well-known fact that the NAND gate is universal: You can construct any other gate using only a finite set of suitably interconnected NANDs.
For example, consider the unary NOT gate – a gate that outputs 0 if the input is 1, and vice versa. This gate can be constructed using a single NAND gate: NOT(x) is the same as NAND(x,x).
Of course, sometimes the construction is more involved. For example, to construct the binary XOR gate (a gate that returns 1 if the inputs are different and 0 if they are equal) we need at least four NAND gates. One possible construction: XOR(x,y) = NAND(NAND(x,NAND(x,y)),NAND(y,NAND(x,y))).
The above expression has five NANDs, but NAND(x,y) occurs twice, and can be implemented by a single gate in hardware, as shown in the figure below.
There are no universal unary gates, and only two universal binary gates: the gate NAND described above, and the gate NOR that implements the Boolean function “not or”.
Problem specification
In this problem we are interested in ternary gates: gates with three inputs and one output. An example of a ternary gate is the MAJ gate that returns the majority element – i.e., it returns 1 if at least two inputs are 1, and 0 if at least two inputs are 0. Below is the truth table of MAJ with inputs w, x, y and output z:
Easy subproblem J1: Find at least seven universal ternary gates.
Hard subproblem J2: Find all universal ternary gates.
Input specification
There is no input.
Output specification
Each line of your output file must describe a universal ternary gate, written as a space-separated list of zeroes and ones: the output row of its truth table, in order.
For the easy subproblem, the output must contain at least seven distinct rows, for the hard subproblem it has to contain all universal ternary gates. (I.e., any correct output for the hard subproblem will also be accepted if you submit it as your answer to the easy subproblem.)
Example output
This is a syntactically correct output file. It describes three ternary gates: the first row is MAJ, the second row is a gate that always returns 0, and the third row is the AND3 gate (ternary and): its output is the logical “and” of all three inputs.
(This is an incorrect output: it contains too few gates, and the gates it contains are not universal.)