[Math] How to create an AND , OR , XOR and NOT gates with a fredkin gate

boolean-algebra

Ok so I am studying for an exam which is about logic gates and circuits , etc .The problem I have is with these two questions that are in the picture , it says build an AND , OR and NOT gate using logics 0 ,1 and one fredkin gate and then after build an XOR with two fredkin gates. I am aware what a fredkin gate is, but I don't understand how we picked those particular variables as inputs. I wouldn't ask this here ,but there is a limited amount of information regarding fredkin gates online and I need to know.
picture here…

Best Answer

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 ? ;-$)$

Related Question