# On the functional-completeness of the sheffer stroke

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:

Truth-Preserving

False-Preserving

Linear

Monotone

Self-Dual

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?

• What calculations have you done that make you think it is self-dual? – 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.
• 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. – BrianO Feb 10 '16 at 2:44