$¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ no puede expresarse utilizando sólo conectivos en $\{∧,\rightarrow\}$

Question

Demuestre que la fórmula $¬((p_1 \rightarrow p_2)\rightarrow (p_2\rightarrow p_3))$ no es lógicamente equivalente a una fórmula que incluya sólo conectivas del conjunto $\{,\rightarrow\}$ .

¿Estoy en lo cierto al pensar que es porque no podemos escribir la conectiva de negación $¬$ y el conectivo $\rightarrow$ utilizando sólo las conectivas del conjunto $\{,\rightarrow \}?$

( $\phi \rightarrow \psi$ ) es lógicamente equivalente a (( $\lnot\phi)\lor \psi$ ) pero las conectivas $¬$ y $\lor$ no existen en el conjunto $\{\land, \rightarrow \}.$

Pero no sé cómo ir más allá para mostrarlo.

Gracias

Answer 1

Ver Herbert Enderton, Introducción matemática a la lógica (2ª ed. Harcourt - 2001), página 50.

Con sólo el $\land$ y $\rightarrow$ conectivas, si a los símbolos de la frase en nuestra fórmula se les asigna el valor $\top$ entonces a toda la fórmula se le asigna el valor $\top$ .

Tenemos que demostrarlo por inducción en la longitud de la fórmula; es decir, tenemos que demostrar que para cualquier wff $\alpha$ construido usando sólo estos conectivos tenemos que :

en cada valoración $v$ tal que $v(p_i) = \top$ para cada $p_i$ en $\alpha$ entonces $v(\alpha) = \top$ .

La prueba es trivial:

Base

$\alpha$ es $p_1$ ; entonces, $v(p_1) = \top = v(\alpha)$ .

Paso de inducción

$\alpha$ es $\alpha_1 \land \alpha_2$ o $\alpha_1 \rightarrow \alpha_2$ donde asumimos por hipótesis de inducción que..:

si $v(p_i)=\top$ para cada $p_i$ en $\alpha_1$ y $\alpha_2$ entonces $v(\alpha_1)=v(\alpha_2)=\top$ .

Basta con utilizar tablas de verdad.

Habiendo mostrado esto, hemos demostrado que con sólo los dos conectivos $\land$ y $\rightarrow$ no somos capaces de "producir" una fórmula que, cuando todas sus letras de la frase se evalúan a $\top$ (es decir TRUE ), da como resultado el valor $\bot$ (es decir FALSO ).

Pero con la valoración $v_0$ tal que :

$v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$

la fórmula $\alpha := \lnot [(p_1 \rightarrow p_2) \rightarrow (p_2 \rightarrow p_3)]$

tendrá el valor $\bot$ .

Otra forma de demostrarlo es basándose en :

la equivalencia entre : $p \rightarrow q$ y $\lnot (p \land \lnot q)$ ,

en clásico lógica : porque necesitamos Doble negación .

Utilizando esta equivalencia, podemos reescribir nuestra fórmula como :

$(p_1 \rightarrow p_2) \land \lnot (p_2 \rightarrow p_3)$

y de nuevo como :

$\lnot (p_1 \land \lnot p_2) \land (p_2 \land \lnot p_3)$ .

Ahora podemos aplicar el argumento anterior en términos de valoraciones con $v_0(p_1)=v_0(p_2)=v_0(p_3)= \top$ tenemos que :

$[\lnot (\top \land \lnot \top) \land (\top \land \lnot \top)] \equiv [\lnot (\top \land \bot) \land (\top \land \bot)] \equiv (\lnot \bot \land \bot) \equiv (\top \land \bot) \equiv \bot$ .

Pero tenemos el resultado anterior de que con sólo el $\land$ y $\rightarrow$ conectivas, si a los símbolos de la frase en una fórmula se les asigna el valor $\top$ entonces a toda la fórmula se le asigna el valor $\top$ .

Por lo tanto, no es posible encontrar una fórmula con sólo $\land$ y $\rightarrow$ que es equivalente al original.

Answer 2

$$\begin{align} \lnot((p_1 \rightarrow p_2) \rightarrow(p_2 \rightarrow p_3)) & \equiv \lnot(\lnot(p_1\rightarrow p_2) \lor (p_2\rightarrow p_3))\tag{1}\\ \\ & \equiv (p_1\rightarrow p_2) \land \lnot(p_2\rightarrow p_3)\tag{2}\\ \\ &\equiv (p_1 \rightarrow p_2) \land \lnot(\lnot p_2 \lor p_3) \tag{3}\\ \\ & \equiv (p_1 \rightarrow p_2) \land p_2 \land \lnot p_3\tag{4}\end{align}$$

En $(4)$ tenemos las conectivas $\land, \rightarrow$ pero también tenemos la negación $\lnot$ del literal $p_3$ . (Del mismo modo, en $(2)$ tenemos el único $\rightarrow$ y $\land$ , pero aún así también es necesario $\lnot$ .) No podemos simplemente omitir el signo de negación en ninguna de las dos sin perder el significado de la proposición.

Véase la entrada de Wikipedia sobre Completitud funcional para un tratamiento más formal sobre cómo determinar si un conjunto de conectivas es completo, o adecuado, para expresar todas las posibles valoraciones de verdad para, en este caso, una expresión con tres variables.

Answer 3

Toda función creada con las conectivas $\rightarrow$ y $\land$ tiene la propiedad de que $f(\text{true}, \text{true}, \dots) = \text{true}$

Demostrar con inducción estructural.

La función proporcionada no tiene esa propiedad.