Integridad funcional de la lógica de 3 valores

En el contexto de algunos trabajos recientes , hemos estado definiendo un lenguaje basado en una lógica de tres valores à la Kleene, donde significa verdadero, para falso y para error o no sabe. Para demostrar que nuestro lenguaje era expresivo, queríamos demostrar que podíamos construir un conjunto de operadores funcionalmente completos. $1$ $0$ $\bot$

Fue bastante difícil encontrar resultados existentes en la literatura. Encontramos un artículo escrito en 1962 por Jobe, que establece el siguiente teorema:

Jobe 1962 Theorem Paper (acceso restringido).

La lógica tres valores expresada sobre el conjunto y definida por los operadores y , dada a continuación, es funcionalmente completa. $E$ $\{1, 2, 3\}$ $\bullet, E_1$ $E_2$

$\begin{array}{cccccc} ∙ & 3 & 2 & 1 & E_{1} & E_{2} \\ 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$ $\begin{array}{c|ccc|c|c} ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$

En nuestro artículo, hemos utilizado este resultado al mostrar una correspondencia entre nuestros operadores y los definidos por Jobe (en términos generales, usamos la conjunción fuerte, la negación y un operador que transforma el no-saber en falso).

Mi principal preocupación es que en realidad no puedo entender la prueba de integridad funcional de Jobe, y no hemos podido encontrar ningún otro resultado (positivo o negativo) después de esta fecha, lo que de alguna manera es un poco sorprendente.

Entonces mi pregunta es la siguiente: ¿hay algunos resultados más conocidos sobre la integridad funcional de las lógicas de 3 valores? Cualquier información en esta dirección sería útil.

reference-request lo.logic Charles
fuente

El campo de elementos está funcionalmente completo. El álgebra posterior de elementos está funcionalmente completo.

3

$3$

3

$3$

Emil Jeřábek

@ EmilJeřábek Gracias, acabo de leer sobre Ternary Post Logic, y eso parece corresponder (aunque tampoco puedo encontrar mucho sobre este tema). ¿Tendrías alguna referencia sobre el campo de 3 elementos? Google es un poco vago.

Charles

No puedo darle una referencia de antemano, pero es un hecho fácil: la interpolación estándar (multivariada) implica que cualquier operación en un campo finito puede expresarse mediante un polinomio. Además, si el campo es primo (como aquí), entonces los coeficientes del polinomio son definibles por términos constantes ( ). Por lo tanto, los campos principales en el lenguaje están funcionalmente completos.

1 + 1 + \dots + 1

$1+1+\cdots+1$

{+, \cdot, 1}

$\{+,\cdot,1\}$

Emil Jeřábek

Los capítulos 5 y 6 del libro [Álgebras de funciones en conjuntos finitos, Dietlinde Lau, 2006] contienen un tratamiento en profundidad de la integridad funcional en la lógica de muchos valores (incluidas las pruebas). En resumen: la caracterización de Rosenbergs [1965, 1970] de los clones máximos (también llamados clones precompletos) proporciona un criterio para la completitud funcional en la lógica con valores k para cualquier k.

Para el caso especial de la lógica de 3 valores, Jablonskij ya dio esa caracterización (que consta de 18 clases máximas / precompletas) en 1954. Por lo tanto, para verificar que su conjunto de "operadores" de 3 valores esté funcionalmente completo, es suficiente para comprobar que no caen en ninguna de las 18 clases precompletas.

Gustav Nordh
fuente

Integridad funcional de la lógica de 3 valores

Respuestas: