Post's functional completeness theorem.
Norman M. Martin, Francis Jeffry Pelletier · Notre Dame Journal of Formal Logic · 1990
The paper provides a new proof, in a style accessible to modern logicians and teachers of elementary logic, of Post's Functional Completeness Theorem.Post's Theorem states the necessary and sufficient conditions for an arbitrary set of (2-valued) truth functional connectives to be expressively complete, that is, to be able to express every (2-valued) truth function or truth table.The theorem is stated in terms of five properties that an arbitrary connective may have, and claims that a set of connectives is expressively complete iff for each of the five properties there is a connective that lacks that property.Everyone knows the technique whereby, given an arbitrary (2-valued) truth table, one can construct a conjunctive (or disjunctive) normal form formula (using only connectives from {V,Λ,~ }) which has exactly that truth table.This proves that the set of connectives {V,Λ,~} is functionally complete: any (2valued) truth table can be constructed from them.Everyone also knows the definitions of Λ in terms of {v,~} and of v in terms of {Λ,~ j.This shows that {Λ,~ } and {v,~} are also functionally complete sets of connectives.Everyone also knows that the sheffer stroke functions, ΐ and I, are each functionally complete.Most everyone knows that {-sF} is functionally complete and that {->,γ} is functionally complete (F is the constant-false truth function, y is "exclusive or").Some people, having worked through Church ([1], p. 131f.), even know that {[ ],T,F} is functionally complete ([ ] is the ternary connective of "conditional disjunction": [p,q 9 r] means "if 47, then/?else r").However, what is not generally known is why these things are so.What is it about these particular sets of connectives that makes them functionally complete while (say) {<-•,-} is not functionally complete?Thanks are due to Errol Martin, Graham Priest, and an anonymous referee for discussions and help with some of the proofs.