Completude funcional

Em lógica, um grupo de conectivos ou operadores Booleanos tem a propriedade da completude funcional se todos outros conectivos possíveis podem ser definidos em função dele.

Do ponto de vista da eletrônica digital, completude funcional significa que cada porta lógica possível pode ser tratada como uma rede de portas dos tipos prescritos pelo conjunto. Em particular, todas as portas lógicas podem ser montadas a partir de apenas NANDs e NOR.

Definição Formal

Dado o domínio Booleano B = {0,1}, um conjunto F de funções booleanas ƒi: Bni ? B é funcionalmente completa- se o clone algébrico em B gerado pelas funções básicas ƒi contém todas funções ƒ: Bn ? B, para todos inteiros positivos {{{1}}}. Em outras palavras , o conjunto é funcionalmente completo se cada função booleana que leva pelo menos uma variável pode ser expressa em termos das funções ƒ i . Uma vez que cada função booleana de pelo menos uma variável pode ser expressa em termos de funções booleanas binárias , F é funcionalmente completo se somente se cada função booleana binária pode ser expressa em termos das funções de F.

Uma condição mais natural seria que o clone gerado por F consistem de todas as funções ƒ: Bn ? B, para todos os inteiros {{{1}}}. Porém, os exemplos dados acima não são funcionalmente completos na forma mais forte porque não é possível escrever uma função nulária, ou seja, uma expressão constante, em termos de F se o próprio F não contêm pelo menos uma função nulária.

Outra condição natural seria se o clone algébrico gerado por F juntamente com as duas funções constantes nulárias ser funcionalmente completo ou. O exemplo da função booleana dada por S(x, y, z) = z se x = y e S(x, y, z) = x entretanto mostra que esta condição é estritamente mais fraca do que completude funcional .


Definição Informal

Textos recentes sobre lógica tomam como primitivo algum subconjunto de conectivos : conjução (); disjunção () ; negação (); implicação (); e bi implicação (). Esses conectivos são funcionalmente completos. No entanto , eles não formam um conjunto mínimo funcionalmente completo, já que a implicação e bi implicação podem ser definidas como :

Então também é funcionamente completo. Mas então, pode ser definido como:

também pode ser definido em termos de de uma maneira semelhante.


Caracterização da Completude Funcional

Emil Post provou que um conjunto de conectivos lógicos é funcionalmente completo se somente se for um subconjunto de qualquer um dos seguintes conjuntos de conectivos:


Conjunto Mínimo de Operadores Funcionalmente Completos

Quando um único conectivo lógico ou operador booleano é funcionalmente completo por si só, ela é chamada de função de Sheffer. Não há operadores unários com esta propriedade, e as únicas funções de Sheffer binárias - NAND e NOR são duais. Estas foram descobertas, mas não publicadas por Charles Sanders Peirce por volta de 1880, e redescobertas independentemente e publicadas por Henry M. Sheffer em 1913.

A seguir estão os conjuntos mínimos funcionalmente completos de conectivos lógicos com aridade 2:


Um Elemento
{NAND}, {NOR}.
Dois Elementos
{, ¬}, {, ¬}, {?, ¬}, {?, ¬}, {?, }, {?, }, {?, }, {?, }, {?, }, {?, }, {?, }, {?, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.
Três Elementos
{, , }, {, , }, {, , }, {, , }, {, , }, {, , }.

Não há conjuntos mínimos funcionalmente completos de mais de três conectivos lógicos binários.

Exemplos


Teoria dos Conjuntos

Há um isomorfismo entre a álgebra de conjuntos e a álgebra booleana, ou seja, eles tem a mesma estrutura. Os mais populares "Conjuntos Mínimo de Operadores Funcionalmente Completos" são {¬, ∩} and {¬, ∪}.

Ver também