Completude funcional

Em lógica, um grupo de conectivos ou operadores Booleanos [1] 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. [2] [3][4][5]

Definição Formal editar

Dado o domínio Booleano B = {0,1}, um conjunto F de funções booleanas ƒiBni ? 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(xyz) = z se x = y e S(xyz) = x entretanto mostra que esta condição é estritamente mais fraca do que completude funcional .


Definição Informal editar

Textos recentes sobre lógica tomam como primitivo algum subconjunto de conectivos [6]: 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 editar

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:

  • Os conectivos monoatômicos; mudar a valoração verdade de qualquer variável ligada de F para T sem mudar de T para F nunca fará com que esses conectivos mudem seus valores de retorno de T para F.  ,  ,  ,  .
  • Os conectivos afins, de modo que cada variável conectada sempre ou nunca afeta o valor verdade de retorno desses conectivos ,  ,  ,  ,  .
  • Os conectivos de preservação da verdade; eles retornam a valoração verdade de T sob qualquer interpretação que atribui T para todas as variáveis.  ,  ,  ,  ,  .
  • Os conectivos de preservação da falsidade; eles retornam a valoração verdade de F sob qualquer interpretação que atribui F para todas as variáveis.  ,  ,  ,  ,  .


Conjunto Mínimo de Operadores Funcionalmente Completos editar

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: [7]


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 editar

  • Exemplo do uso da completude do NAND. [8]
    • ¬A = A NAND A
    • A ∧ B = ¬(A NAND B) = (A NAND B) NAND (A NAND B)
    • A ∨ B = (A NAND A) NAND (B NAND B)
  • Exemplo do uso da completude do NOR. [9]
    • ¬A = A NOR A
    • A ∧ B = (A NOR A) NOR (B NOR B)
    • A ∨ B = (A NOR B) NOR (A NOR B)


Teoria dos Conjuntos editar

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 {¬, ∪}.

Veja também editar

Referências editar

  1. Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic, ISBN 978-0-07-046649-4 2nd ed. , New York: McGraw–Hill . ("[F]unctional completeness of [a] set of logical operators").
  2. Smith, Peter (2003), An introduction to formal logic, ISBN 978-0-521-00804-4, Cambridge University Press . (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
  3. Wesselkamper, T.C. (1975), «A sole sufficient operator», Notre Dame Journal of Formal Logic, 16: 86–88, doi:10.1305/ndjfl/1093891614 
  4. Massey, G.J. (1975), «Concerning an alleged Sheffer function», Notre Dame Journal of Formal Logic, 16 (4): 549–550, doi:10.1305/ndjfl/1093891898 
  5. Wesselkamper, T.C. (1975), «A Correction To My Paper" A. Sole Sufficient Operator», Notre Dame Journal of Formal Logic, 16 (4), doi:10.1305/ndjfl/1093891899 
  6. The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, ISBN 978-0-521-36770-7, Cambridge University Press, p. 54 .
  7. Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between   and  .
  8. "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
  9. "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html