I have to implement a circuit following the boolean equation A XOR B XOR C, however the XOR gates I am using only have two inputs (I am using the 7486 XOR gate to be exact, in case that makes a difference)… is there a way around this?
[Math] 3 input XOR gate
boolean-algebra
Related Solutions
(Note in passing that this is exactly the truth table for $b\to a$).
Hint: if that is the only gate you have, can you create any function that returns 0 when all its inputs are 1?
This is beyond easy ! :-$)$
S
|
.-------.
In1 _| |_ Out1
| |
In2 _| |_ Out2
| |
'-------'
When is $AB=1$ ? Only when $A=B=1$. Otherwise, if either A or B is $0$, then $AB=0$. In other words, $AB=\begin{cases}~0,\quad A=0\\B,\quad A=1\end{cases}$ . So connect one of the two values to the selector of the Fredkin gate $(S=A)$, and $0$ to the first input $(I_1=0)$, and the other value to the second input $(I_2=B)$. What will happen ? If $A=0$, then $O_1=I_1=0$. And if $A=1$, then $O_1=I_2=B$.
When is $A+B=0$ ? Only when $A=B=0$. Otherwise, if either A or B is $1$, then $A+B=1$. In other words, $A+B=\begin{cases}~1,\quad A=1\\B,\quad A=0\end{cases}$ . So connect one of the two values to the selector of the Fredkin gate $(S=A)$, and $1$ to the second input $(I_2=1)$, and the other value to the first input $(I_1=B)$. What will happen ? If $A=1$, then $O_1=I_2=1$. And if $A=0$, then $O_1=I_1=B$.
The implementation of the NOT gate is trivial, so I'll just leave that up to you! :-$)$ The tricky part, however, is implementing the XOR gate with only two Fredkin gates. Obviously, we'd be very comfortable using five, since $A\bigoplus B=\bar AB+A\bar B$ requires two negations, two conjunctions, and one disjunction, and we've already implemented all three operations above. But the good new is that we don't need to use that many. Indeed, two will suffice. To understand why this is so, please take a look at the truth table for the XOR gate, and try to express the output in terms of B for each value of A, just like I've done for the other two gates above. Can you take it from here ? ;-$)$
Best Answer
Take the output of A XOR B and pipe it into an XOR having C as the other input. (This implements (A XOR B) XOR C, and XOR is associative.