# XOR gate from default-on/default-off relays, this simplest possible?

Playing nandgate to learn logical gates. Is the design below the simplest xor gate that can be built using the relays available? Seems like crossover relays allow a much simpler xor gate but don't have those there. "Simplest" is not well-defined so I assume you are interested in knowing if you can use less than 7 relays of types "default-off" or "default-on".

It seems that a default-off relay is essentially an "and" gate (both the "in" and the "on" input must be high for the output to be "high"). I will denote this with $$\wedge$$.

A default-on relay is essentially an "and" gate where one of its inputs is negated. I will denote $$\neg a \wedge b$$ with $$a \otimes b$$ (notice that $$\otimes$$ is not commutative!). As a consequence, $$a \otimes 1 = \neg a \wedge 1 = \neg a$$ and $$a \vee b = \neg (\neg a \wedge \neg b) = ((a \otimes 1) \wedge (b \otimes 1)) \otimes 1.$$ This shows that $$a \vee b$$ can be computed using $$4$$ relays.

Consider then:

\begin{align*} a \oplus b &= (\neg a \wedge b) \vee (\neg b \wedge a) = (a \otimes b) \vee (b \otimes a) \\ &= (((a \otimes b) \otimes 1) \wedge ((b \otimes a) \otimes 1)) \otimes 1 \end{align*}

This shows that $$a \oplus b$$ can be computed using at most $$6$$ relays, while your solution uses 7.

Following you comment it seems that you are interested in minimizing the number of relays. The following solution uses only 5 relays. Let $$\overline{b} = \neg b = b \otimes 1$$. Then: $$a \oplus b = (a \otimes \overline{b}) \otimes ((\overline{b} \otimes a) \otimes 1).$$

Notice that $$\overline{b}$$ can be found using only one relay but it is then used twice in the expression for $$a \oplus b$$. Here is the corresponding truth table:

$$a$$ $$b$$ $$\overline{b}$$ $$a \otimes \overline{b}$$ $$\overline{b} \otimes a$$ $$(\overline{b} \otimes a) \otimes 1$$ $$(a \otimes \overline{b}) \otimes ((\overline{b} \otimes a) \otimes 1)$$
0 0 1 1 0 1 0
0 1 0 0 0 1 1
1 0 1 0 0 1 1
1 1 0 0 1 0 0

An exhaustive search shows that there are no solutions using at most 4 relays. Moreover, this shows that $$5$$ relays suffice even when just default-off relays are available.

• Thank you very much for your really good answer, helps a lot. Yes was asking mostly about less components. I'm able to do the 𝑎∨𝑏=¬(¬𝑎∧¬𝑏), i.imgur.com/Wn1cO0D.png, but, 𝑎⊕𝑏=(¬𝑎∧𝑏)∨(¬𝑏∧𝑎) with the OR operator, what does it look like using just the relays? Is it ¬((¬(¬𝑎∧𝑏))∧(¬(¬𝑏∧𝑎))), or can it be simplified? Aug 17 at 12:06
• I gave an expressions that computes $a \oplus b$ using just relays (i.e., $\wedge$ and $\otimes$) at the end of the (first part) of my answer. That expression requires $6$ relays. Moreover, I have added an alternative construction that uses $5$ relays. This is optimal since an exhaustive search shows that it is impossible to compute $a \oplus b$ using $4$ or less relays. Aug 17 at 17:27