2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This is part of the question asked here. (My answer there describes among other things a systematic procedure for investigating completeness). $\endgroup$
    – hmakholm left over Monica
    Feb 9, 2013 at 20:47
  • $\begingroup$ @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. $\endgroup$
    – Amateur Math Guy
    Feb 9, 2013 at 21:22
  • $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Feb 9, 2013 at 21:30
  • $\begingroup$ Ok this makes sense now. Thanks! $\endgroup$
    – Amateur Math Guy
    Feb 9, 2013 at 21:35

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Feb 9, 2013 at 20:57

Not the answer you're looking for? Browse other questions tagged .