Demostrar que $\{Tri, \lnot \}$ no es funcionalmente completo

Question

Que la función $Tri(p,q,r)$ que devuelve $t$ si y sólo si al menos 2 de las 3 variables de entrada son $t$ . Demostrar que $\{Tri, \lnot\}$ no es funcionalmente completa.

Estaría encantado de recibir ayuda, porque francamente, no tengo una pista aquí.

Básicamente, la idea general es inventar alguna función con alguna propiedad y afirmar que esta función no puede ser construida por este conjunto.

Gracias

Answer 1

Tuve problemas para implementar el enfoque sugerido por @Wojowu, así que aquí hay uno diferente.

Veamos $F$ el conjunto de funciones de dos variables que se pueden crear a partir de $T=\{Tri,\neg\}$ . Demostraremos que (por ejemplo) $OR \notin F$ . Por lo tanto, $T$ no es funcionalmente completa.

Denote $\phi(x,y) \in F$ . Consideraremos algunos casos diferentes por la complejidad de $\phi$ (de manera informal - cuántas veces cualquier operador de $T$ utilizado en $\phi$ ).

1. Para la complejidad cero, $\phi(x,y)=x,y$ (donde la coma significa aquí sólo uno de ellos). Por lo tanto, las funciones constantes están en $F$ .

2. A continuación, añadimos un operador de $T$ (complejidad uno):

   • Añadir $\neg$ tenemos que $\phi(x,y)=(\neg x), (\neg y)$ . Por lo tanto, las funciones constantes negativas están en $F$ .

   • Añadir $Tri$ una de las siguientes es verdadera:

     • $\phi(x,y)=Tri(x,x,x)=x$
     • $\phi(x,y)=Tri(x,x,y)=x$
     • $\phi(x,y)=Tri(x,y,y)=y$
     • Por simetría en los argumentos de $\phi$ y $Tri$ , obtenemos todos los demás casos.

     Así que no se añade ninguna función nueva a $F$ Además de los que ya conocemos.

3. Para el último paso, vamos a añadir otro operador de $T$ :

   • Añadir $\neg$ tenemos que $\phi(x,y)=x,y,(\neg x),(\neg y)$ .
   • Añadir $Tri$ una de las siguientes es verdadera:
     • $\phi(x,y)=Tri(x,\neg x,\neg y)=\neg y$
     • $\phi(x,y)=Tri(x,\neg x, y)=y$
     • Se da uno de los casos que vimos en (2).
     • De nuevo, por simetría obtenemos todos los demás casos.

   En todos los casos, no se añade ninguna función nueva a $F$ .

Concluimos que $F=\{x,y,(\neg x),(\neg y)\}$ . En particular, $OR \notin F$ . Por lo tanto, $T$ no es funcionalmente completa.