I read this set of notes regarding proving that a set of boolean functions are universal, i.e. that any boolean function can be written with those in the set:
http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf
I am curious about the function $x \circ y = x \lor \neg y$. The truth table is as follows:
x y output 0 0 1 0 1 0 1 0 1 1 1 1
Plainly, this function satisfies "preserves 1" (when x = 1 and y = 1, the output is 1), so it can't be universal according to Post. However, it appears to be universal, since you can derive NOT and OR as follows (using 0 for false and 1 for true):
$ 0 \circ x = 0 \lor \neg x = \neg x$
$ x \circ (0 \circ y) = x \lor \neg (0 \circ y) = x \lor \neg \neg y = x \lor y$
Since NOT and OR are a universal set, $\circ$ is universal - but it doesn't seem to fit Post's criteria. How is this possible?
The constants $0$ and $1$ should be considered as functions; they should either be included in your universal set or derivable from it. For example, from the set $\{\land,\neg\},$ we get $0=x\land\neg x$ and $1=\neg0.$
Your function $x\circ y$ is equivalent to $y\to x.$ By itself, it is not universal; every function obtainable from $\circ$ by composition has the property of being true when all the variables are true.
It's well known that $\{\circ,0\}$ or equivalently $\{\to,0\}$ is complete. The presentation of propositional logic in Alonzo Church's Introduction to Mathematical Logic used $\to$ and $0$ as the primitive connectives.