Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I’m working to understand proofs that involve showing the completeness (or incompleteness) of a set of binary connectives and I have run into some confusion. Alright, so I believe I understand how to show a set of binary connectives is complete; you just need to show that this set is equivalent to a set you know is complete. For example, in order to show that {|} (i.e. Sheffer’s Stroke ) is complete we note the following: $$ ¬ \alpha \Leftrightarrow \alpha | \alpha$$

$$ \alpha \vee \beta \Leftrightarrow (¬ \alpha) | (¬ \beta) $$

And since we know that {¬, $\vee$} is complete and this sets behavior can be simulated with only {|}, we know that {|} is complete.

But how would we show that a particular set of binary connectives is not complete? For instance how would we show that {$\rightarrow$}, {$\vee$}, or any other single binary connective except {$\downarrow$ } is not complete? Any help would be appreciated

share|cite|improve this question

marked as duplicate by Henning Makholm, Hagen von Eitzen, Ittay Weiss, Henry T. Horton, Davide Giraudo Feb 9 '13 at 21:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

This is part of the question asked here. (My answer there describes among other things a systematic procedure for investigating completeness). – Henning Makholm Feb 9 '13 at 20:47
@HenningMakholm Do you mind providing a quick example making use of the procedure you describe, I'm getting kind of lost in the wording and that examples original question is in sort of a different format. – Amateur Math Guy Feb 9 '13 at 21:22
André's answer here corresponds to the first (and in this case conclusive) step in my procedure: If, for example your connective is $\land$, the only function of one Boolean variable you can express is the identity, because $A\land A\equiv A$ -- so any expression built solely from $A$'s and $\land$ can be rewritten from the leaves up to $A$. Because the negation function cannot be expressed, so $\{\land\}$ is not complete. – Henning Makholm Feb 9 '13 at 21:30
Ok this makes sense now. Thanks! – Amateur Math Guy Feb 9 '13 at 21:35
up vote 1 down vote accepted

The fact that disjunction $\lor$ by itself, or even together with $\land$, is not complete can be shown by noting that if $A$ is the single proposition letter, then anything you construct using $\lor$ and/or $\land$ and the proposition letter $A$ must be true whenever $A$ is true. So in particular $\lnot$ cannot be simulated.

If you want a formal proof, it can be done by (strong) induction on the length of formulas.

The same argument works with say $\to$ by itself.

share|cite|improve this answer
This also works for $\leftarrow$, $\leftrightarrow$, the constant "True" function, and the two operators that always return their left (or right) operand unchanged and ignores the other one. A similar argument with "false" instead of "true" takes care of four more operators; the two $f(x,y)=\neg x$ and $f(x,y)=\neg y$ obviously can't produce nontrivial functions of more than one variable, and then there's only NOR and NAND left of the 16 possible binary boolean operators, which are known to be complete. – Henning Makholm Feb 9 '13 at 20:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.