[Math] Is set of { AND , EXOR } gates functionally complete set

logicpropositional-calculus

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 .

Best Answer

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.

Related Question