0

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

alphagamma
  • 15

1 Answers1

2

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

Lucian
  • 48,334
  • 2
  • 83
  • 154
  • 1
    Please, try not to call things "easy" especially "beyond easy", this would be very difficult for some people and not difficult at all for others. The only thing you can do by saying that is discouraging people. Furthermore, you didn't supply much useful information on the actually challenging part: The XOR gate. Also, you didn't say what A and B were, I assume they represent the inputs, IN1 and IN2, but have no way of knowing what they are because you didn't actually define them. – ICW Sep 14 '18 at 17:54
  • @YungGun: If you want to, we can discard the notations completely, and simply say the Boolean product of two variables is 1 only if both of them are 1, or the Boolean sum of two variables is 0 only if both of them are 0. As for the XOR gate, I believe my words are plain: try to express the output in terms of B for each value of A, where A and B are, of course, the XOR gate's two inputs. So, how many billions and trillions of Boolean values could the input A possibly take ? And, for each of these millions of possible values, how could we express the output in terms of the other input, B ? – Lucian Sep 14 '18 at 18:26
  • Thanks for response, maybe our ways of thinking are just too different? What do you mean billions of boolean values? There are but two boolean values: {0, 1}. That's what makes it boolean of course. I actually solved the problem through trial and error, and did so by experimenting and figuring out what kinds of gates you can make by inputting constants to the Fredkin as well as actual inputs. Then, combining two of these I was able to get the desired result, although it felt somewhat by chance. I still can't decipher what you're saying but thats ok you have your own way of getting it. – ICW Sep 15 '18 at 17:37
  • @YungGun: Yes, precisely, there are, of course, only two possible Boolean values. Now, as one of the two entries, A, is set to each of these two values, could we express, in each case, the output in terms of the other input, B ? Inspecting only two options is hardly a difficult task; after all, it's not as if we are asked to investigate millions, or perhaps even billions, of possible combinations. – Lucian Sep 15 '18 at 17:57