Ejercicio sobre las funciones de verdad en la "lógica matemática" de J.R.Shoenfield

Question

El primer ejercicio de la "lógica matemática" de Joseph R. Shoenfield es:

Una función de verdad n-aria $H$ es definible en términos de las funciones de verdad $H_1,\dots,H_k$ si $H$ tiene una definición $$H(a_1,\dots,a_n)=\dots$$ donde el lado derecho se construye a partir de $H_1,\dots,H_k$ , $a_1,\dots,a_n$ y comas y paréntesis.

a) Que $H_{d,n}$ sea la función de verdad definida al establecer $$H_{d,n}(a_1,\dots,a_n)=\mathbf{T} \iff a_i=\mathbf{T}$$ para al menos una $i$ y que $H_{c,n}$ sea la función de verdad definida al establecer $$H_{c,n}(a_1,\dots,a_n)=\mathbf{T}\iff a_i=\mathbf{T}$$ para todos $i$ .

Demuestre que toda función de verdad es definible en términos de $H_\neg$ y algunos de los $H_{d,n}$ y $H_{c,n}$

Donde $H_\neg$ es la negación unaria estándar ( $H_\neg(\mathbf{T})=\mathbf{F}$ y $H_\neg(\mathbf{F})=\mathbf{T}$ )

Mi opinión sobre este problema:
Podemos ver que esto es cierto para las funciones de verdad unarias probando los 4 casos y para todas las funciones de verdad binarias probando los 16 casos a mano.

Por ejemplo, considere la función de verdad definida por $$H(\mathbf{T},\mathbf{T})=\mathbf{F}$$ $$H(\mathbf{T},\mathbf{F})=\mathbf{F}$$ $$H(\mathbf{F},\mathbf{T})=\mathbf{F}$$ $$H(\mathbf{F},\mathbf{F})=\mathbf{T}$$ Es decir, en términos de las funciones permitidas por el problema $H_\neg(H_{d,2}(\mathbf{A},\mathbf{B}))$ , donde $\mathbf{A}$ y $\mathbf{B}$ son expresiones con un valor de verdad, posiblemente otras funciones de verdad.

Ahora que sabemos que este hecho es válido para las funciones de verdad binarias, podemos dividir cada $n$ -función de verdad en 2 partes, una unaria y otra $(n-1)$ -ario que se combinan en el original $n-ary$ función de verdad en una de las 16 formas posibles (y sabemos que todas son definibles en términos de la función permitida, porque las he comprobado a mano).
Ahora podemos razonar de la misma manera en el $(n-1)$ -y seguimos dividiendo hasta llegar a nuestro caso base de funciones binarias, demostrando así el hecho que debíamos demostrar.

El problema es que no sé si mi prueba es correcta y aunque lo sea creo que es bastante fea, implicando un montón de casos que hay que comprobar a mano, ¿hay alguna manera más fácil de abordar este problema? (Sería estupendo que me dierais una pista en lugar de la respuesta completa)
Gracias
Alessandro

Answer 1

He leído todo el problema en el libro de Shoenfield, y creo que está bastante claro que el autor está guiando a los lectores al concepto de conjunto de conectivos expresivamente adecuados (los que pueden expresar todas las funciones de verdad del lenguaje), dividiendo el proceso en varios pasos. Y no estoy seguro de lo que el autor quiere decir con "algunas de las $H_{d,n}$ y $H_{c,n}$ ". Tal vez todos los que queramos, o tal vez la opción "obvia": $H_{d,2}$ y $H_{c,2}$ (que son $H_{\lor}$ y $H_\&$ ). De hecho, no importa ya que cualquier $H_{d,n}$ es definible en términos de $H_{d,2}$ (y lo mismo para $H_{c,n}$ ):

$H_{d,n}=H_{d,2}(a_1,H_{d,2}(a_2,H_{d,2}(a_3,H_{d,2}(\dots,H_{d,n}(a_{n-1},a_n)\dots))))$

Tu prueba me parece correcta, pero creo que tu respuesta es un resultado mucho más fuerte que el que se pide en la parte (a) del problema. De hecho, si en el segundo paso demuestras que cualquier función binaria es definible en términos de $H_\neg$ y $H_{d,2}$ (que estoy seguro de que puedes hacer...), estás respondiendo a la pregunta b) del problema:

b) Demuestre que toda función de verdad es definible en términos de $H_\neg$ y $H_{\lor}$ . [Usa (a).]

Para la parte (a), yo haría lo siguiente, que equivale a escribir una fórmula en forma normal disyuntiva (uno o más disyuntos, cada uno de los cuales es una conjunción básica).

Dejemos que $H$ sea cualquier $n$ -función de verdad de tipo elemental. Entonces, o bien $H$ es siempre $\mathbf{F}$ o es $\mathbf{T}$ para al menos una valoración de sus argumentos:

• Si $H(a_1,\dots,a_n)=\mathbf{F}$ para cualquier valoración de $a_1,\dots,a_n$ entonces: $H(a_1,\dots,a_n)=H_{d,n}(H_{c,2}(a_1,H_\neg(a_1)),H_{c,2}(a_2,H_\neg(a_2)),\dots, H_{c,2}(a_n,H_\neg(a_n)))$ (o cualquier otra expresión que cumpla los criterios del problema y tenga el valor constante $\mathbf{F}$ ).

• Digamos que $H=\mathbf{T}$ para $m$ diferentes n-tuplas (valoraciones). Entonces $H=H_{d,m}(H_{c,n}(1),\dots,H_{c,n}(m))$ donde cada $H_{c,n}(i)$ se construye de la siguiente manera: es la misma que la función $H_{c,n}$ pero con la negación unaria aplicada a cualquier argumento cuyo valor en la tupla i (valoración) sea $\mathbf{F}$ . Por ejemplo, si $H=\mathbf{T}$ sólo para los dos casos: $a_1=\mathbf{F}$ , $a_2=\dots=a_n=\mathbf{T}$ y $a_1=\dots=a_{n-1}=\mathbf{T}, a_n=\mathbf{F}$ entonces:

  $H(a_1,\dots,a_n)=H_{d,2}(H_{c,n}(H_\neg(a_1),a_2,\dots,a_n),H_{c,n}(a_1,a_2,\dots,H_\neg(a_n)))$

  Es fácil comprobar que esto se evalúa como $\mathbf{T}$ sólo en esos dos casos, porque de hecho se ha construido para ello.

Entonces, esto demuestra que cualquier función n-aria $H$ es definible en términos de $H_\neg$ , $H_{c,n}$ , $H_{c,2}$ y una función $H_{d,m}$ . Pero (dadas las observaciones anteriores sobre las funciones binarias), esto implica que es definible en términos $H_\neg$ , $H_{\lor}$ y $H_{\&}$ .

Answer 2

Me parece correcto. Esencialmente estás probando esto por inducción en $n$ . Y sí, es un poco feo porque hay que pasar por los 16 casos una vez, pero creo que no hay forma "elegante" de evitarlo.