Self-referential circuit

This is a more "real" version of the previous edition , now actually saying what you need to do. However, it's also easier than that: there are only three outputs at the bottom, so we can try all $2^3 = 8$ combinations and feed them through the circuit to check which one works.

But let's actually solve this thing in a more interesting fashion. Call the outputs of the gates $A, B, C, D, E, F$ in the same order as they are asked in the answer. Let $\cdot, +, \oplus$ be AND, OR, XOR gates respectively, and $\overline{x}$ as negation of $x$ . Let 1 stands for true and 0 stands for false. The equations are:

• $A = E + F$
• $B = D \cdot A$
• $C = A \oplus F$
• $D = \overline{D \oplus B}$
• $E = \overline{B + C}$
• $F = \overline{C \cdot E}$

Note that $\overline{x} = x \oplus 1$ , so the fourth equation can be rewritten as $D \oplus 1 = D \oplus B$ . But we can cancel like terms in XOR (or otherwise XOR both sides with $D$ ), so we get $B = 1$ .

And that's all the hard work. Feeding $B = 1$ to the second equation, we get $A = D = 1$ (the only way to make an AND to give 1). Feeding $B = 1$ to the fifth equation, we get $E = 0$ (because $B+C = 1$ no matter what $C$ is). From the first equation, since $A = 1$ and $E = 0$ , the only way to satisfy it is $F = 1$ . Since we now have $A = F = 1$ , we can plug it in to the third equation to give $C = 0$ . We can verify all equations are satisfied with this assignment: $(A, B, C, D, E, F) = (1, 1, 0, 1, 0, 1)$ . Thus that's our answer, $\boxed{110101}$ .

Here is an (abstract) algebraic approach using the finite (Galois) field $GF(2)$ (just $\{0,1,+,\cdot\}$ with mod 2 arithmetic). It gives a systematic approach to these kinds of problems. First, the logical gate operators can be formed as algebraic expressions in operators, constants, and variables $x, y$ in $GF(2)$ . $\begin{aligned} &\text{NOT } x = 1 + x \;, \\ &x \text{ AND } y = xy \;, \\ &x \text{ XOR } y = x + y \;, \\ &x \text{ OR } y = x + y + xy \;. \\ \end{aligned}$ Next, assign gate output variables $\{b_n\}_{n=0, …,5} \in GF(2)$ as shown in the figure. As per the circuit diagram, equate the logical gate outputs based on the inputs to the assigned output variables to produce the following system of equations:

$\begin{aligned} (0) \; &b_0 = 1 + b_1 b_3 \; ,\\ (1) \; &b_1 = 1 + b_3 + b_4 + b_3 b_4 \; ,\\ (2) \; &b_2 = 1 + b_2 + b_4 \; ,\\ (3) \; &b_3 = b_0 + b_5 \; ,\\ (4) \; &b_4 = b_2 b_5 \; ,\\ (5) \; &b_5 = b_0 + b_1 + b_0 b_1 \; .\\ \end{aligned}$

Solve by using $GF(2)$ ’s multiplicative idempotency ( $x^2 = x$ ) and additive nilpotency ( $x + x = 0$ ) for simplification (along with its other props).

Add $b_2$ to both sides of (2): $b_2 + b_2 = b_2 + 1 + b_2 + b_4 \iff 0 = 0 + 1 + b_4.$ Add 1 to both sides: $1 + 0 = 1 + 1 + b_4 \iff 1 = b_4 \therefore b_4 = 1.$

Sub $b_4$ into (1): $b_1 = 1 + b_3 + b_4 + b_3 b_4 = 1 + b_3 + 1 + b_3 \cdot 1 = (1 + 1) + (b_3 + b_3) = 0 + 0 = 0 \therefore b_1 = 0.$

Multiply (1) by $b_3$ : $b_3 b_1 = b_3 \cdot 1 + b_3^2 + b_3 b_4 + b_3^2 b_4 = (b_3 + b_3) + (b_3 b_4 + b_3 b_4) = 0 + 0 = 0 \therefore$ $(6) \; b_1 b_3 = 0 \qquad \qquad \;.$ Sub (6) into (0): $b_0 = 1 + b_1 b_3 = 1 + 0 = 1 \therefore b_0 = 1.$

Sub $b_0$ and $b_1$ into (5): $b_5 = b_0 + b_1 + b_0 b_1 = 1 + 0 + 1 \cdot 0 = 1 + 0 + 0 = 1 \therefore b_5 = 1.$

Sub $b_0$ and $b_5$ into (3): $b_3 = b_0 + b_5 = 1 + 1 = 0 \therefore b_3 = 0.$

Sub $b_4$ and $b_5$ into (4): $b_4 = b_2 b_5 \iff 1 = b_2 \cdot 1 = b_2 \therefore b_2 = 1.$

Therefore, $b_5 b_4 b_3 b_2 b_1 b_0 = \boxed{110101_2} = 53_{10} .$

Not as elegant, but a truth table approach...

Let ABC be three inputs top to bottom, outputs 1 to 6 from the outputs of the gates in order top to bottom, left to right

By reversing 4 to 6 so their outputs match AtoC we see only 101 input matches 101 output so the coded answer is the middle six bits.

ABC 123456 654

000 000111 111

001 000010 010

010 101100 001

011 111100 001

100 100111 111

101 110101 101 in=out

110 100111 111

111 110101 101

Answer = 110101

If we rename the gates according to their positions top to bottom first, then left to right by the row, then the we'll have an OR A, AND B, XOR C, XNOR D, NOR E and NAND F.

A = E + F
B = A × D
C = F 🔀 A
D = –( D 🔀 B )
E = –( B + C )
F = –( C × E )

Let's look at D, since it's one of the special self-made gate. As an XNOR gate, it will outputs 1 for the same inputs and outputs 0 for different inputs. Therefore, the only possible B in both cases is B = 1. Then, AND B can only have A = D = 1 as inputs itself, while at the same time will influence NOR E to be 0. E = 0 would need F = 1 as an input pair in a positive OR A, and C = 1 🔀 1 = 0 is the final output that we need here.

Answer = 110101

One way to solve can be to start from the bottom of the circuit and call the 3 outputs as x , y and z . Then if we feed y and z (as per circuit) to first gate which is the OR / addition gate. We get

Output 1= y+z

Output 2= x(y+z)

Output 3= yz'

Output 4 = x'+xy+xz which is also equal to x

Output 5 = x'y'+x'z+y'z' which is also equal to y

Output 6 = y'+z which is also equal to z

Thus we get 3 equations and starting with y'+z = z we see that there are 2 possible solutions,

1) y=1 and z either 0 or 1. But with this the output 4 equation gives x=1 but then equation 5 is not satisfied.

2) y=0 and z=1. In this case we get from output 4 that x=1 and the output 5 is satisfied. Thus x=1, y=0, z=1. Hence Output 1 = 1, Output 2 = 1 and Output 3 = 0.

Thus the answer will be 1,1,0,1,0,1.