In boolean algebra, I could prove an operator is universal by implementing a NAND or NOR gate with it. But is there a way to prove a boolean operator isn't universal?
I would like to know a general method that should work for every (or almost every) incomplete operator.
Right now, I want to prove incompleteness of this operator:
$$ T(w,x,y,z) = (\neg w \lor \neg x \lor \neg y) \oplus (xyz)$$ After simplification I could write it like one of the following:
$$(\neg(wx y)) \oplus (xyz) =wxyz \lor \neg w\neg x \lor \neg w\neg y \lor \neg w\neg z \lor \neg x\neg y \lor \neg x\neg z \lor \neg y\neg z$$
$\oplus$ is the eXclusive OR operator, $\lor$ is OR, and I'm using implicit AND for simple reading
Yes, though the details generally depend considerably on the specific operator or operators. This answer is an example of the kind of argument that can be used. For more information you might read about functional completeness.
Added: If $T(w,x,y,z)=\neg(wxy)\oplus(xyz)$, then $T(x,x,x,x)=x\lor\neg x=\top$. (I use $\bot$ for false and $\top$ for true.) Suppose that each of the terms $t_1,t_2,t_3$, and $t_4$ is equivalent either to $x$ or to $\top$. Then $t_1t_2t_3$ is equivalent either to $x$ or to $\top$, as is $t_2t_3t_4$, and $T(t_1,t_2,t_3,t_4)$ is equivalent to one of $\neg x\oplus x=\top$, $\neg x\oplus\top=x$, $\bot\oplus x=x$, and $\bot\oplus\top=\top$. It follows by induction that every term built up from a single variable $x$ using $T$ is equivalent either to $x$ or to $\top$. In particular, $T$ cannot generate $\neg x$ and therefore is not universal.