3

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

  1. XOR gates, NOT gates
  2. $2$ to $1$ multiplexers
  3. AND gates, XOR gates
  4. Three-input gates that output (A.B) + C for the inputs A, B and C.

My attempt $:$

Both option $(2)$ and $(3)$ are correct .

For $(2)$ , obviously $2$ to $1$ multiplexers are functionally complete set .

For option $(3)$ , as we have $1$ as input in option $(2)$ , so we can use $1$ as input in option $(3)$ , else option $(2)$ will not be true .

if we have explicitly 1 as input then- option (c) we have AND and XOR gate , we can derive NOT gate using XOR gate ,

$(1 XOR x) = 0.x + 1. x' = x' = NOT(x)$

now we have ( NOT , AND , XOR ) gates , since ( NOT and AND) gates are functionally complete set , so we can derive all other gates also .

Is set of { AND , EXOR } gates functionally complete set ?

Here explanation is given by sir , but I'm not satisfied (I explained in option $(3)$ with my best .) , I've not enough reputation to make any comment there .

Community
  • 1
Mithlesh Upadhyay
  • 4,787

2 Answers2

4

Your argument shows that $\{\land,\oplus,\top\}$ (i.e., AND, XOR, and $1$) is functionally complete: you need a source for that $1$ that you used, so if no input is $1$, it has to come from the available connectives (gates). If you have all three, you’re argument works, since $x\oplus\top=\neg x$. But if you have only the two binary connectives (gates), then you can’t get $\neg x$: when all inputs are $0$, you’ll always get the output $0$, as Henning said in his answer.

Brian M. Scott
  • 616,228
  • yes sir , when all inputs are $0$ , how we generate $NOT$ gate without input $1$ in $2x1$ multiplexers , I try to say both options is correct .rt ? – Mithlesh Upadhyay Nov 03 '15 at 18:09
  • @Mithlesh: I’m not familiar with multiplexers, but I just read the description of them in Wikipedia, and it appears to me that they’re not functionally complete either, for essentially the same reason: if both inputs are $0$, the output is necessarily $0$. – Brian M. Scott Nov 03 '15 at 18:13
  • You are right sir , but AFAIK $2x1$ multiplexers is functionally complete . Is it not ? – Mithlesh Upadhyay Nov 03 '15 at 18:17
  • @Mithlesh: If I understand them correctly, they’re not, and I see that Rob Arthan says the same in his answer. – Brian M. Scott Nov 03 '15 at 18:18
  • @BrianM.Scott: I wasn't reading these comments while I was writing my answer, I hope you don't mind being classified as very pure $\ddot{\smile}$. – Rob Arthan Nov 03 '15 at 18:22
  • @Rob: Not in the least; pretty hard for a set-theoretic topologist to avoid! – Brian M. Scott Nov 03 '15 at 18:23
2

A $2$ to $1$ multiplexer with inputs all false has its output false, which means you can't implement negation just with multiplexers, so the second component set is not functionally complete. As in the answer by Brian Scott about the third component set, you shouldn't assume you have the constants $0$ and $1$: $\{\mathsf{MUX}\}$ is not functionally complete but $\{0, 1, \mathsf{MUX}\}$ is. (Aside for very pure mathematicians: a multiplexer has three boolean inputs and computes $\mathsf{MUX}(X, Y, Z) = \mathsf{if}\,X\,\mathsf{then}\,Y\,\mathsf{else}\,Z$.)

Rob Arthan
  • 48,577