I am trying to prove that the set of five connectives:
$$\{ ¬, ∧, ∨, →, ↔\}$$
Is adequate (functionally complete) for all possible Boolean functions in propositional logic (only). I.e. EVERY Boolean function can be generated from these 5 operators.
This includes propositions with any number of atomic terms, i.e. the range from nullary operator on zero terms and 2 truth expressions $\{T,F\},$ through unary operator on one term and 4 truth functions, through binary+unary operators on two terms and 16 truth functions, all the way to <=n’ary operators on n terms generating 2^(2^n) functions, and presumably on to to infinite terms.
It is trivial to show that more minimal sets are producible. E.g. a set of ¬ and one of $\{ ∧, ∨, →\}$ is complete. As is the binary NAND or the binary NOR as singleton sets. These have all been shown to derive from the 5 operator set originally, then applying some law of logic to minimise that set one operator at a time.
However, I have been unable to prove the functional completeness of the (seemingly untrivial) 5 operator case for ANY Boolean Function with any number of terms.
Your help would be kindly appreciated.
Let $f$ be an $n$ary boolean function, $n\ge1$. Among all boolean $n$ary functions expressible with the five operators, let $g$ be one that agrees with $f$ for the maximal number of possible inputs. (Such $g$ exists because there are only finitely many inputs). Then $g$ agrees with $f$ on all inputs. For if we assume otherwise, there exists an assignment of $n$ values $a_1,\ldots, a_n\in\{T,F\}$ to the input parameters such that $f(a_1,\ldots,a_n)\ne g(a_1,\ldots, a_n)$. For each $i$, $1\le i\le n$, define $\phi_i:=\neg X_i$ if $a_i=T$ and define $\phi_i:=X_i$ if $a_i=F$. Then $$\hat g(X_1,\ldots, X_n):= g(X_1,\ldots,X_n)\leftrightarrow(\phi_1\lor\ldots\lor \phi_n)$$ is built from the 5 operators and agrees with $f$ on more inputs than $g$ does, contradiction