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.

enter image description here


1 Answer 1


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

  • $\begingroup$ 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? $\endgroup$
    – Timeless
    Aug 17, 2021 at 12:06
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Aug 17, 2021 at 17:27

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.