I am reading about Functional Completeness in Wikipedia. In the "Formal Definition:
"Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, F is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in F"
But the article does not explain how any Boolean function (with n inputs) can be expressed in terms of binary Boolean functions. Can anyone prove this or refer me to a book where this is covered?
Thank you in advance.
One way to do this is with disjunctive normal form (DNF). I'll do an example of a 4-input function $f$.
Suppose that $f$ only outputs T for two inputs as shown in the partial truth table below. \begin{array}{|cccc|c|} A_1 & A_2 & A_3 & A_4 & f \\ \hline T & F & T & F & T\\ T & F & F & T & T\\ \end{array}
We can describe $f$ with the following formula that only uses binary Boolean functions, namely $\wedge$ and $\vee$,
$$ (A_1 \wedge \neg A_2 \wedge A_3 \wedge \neg A_4 )\vee (A_1 \wedge \neg A_2 \wedge \neg A_3 \wedge A_4) $$
Notice that there is a disjunct for every line of the truth-table where $f$ outputs $T$. The first disjunct describes the first line and the second disjunct the second line. You can generalize this process and express any n-ary function in DNF which only uses $\vee$ and $\wedge$.
Hope this helps