Completitud funcional booleana del conjunto de 5 operadores en la lógica proposicional

Question

Estoy tratando de demostrar que el conjunto de cinco conectivos:

$$\{ ¬, , , , \}$$

Es adecuada (funcionalmente completa) para todas las funciones booleanas posibles en la lógica proposicional (únicamente). Es decir, TODA función booleana puede generarse a partir de estos 5 operadores.

Esto incluye proposiciones con cualquier número de términos atómicos, es decir, el rango de operador nulo en términos cero y 2 expresiones de verdad $\{T,F\},$ a través de operadores unarios en un término y 4 funciones de verdad, a través de operadores binarios+unarios en dos términos y 16 funciones de verdad, hasta llegar a operadores <=n'ary en n términos generando 2^(2^n) funciones, y presumiblemente hasta infinitos términos.

Es trivial demostrar que se pueden producir más conjuntos mínimos. Por ejemplo, un conjunto de ¬ y uno de $\{ , , \}$ está completo. Al igual que el NAND binario o el NOR binario como conjuntos únicos. Se ha demostrado que todos ellos derivan del conjunto de 5 operadores originalmente, aplicando luego alguna ley de la lógica para minimizar ese conjunto un operador a la vez.

Sin embargo, he sido incapaz de demostrar la completitud funcional del caso (aparentemente no trivial) de 5 operadores para CUALQUIER función booleana con cualquier número de términos.

Le agradecemos su ayuda.

Answer 1

Dejemos que $f$ ser un $n$ a función booleana, $n\ge1$ . Entre todos los booleanos $n$ funciones expresables con los cinco operadores, sea $g$ sea uno que esté de acuerdo con $f$ para el número máximo de entradas posibles. (Tales $g$ existe porque sólo hay un número finito de entradas). Entonces $g$ está de acuerdo con $f$ en todas las entradas. Porque si suponemos lo contrario, existe una asignación de $n$ valores $a_1,\ldots, a_n\in\{T,F\}$ a los parámetros de entrada de forma que $f(a_1,\ldots,a_n)\ne g(a_1,\ldots, a_n)$ . Para cada $i$ , $1\le i\le n$ , defina $\phi_i:=\neg X_i$ si $a_i=T$ y definir $\phi_i:=X_i$ si $a_i=F$ . Entonces $$\hat g(X_1,\ldots, X_n):= g(X_1,\ldots,X_n)\leftrightarrow(\phi_1\lor\ldots\lor \phi_n)$$ se construye a partir de los 5 operadores y coincide con $f$ en más entradas que $g$ hace, contradicción