3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Why it's sufficient to show incompleteness "as long as we work with at most two sentence letters"? $\endgroup$
    – User
    Jun 28 '13 at 13:26
  • $\begingroup$ I've edited the question and added my specific operator. Surprisingly, it's also symmetric, and has the same result for different permutations $\endgroup$
    – User
    Jun 28 '13 at 13:40
  • $\begingroup$ @User: If $\#$ were complete, it could generate every Boolean function of two letters. I show that it cannot do so, so it must be incomplete. In the description of $T$, is $\oplus$ exclusive OR? $\endgroup$ Jun 28 '13 at 19:43
  • $\begingroup$ Yes, question edited $\endgroup$
    – User
    Jun 29 '13 at 18:48
1
$\begingroup$

A simplified form of your operator is:

$T = \neg X \lor \neg Y \lor W Z \lor \neg W \neg Z$

For $ W \ne Z $ this becomes:

$T = \neg X \lor \neg Y = \neg (X Y)$

This is a NAND with two inputs and thus a universal operator.

$\endgroup$
2
  • $\begingroup$ But I can't rely on $ W \ne Z $... $\endgroup$
    – User
    Jun 29 '13 at 19:41
  • 2
    $\begingroup$ If you are not allowed to assign constants to $W$ and $Z$, the operator $T$ is not universal. $T(x,x,x,x)$ yields $true$, but there is no combination of inputs to get a constant $false$. $\endgroup$ Jun 30 '13 at 8:59
1
$\begingroup$

Following this relevant question which I asked on cs.stackexchange, a relatively general and easy way that works many times is to use the property that if an operator $T$ is universal, then necessarily $T(x,...,x)=\neg x$. In your case: $$T(x,x,x,x)=(\neg x \vee \neg x\vee \neg x)\oplus(xxx)=\neg x\oplus x=1$$ And since this isn't $\neg x$, then $T$ necessarily isn't universal.

$\endgroup$

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.