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.

  • $\begingroup$ See Karnaugh map. $\endgroup$ – Git Gud Oct 29 '14 at 12:56
  • 1
    $\begingroup$ I believe you mean $n \in \mathbb{N}$.. $\endgroup$ – 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?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.