I have seen functional-completeness (in regards to boolean functions) defined as:

A set X of truth-functions (of 2-valued logic) is functionally complete if and only if for each of the five defined classes, there is a member of X which does not belong to that class

With those 5 classes being:






So since | is functionally-complete, this means it is not any one of the 5 type of functions listed above, right?

But I am not quite seeing how it is not self-dual, it seems like it IS self-dual. Could someone go over the self-dual functions and show the sheffer stroke is not self-dual?

  • $\begingroup$ What calculations have you done that make you think it is self-dual? $\endgroup$ – Rob Arthan Feb 10 '16 at 2:07

A Boolean operator $f(x_1, \dotsc, x_n)$ is self-dual iff $ f(\neg x_1, \dotsc, \neg x_n) = \neg f(x_1, \dotsc, x_n)$.

In the case of the Sheffer stroke (NAND), $(p|q) \equiv \neg (p \land q) \equiv (\neg p \lor \neg q)$, so $(\neg p | \neg q) \equiv (p\lor q)$, whereas $\neg (p|q) \equiv (p \land q)$. As $\lor$ and $\land$ are distinct Boolean functions, $|$ isn't self-dual.

  • $\begingroup$ Ah, ok, I see. Thank you $\endgroup$ – Boolean_functions Feb 10 '16 at 2:12
  • $\begingroup$ You're welcome. Tips appreciated ;) $\endgroup$ – BrianO Feb 10 '16 at 2:18
  • $\begingroup$ Sorry, your post made a lot of sense and so I almost forgot where my original confusion came from. ...So it doesn't matter that the function would appear to be self-dual if both operands were P? I was thinking of it and asking myself this: If we had (P|P) when P is true, then the function is false. Now if the negation of the function when P is false = false, than it would be self-dual. And it does. Checking the self-dual property needs to be done in terms of 2 distinct variables? $\endgroup$ – Boolean_functions Feb 10 '16 at 2:22
  • $\begingroup$ Self dual means: invert the value of the inputs => output value is inverted. Thus, $f(0,0) = \neg f(1,1)$. For $f=|$, $f(0,0) = 1, f(1,1) = 0$, so it non-self-duality is seen here too. $\endgroup$ – BrianO Feb 10 '16 at 2:44
  • $\begingroup$ But, yes that's correct: checking the self-dual property has to be done with distinct variables. $\endgroup$ – BrianO Feb 10 '16 at 2:54

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.