-1
$\begingroup$

I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output would need to depend on every input bit as just looking at some of them would leave out the possibility that those that weren't looked at could change the answer. Any help is appreciated.

$\endgroup$
  • $\begingroup$ Please specify in the question exactly what a MOD3 gate is, to avoid possible confusion. What function does it compute? $\endgroup$ – D.W. Apr 27 '18 at 0:32
  • $\begingroup$ Well a MOD3 gate would output 1 iff the remainder after dividing the sum of the input bits by 3 is non-zero. This definition would indicate that every input bit must be added in order to get the correct answer, no? $\endgroup$ – T. Pruden Apr 27 '18 at 0:57
  • $\begingroup$ Is this homework? $\endgroup$ – Albert Hendriks Apr 27 '18 at 1:54
  • $\begingroup$ The binary OR function has two inputs. $\endgroup$ – Yuval Filmus Apr 27 '18 at 7:39
  • $\begingroup$ This is part of my homework yes. This question isn't outright asked, but I've found in order to answer another part of the assignment I need to understand this. $\endgroup$ – T. Pruden Apr 27 '18 at 16:25
0
$\begingroup$

Well a MOD3 gate would output 1 iff the remainder after dividing the sum of the input bits by 3 is non-zero.

Well in this case an OR gate is simply a MOD3 gate with fan-in 2. Consider the truth table:

A  B  (A + B) % 3  OUT
0  0      0         0
0  1      1         1
1  0      1         1
1  1      2         1
$\endgroup$
  • $\begingroup$ I see. I was completely misinterpreting the question being asked. Thanks for the answer $\endgroup$ – T. Pruden Apr 27 '18 at 16:25

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.