Mostrar funcionalmente la integridad de la propiedad para la lógica proposicional

Question

Deje $n>0, n\in \mathbb{Z}$ y sea t,f denotan la verdadera y la falsa.

Para cada función

$$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, utilizando sólo las conectivas $\neg, \wedge$ y se construye a partir de la atómica fórmulas de $P_1,\ldots, P_n$ tal que para cada asignación de verdad $$\mathcal{A}:\{P_1,\ldots, P_n\}\to \{t,f \}$$

$$A\modelos de B \text{ si y sólo si } g(\mathcal{A}(P_1),\ldots , > \mathcal{A}(P_1)) = t$$

Yo no sé realmente cómo probar esto. Yo entiendo que de alguna manera debe el código anterior como una fórmula y, a continuación, "reducir" a un equivalente de la fórmula que consta sólo de $\neg, \wedge$ usando el bien conocido equivalencias y, a continuación, probar la de arriba con la inducción. Yo realmente no se por donde empezar. Cualquier ayuda o referencias de donde esto queda demostrado en detalle sería muy apreciada.

Answer 1

La prueba naturalmente, como una inducción en $n$:

(Caso Base) Deje $n=1$. Esto es suficiente para mostrar que no hay una fórmula que consta de $\neg, \wedge$ con el de todos los posibles unario conectivas se definen por los siguientes 4 tablas de verdad:

$$\begin{array} {|c|} \hline 1 & 1 \\ \hline 0 & 1 \\ \hline \end{array} \begin{array} {|c|} \hline 1 & 1 \\ \hline 0 & 0 \\ \hline \end{array} \begin{array} {|c|} \hline 1 & 0 \\ \hline 0 & 1 \\ \hline \end{array} \begin{array} {|c|} \hline 1 & 0 \\ \hline 0 & 0 \\ \hline \end{array}$$ es decir, las proposiciones $\neg(P \wedge \neg P)$, $P$, $\neg P$ y $P \wedge \neg P$ respectivamente.

(Inductivo Caso) Inductivo Hipótesis: Supongamos que para cada $n$-ary conectivo que se define por su valoración de la función, hay fórmulas que consta de $\neg, \wedge$. Tenemos que mostrar que para cada $n+1$-ary conectivas, proposiciones se han encontrado (se Puede seguir desde aquí?)