Funcional completo y xor

Question

Dé un prueba formal de la afirmación de que el conjunto $\{xor\}$ no es funcionalmente completo.

Una posible forma es mostrar que no podemos crear la función $\lnot$. Intenté probarlo usando la inducción en la estructura de $A$. Si $A$ es una fórmula y $V$ es un modelo que asigna $f$ a todas las fórmulas atómicas, entonces $V(A) = f$. El caso base es $A = p$ y por lo tanto $V(A) = f$. Suponemos que se cumple para las fórmulas $B$ y $C$. Tenemos $A = xor(B,C)$ y usando la hipótesis de inducción y la definición de $xor$ obtenemos $V(A) = f.

Pero quiero mostrar que no podemos crear la función $\land$. Intenté usar el mismo método que antes pero parece que no funciona. ¿Cuál debería ser la hipótesis de inducción en este caso?

Answer 1

Tienes que considerar una inducción en el número de ocurrencias del conectivo en la fórmula.

Consideremos $\land$

Caso base : en $p \land q$, cuando $p$ y $q$ tienen valores de verdad diferentes, entonces $p \land q$ es falso.

Paso de inducción : sea $F_n^{\land}(p,q)$ una fórmula construida solo con los literales $p$ y $q$ con $n$ ocurrencias de $\land$, y asumamos como hipótesis de inducción que es idénticamente falsa.

Si ahora consideramos $F_{n+1}^{\land}(p,q)$ (es decir $F_n^{\land}(p,q) \land p$ o $F_n^{\land}(p,q) \land q$), nuevamente es idénticamente falsa.

Consideremos $xor$ (es decir, $\nLeftrightarrow$)

Caso base : en $p \nLeftrightarrow q$, cuando $p$ y $q$ tienen valores de verdad diferentes, entonces $p \nLeftrightarrow q$ es verdadero.

Paso de inducción : sea $F_n^{\nLeftrightarrow}(p,q)$ una fórmula construida solo con los literales $p$ y $q$ con $n$ ocurrencias de $\nLeftrightarrow $, y asumamos como hipótesis de inducción que no es idénticamente falsa.

Si ahora consideramos $F_{n+1}^{\nLeftrightarrow}(p,q)$ (es decir $F_n^{\nLeftrightarrow}(p,q) \nLeftrightarrow p$ o $F_n^{\land}(p,q) \nLeftrightarrow q$), puede ser verdadero o falso, y agregando un nuevo literal $p$ (o $q$), el resultado $F_{n+1}^{\nLeftrightarrow}$ "cambiará" según el valor de $p$ (o $q$).

Así, tenemos que no es idénticamente falsa.