# Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false.

For every function

$$g:\{t,f \}^n \to \{t,f\}$$ There is a propositional forumala $B$, using only the connectives $\neg, \wedge$ and built up from from the atomic formulas $P_1,\ldots, P_n$ such that for every truth assignment $$\mathcal{A}:\{P_1,\ldots, P_n\}\to \{t,f \}$$

$$A\models B \text{ if and only if } g(\mathcal{A}(P_1),\ldots , > \mathcal{A}(P_1)) = t$$

I don't really know how to prove this. I understand that I somehow must code the above as a formula and then "reducing" it to a equivalent formula consisting only of $\neg, \wedge$ using well known equivalences and then prove the above with induction. I don't really where to start. Any help or references to where this is proved in detail would be greatly appreciated.

• See Karnaugh map. – Git Gud Oct 29 '14 at 12:56
• I believe you mean $n \in \mathbb{N}$.. – Bruno Bentzen Oct 29 '14 at 14:48

The proof naturally goes as an induction on $$n$$:
(Basis Case) Let $$n=1$$. It suffices to show that there is a formula consisting of $$\neg, \wedge$$ with the all possible unary connectives defined by the following 4 truth tables:
$$\begin{array} {|c|} \hline P & \neg(P\wedge\neg P) \\ \hline 1 & 1 \\ \hline 0 & 1 \\ \hline \end{array} \begin{array} {|c|} \hline P & P \\ \hline 1 & 1 \\ \hline 0 & 0 \\ \hline \end{array} \begin{array} {|c|} \hline P & \neg P \\ \hline 1 & 0 \\ \hline 0 & 1 \\ \hline \end{array} \begin{array} {|c|} \hline P & P\wedge\neg P \\ \hline 1 & 0 \\ \hline 0 & 0 \\ \hline \end{array}$$
(Inductive Case) Inductive Hypothesis: Suppose that for every $$n$$-ary connective defined by its valuation function, there are formulae consisting of $$\neg, \wedge$$. We need to show that for every $$n+1$$-ary connectives, propositions have been found. (Can you continue from here?)