Completude funcional da lógica de 3 valores

9

No contexto de alguns trabalhos recentes , definimos uma linguagem baseada em uma lógica de três valores à la Kleene, onde 1 1 significa verdadeiro, para falso e para erro ou não sei. Para mostrar que nossa linguagem era expressiva, queríamos provar que poderíamos criar um conjunto de operadores funcionalmente completos.0 0

Foi bastante difícil encontrar resultados existentes na literatura. Encontramos um artigo escrito em 1962 por Jobe, que afirma o seguinte teorema:

Jobe 1962 Theorem Paper (acesso restrito).

A lógica de três valores expressa sobre o conjunto e definida pelos operadores e , fornecidos abaixo, está funcionalmente completa.E{1 1,2,3},E1 1E2

   3  2  1 1  E1 1  E2 3321 131 12221 11 121 11 11 11 123

Em nosso artigo, usamos esse resultado mostrando uma correspondência entre nossos operadores e os definidos por Jobe (grosso modo, usamos a conjunção forte, a negação e um operador que transforma o não-sei em falso).

Minha principal preocupação é que, na verdade, não sou capaz de entender a prova da integridade funcional do Jobe e não conseguimos encontrar nenhum outro resultado (positivo ou negativo) após essa data, o que é de alguma forma um pouco surpreendente.

Portanto, minha pergunta é a seguinte: existem resultados mais conhecidos sobre a integridade funcional de lógicas com 3 valores? Qualquer informação nessa direção seria útil.

Charles
fonte
O campo de elementos está funcionalmente completo. A álgebra de 3 elementos está funcionalmente completa. 33
Emil Jerabek
@ EmilJeřábek Obrigado, acabei de ler sobre a Ternary Post Logic, e isso parece corresponder (embora também não consiga encontrar muita coisa sobre esse assunto). Você teria alguma referência sobre o campo de 3 elementos? O Google é um pouco vago.
Charles
11
Não posso fornecer uma referência imediata, mas é um fato fácil: a interpolação padrão (multivariada) implica que qualquer operação em um campo finito pode ser expressa por um polinômio. Além disso, se o campo for primo (como aqui), os coeficientes do polinômio são definíveis por termos constantes ( ). Assim, os campos primos no idioma { + , , 1 } são funcionalmente completos. 1 1+1 1++1 1{+,,1 1}
Emil Jerabek

Respostas:

2

Os capítulos 5 e 6 do livro [Álgebras de funções em conjuntos finitos, Dietlinde Lau, 2006] contêm um tratamento aprofundado da completude funcional na lógica de muitos valores (incluindo provas). Em resumo: a caracterização de Rosenbergs [1965, 1970] de clones máximos (também chamados de clones pré-completos) fornece um critério para completude funcional na lógica com valor k para qualquer k.

Para o caso especial da lógica com 3 valores, essa caracterização (que consiste em 18 classes máximas / pré-completas) foi dada por Jablonskij já em 1954. Portanto, para verificar se seu conjunto de "operadores" com 3 valores está funcionalmente completo, é suficiente para verificar se eles não se enquadram em nenhuma das 18 classes pré-completas.

Gustav Nordh
fonte