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


"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 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 at 17:27

Your Answer

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

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